| OLD | NEW |
|---|
| (Empty) |
| 1 /* This Source Code Form is subject to the terms of the Mozilla Public | |
| 2 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 3 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 4 | |
| 5 /* | |
| 6 * hash.c | |
| 7 * | |
| 8 * This is merely a couple wrappers around NSPR's PLHashTable, using | |
| 9 * the identity hash and arena-aware allocators. | |
| 10 * This is a copy of ckfw/hash.c, with modifications to use NSS types | |
| 11 * (not Cryptoki types). Would like for this to be a single implementation, | |
| 12 * but doesn't seem like it will work. | |
| 13 */ | |
| 14 | |
| 15 #ifndef BASE_H | |
| 16 #include "base.h" | |
| 17 #endif /* BASE_H */ | |
| 18 | |
| 19 #include "prbit.h" | |
| 20 | |
| 21 /* | |
| 22 * nssHash | |
| 23 * | |
| 24 * nssHash_Create | |
| 25 * nssHash_Destroy | |
| 26 * nssHash_Add | |
| 27 * nssHash_Remove | |
| 28 * nssHash_Count | |
| 29 * nssHash_Exists | |
| 30 * nssHash_Lookup | |
| 31 * nssHash_Iterate | |
| 32 */ | |
| 33 | |
| 34 struct nssHashStr { | |
| 35 NSSArena *arena; | |
| 36 PRBool i_alloced_arena; | |
| 37 PRLock *mutex; | |
| 38 | |
| 39 /* | |
| 40 * The invariant that mutex protects is: | |
| 41 * The count accurately reflects the hashtable state. | |
| 42 */ | |
| 43 | |
| 44 PLHashTable *plHashTable; | |
| 45 PRUint32 count; | |
| 46 }; | |
| 47 | |
| 48 static PLHashNumber | |
| 49 nss_identity_hash(const void *key) | |
| 50 { | |
| 51 return (PLHashNumber)((char *)key - (char *)NULL); | |
| 52 } | |
| 53 | |
| 54 static PLHashNumber | |
| 55 nss_item_hash(const void *key) | |
| 56 { | |
| 57 unsigned int i; | |
| 58 PLHashNumber h; | |
| 59 NSSItem *it = (NSSItem *)key; | |
| 60 h = 0; | |
| 61 for (i = 0; i < it->size; i++) | |
| 62 h = PR_ROTATE_LEFT32(h, 4) ^ ((unsigned char *)it->data)[i]; | |
| 63 return h; | |
| 64 } | |
| 65 | |
| 66 static int | |
| 67 nss_compare_items(const void *v1, const void *v2) | |
| 68 { | |
| 69 PRStatus ignore; | |
| 70 return (int)nssItem_Equal((NSSItem *)v1, (NSSItem *)v2, &ignore); | |
| 71 } | |
| 72 | |
| 73 /* | |
| 74 * nssHash_create | |
| 75 * | |
| 76 */ | |
| 77 NSS_IMPLEMENT nssHash * | |
| 78 nssHash_Create(NSSArena *arenaOpt, PRUint32 numBuckets, PLHashFunction keyHash, | |
| 79 PLHashComparator keyCompare, PLHashComparator valueCompare) | |
| 80 { | |
| 81 nssHash *rv; | |
| 82 NSSArena *arena; | |
| 83 PRBool i_alloced; | |
| 84 | |
| 85 #ifdef NSSDEBUG | |
| 86 if (arenaOpt && PR_SUCCESS != nssArena_verifyPointer(arenaOpt)) { | |
| 87 nss_SetError(NSS_ERROR_INVALID_POINTER); | |
| 88 return (nssHash *)NULL; | |
| 89 } | |
| 90 #endif /* NSSDEBUG */ | |
| 91 | |
| 92 if (arenaOpt) { | |
| 93 arena = arenaOpt; | |
| 94 i_alloced = PR_FALSE; | |
| 95 } else { | |
| 96 arena = nssArena_Create(); | |
| 97 i_alloced = PR_TRUE; | |
| 98 } | |
| 99 | |
| 100 rv = nss_ZNEW(arena, nssHash); | |
| 101 if ((nssHash *)NULL == rv) { | |
| 102 goto loser; | |
| 103 } | |
| 104 | |
| 105 rv->mutex = PZ_NewLock(nssILockOther); | |
| 106 if ((PZLock *)NULL == rv->mutex) { | |
| 107 goto loser; | |
| 108 } | |
| 109 | |
| 110 rv->plHashTable = | |
| 111 PL_NewHashTable(numBuckets, keyHash, keyCompare, valueCompare, | |
| 112 &nssArenaHashAllocOps, arena); | |
| 113 if ((PLHashTable *)NULL == rv->plHashTable) { | |
| 114 (void)PZ_DestroyLock(rv->mutex); | |
| 115 goto loser; | |
| 116 } | |
| 117 | |
| 118 rv->count = 0; | |
| 119 rv->arena = arena; | |
| 120 rv->i_alloced_arena = i_alloced; | |
| 121 | |
| 122 return rv; | |
| 123 loser: | |
| 124 (void)nss_ZFreeIf(rv); | |
| 125 return (nssHash *)NULL; | |
| 126 } | |
| 127 | |
| 128 /* | |
| 129 * nssHash_CreatePointer | |
| 130 * | |
| 131 */ | |
| 132 NSS_IMPLEMENT nssHash * | |
| 133 nssHash_CreatePointer(NSSArena *arenaOpt, PRUint32 numBuckets) | |
| 134 { | |
| 135 return nssHash_Create(arenaOpt, numBuckets, nss_identity_hash, | |
| 136 PL_CompareValues, PL_CompareValues); | |
| 137 } | |
| 138 | |
| 139 /* | |
| 140 * nssHash_CreateString | |
| 141 * | |
| 142 */ | |
| 143 NSS_IMPLEMENT nssHash * | |
| 144 nssHash_CreateString(NSSArena *arenaOpt, PRUint32 numBuckets) | |
| 145 { | |
| 146 return nssHash_Create(arenaOpt, numBuckets, PL_HashString, | |
| 147 PL_CompareStrings, PL_CompareStrings); | |
| 148 } | |
| 149 | |
| 150 /* | |
| 151 * nssHash_CreateItem | |
| 152 * | |
| 153 */ | |
| 154 NSS_IMPLEMENT nssHash * | |
| 155 nssHash_CreateItem(NSSArena *arenaOpt, PRUint32 numBuckets) | |
| 156 { | |
| 157 return nssHash_Create(arenaOpt, numBuckets, nss_item_hash, | |
| 158 nss_compare_items, PL_CompareValues); | |
| 159 } | |
| 160 | |
| 161 /* | |
| 162 * nssHash_Destroy | |
| 163 * | |
| 164 */ | |
| 165 NSS_IMPLEMENT void | |
| 166 nssHash_Destroy(nssHash *hash) | |
| 167 { | |
| 168 (void)PZ_DestroyLock(hash->mutex); | |
| 169 PL_HashTableDestroy(hash->plHashTable); | |
| 170 if (hash->i_alloced_arena) { | |
| 171 nssArena_Destroy(hash->arena); | |
| 172 } else { | |
| 173 nss_ZFreeIf(hash); | |
| 174 } | |
| 175 } | |
| 176 | |
| 177 /* | |
| 178 * nssHash_Add | |
| 179 * | |
| 180 */ | |
| 181 NSS_IMPLEMENT PRStatus | |
| 182 nssHash_Add(nssHash *hash, const void *key, const void *value) | |
| 183 { | |
| 184 PRStatus error = PR_FAILURE; | |
| 185 PLHashEntry *he; | |
| 186 | |
| 187 PZ_Lock(hash->mutex); | |
| 188 | |
| 189 he = PL_HashTableAdd(hash->plHashTable, key, (void *)value); | |
| 190 if ((PLHashEntry *)NULL == he) { | |
| 191 nss_SetError(NSS_ERROR_NO_MEMORY); | |
| 192 } else if (he->value != value) { | |
| 193 nss_SetError(NSS_ERROR_HASH_COLLISION); | |
| 194 } else { | |
| 195 hash->count++; | |
| 196 error = PR_SUCCESS; | |
| 197 } | |
| 198 | |
| 199 (void)PZ_Unlock(hash->mutex); | |
| 200 | |
| 201 return error; | |
| 202 } | |
| 203 | |
| 204 /* | |
| 205 * nssHash_Remove | |
| 206 * | |
| 207 */ | |
| 208 NSS_IMPLEMENT void | |
| 209 nssHash_Remove(nssHash *hash, const void *it) | |
| 210 { | |
| 211 PRBool found; | |
| 212 | |
| 213 PZ_Lock(hash->mutex); | |
| 214 | |
| 215 found = PL_HashTableRemove(hash->plHashTable, it); | |
| 216 if (found) { | |
| 217 hash->count--; | |
| 218 } | |
| 219 | |
| 220 (void)PZ_Unlock(hash->mutex); | |
| 221 return; | |
| 222 } | |
| 223 | |
| 224 /* | |
| 225 * nssHash_Count | |
| 226 * | |
| 227 */ | |
| 228 NSS_IMPLEMENT PRUint32 | |
| 229 nssHash_Count(nssHash *hash) | |
| 230 { | |
| 231 PRUint32 count; | |
| 232 | |
| 233 PZ_Lock(hash->mutex); | |
| 234 | |
| 235 count = hash->count; | |
| 236 | |
| 237 (void)PZ_Unlock(hash->mutex); | |
| 238 | |
| 239 return count; | |
| 240 } | |
| 241 | |
| 242 /* | |
| 243 * nssHash_Exists | |
| 244 * | |
| 245 */ | |
| 246 NSS_IMPLEMENT PRBool | |
| 247 nssHash_Exists(nssHash *hash, const void *it) | |
| 248 { | |
| 249 void *value; | |
| 250 | |
| 251 PZ_Lock(hash->mutex); | |
| 252 | |
| 253 value = PL_HashTableLookup(hash->plHashTable, it); | |
| 254 | |
| 255 (void)PZ_Unlock(hash->mutex); | |
| 256 | |
| 257 if ((void *)NULL == value) { | |
| 258 return PR_FALSE; | |
| 259 } else { | |
| 260 return PR_TRUE; | |
| 261 } | |
| 262 } | |
| 263 | |
| 264 /* | |
| 265 * nssHash_Lookup | |
| 266 * | |
| 267 */ | |
| 268 NSS_IMPLEMENT void * | |
| 269 nssHash_Lookup(nssHash *hash, const void *it) | |
| 270 { | |
| 271 void *rv; | |
| 272 | |
| 273 PZ_Lock(hash->mutex); | |
| 274 | |
| 275 rv = PL_HashTableLookup(hash->plHashTable, it); | |
| 276 | |
| 277 (void)PZ_Unlock(hash->mutex); | |
| 278 | |
| 279 return rv; | |
| 280 } | |
| 281 | |
| 282 struct arg_str { | |
| 283 nssHashIterator fcn; | |
| 284 void *closure; | |
| 285 }; | |
| 286 | |
| 287 static PRIntn | |
| 288 nss_hash_enumerator(PLHashEntry *he, PRIntn index, void *arg) | |
| 289 { | |
| 290 struct arg_str *as = (struct arg_str *)arg; | |
| 291 as->fcn(he->key, he->value, as->closure); | |
| 292 return HT_ENUMERATE_NEXT; | |
| 293 } | |
| 294 | |
| 295 /* | |
| 296 * nssHash_Iterate | |
| 297 * | |
| 298 * NOTE that the iteration function will be called with the hashtable locked. | |
| 299 */ | |
| 300 NSS_IMPLEMENT void | |
| 301 nssHash_Iterate(nssHash *hash, nssHashIterator fcn, void *closure) | |
| 302 { | |
| 303 struct arg_str as; | |
| 304 as.fcn = fcn; | |
| 305 as.closure = closure; | |
| 306 | |
| 307 PZ_Lock(hash->mutex); | |
| 308 | |
| 309 PL_HashTableEnumerateEntries(hash->plHashTable, nss_hash_enumerator, &as); | |
| 310 | |
| 311 (void)PZ_Unlock(hash->mutex); | |
| 312 | |
| 313 return; | |
| 314 } | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2078763002:
Delete bundled copy of NSS and replace with README. (Closed)
Base URL: https://chromium.googlesource.com/chromium/deps/nss@master