js/src/jshash.cpp

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
   2  *
   3  * ***** BEGIN LICENSE BLOCK *****
   4  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
   5  *
   6  * The contents of this file are subject to the Mozilla Public License Version
   7  * 1.1 (the "License"); you may not use this file except in compliance with
   8  * the License. You may obtain a copy of the License at
   9  * http://www.mozilla.org/MPL/
  10  *
  11  * Software distributed under the License is distributed on an "AS IS" basis,
  12  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
  13  * for the specific language governing rights and limitations under the
  14  * License.
  15  *
  16  * The Original Code is Mozilla Communicator client code, released
  17  * March 31, 1998.
  18  *
  19  * The Initial Developer of the Original Code is
  20  * Netscape Communications Corporation.
  21  * Portions created by the Initial Developer are Copyright (C) 1998
  22  * the Initial Developer. All Rights Reserved.
  23  *
  24  * Contributor(s):
  25  *
  26  * Alternatively, the contents of this file may be used under the terms of
  27  * either of the GNU General Public License Version 2 or later (the "GPL"),
  28  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
  29  * in which case the provisions of the GPL or the LGPL are applicable instead
  30  * of those above. If you wish to allow use of your version of this file only
  31  * under the terms of either the GPL or the LGPL, and not to allow others to
  32  * use your version of this file under the terms of the MPL, indicate your
  33  * decision by deleting the provisions above and replace them with the notice
  34  * and other provisions required by the GPL or the LGPL. If you do not delete
  35  * the provisions above, a recipient may use your version of this file under
  36  * the terms of any one of the MPL, the GPL or the LGPL.
  37  *
  38  * ***** END LICENSE BLOCK ***** */
  39
  40 /*
  41  * PR hash table package.
  42  */
  43 #include "jsstddef.h"
  44 #include <stdlib.h>
  45 #include <string.h>
  46 #include "jstypes.h"
  47 #include "jsbit.h"
  48 #include "jsutil.h" /* Added by JSIFY */
  49 #include "jshash.h" /* Added by JSIFY */
  50
  51 /* Compute the number of buckets in ht */
  52 #define NBUCKETS(ht)    JS_BIT(JS_HASH_BITS - (ht)->shift)
  53
  54 /* The smallest table has 16 buckets */
  55 #define MINBUCKETSLOG2  4
  56 #define MINBUCKETS      JS_BIT(MINBUCKETSLOG2)
  57
  58 /* Compute the maximum entries given n buckets that we will tolerate, ~90% */
  59 #define OVERLOADED(n)   ((n) - ((n) >> 3))
  60
  61 /* Compute the number of entries below which we shrink the table by half */
  62 #define UNDERLOADED(n)  (((n) > MINBUCKETS) ? ((n) >> 2) : 0)
  63
  64 /*
  65 ** Stubs for default hash allocator ops.
  66 */
  67 static void *
  68 DefaultAllocTable(void *pool, size_t size)
  69 {
  70     return malloc(size);
  71 }
  72
  73 static void
  74 DefaultFreeTable(void *pool, void *item)
  75 {
  76     free(item);
  77 }
  78
  79 static JSHashEntry *
  80 DefaultAllocEntry(void *pool, const void *key)
  81 {
  82     return (JSHashEntry*) malloc(sizeof(JSHashEntry));
  83 }
  84
  85 static void
  86 DefaultFreeEntry(void *pool, JSHashEntry *he, uintN flag)
  87 {
  88     if (flag == HT_FREE_ENTRY)
  89         free(he);
  90 }
  91
  92 static JSHashAllocOps defaultHashAllocOps = {
  93     DefaultAllocTable, DefaultFreeTable,
  94     DefaultAllocEntry, DefaultFreeEntry
  95 };
  96
  97 JS_PUBLIC_API(JSHashTable *)
  98 JS_NewHashTable(uint32 n, JSHashFunction keyHash,
  99                 JSHashComparator keyCompare, JSHashComparator valueCompare,
 100                 JSHashAllocOps *allocOps, void *allocPriv)
 101 {
 102     JSHashTable *ht;
 103     size_t nb;
 104
 105     if (n <= MINBUCKETS) {
 106         n = MINBUCKETSLOG2;
 107     } else {
 108         n = JS_CeilingLog2(n);
 109         if ((int32)n < 0)
 110             return NULL;
 111     }
 112
 113     if (!allocOps) allocOps = &defaultHashAllocOps;
 114
 115     ht = (JSHashTable*) allocOps->allocTable(allocPriv, sizeof *ht);
 116     if (!ht)
 117         return NULL;
 118     memset(ht, 0, sizeof *ht);
 119     ht->shift = JS_HASH_BITS - n;
 120     n = JS_BIT(n);
 121     nb = n * sizeof(JSHashEntry *);
 122     ht->buckets = (JSHashEntry**) allocOps->allocTable(allocPriv, nb);
 123     if (!ht->buckets) {
 124         allocOps->freeTable(allocPriv, ht);
 125         return NULL;
 126     }
 127     memset(ht->buckets, 0, nb);
 128
 129     ht->keyHash = keyHash;
 130     ht->keyCompare = keyCompare;
 131     ht->valueCompare = valueCompare;
 132     ht->allocOps = allocOps;
 133     ht->allocPriv = allocPriv;
 134     return ht;
 135 }
 136
 137 JS_PUBLIC_API(void)
 138 JS_HashTableDestroy(JSHashTable *ht)
 139 {
 140     uint32 i, n;
 141     JSHashEntry *he, **hep;
 142     JSHashAllocOps *allocOps = ht->allocOps;
 143     void *allocPriv = ht->allocPriv;
 144
 145     n = NBUCKETS(ht);
 146     for (i = 0; i < n; i++) {
 147         hep = &ht->buckets[i];
 148         while ((he = *hep) != NULL) {
 149             *hep = he->next;
 150             allocOps->freeEntry(allocPriv, he, HT_FREE_ENTRY);
 151         }
 152     }
 153 #ifdef DEBUG
 154     memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
 155 #endif
 156     allocOps->freeTable(allocPriv, ht->buckets);
 157 #ifdef DEBUG
 158     memset(ht, 0xDB, sizeof *ht);
 159 #endif
 160     allocOps->freeTable(allocPriv, ht);
 161 }
 162
 163 /*
 164  * Multiplicative hash, from Knuth 6.4.
 165  */
 166 #define BUCKET_HEAD(ht, keyHash)                                              \
 167     (&(ht)->buckets[((keyHash) * JS_GOLDEN_RATIO) >> (ht)->shift])
 168
 169 JS_PUBLIC_API(JSHashEntry **)
 170 JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key)
 171 {
 172     JSHashEntry *he, **hep, **hep0;
 173
 174 #ifdef JS_HASHMETER
 175     ht->nlookups++;
 176 #endif
 177     hep = hep0 = BUCKET_HEAD(ht, keyHash);
 178     while ((he = *hep) != NULL) {
 179         if (he->keyHash == keyHash && ht->keyCompare(key, he->key)) {
 180             /* Move to front of chain if not already there */
 181             if (hep != hep0) {
 182                 *hep = he->next;
 183                 he->next = *hep0;
 184                 *hep0 = he;
 185             }
 186             return hep0;
 187         }
 188         hep = &he->next;
 189 #ifdef JS_HASHMETER
 190         ht->nsteps++;
 191 #endif
 192     }
 193     return hep;
 194 }
 195
 196 static JSBool
 197 Resize(JSHashTable *ht, uint32 newshift)
 198 {
 199     size_t nb, nentries, i;
 200     JSHashEntry **oldbuckets, *he, *next, **hep;
 201 #ifdef DEBUG
 202     size_t nold = NBUCKETS(ht);
 203 #endif
 204
 205     JS_ASSERT(newshift < JS_HASH_BITS);
 206
 207     nb = (size_t)1 << (JS_HASH_BITS - newshift);
 208
 209     /* Integer overflow protection. */
 210     if (nb > (size_t)-1 / sizeof(JSHashEntry*))
 211         return JS_FALSE;
 212     nb *= sizeof(JSHashEntry*);
 213
 214     oldbuckets = ht->buckets;
 215     ht->buckets = (JSHashEntry**)ht->allocOps->allocTable(ht->allocPriv, nb);
 216     if (!ht->buckets) {
 217         ht->buckets = oldbuckets;
 218         return JS_FALSE;
 219     }
 220     memset(ht->buckets, 0, nb);
 221
 222     ht->shift = newshift;
 223     nentries = ht->nentries;
 224
 225     for (i = 0; nentries != 0; i++) {
 226         for (he = oldbuckets[i]; he; he = next) {
 227             JS_ASSERT(nentries != 0);
 228             --nentries;
 229             next = he->next;
 230             hep = BUCKET_HEAD(ht, he->keyHash);
 231
 232             /*
 233              * Since he comes from the old table, it must be unique and we
 234              * simply add it to the head of bucket chain without chain lookup.
 235              */
 236             he->next = *hep;
 237             *hep = he;
 238         }
 239     }
 240 #ifdef DEBUG
 241     memset(oldbuckets, 0xDB, nold * sizeof oldbuckets[0]);
 242 #endif
 243     ht->allocOps->freeTable(ht->allocPriv, oldbuckets);
 244     return JS_TRUE;
 245 }
 246
 247 JS_PUBLIC_API(JSHashEntry *)
 248 JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **hep,
 249                    JSHashNumber keyHash, const void *key, void *value)
 250 {
 251     uint32 n;
 252     JSHashEntry *he;
 253
 254     /* Grow the table if it is overloaded */
 255     n = NBUCKETS(ht);
 256     if (ht->nentries >= OVERLOADED(n)) {
 257         if (!Resize(ht, ht->shift - 1))
 258             return NULL;
 259 #ifdef JS_HASHMETER
 260         ht->ngrows++;
 261 #endif
 262         hep = JS_HashTableRawLookup(ht, keyHash, key);
 263     }
 264
 265     /* Make a new key value entry */
 266     he = ht->allocOps->allocEntry(ht->allocPriv, key);
 267     if (!he)
 268         return NULL;
 269     he->keyHash = keyHash;
 270     he->key = key;
 271     he->value = value;
 272     he->next = *hep;
 273     *hep = he;
 274     ht->nentries++;
 275     return he;
 276 }
 277
 278 JS_PUBLIC_API(JSHashEntry *)
 279 JS_HashTableAdd(JSHashTable *ht, const void *key, void *value)
 280 {
 281     JSHashNumber keyHash;
 282     JSHashEntry *he, **hep;
 283
 284     keyHash = ht->keyHash(key);
 285     hep = JS_HashTableRawLookup(ht, keyHash, key);
 286     if ((he = *hep) != NULL) {
 287         /* Hit; see if values match */
 288         if (ht->valueCompare(he->value, value)) {
 289             /* key,value pair is already present in table */
 290             return he;
 291         }
 292         if (he->value)
 293             ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_VALUE);
 294         he->value = value;
 295         return he;
 296     }
 297     return JS_HashTableRawAdd(ht, hep, keyHash, key, value);
 298 }
 299
 300 JS_PUBLIC_API(void)
 301 JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he)
 302 {
 303     uint32 n;
 304
 305     *hep = he->next;
 306     ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY);
 307
 308     /* Shrink table if it's underloaded */
 309     n = NBUCKETS(ht);
 310     if (--ht->nentries < UNDERLOADED(n)) {
 311         Resize(ht, ht->shift + 1);
 312 #ifdef JS_HASHMETER
 313         ht->nshrinks++;
 314 #endif
 315     }
 316 }
 317
 318 JS_PUBLIC_API(JSBool)
 319 JS_HashTableRemove(JSHashTable *ht, const void *key)
 320 {
 321     JSHashNumber keyHash;
 322     JSHashEntry *he, **hep;
 323
 324     keyHash = ht->keyHash(key);
 325     hep = JS_HashTableRawLookup(ht, keyHash, key);
 326     if ((he = *hep) == NULL)
 327         return JS_FALSE;
 328
 329     /* Hit; remove element */
 330     JS_HashTableRawRemove(ht, hep, he);
 331     return JS_TRUE;
 332 }
 333
 334 JS_PUBLIC_API(void *)
 335 JS_HashTableLookup(JSHashTable *ht, const void *key)
 336 {
 337     JSHashNumber keyHash;
 338     JSHashEntry *he, **hep;
 339
 340     keyHash = ht->keyHash(key);
 341     hep = JS_HashTableRawLookup(ht, keyHash, key);
 342     if ((he = *hep) != NULL) {
 343         return he->value;
 344     }
 345     return NULL;
 346 }
 347
 348 /*
 349 ** Iterate over the entries in the hash table calling func for each
 350 ** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP).
 351 ** Return a count of the number of elements scanned.
 352 */
 353 JS_PUBLIC_API(int)
 354 JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg)
 355 {
 356     JSHashEntry *he, **hep, **bucket;
 357     uint32 nlimit, n, nbuckets, newlog2;
 358     int rv;
 359
 360     nlimit = ht->nentries;
 361     n = 0;
 362     for (bucket = ht->buckets; n != nlimit; ++bucket) {
 363         hep = bucket;
 364         while ((he = *hep) != NULL) {
 365             JS_ASSERT(n < nlimit);
 366             rv = f(he, n, arg);
 367             n++;
 368             if (rv & HT_ENUMERATE_REMOVE) {
 369                 *hep = he->next;
 370                 ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY);
 371                 --ht->nentries;
 372             } else {
 373                 hep = &he->next;
 374             }
 375             if (rv & HT_ENUMERATE_STOP) {
 376                 goto out;
 377             }
 378         }
 379     }
 380
 381 out:
 382     /* Shrink table if removal of entries made it underloaded */
 383     if (ht->nentries != nlimit) {
 384         JS_ASSERT(ht->nentries < nlimit);
 385         nbuckets = NBUCKETS(ht);
 386         if (MINBUCKETS < nbuckets && ht->nentries < UNDERLOADED(nbuckets)) {
 387             newlog2 = JS_CeilingLog2(ht->nentries);
 388             if (newlog2 < MINBUCKETSLOG2)
 389                 newlog2 = MINBUCKETSLOG2;
 390
 391             /*  Check that we really shrink the table. */
 392             JS_ASSERT(JS_HASH_BITS - ht->shift > newlog2);
 393             Resize(ht, JS_HASH_BITS - newlog2);
 394         }
 395     }
 396     return (int)n;
 397 }
 398
 399 #ifdef JS_HASHMETER
 400 #include <stdio.h>
 401
 402 JS_PUBLIC_API(void)
 403 JS_HashTableDumpMeter(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
 404 {
 405     double sqsum, mean, sigma;
 406     uint32 nchains, nbuckets;
 407     uint32 i, n, maxChain, maxChainLen;
 408     JSHashEntry *he;
 409
 410     sqsum = 0;
 411     nchains = 0;
 412     maxChain = maxChainLen = 0;
 413     nbuckets = NBUCKETS(ht);
 414     for (i = 0; i < nbuckets; i++) {
 415         he = ht->buckets[i];
 416         if (!he)
 417             continue;
 418         nchains++;
 419         for (n = 0; he; he = he->next)
 420             n++;
 421         sqsum += n * n;
 422         if (n > maxChainLen) {
 423             maxChainLen = n;
 424             maxChain = i;
 425         }
 426     }
 427
 428     mean = JS_MeanAndStdDev(nchains, ht->nentries, sqsum, &sigma);
 429
 430     fprintf(fp, "\nHash table statistics:\n");
 431     fprintf(fp, "     number of lookups: %u\n", ht->nlookups);
 432     fprintf(fp, "     number of entries: %u\n", ht->nentries);
 433     fprintf(fp, "       number of grows: %u\n", ht->ngrows);
 434     fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);
 435     fprintf(fp, "   mean steps per hash: %g\n", (double)ht->nsteps
 436                                                 / ht->nlookups);
 437     fprintf(fp, "mean hash chain length: %g\n", mean);
 438     fprintf(fp, "    standard deviation: %g\n", sigma);
 439     fprintf(fp, " max hash chain length: %u\n", maxChainLen);
 440     fprintf(fp, "        max hash chain: [%u]\n", maxChain);
 441
 442     for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
 443         if (dump(he, i, fp) != HT_ENUMERATE_NEXT)
 444             break;
 445 }
 446 #endif /* JS_HASHMETER */
 447
 448 JS_PUBLIC_API(int)
 449 JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
 450 {
 451     int count;
 452
 453     count = JS_HashTableEnumerateEntries(ht, dump, fp);
 454 #ifdef JS_HASHMETER
 455     JS_HashTableDumpMeter(ht, dump, fp);
 456 #endif
 457     return count;
 458 }
 459
 460 JS_PUBLIC_API(JSHashNumber)
 461 JS_HashString(const void *key)
 462 {
 463     JSHashNumber h;
 464     const unsigned char *s;
 465
 466     h = 0;
 467     for (s = (const unsigned char *)key; *s; s++)
 468         h = JS_ROTATE_LEFT32(h, 4) ^ *s;
 469     return h;
 470 }
 471
 472 JS_PUBLIC_API(int)
 473 JS_CompareValues(const void *v1, const void *v2)
 474 {
 475     return v1 == v2;
 476 }