| OLD | NEW |
|---|
| (Empty) |
| 1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */ | |
| 2 /* This Source Code Form is subject to the terms of the Mozilla Public | |
| 3 * License, v. 2.0. If a copy of the MPL was not distributed with this | |
| 4 * file, You can obtain one at http://mozilla.org/MPL/2.0/. */ | |
| 5 | |
| 6 /* | |
| 7 * PL hash table package. | |
| 8 */ | |
| 9 #include "plhash.h" | |
| 10 #include "prbit.h" | |
| 11 #include "prlog.h" | |
| 12 #include "prmem.h" | |
| 13 #include "prtypes.h" | |
| 14 #include <stdlib.h> | |
| 15 #include <string.h> | |
| 16 | |
| 17 /* Compute the number of buckets in ht */ | |
| 18 #define NBUCKETS(ht) (1 << (PL_HASH_BITS - (ht)->shift)) | |
| 19 | |
| 20 /* The smallest table has 16 buckets */ | |
| 21 #define MINBUCKETSLOG2 4 | |
| 22 #define MINBUCKETS (1 << MINBUCKETSLOG2) | |
| 23 | |
| 24 /* Compute the maximum entries given n buckets that we will tolerate, ~90% */ | |
| 25 #define OVERLOADED(n) ((n) - ((n) >> 3)) | |
| 26 | |
| 27 /* Compute the number of entries below which we shrink the table by half */ | |
| 28 #define UNDERLOADED(n) (((n) > MINBUCKETS) ? ((n) >> 2) : 0) | |
| 29 | |
| 30 /* | |
| 31 ** Stubs for default hash allocator ops. | |
| 32 */ | |
| 33 static void * PR_CALLBACK | |
| 34 DefaultAllocTable(void *pool, PRSize size) | |
| 35 { | |
| 36 return PR_MALLOC(size); | |
| 37 } | |
| 38 | |
| 39 static void PR_CALLBACK | |
| 40 DefaultFreeTable(void *pool, void *item) | |
| 41 { | |
| 42 PR_Free(item); | |
| 43 } | |
| 44 | |
| 45 static PLHashEntry * PR_CALLBACK | |
| 46 DefaultAllocEntry(void *pool, const void *key) | |
| 47 { | |
| 48 return PR_NEW(PLHashEntry); | |
| 49 } | |
| 50 | |
| 51 static void PR_CALLBACK | |
| 52 DefaultFreeEntry(void *pool, PLHashEntry *he, PRUintn flag) | |
| 53 { | |
| 54 if (flag == HT_FREE_ENTRY) | |
| 55 PR_Free(he); | |
| 56 } | |
| 57 | |
| 58 static PLHashAllocOps defaultHashAllocOps = { | |
| 59 DefaultAllocTable, DefaultFreeTable, | |
| 60 DefaultAllocEntry, DefaultFreeEntry | |
| 61 }; | |
| 62 | |
| 63 PR_IMPLEMENT(PLHashTable *) | |
| 64 PL_NewHashTable(PRUint32 n, PLHashFunction keyHash, | |
| 65 PLHashComparator keyCompare, PLHashComparator valueCompare, | |
| 66 const PLHashAllocOps *allocOps, void *allocPriv) | |
| 67 { | |
| 68 PLHashTable *ht; | |
| 69 PRSize nb; | |
| 70 | |
| 71 if (n <= MINBUCKETS) { | |
| 72 n = MINBUCKETSLOG2; | |
| 73 } else { | |
| 74 n = PR_CeilingLog2(n); | |
| 75 if ((PRInt32)n < 0) | |
| 76 return 0; | |
| 77 } | |
| 78 | |
| 79 if (!allocOps) allocOps = &defaultHashAllocOps; | |
| 80 | |
| 81 ht = (PLHashTable*)((*allocOps->allocTable)(allocPriv, sizeof *ht)); | |
| 82 if (!ht) | |
| 83 return 0; | |
| 84 memset(ht, 0, sizeof *ht); | |
| 85 ht->shift = PL_HASH_BITS - n; | |
| 86 n = 1 << n; | |
| 87 nb = n * sizeof(PLHashEntry *); | |
| 88 ht->buckets = (PLHashEntry**)((*allocOps->allocTable)(allocPriv, nb)); | |
| 89 if (!ht->buckets) { | |
| 90 (*allocOps->freeTable)(allocPriv, ht); | |
| 91 return 0; | |
| 92 } | |
| 93 memset(ht->buckets, 0, nb); | |
| 94 | |
| 95 ht->keyHash = keyHash; | |
| 96 ht->keyCompare = keyCompare; | |
| 97 ht->valueCompare = valueCompare; | |
| 98 ht->allocOps = allocOps; | |
| 99 ht->allocPriv = allocPriv; | |
| 100 return ht; | |
| 101 } | |
| 102 | |
| 103 PR_IMPLEMENT(void) | |
| 104 PL_HashTableDestroy(PLHashTable *ht) | |
| 105 { | |
| 106 PRUint32 i, n; | |
| 107 PLHashEntry *he, *next; | |
| 108 const PLHashAllocOps *allocOps = ht->allocOps; | |
| 109 void *allocPriv = ht->allocPriv; | |
| 110 | |
| 111 n = NBUCKETS(ht); | |
| 112 for (i = 0; i < n; i++) { | |
| 113 for (he = ht->buckets[i]; he; he = next) { | |
| 114 next = he->next; | |
| 115 (*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY); | |
| 116 } | |
| 117 } | |
| 118 #ifdef DEBUG | |
| 119 memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]); | |
| 120 #endif | |
| 121 (*allocOps->freeTable)(allocPriv, ht->buckets); | |
| 122 #ifdef DEBUG | |
| 123 memset(ht, 0xDB, sizeof *ht); | |
| 124 #endif | |
| 125 (*allocOps->freeTable)(allocPriv, ht); | |
| 126 } | |
| 127 | |
| 128 /* | |
| 129 ** Multiplicative hash, from Knuth 6.4. | |
| 130 */ | |
| 131 #define GOLDEN_RATIO 0x9E3779B9U /* 2/(1+sqrt(5))*(2^32) */ | |
| 132 | |
| 133 PR_IMPLEMENT(PLHashEntry **) | |
| 134 PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key) | |
| 135 { | |
| 136 PLHashEntry *he, **hep, **hep0; | |
| 137 PLHashNumber h; | |
| 138 | |
| 139 #ifdef HASHMETER | |
| 140 ht->nlookups++; | |
| 141 #endif | |
| 142 h = keyHash * GOLDEN_RATIO; | |
| 143 h >>= ht->shift; | |
| 144 hep = hep0 = &ht->buckets[h]; | |
| 145 while ((he = *hep) != 0) { | |
| 146 if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) { | |
| 147 /* Move to front of chain if not already there */ | |
| 148 if (hep != hep0) { | |
| 149 *hep = he->next; | |
| 150 he->next = *hep0; | |
| 151 *hep0 = he; | |
| 152 } | |
| 153 return hep0; | |
| 154 } | |
| 155 hep = &he->next; | |
| 156 #ifdef HASHMETER | |
| 157 ht->nsteps++; | |
| 158 #endif | |
| 159 } | |
| 160 return hep; | |
| 161 } | |
| 162 | |
| 163 /* | |
| 164 ** Same as PL_HashTableRawLookup but doesn't reorder the hash entries. | |
| 165 */ | |
| 166 PR_IMPLEMENT(PLHashEntry **) | |
| 167 PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash, | |
| 168 const void *key) | |
| 169 { | |
| 170 PLHashEntry *he, **hep; | |
| 171 PLHashNumber h; | |
| 172 | |
| 173 #ifdef HASHMETER | |
| 174 ht->nlookups++; | |
| 175 #endif | |
| 176 h = keyHash * GOLDEN_RATIO; | |
| 177 h >>= ht->shift; | |
| 178 hep = &ht->buckets[h]; | |
| 179 while ((he = *hep) != 0) { | |
| 180 if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) { | |
| 181 break; | |
| 182 } | |
| 183 hep = &he->next; | |
| 184 #ifdef HASHMETER | |
| 185 ht->nsteps++; | |
| 186 #endif | |
| 187 } | |
| 188 return hep; | |
| 189 } | |
| 190 | |
| 191 PR_IMPLEMENT(PLHashEntry *) | |
| 192 PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep, | |
| 193 PLHashNumber keyHash, const void *key, void *value) | |
| 194 { | |
| 195 PRUint32 i, n; | |
| 196 PLHashEntry *he, *next, **oldbuckets; | |
| 197 PRSize nb; | |
| 198 | |
| 199 /* Grow the table if it is overloaded */ | |
| 200 n = NBUCKETS(ht); | |
| 201 if (ht->nentries >= OVERLOADED(n)) { | |
| 202 oldbuckets = ht->buckets; | |
| 203 nb = 2 * n * sizeof(PLHashEntry *); | |
| 204 ht->buckets = (PLHashEntry**) | |
| 205 ((*ht->allocOps->allocTable)(ht->allocPriv, nb)); | |
| 206 if (!ht->buckets) { | |
| 207 ht->buckets = oldbuckets; | |
| 208 return 0; | |
| 209 } | |
| 210 memset(ht->buckets, 0, nb); | |
| 211 #ifdef HASHMETER | |
| 212 ht->ngrows++; | |
| 213 #endif | |
| 214 ht->shift--; | |
| 215 | |
| 216 for (i = 0; i < n; i++) { | |
| 217 for (he = oldbuckets[i]; he; he = next) { | |
| 218 next = he->next; | |
| 219 hep = PL_HashTableRawLookup(ht, he->keyHash, he->key); | |
| 220 PR_ASSERT(*hep == 0); | |
| 221 he->next = 0; | |
| 222 *hep = he; | |
| 223 } | |
| 224 } | |
| 225 #ifdef DEBUG | |
| 226 memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]); | |
| 227 #endif | |
| 228 (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets); | |
| 229 hep = PL_HashTableRawLookup(ht, keyHash, key); | |
| 230 } | |
| 231 | |
| 232 /* Make a new key value entry */ | |
| 233 he = (*ht->allocOps->allocEntry)(ht->allocPriv, key); | |
| 234 if (!he) | |
| 235 return 0; | |
| 236 he->keyHash = keyHash; | |
| 237 he->key = key; | |
| 238 he->value = value; | |
| 239 he->next = *hep; | |
| 240 *hep = he; | |
| 241 ht->nentries++; | |
| 242 return he; | |
| 243 } | |
| 244 | |
| 245 PR_IMPLEMENT(PLHashEntry *) | |
| 246 PL_HashTableAdd(PLHashTable *ht, const void *key, void *value) | |
| 247 { | |
| 248 PLHashNumber keyHash; | |
| 249 PLHashEntry *he, **hep; | |
| 250 | |
| 251 keyHash = (*ht->keyHash)(key); | |
| 252 hep = PL_HashTableRawLookup(ht, keyHash, key); | |
| 253 if ((he = *hep) != 0) { | |
| 254 /* Hit; see if values match */ | |
| 255 if ((*ht->valueCompare)(he->value, value)) { | |
| 256 /* key,value pair is already present in table */ | |
| 257 return he; | |
| 258 } | |
| 259 if (he->value) | |
| 260 (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE); | |
| 261 he->value = value; | |
| 262 return he; | |
| 263 } | |
| 264 return PL_HashTableRawAdd(ht, hep, keyHash, key, value); | |
| 265 } | |
| 266 | |
| 267 PR_IMPLEMENT(void) | |
| 268 PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he) | |
| 269 { | |
| 270 PRUint32 i, n; | |
| 271 PLHashEntry *next, **oldbuckets; | |
| 272 PRSize nb; | |
| 273 | |
| 274 *hep = he->next; | |
| 275 (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY); | |
| 276 | |
| 277 /* Shrink table if it's underloaded */ | |
| 278 n = NBUCKETS(ht); | |
| 279 if (--ht->nentries < UNDERLOADED(n)) { | |
| 280 oldbuckets = ht->buckets; | |
| 281 nb = n * sizeof(PLHashEntry*) / 2; | |
| 282 ht->buckets = (PLHashEntry**)( | |
| 283 (*ht->allocOps->allocTable)(ht->allocPriv, nb)); | |
| 284 if (!ht->buckets) { | |
| 285 ht->buckets = oldbuckets; | |
| 286 return; | |
| 287 } | |
| 288 memset(ht->buckets, 0, nb); | |
| 289 #ifdef HASHMETER | |
| 290 ht->nshrinks++; | |
| 291 #endif | |
| 292 ht->shift++; | |
| 293 | |
| 294 for (i = 0; i < n; i++) { | |
| 295 for (he = oldbuckets[i]; he; he = next) { | |
| 296 next = he->next; | |
| 297 hep = PL_HashTableRawLookup(ht, he->keyHash, he->key); | |
| 298 PR_ASSERT(*hep == 0); | |
| 299 he->next = 0; | |
| 300 *hep = he; | |
| 301 } | |
| 302 } | |
| 303 #ifdef DEBUG | |
| 304 memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]); | |
| 305 #endif | |
| 306 (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets); | |
| 307 } | |
| 308 } | |
| 309 | |
| 310 PR_IMPLEMENT(PRBool) | |
| 311 PL_HashTableRemove(PLHashTable *ht, const void *key) | |
| 312 { | |
| 313 PLHashNumber keyHash; | |
| 314 PLHashEntry *he, **hep; | |
| 315 | |
| 316 keyHash = (*ht->keyHash)(key); | |
| 317 hep = PL_HashTableRawLookup(ht, keyHash, key); | |
| 318 if ((he = *hep) == 0) | |
| 319 return PR_FALSE; | |
| 320 | |
| 321 /* Hit; remove element */ | |
| 322 PL_HashTableRawRemove(ht, hep, he); | |
| 323 return PR_TRUE; | |
| 324 } | |
| 325 | |
| 326 PR_IMPLEMENT(void *) | |
| 327 PL_HashTableLookup(PLHashTable *ht, const void *key) | |
| 328 { | |
| 329 PLHashNumber keyHash; | |
| 330 PLHashEntry *he, **hep; | |
| 331 | |
| 332 keyHash = (*ht->keyHash)(key); | |
| 333 hep = PL_HashTableRawLookup(ht, keyHash, key); | |
| 334 if ((he = *hep) != 0) { | |
| 335 return he->value; | |
| 336 } | |
| 337 return 0; | |
| 338 } | |
| 339 | |
| 340 /* | |
| 341 ** Same as PL_HashTableLookup but doesn't reorder the hash entries. | |
| 342 */ | |
| 343 PR_IMPLEMENT(void *) | |
| 344 PL_HashTableLookupConst(PLHashTable *ht, const void *key) | |
| 345 { | |
| 346 PLHashNumber keyHash; | |
| 347 PLHashEntry *he, **hep; | |
| 348 | |
| 349 keyHash = (*ht->keyHash)(key); | |
| 350 hep = PL_HashTableRawLookupConst(ht, keyHash, key); | |
| 351 if ((he = *hep) != 0) { | |
| 352 return he->value; | |
| 353 } | |
| 354 return 0; | |
| 355 } | |
| 356 | |
| 357 /* | |
| 358 ** Iterate over the entries in the hash table calling func for each | |
| 359 ** entry found. Stop if "f" says to (return value & PR_ENUMERATE_STOP). | |
| 360 ** Return a count of the number of elements scanned. | |
| 361 */ | |
| 362 PR_IMPLEMENT(int) | |
| 363 PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg) | |
| 364 { | |
| 365 PLHashEntry *he, **hep; | |
| 366 PRUint32 i, nbuckets; | |
| 367 int rv, n = 0; | |
| 368 PLHashEntry *todo = 0; | |
| 369 | |
| 370 nbuckets = NBUCKETS(ht); | |
| 371 for (i = 0; i < nbuckets; i++) { | |
| 372 hep = &ht->buckets[i]; | |
| 373 while ((he = *hep) != 0) { | |
| 374 rv = (*f)(he, n, arg); | |
| 375 n++; | |
| 376 if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) { | |
| 377 *hep = he->next; | |
| 378 if (rv & HT_ENUMERATE_REMOVE) { | |
| 379 he->next = todo; | |
| 380 todo = he; | |
| 381 } | |
| 382 } else { | |
| 383 hep = &he->next; | |
| 384 } | |
| 385 if (rv & HT_ENUMERATE_STOP) { | |
| 386 goto out; | |
| 387 } | |
| 388 } | |
| 389 } | |
| 390 | |
| 391 out: | |
| 392 hep = &todo; | |
| 393 while ((he = *hep) != 0) { | |
| 394 PL_HashTableRawRemove(ht, hep, he); | |
| 395 } | |
| 396 return n; | |
| 397 } | |
| 398 | |
| 399 #ifdef HASHMETER | |
| 400 #include <math.h> | |
| 401 #include <stdio.h> | |
| 402 | |
| 403 PR_IMPLEMENT(void) | |
| 404 PL_HashTableDumpMeter(PLHashTable *ht, PLHashEnumerator dump, FILE *fp) | |
| 405 { | |
| 406 double mean, variance; | |
| 407 PRUint32 nchains, nbuckets; | |
| 408 PRUint32 i, n, maxChain, maxChainLen; | |
| 409 PLHashEntry *he; | |
| 410 | |
| 411 variance = 0; | |
| 412 nchains = 0; | |
| 413 maxChainLen = 0; | |
| 414 nbuckets = NBUCKETS(ht); | |
| 415 for (i = 0; i < nbuckets; i++) { | |
| 416 he = ht->buckets[i]; | |
| 417 if (!he) | |
| 418 continue; | |
| 419 nchains++; | |
| 420 for (n = 0; he; he = he->next) | |
| 421 n++; | |
| 422 variance += n * n; | |
| 423 if (n > maxChainLen) { | |
| 424 maxChainLen = n; | |
| 425 maxChain = i; | |
| 426 } | |
| 427 } | |
| 428 mean = (double)ht->nentries / nchains; | |
| 429 variance = fabs(variance / nchains - mean * mean); | |
| 430 | |
| 431 fprintf(fp, "\nHash table statistics:\n"); | |
| 432 fprintf(fp, " number of lookups: %u\n", ht->nlookups); | |
| 433 fprintf(fp, " number of entries: %u\n", ht->nentries); | |
| 434 fprintf(fp, " number of grows: %u\n", ht->ngrows); | |
| 435 fprintf(fp, " number of shrinks: %u\n", ht->nshrinks); | |
| 436 fprintf(fp, " mean steps per hash: %g\n", (double)ht->nsteps | |
| 437 / ht->nlookups); | |
| 438 fprintf(fp, "mean hash chain length: %g\n", mean); | |
| 439 fprintf(fp, " standard deviation: %g\n", sqrt(variance)); | |
| 440 fprintf(fp, " max hash chain length: %u\n", maxChainLen); | |
| 441 fprintf(fp, " max hash chain: [%u]\n", maxChain); | |
| 442 | |
| 443 for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++) | |
| 444 if ((*dump)(he, i, fp) != HT_ENUMERATE_NEXT) | |
| 445 break; | |
| 446 } | |
| 447 #endif /* HASHMETER */ | |
| 448 | |
| 449 PR_IMPLEMENT(int) | |
| 450 PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp) | |
| 451 { | |
| 452 int count; | |
| 453 | |
| 454 count = PL_HashTableEnumerateEntries(ht, dump, fp); | |
| 455 #ifdef HASHMETER | |
| 456 PL_HashTableDumpMeter(ht, dump, fp); | |
| 457 #endif | |
| 458 return count; | |
| 459 } | |
| 460 | |
| 461 PR_IMPLEMENT(PLHashNumber) | |
| 462 PL_HashString(const void *key) | |
| 463 { | |
| 464 PLHashNumber h; | |
| 465 const PRUint8 *s; | |
| 466 | |
| 467 h = 0; | |
| 468 for (s = (const PRUint8*)key; *s; s++) | |
| 469 h = PR_ROTATE_LEFT32(h, 4) ^ *s; | |
| 470 return h; | |
| 471 } | |
| 472 | |
| 473 PR_IMPLEMENT(int) | |
| 474 PL_CompareStrings(const void *v1, const void *v2) | |
| 475 { | |
| 476 return strcmp((const char*)v1, (const char*)v2) == 0; | |
| 477 } | |
| 478 | |
| 479 PR_IMPLEMENT(int) | |
| 480 PL_CompareValues(const void *v1, const void *v2) | |
| 481 { | |
| 482 return v1 == v2; | |
| 483 } | |
| 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