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 <stdlib.h>
  44 #include <string.h>
  45 #include "jstypes.h"
  46 #include "jsstdint.h"
  47 #include "jsbit.h"
  48 #include "jsutil.h"
  49 #include "jshash.h"
  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 js_malloc(size);
  71 }
  72
  73 static void
  74 DefaultFreeTable(void *pool, void *item, size_t size)
  75 {
  76     js_free(item);
  77 }
  78
  79 static JSHashEntry *
  80 DefaultAllocEntry(void *pool, const void *key)
  81 {
  82     return (JSHashEntry*) js_malloc(sizeof(JSHashEntry));
  83 }
  84
  85 static void
  86 DefaultFreeEntry(void *pool, JSHashEntry *he, uintN flag)
  87 {
  88     if (flag == HT_FREE_ENTRY)
  89         js_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, nb);
 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, n * sizeof ht->buckets[0]);
 157 #ifdef DEBUG
 158     memset(ht, 0xDB, sizeof *ht);
 159 #endif
 160     allocOps->freeTable(allocPriv, ht, sizeof *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     size_t nold = NBUCKETS(ht);
 202
 203     JS_ASSERT(newshift < JS_HASH_BITS);
 204
 205     nb = (size_t)1 << (JS_HASH_BITS - newshift);
 206
 207     /* Integer overflow protection. */
 208     if (nb > (size_t)-1 / sizeof(JSHashEntry*))
 209         return JS_FALSE;
 210     nb *= sizeof(JSHashEntry*);
 211
 212     oldbuckets = ht->buckets;
 213     ht->buckets = (JSHashEntry**)ht->allocOps->allocTable(ht->allocPriv, nb);
 214     if (!ht->buckets) {
 215         ht->buckets = oldbuckets;
 216         return JS_FALSE;
 217     }
 218     memset(ht->buckets, 0, nb);
 219
 220     ht->shift = newshift;
 221     nentries = ht->nentries;
 222
 223     for (i = 0; nentries != 0; i++) {
 224         for (he = oldbuckets[i]; he; he = next) {
 225             JS_ASSERT(nentries != 0);
 226             --nentries;
 227             next = he->next;
 228             hep = BUCKET_HEAD(ht, he->keyHash);
 229
 230             /*
 231              * We do not require unique entries, instead appending he to the
 232              * chain starting at hep.
 233              */
 234             while (*hep)
 235                 hep = &(*hep)->next;
 236             he->next = NULL;
 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                             nold * sizeof oldbuckets[0]);
 245     return JS_TRUE;
 246 }
 247
 248 JS_PUBLIC_API(JSHashEntry *)
 249 JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **&hep,
 250                    JSHashNumber keyHash, const void *key, void *value)
 251 {
 252     uint32 n;
 253     JSHashEntry *he;
 254
 255     /* Grow the table if it is overloaded */
 256     n = NBUCKETS(ht);
 257     if (ht->nentries >= OVERLOADED(n)) {
 258         if (!Resize(ht, ht->shift - 1))
 259             return NULL;
 260 #ifdef JS_HASHMETER
 261         ht->ngrows++;
 262 #endif
 263         hep = JS_HashTableRawLookup(ht, keyHash, key);
 264     }
 265
 266     /* Make a new key value entry */
 267     he = ht->allocOps->allocEntry(ht->allocPriv, key);
 268     if (!he)
 269         return NULL;
 270     he->keyHash = keyHash;
 271     he->key = key;
 272     he->value = value;
 273     he->next = *hep;
 274     *hep = he;
 275     ht->nentries++;
 276     return he;
 277 }
 278
 279 JS_PUBLIC_API(JSHashEntry *)
 280 JS_HashTableAdd(JSHashTable *ht, const void *key, void *value)
 281 {
 282     JSHashNumber keyHash;
 283     JSHashEntry *he, **hep;
 284
 285     keyHash = ht->keyHash(key);
 286     hep = JS_HashTableRawLookup(ht, keyHash, key);
 287     if ((he = *hep) != NULL) {
 288         /* Hit; see if values match */
 289         if (ht->valueCompare(he->value, value)) {
 290             /* key,value pair is already present in table */
 291             return he;
 292         }
 293         if (he->value)
 294             ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_VALUE);
 295         he->value = value;
 296         return he;
 297     }
 298     return JS_HashTableRawAdd(ht, hep, keyHash, key, value);
 299 }
 300
 301 JS_PUBLIC_API(void)
 302 JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he)
 303 {
 304     uint32 n;
 305
 306     *hep = he->next;
 307     ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY);
 308
 309     /* Shrink table if it's underloaded */
 310     n = NBUCKETS(ht);
 311     if (--ht->nentries < UNDERLOADED(n)) {
 312         Resize(ht, ht->shift + 1);
 313 #ifdef JS_HASHMETER
 314         ht->nshrinks++;
 315 #endif
 316     }
 317 }
 318
 319 JS_PUBLIC_API(JSBool)
 320 JS_HashTableRemove(JSHashTable *ht, const void *key)
 321 {
 322     JSHashNumber keyHash;
 323     JSHashEntry *he, **hep;
 324
 325     keyHash = ht->keyHash(key);
 326     hep = JS_HashTableRawLookup(ht, keyHash, key);
 327     if ((he = *hep) == NULL)
 328         return JS_FALSE;
 329
 330     /* Hit; remove element */
 331     JS_HashTableRawRemove(ht, hep, he);
 332     return JS_TRUE;
 333 }
 334
 335 JS_PUBLIC_API(void *)
 336 JS_HashTableLookup(JSHashTable *ht, const void *key)
 337 {
 338     JSHashNumber keyHash;
 339     JSHashEntry *he, **hep;
 340
 341     keyHash = ht->keyHash(key);
 342     hep = JS_HashTableRawLookup(ht, keyHash, key);
 343     if ((he = *hep) != NULL) {
 344         return he->value;
 345     }
 346     return NULL;
 347 }
 348
 349 /*
 350 ** Iterate over the entries in the hash table calling func for each
 351 ** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP).
 352 ** Return a count of the number of elements scanned.
 353 */
 354 JS_PUBLIC_API(int)
 355 JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg)
 356 {
 357     JSHashEntry *he, **hep, **bucket;
 358     uint32 nlimit, n, nbuckets, newlog2;
 359     int rv;
 360
 361     nlimit = ht->nentries;
 362     n = 0;
 363     for (bucket = ht->buckets; n != nlimit; ++bucket) {
 364         hep = bucket;
 365         while ((he = *hep) != NULL) {
 366             JS_ASSERT(n < nlimit);
 367             rv = f(he, n, arg);
 368             n++;
 369             if (rv & HT_ENUMERATE_REMOVE) {
 370                 *hep = he->next;
 371                 ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY);
 372                 --ht->nentries;
 373             } else {
 374                 hep = &he->next;
 375             }
 376             if (rv & HT_ENUMERATE_STOP) {
 377                 goto out;
 378             }
 379         }
 380     }
 381
 382 out:
 383     /* Shrink table if removal of entries made it underloaded */
 384     if (ht->nentries != nlimit) {
 385         JS_ASSERT(ht->nentries < nlimit);
 386         nbuckets = NBUCKETS(ht);
 387         if (MINBUCKETS < nbuckets && ht->nentries < UNDERLOADED(nbuckets)) {
 388             newlog2 = JS_CeilingLog2(ht->nentries);
 389             if (newlog2 < MINBUCKETSLOG2)
 390                 newlog2 = MINBUCKETSLOG2;
 391
 392             /*  Check that we really shrink the table. */
 393             JS_ASSERT(JS_HASH_BITS - ht->shift > newlog2);
 394             Resize(ht, JS_HASH_BITS - newlog2);
 395         }
 396     }
 397     return (int)n;
 398 }
 399
 400 #ifdef JS_HASHMETER
 401 #include <stdio.h>
 402
 403 JS_PUBLIC_API(void)
 404 JS_HashTableDumpMeter(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
 405 {
 406     double sqsum, mean, sigma;
 407     uint32 nchains, nbuckets;
 408     uint32 i, n, maxChain, maxChainLen;
 409     JSHashEntry *he;
 410
 411     sqsum = 0;
 412     nchains = 0;
 413     maxChain = 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         sqsum += n * n;
 423         if (n > maxChainLen) {
 424             maxChainLen = n;
 425             maxChain = i;
 426         }
 427     }
 428
 429     mean = JS_MeanAndStdDev(nchains, ht->nentries, sqsum, &sigma);
 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", sigma);
 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 /* JS_HASHMETER */
 448
 449 JS_PUBLIC_API(int)
 450 JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
 451 {
 452     int count;
 453
 454     count = JS_HashTableEnumerateEntries(ht, dump, fp);
 455 #ifdef JS_HASHMETER
 456     JS_HashTableDumpMeter(ht, dump, fp);
 457 #endif
 458     return count;
 459 }
 460
 461 JS_PUBLIC_API(JSHashNumber)
 462 JS_HashString(const void *key)
 463 {
 464     JSHashNumber h;
 465     const unsigned char *s;
 466
 467     h = 0;
 468     for (s = (const unsigned char *)key; *s; s++)
 469         h = JS_ROTATE_LEFT32(h, 4) ^ *s;
 470     return h;
 471 }
 472
 473 JS_PUBLIC_API(int)
 474 JS_CompareValues(const void *v1, const void *v2)
 475 {
 476     return v1 == v2;
 477 }