js/src/liveconnect/jsj_hash.c

   1 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
   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  * This is a copy of the NSPR hash-table library, but it has been slightly
  42  * modified to allow an additional argument to be passed into the hash
  43  * key-comparison function.  This is used to maintain thread-safety by
  44  * passing in a JNIEnv pointer to the key-comparison function rather
  45  * than storing it in a global.  All types,function names, etc. have
  46  * been renamed from their original NSPR names to protect the innocent.
  47  */
  48
  49 #include <stdlib.h>
  50 #include <string.h>
  51
  52 #include "jsj_hash.h"
  53 #include "jstypes.h"
  54 #include "jsutil.h"
  55 #include "jsbit.h"
  56
  57
  58 /* Compute the number of buckets in ht */
  59 #define NBUCKETS(ht)    (1 << (JSJ_HASH_BITS - (ht)->shift))
  60
  61 /* The smallest table has 16 buckets */
  62 #define MINBUCKETSLOG2  4
  63 #define MINBUCKETS      (1 << MINBUCKETSLOG2)
  64
  65 /* Compute the maximum entries given n buckets that we will tolerate, ~90% */
  66 #define OVERLOADED(n)   ((n) - ((n) >> 3))
  67
  68 /* Compute the number of entries below which we shrink the table by half */
  69 #define UNDERLOADED(n)  (((n) > MINBUCKETS) ? ((n) >> 2) : 0)
  70
  71 /*
  72 ** Stubs for default hash allocator ops.
  73 */
  74 static void *
  75 DefaultAllocTable(void *pool, size_t size)
  76 {
  77     return malloc(size);
  78 }
  79
  80 static void
  81 DefaultFreeTable(void *pool, void *item)
  82 {
  83     free(item);
  84 }
  85
  86 static JSJHashEntry *
  87 DefaultAllocEntry(void *pool, const void *key)
  88 {
  89     return malloc(sizeof(JSJHashEntry));
  90 }
  91
  92 static void
  93 DefaultFreeEntry(void *pool, JSJHashEntry *he, JSUintn flag)
  94 {
  95     if (flag == HT_FREE_ENTRY)
  96         free(he);
  97 }
  98
  99 static JSJHashAllocOps defaultHashAllocOps = {
 100     DefaultAllocTable, DefaultFreeTable,
 101     DefaultAllocEntry, DefaultFreeEntry
 102 };
 103
 104 JS_EXPORT_API(JSJHashTable *)
 105 JSJ_NewHashTable(JSUint32 n, JSJHashFunction keyHash,
 106                 JSJHashComparator keyCompare, JSJHashComparator valueCompare,
 107                 JSJHashAllocOps *allocOps, void *allocPriv)
 108 {
 109     JSJHashTable *ht;
 110     JSUint32 nb;
 111
 112     if (n <= MINBUCKETS) {
 113         n = MINBUCKETSLOG2;
 114     } else {
 115         n = JS_CeilingLog2(n);
 116         if ((JSInt32)n < 0)
 117             return 0;
 118     }
 119
 120     if (!allocOps) allocOps = &defaultHashAllocOps;
 121
 122     ht = (*allocOps->allocTable)(allocPriv, sizeof *ht);
 123     if (!ht)
 124     return 0;
 125     memset(ht, 0, sizeof *ht);
 126     ht->shift = JSJ_HASH_BITS - n;
 127     n = 1 << n;
 128 #if (defined(XP_WIN) || defined(XP_OS2)) && !defined(_WIN32)
 129     if (n > 16000) {
 130         (*allocOps->freeTable)(allocPriv, ht);
 131         return 0;
 132     }
 133 #endif  /* WIN16 */
 134     nb = n * sizeof(JSJHashEntry *);
 135     ht->buckets = (*allocOps->allocTable)(allocPriv, nb);
 136     if (!ht->buckets) {
 137         (*allocOps->freeTable)(allocPriv, ht);
 138         return 0;
 139     }
 140     memset(ht->buckets, 0, nb);
 141
 142     ht->keyHash = keyHash;
 143     ht->keyCompare = keyCompare;
 144     ht->valueCompare = valueCompare;
 145     ht->allocOps = allocOps;
 146     ht->allocPriv = allocPriv;
 147     return ht;
 148 }
 149
 150 JS_EXPORT_API(void)
 151 JSJ_HashTableDestroy(JSJHashTable *ht)
 152 {
 153     JSUint32 i, n;
 154     JSJHashEntry *he, *next;
 155     JSJHashAllocOps *allocOps = ht->allocOps;
 156     void *allocPriv = ht->allocPriv;
 157
 158     n = NBUCKETS(ht);
 159     for (i = 0; i < n; i++) {
 160         for (he = ht->buckets[i]; he; he = next) {
 161             next = he->next;
 162             (*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY);
 163         }
 164     }
 165 #ifdef DEBUG
 166     memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
 167 #endif
 168     (*allocOps->freeTable)(allocPriv, ht->buckets);
 169 #ifdef DEBUG
 170     memset(ht, 0xDB, sizeof *ht);
 171 #endif
 172     (*allocOps->freeTable)(allocPriv, ht);
 173 }
 174
 175 /*
 176 ** Multiplicative hash, from Knuth 6.4.
 177 */
 178 #define GOLDEN_RATIO    0x9E3779B9U
 179
 180 JS_EXPORT_API(JSJHashEntry **)
 181 JSJ_HashTableRawLookup(JSJHashTable *ht, JSJHashNumber keyHash, const void *key, void *arg)
 182 {
 183     JSJHashEntry *he, **hep, **hep0;
 184     JSJHashNumber h;
 185
 186 #ifdef HASHMETER
 187     ht->nlookups++;
 188 #endif
 189     h = keyHash * GOLDEN_RATIO;
 190     h >>= ht->shift;
 191     hep = hep0 = &ht->buckets[h];
 192     while ((he = *hep) != 0) {
 193         if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key, arg)) {
 194             /* Move to front of chain if not already there */
 195             if (hep != hep0) {
 196                 *hep = he->next;
 197                 he->next = *hep0;
 198                 *hep0 = he;
 199             }
 200             return hep0;
 201         }
 202         hep = &he->next;
 203 #ifdef HASHMETER
 204         ht->nsteps++;
 205 #endif
 206     }
 207     return hep;
 208 }
 209
 210 JS_EXPORT_API(JSJHashEntry *)
 211 JSJ_HashTableRawAdd(JSJHashTable *ht, JSJHashEntry **hep,
 212                     JSJHashNumber keyHash, const void *key, void *value,
 213                     void *arg)
 214 {
 215     JSUint32 i, n;
 216     JSJHashEntry *he, *next, **oldbuckets;
 217     JSUint32 nb;
 218
 219     /* Grow the table if it is overloaded */
 220     n = NBUCKETS(ht);
 221     if (ht->nentries >= OVERLOADED(n)) {
 222 #ifdef HASHMETER
 223         ht->ngrows++;
 224 #endif
 225         ht->shift--;
 226         oldbuckets = ht->buckets;
 227 #if (defined(XP_WIN) || defined(XP_OS2)) && !defined(_WIN32)
 228         if (2 * n > 16000)
 229             return 0;
 230 #endif  /* WIN16 */
 231         nb = 2 * n * sizeof(JSJHashEntry *);
 232         ht->buckets = (*ht->allocOps->allocTable)(ht->allocPriv, nb);
 233         if (!ht->buckets) {
 234             ht->buckets = oldbuckets;
 235             return 0;
 236         }
 237         memset(ht->buckets, 0, nb);
 238
 239         for (i = 0; i < n; i++) {
 240             for (he = oldbuckets[i]; he; he = next) {
 241                 next = he->next;
 242                 hep = JSJ_HashTableRawLookup(ht, he->keyHash, he->key, arg);
 243                 JS_ASSERT(*hep == 0);
 244                 he->next = 0;
 245                 *hep = he;
 246             }
 247         }
 248 #ifdef DEBUG
 249         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
 250 #endif
 251         (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
 252         hep = JSJ_HashTableRawLookup(ht, keyHash, key, arg);
 253     }
 254
 255     /* Make a new key value entry */
 256     he = (*ht->allocOps->allocEntry)(ht->allocPriv, key);
 257     if (!he)
 258     return 0;
 259     he->keyHash = keyHash;
 260     he->key = key;
 261     he->value = value;
 262     he->next = *hep;
 263     *hep = he;
 264     ht->nentries++;
 265     return he;
 266 }
 267
 268 JS_EXPORT_API(JSJHashEntry *)
 269 JSJ_HashTableAdd(JSJHashTable *ht, const void *key, void *value, void *arg)
 270 {
 271     JSJHashNumber keyHash;
 272     JSJHashEntry *he, **hep;
 273
 274     keyHash = (*ht->keyHash)(key, arg);
 275     hep = JSJ_HashTableRawLookup(ht, keyHash, key, arg);
 276     if ((he = *hep) != 0) {
 277         /* Hit; see if values match */
 278         if ((*ht->valueCompare)(he->value, value, arg)) {
 279             /* key,value pair is already present in table */
 280             return he;
 281         }
 282         if (he->value)
 283             (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE);
 284         he->value = value;
 285         return he;
 286     }
 287     return JSJ_HashTableRawAdd(ht, hep, keyHash, key, value, arg);
 288 }
 289
 290 JS_EXPORT_API(void)
 291 JSJ_HashTableRawRemove(JSJHashTable *ht, JSJHashEntry **hep, JSJHashEntry *he, void *arg)
 292 {
 293     JSUint32 i, n;
 294     JSJHashEntry *next, **oldbuckets;
 295     JSUint32 nb;
 296
 297     *hep = he->next;
 298     (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY);
 299
 300     /* Shrink table if it's underloaded */
 301     n = NBUCKETS(ht);
 302     if (--ht->nentries < UNDERLOADED(n)) {
 303 #ifdef HASHMETER
 304         ht->nshrinks++;
 305 #endif
 306         ht->shift++;
 307         oldbuckets = ht->buckets;
 308         nb = n * sizeof(JSJHashEntry*) / 2;
 309         ht->buckets = (*ht->allocOps->allocTable)(ht->allocPriv, nb);
 310         if (!ht->buckets) {
 311             ht->buckets = oldbuckets;
 312             return;
 313         }
 314         memset(ht->buckets, 0, nb);
 315
 316         for (i = 0; i < n; i++) {
 317             for (he = oldbuckets[i]; he; he = next) {
 318                 next = he->next;
 319                 hep = JSJ_HashTableRawLookup(ht, he->keyHash, he->key, arg);
 320                 JS_ASSERT(*hep == 0);
 321                 he->next = 0;
 322                 *hep = he;
 323             }
 324         }
 325 #ifdef DEBUG
 326         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
 327 #endif
 328         (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
 329     }
 330 }
 331
 332 JS_EXPORT_API(JSBool)
 333 JSJ_HashTableRemove(JSJHashTable *ht, const void *key, void *arg)
 334 {
 335     JSJHashNumber keyHash;
 336     JSJHashEntry *he, **hep;
 337
 338     keyHash = (*ht->keyHash)(key, arg);
 339     hep = JSJ_HashTableRawLookup(ht, keyHash, key, arg);
 340     if ((he = *hep) == 0)
 341         return JS_FALSE;
 342
 343     /* Hit; remove element */
 344     JSJ_HashTableRawRemove(ht, hep, he, arg);
 345     return JS_TRUE;
 346 }
 347
 348 JS_EXPORT_API(void *)
 349 JSJ_HashTableLookup(JSJHashTable *ht, const void *key, void *arg)
 350 {
 351     JSJHashNumber keyHash;
 352     JSJHashEntry *he, **hep;
 353
 354     keyHash = (*ht->keyHash)(key, arg);
 355     hep = JSJ_HashTableRawLookup(ht, keyHash, key, arg);
 356     if ((he = *hep) != 0) {
 357         return he->value;
 358     }
 359     return 0;
 360 }
 361
 362 /*
 363 ** Iterate over the entries in the hash table calling func for each
 364 ** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP).
 365 ** Return a count of the number of elements scanned.
 366 */
 367 JS_EXPORT_API(int)
 368 JSJ_HashTableEnumerateEntries(JSJHashTable *ht, JSJHashEnumerator f, void *arg)
 369 {
 370     JSJHashEntry *he, **hep;
 371     JSUint32 i, nbuckets;
 372     int rv, n = 0;
 373     JSJHashEntry *todo = 0;
 374
 375     nbuckets = NBUCKETS(ht);
 376     for (i = 0; i < nbuckets; i++) {
 377         hep = &ht->buckets[i];
 378         while ((he = *hep) != 0) {
 379             rv = (*f)(he, n, arg);
 380             n++;
 381             if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {
 382                 *hep = he->next;
 383                 if (rv & HT_ENUMERATE_REMOVE) {
 384                     he->next = todo;
 385                     todo = he;
 386                 }
 387             } else {
 388                 hep = &he->next;
 389             }
 390             if (rv & HT_ENUMERATE_STOP) {
 391                 goto out;
 392             }
 393         }
 394     }
 395
 396 out:
 397     hep = &todo;
 398     while ((he = *hep) != 0) {
 399         JSJ_HashTableRawRemove(ht, hep, he, arg);
 400     }
 401     return n;
 402 }
 403
 404 #ifdef HASHMETER
 405 #include <math.h>
 406 #include <stdio.h>
 407
 408 JS_EXPORT_API(void)
 409 JSJ_HashTableDumpMeter(JSJHashTable *ht, JSJHashEnumerator dump, FILE *fp)
 410 {
 411     double mean, variance;
 412     JSUint32 nchains, nbuckets;
 413     JSUint32 i, n, maxChain, maxChainLen;
 414     JSJHashEntry *he;
 415
 416     variance = 0;
 417     nchains = 0;
 418     maxChainLen = 0;
 419     nbuckets = NBUCKETS(ht);
 420     for (i = 0; i < nbuckets; i++) {
 421         he = ht->buckets[i];
 422         if (!he)
 423             continue;
 424         nchains++;
 425         for (n = 0; he; he = he->next)
 426             n++;
 427         variance += n * n;
 428         if (n > maxChainLen) {
 429             maxChainLen = n;
 430             maxChain = i;
 431         }
 432     }
 433     mean = (double)ht->nentries / nchains;
 434     variance = fabs(variance / nchains - mean * mean);
 435
 436     fprintf(fp, "\nHash table statistics:\n");
 437     fprintf(fp, "     number of lookups: %u\n", ht->nlookups);
 438     fprintf(fp, "     number of entries: %u\n", ht->nentries);
 439     fprintf(fp, "       number of grows: %u\n", ht->ngrows);
 440     fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);
 441     fprintf(fp, "   mean steps per hash: %g\n", (double)ht->nsteps
 442                                                 / ht->nlookups);
 443     fprintf(fp, "mean hash chain length: %g\n", mean);
 444     fprintf(fp, "    standard deviation: %g\n", sqrt(variance));
 445     fprintf(fp, " max hash chain length: %u\n", maxChainLen);
 446     fprintf(fp, "        max hash chain: [%u]\n", maxChain);
 447
 448     for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
 449         if ((*dump)(he, i, fp) != HT_ENUMERATE_NEXT)
 450             break;
 451 }
 452 #endif /* HASHMETER */
 453
 454 JS_EXPORT_API(int)
 455 JSJ_HashTableDump(JSJHashTable *ht, JSJHashEnumerator dump, FILE *fp)
 456 {
 457     int count;
 458
 459     count = JSJ_HashTableEnumerateEntries(ht, dump, fp);
 460 #ifdef HASHMETER
 461     JSJ_HashTableDumpMeter(ht, dump, fp);
 462 #endif
 463     return count;
 464 }
 465
 466 JS_EXPORT_API(JSJHashNumber)
 467 JSJ_HashString(const void *key)
 468 {
 469     JSJHashNumber h;
 470     const unsigned char *s;
 471
 472     h = 0;
 473     for (s = key; *s; s++)
 474         h = JS_ROTATE_LEFT32(h, 4) ^ *s;
 475     return h;
 476 }
 477
 478 JS_EXPORT_API(int)
 479 JSJ_CompareStrings(const void *v1, const void *v2)
 480 {
 481     return strcmp(v1, v2) == 0;
 482 }
 483
 484 JS_EXPORT_API(int)
 485 JSJ_CompareValues(const void *v1, const void *v2)
 486 {
 487     return v1 == v2;
 488 }