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