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