nsprpub/lib/ds/plhash.c

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