src/dom/js/jshash.c

   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 JS_PUBLIC_API(JSHashEntry **)
 167 JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key)
 168 {
 169     JSHashEntry *he, **hep, **hep0;
 170     JSHashNumber h;
 171
 172 #ifdef HASHMETER
 173     ht->nlookups++;
 174 #endif
 175     h = keyHash * JS_GOLDEN_RATIO;
 176     h >>= ht->shift;
 177     hep = hep0 = &ht->buckets[h];
 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 HASHMETER
 190         ht->nsteps++;
 191 #endif
 192     }
 193     return hep;
 194 }
 195
 196 JS_PUBLIC_API(JSHashEntry *)
 197 JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **hep,
 198                    JSHashNumber keyHash, const void *key, void *value)
 199 {
 200     uint32 i, n;
 201     JSHashEntry *he, *next, **oldbuckets;
 202     size_t nb;
 203
 204     /* Grow the table if it is overloaded */
 205     n = NBUCKETS(ht);
 206     if (ht->nentries >= OVERLOADED(n)) {
 207         oldbuckets = ht->buckets;
 208         nb = 2 * n * sizeof(JSHashEntry *);
 209         ht->buckets = (JSHashEntry**)
 210             ht->allocOps->allocTable(ht->allocPriv, nb);
 211         if (!ht->buckets) {
 212             ht->buckets = oldbuckets;
 213             return NULL;
 214         }
 215         memset(ht->buckets, 0, nb);
 216 #ifdef HASHMETER
 217         ht->ngrows++;
 218 #endif
 219         ht->shift--;
 220
 221         for (i = 0; i < n; i++) {
 222             for (he = oldbuckets[i]; he; he = next) {
 223                 next = he->next;
 224                 hep = JS_HashTableRawLookup(ht, he->keyHash, he->key);
 225                 JS_ASSERT(*hep == NULL);
 226                 he->next = NULL;
 227                 *hep = he;
 228             }
 229         }
 230 #ifdef DEBUG
 231         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
 232 #endif
 233         ht->allocOps->freeTable(ht->allocPriv, oldbuckets);
 234         hep = JS_HashTableRawLookup(ht, keyHash, key);
 235     }
 236
 237     /* Make a new key value entry */
 238     he = ht->allocOps->allocEntry(ht->allocPriv, key);
 239     if (!he)
 240         return NULL;
 241     he->keyHash = keyHash;
 242     he->key = key;
 243     he->value = value;
 244     he->next = *hep;
 245     *hep = he;
 246     ht->nentries++;
 247     return he;
 248 }
 249
 250 JS_PUBLIC_API(JSHashEntry *)
 251 JS_HashTableAdd(JSHashTable *ht, const void *key, void *value)
 252 {
 253     JSHashNumber keyHash;
 254     JSHashEntry *he, **hep;
 255
 256     keyHash = ht->keyHash(key);
 257     hep = JS_HashTableRawLookup(ht, keyHash, key);
 258     if ((he = *hep) != NULL) {
 259         /* Hit; see if values match */
 260         if (ht->valueCompare(he->value, value)) {
 261             /* key,value pair is already present in table */
 262             return he;
 263         }
 264         if (he->value)
 265             ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_VALUE);
 266         he->value = value;
 267         return he;
 268     }
 269     return JS_HashTableRawAdd(ht, hep, keyHash, key, value);
 270 }
 271
 272 JS_PUBLIC_API(void)
 273 JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he)
 274 {
 275     uint32 i, n;
 276     JSHashEntry *next, **oldbuckets;
 277     size_t nb;
 278
 279     *hep = he->next;
 280     ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY);
 281
 282     /* Shrink table if it's underloaded */
 283     n = NBUCKETS(ht);
 284     if (--ht->nentries < UNDERLOADED(n)) {
 285         oldbuckets = ht->buckets;
 286         nb = n * sizeof(JSHashEntry*) / 2;
 287         ht->buckets = (JSHashEntry**)
 288             ht->allocOps->allocTable(ht->allocPriv, nb);
 289         if (!ht->buckets) {
 290             ht->buckets = oldbuckets;
 291             return;
 292         }
 293         memset(ht->buckets, 0, nb);
 294 #ifdef HASHMETER
 295         ht->nshrinks++;
 296 #endif
 297         ht->shift++;
 298
 299         for (i = 0; i < n; i++) {
 300             for (he = oldbuckets[i]; he; he = next) {
 301                 next = he->next;
 302                 hep = JS_HashTableRawLookup(ht, he->keyHash, he->key);
 303                 JS_ASSERT(*hep == NULL);
 304                 he->next = NULL;
 305                 *hep = he;
 306             }
 307         }
 308 #ifdef DEBUG
 309         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
 310 #endif
 311         ht->allocOps->freeTable(ht->allocPriv, oldbuckets);
 312     }
 313 }
 314
 315 JS_PUBLIC_API(JSBool)
 316 JS_HashTableRemove(JSHashTable *ht, const void *key)
 317 {
 318     JSHashNumber keyHash;
 319     JSHashEntry *he, **hep;
 320
 321     keyHash = ht->keyHash(key);
 322     hep = JS_HashTableRawLookup(ht, keyHash, key);
 323     if ((he = *hep) == NULL)
 324         return JS_FALSE;
 325
 326     /* Hit; remove element */
 327     JS_HashTableRawRemove(ht, hep, he);
 328     return JS_TRUE;
 329 }
 330
 331 JS_PUBLIC_API(void *)
 332 JS_HashTableLookup(JSHashTable *ht, const void *key)
 333 {
 334     JSHashNumber keyHash;
 335     JSHashEntry *he, **hep;
 336
 337     keyHash = ht->keyHash(key);
 338     hep = JS_HashTableRawLookup(ht, keyHash, key);
 339     if ((he = *hep) != NULL) {
 340         return he->value;
 341     }
 342     return NULL;
 343 }
 344
 345 /*
 346 ** Iterate over the entries in the hash table calling func for each
 347 ** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP).
 348 ** Return a count of the number of elements scanned.
 349 */
 350 JS_PUBLIC_API(int)
 351 JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg)
 352 {
 353     JSHashEntry *he, **hep;
 354     uint32 i, nbuckets;
 355     int rv, n = 0;
 356     JSHashEntry *todo = NULL;
 357
 358     nbuckets = NBUCKETS(ht);
 359     for (i = 0; i < nbuckets; i++) {
 360         hep = &ht->buckets[i];
 361         while ((he = *hep) != NULL) {
 362             rv = f(he, n, arg);
 363             n++;
 364             if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {
 365                 *hep = he->next;
 366                 if (rv & HT_ENUMERATE_REMOVE) {
 367                     he->next = todo;
 368                     todo = he;
 369                 }
 370             } else {
 371                 hep = &he->next;
 372             }
 373             if (rv & HT_ENUMERATE_STOP) {
 374                 goto out;
 375             }
 376         }
 377     }
 378
 379 out:
 380     hep = &todo;
 381     while ((he = *hep) != NULL) {
 382         JS_HashTableRawRemove(ht, hep, he);
 383     }
 384     return n;
 385 }
 386
 387 #ifdef HASHMETER
 388 #include <math.h>
 389 #include <stdio.h>
 390
 391 JS_PUBLIC_API(void)
 392 JS_HashTableDumpMeter(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
 393 {
 394     double sqsum, mean, variance, sigma;
 395     uint32 nchains, nbuckets, nentries;
 396     uint32 i, n, maxChain, maxChainLen;
 397     JSHashEntry *he;
 398
 399     sqsum = 0;
 400     nchains = 0;
 401     maxChainLen = 0;
 402     nbuckets = NBUCKETS(ht);
 403     for (i = 0; i < nbuckets; i++) {
 404         he = ht->buckets[i];
 405         if (!he)
 406             continue;
 407         nchains++;
 408         for (n = 0; he; he = he->next)
 409             n++;
 410         sqsum += n * n;
 411         if (n > maxChainLen) {
 412             maxChainLen = n;
 413             maxChain = i;
 414         }
 415     }
 416     nentries = ht->nentries;
 417     mean = (double)nentries / nchains;
 418     variance = nchains * sqsum - nentries * nentries;
 419     if (variance < 0 || nchains == 1)
 420         variance = 0;
 421     else
 422         variance /= nchains * (nchains - 1);
 423     sigma = sqrt(variance);
 424
 425     fprintf(fp, "\nHash table statistics:\n");
 426     fprintf(fp, "     number of lookups: %u\n", ht->nlookups);
 427     fprintf(fp, "     number of entries: %u\n", ht->nentries);
 428     fprintf(fp, "       number of grows: %u\n", ht->ngrows);
 429     fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);
 430     fprintf(fp, "   mean steps per hash: %g\n", (double)ht->nsteps
 431                                                 / ht->nlookups);
 432     fprintf(fp, "mean hash chain length: %g\n", mean);
 433     fprintf(fp, "    standard deviation: %g\n", sigma);
 434     fprintf(fp, " max hash chain length: %u\n", maxChainLen);
 435     fprintf(fp, "        max hash chain: [%u]\n", maxChain);
 436
 437     for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
 438         if (dump(he, i, fp) != HT_ENUMERATE_NEXT)
 439             break;
 440 }
 441 #endif /* HASHMETER */
 442
 443 JS_PUBLIC_API(int)
 444 JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
 445 {
 446     int count;
 447
 448     count = JS_HashTableEnumerateEntries(ht, dump, fp);
 449 #ifdef HASHMETER
 450     JS_HashTableDumpMeter(ht, dump, fp);
 451 #endif
 452     return count;
 453 }
 454
 455 JS_PUBLIC_API(JSHashNumber)
 456 JS_HashString(const void *key)
 457 {
 458     JSHashNumber h;
 459     const unsigned char *s;
 460
 461     h = 0;
 462     for (s = (const unsigned char *)key; *s; s++)
 463         h = (h >> (JS_HASH_BITS - 4)) ^ (h << 4) ^ *s;
 464     return h;
 465 }
 466
 467 JS_PUBLIC_API(int)
 468 JS_CompareValues(const void *v1, const void *v2)
 469 {
 470     return v1 == v2;
 471 }