Back to index

lightning-sunbird  0.9+nobinonly
jshash.c
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 4 -*-
00002  *
00003  * ***** BEGIN LICENSE BLOCK *****
00004  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00005  *
00006  * The contents of this file are subject to the Mozilla Public License Version
00007  * 1.1 (the "License"); you may not use this file except in compliance with
00008  * the License. You may obtain a copy of the License at
00009  * http://www.mozilla.org/MPL/
00010  *
00011  * Software distributed under the License is distributed on an "AS IS" basis,
00012  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00013  * for the specific language governing rights and limitations under the
00014  * License.
00015  *
00016  * The Original Code is Mozilla Communicator client code, released
00017  * March 31, 1998.
00018  *
00019  * The Initial Developer of the Original Code is
00020  * Netscape Communications Corporation.
00021  * Portions created by the Initial Developer are Copyright (C) 1998
00022  * the Initial Developer. All Rights Reserved.
00023  *
00024  * Contributor(s):
00025  *
00026  * Alternatively, the contents of this file may be used under the terms of
00027  * either of the GNU General Public License Version 2 or later (the "GPL"),
00028  * or the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00029  * in which case the provisions of the GPL or the LGPL are applicable instead
00030  * of those above. If you wish to allow use of your version of this file only
00031  * under the terms of either the GPL or the LGPL, and not to allow others to
00032  * use your version of this file under the terms of the MPL, indicate your
00033  * decision by deleting the provisions above and replace them with the notice
00034  * and other provisions required by the GPL or the LGPL. If you do not delete
00035  * the provisions above, a recipient may use your version of this file under
00036  * the terms of any one of the MPL, the GPL or the LGPL.
00037  *
00038  * ***** END LICENSE BLOCK ***** */
00039 
00040 /*
00041  * PR hash table package.
00042  */
00043 #include "jsstddef.h"
00044 #include <stdlib.h>
00045 #include <string.h>
00046 #include "jstypes.h"
00047 #include "jsbit.h"
00048 #include "jsutil.h" /* Added by JSIFY */
00049 #include "jshash.h" /* Added by JSIFY */
00050 
00051 /* Compute the number of buckets in ht */
00052 #define NBUCKETS(ht)    JS_BIT(JS_HASH_BITS - (ht)->shift)
00053 
00054 /* The smallest table has 16 buckets */
00055 #define MINBUCKETSLOG2  4
00056 #define MINBUCKETS      JS_BIT(MINBUCKETSLOG2)
00057 
00058 /* Compute the maximum entries given n buckets that we will tolerate, ~90% */
00059 #define OVERLOADED(n)   ((n) - ((n) >> 3))
00060 
00061 /* Compute the number of entries below which we shrink the table by half */
00062 #define UNDERLOADED(n)  (((n) > MINBUCKETS) ? ((n) >> 2) : 0)
00063 
00064 /*
00065 ** Stubs for default hash allocator ops.
00066 */
00067 static void *
00068 DefaultAllocTable(void *pool, size_t size)
00069 {
00070     return malloc(size);
00071 }
00072 
00073 static void
00074 DefaultFreeTable(void *pool, void *item)
00075 {
00076     free(item);
00077 }
00078 
00079 static JSHashEntry *
00080 DefaultAllocEntry(void *pool, const void *key)
00081 {
00082     return (JSHashEntry*) malloc(sizeof(JSHashEntry));
00083 }
00084 
00085 static void
00086 DefaultFreeEntry(void *pool, JSHashEntry *he, uintN flag)
00087 {
00088     if (flag == HT_FREE_ENTRY)
00089         free(he);
00090 }
00091 
00092 static JSHashAllocOps defaultHashAllocOps = {
00093     DefaultAllocTable, DefaultFreeTable,
00094     DefaultAllocEntry, DefaultFreeEntry
00095 };
00096 
00097 JS_PUBLIC_API(JSHashTable *)
00098 JS_NewHashTable(uint32 n, JSHashFunction keyHash,
00099                 JSHashComparator keyCompare, JSHashComparator valueCompare,
00100                 JSHashAllocOps *allocOps, void *allocPriv)
00101 {
00102     JSHashTable *ht;
00103     size_t nb;
00104 
00105     if (n <= MINBUCKETS) {
00106         n = MINBUCKETSLOG2;
00107     } else {
00108         n = JS_CeilingLog2(n);
00109         if ((int32)n < 0)
00110             return NULL;
00111     }
00112 
00113     if (!allocOps) allocOps = &defaultHashAllocOps;
00114 
00115     ht = (JSHashTable*) allocOps->allocTable(allocPriv, sizeof *ht);
00116     if (!ht)
00117         return NULL;
00118     memset(ht, 0, sizeof *ht);
00119     ht->shift = JS_HASH_BITS - n;
00120     n = JS_BIT(n);
00121     nb = n * sizeof(JSHashEntry *);
00122     ht->buckets = (JSHashEntry**) allocOps->allocTable(allocPriv, nb);
00123     if (!ht->buckets) {
00124         allocOps->freeTable(allocPriv, ht);
00125         return NULL;
00126     }
00127     memset(ht->buckets, 0, nb);
00128 
00129     ht->keyHash = keyHash;
00130     ht->keyCompare = keyCompare;
00131     ht->valueCompare = valueCompare;
00132     ht->allocOps = allocOps;
00133     ht->allocPriv = allocPriv;
00134     return ht;
00135 }
00136 
00137 JS_PUBLIC_API(void)
00138 JS_HashTableDestroy(JSHashTable *ht)
00139 {
00140     uint32 i, n;
00141     JSHashEntry *he, **hep;
00142     JSHashAllocOps *allocOps = ht->allocOps;
00143     void *allocPriv = ht->allocPriv;
00144 
00145     n = NBUCKETS(ht);
00146     for (i = 0; i < n; i++) {
00147         hep = &ht->buckets[i];
00148         while ((he = *hep) != NULL) {
00149             *hep = he->next;
00150             allocOps->freeEntry(allocPriv, he, HT_FREE_ENTRY);
00151         }
00152     }
00153 #ifdef DEBUG
00154     memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
00155 #endif
00156     allocOps->freeTable(allocPriv, ht->buckets);
00157 #ifdef DEBUG
00158     memset(ht, 0xDB, sizeof *ht);
00159 #endif
00160     allocOps->freeTable(allocPriv, ht);
00161 }
00162 
00163 /*
00164  * Multiplicative hash, from Knuth 6.4.
00165  */
00166 #define BUCKET_HEAD(ht, keyHash)                                              \
00167     (&(ht)->buckets[((keyHash) * JS_GOLDEN_RATIO) >> (ht)->shift])
00168 
00169 JS_PUBLIC_API(JSHashEntry **)
00170 JS_HashTableRawLookup(JSHashTable *ht, JSHashNumber keyHash, const void *key)
00171 {
00172     JSHashEntry *he, **hep, **hep0;
00173 
00174 #ifdef HASHMETER
00175     ht->nlookups++;
00176 #endif
00177     hep = hep0 = BUCKET_HEAD(ht, keyHash);
00178     while ((he = *hep) != NULL) {
00179         if (he->keyHash == keyHash && ht->keyCompare(key, he->key)) {
00180             /* Move to front of chain if not already there */
00181             if (hep != hep0) {
00182                 *hep = he->next;
00183                 he->next = *hep0;
00184                 *hep0 = he;
00185             }
00186             return hep0;
00187         }
00188         hep = &he->next;
00189 #ifdef HASHMETER
00190         ht->nsteps++;
00191 #endif
00192     }
00193     return hep;
00194 }
00195 
00196 static JSBool
00197 Resize(JSHashTable *ht, uint32 newshift)
00198 {
00199     size_t nb, nentries, i;
00200     JSHashEntry **oldbuckets, *he, *next, **hep;
00201 #ifdef DEBUG
00202     size_t nold = NBUCKETS(ht);
00203 #endif
00204 
00205     JS_ASSERT(newshift < JS_HASH_BITS);
00206 
00207     nb = (size_t)1 << (JS_HASH_BITS - newshift);
00208 
00209     /* Integer overflow protection. */
00210     if (nb > (size_t)-1 / sizeof(JSHashEntry*))
00211         return JS_FALSE;
00212     nb *= sizeof(JSHashEntry*);
00213 
00214     oldbuckets = ht->buckets;
00215     ht->buckets = (JSHashEntry**)ht->allocOps->allocTable(ht->allocPriv, nb);
00216     if (!ht->buckets) {
00217         ht->buckets = oldbuckets;
00218         return JS_FALSE;
00219     }
00220     memset(ht->buckets, 0, nb);
00221 
00222     ht->shift = newshift;
00223     nentries = ht->nentries;
00224 
00225     for (i = 0; nentries != 0; i++) {
00226         for (he = oldbuckets[i]; he; he = next) {
00227             JS_ASSERT(nentries != 0);
00228             --nentries;
00229             next = he->next;
00230             hep = BUCKET_HEAD(ht, he->keyHash);
00231 
00232             /*
00233              * Since he comes from the old table, it must be unique and we
00234              * simply add it to the head of bucket chain without chain lookup.
00235              */
00236             he->next = *hep;
00237             *hep = he;
00238         }
00239     }
00240 #ifdef DEBUG
00241     memset(oldbuckets, 0xDB, nold * sizeof oldbuckets[0]);
00242 #endif
00243     ht->allocOps->freeTable(ht->allocPriv, oldbuckets);
00244     return JS_TRUE;
00245 }
00246 
00247 JS_PUBLIC_API(JSHashEntry *)
00248 JS_HashTableRawAdd(JSHashTable *ht, JSHashEntry **hep,
00249                    JSHashNumber keyHash, const void *key, void *value)
00250 {
00251     uint32 n;
00252     JSHashEntry *he;
00253 
00254     /* Grow the table if it is overloaded */
00255     n = NBUCKETS(ht);
00256     if (ht->nentries >= OVERLOADED(n)) {
00257         if (!Resize(ht, ht->shift - 1))
00258             return NULL;
00259 #ifdef HASHMETER
00260         ht->ngrows++;
00261 #endif
00262         hep = JS_HashTableRawLookup(ht, keyHash, key);
00263     }
00264 
00265     /* Make a new key value entry */
00266     he = ht->allocOps->allocEntry(ht->allocPriv, key);
00267     if (!he)
00268         return NULL;
00269     he->keyHash = keyHash;
00270     he->key = key;
00271     he->value = value;
00272     he->next = *hep;
00273     *hep = he;
00274     ht->nentries++;
00275     return he;
00276 }
00277 
00278 JS_PUBLIC_API(JSHashEntry *)
00279 JS_HashTableAdd(JSHashTable *ht, const void *key, void *value)
00280 {
00281     JSHashNumber keyHash;
00282     JSHashEntry *he, **hep;
00283 
00284     keyHash = ht->keyHash(key);
00285     hep = JS_HashTableRawLookup(ht, keyHash, key);
00286     if ((he = *hep) != NULL) {
00287         /* Hit; see if values match */
00288         if (ht->valueCompare(he->value, value)) {
00289             /* key,value pair is already present in table */
00290             return he;
00291         }
00292         if (he->value)
00293             ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_VALUE);
00294         he->value = value;
00295         return he;
00296     }
00297     return JS_HashTableRawAdd(ht, hep, keyHash, key, value);
00298 }
00299 
00300 JS_PUBLIC_API(void)
00301 JS_HashTableRawRemove(JSHashTable *ht, JSHashEntry **hep, JSHashEntry *he)
00302 {
00303     uint32 n;
00304 
00305     *hep = he->next;
00306     ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY);
00307 
00308     /* Shrink table if it's underloaded */
00309     n = NBUCKETS(ht);
00310     if (--ht->nentries < UNDERLOADED(n)) {
00311         Resize(ht, ht->shift + 1);
00312 #ifdef HASHMETER
00313         ht->nshrinks++;
00314 #endif
00315     }
00316 }
00317 
00318 JS_PUBLIC_API(JSBool)
00319 JS_HashTableRemove(JSHashTable *ht, const void *key)
00320 {
00321     JSHashNumber keyHash;
00322     JSHashEntry *he, **hep;
00323 
00324     keyHash = ht->keyHash(key);
00325     hep = JS_HashTableRawLookup(ht, keyHash, key);
00326     if ((he = *hep) == NULL)
00327         return JS_FALSE;
00328 
00329     /* Hit; remove element */
00330     JS_HashTableRawRemove(ht, hep, he);
00331     return JS_TRUE;
00332 }
00333 
00334 JS_PUBLIC_API(void *)
00335 JS_HashTableLookup(JSHashTable *ht, const void *key)
00336 {
00337     JSHashNumber keyHash;
00338     JSHashEntry *he, **hep;
00339 
00340     keyHash = ht->keyHash(key);
00341     hep = JS_HashTableRawLookup(ht, keyHash, key);
00342     if ((he = *hep) != NULL) {
00343         return he->value;
00344     }
00345     return NULL;
00346 }
00347 
00348 /*
00349 ** Iterate over the entries in the hash table calling func for each
00350 ** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP).
00351 ** Return a count of the number of elements scanned.
00352 */
00353 JS_PUBLIC_API(int)
00354 JS_HashTableEnumerateEntries(JSHashTable *ht, JSHashEnumerator f, void *arg)
00355 {
00356     JSHashEntry *he, **hep, **bucket;
00357     uint32 nlimit, n, nbuckets, newlog2;
00358     int rv;
00359 
00360     nlimit = ht->nentries;
00361     n = 0;
00362     for (bucket = ht->buckets; n != nlimit; ++bucket) {
00363         hep = bucket;
00364         while ((he = *hep) != NULL) {
00365             JS_ASSERT(n < nlimit);
00366             rv = f(he, n, arg);
00367             n++;
00368             if (rv & HT_ENUMERATE_REMOVE) {
00369                 *hep = he->next;
00370                 ht->allocOps->freeEntry(ht->allocPriv, he, HT_FREE_ENTRY);
00371                 --ht->nentries;
00372             } else {
00373                 hep = &he->next;
00374             }
00375             if (rv & HT_ENUMERATE_STOP) {
00376                 goto out;
00377             }
00378         }
00379     }
00380 
00381 out:
00382     /* Shrink table if removal of entries made it underloaded */
00383     if (ht->nentries != nlimit) {
00384         JS_ASSERT(ht->nentries < nlimit);
00385         nbuckets = NBUCKETS(ht);
00386         if (MINBUCKETS < nbuckets && ht->nentries < UNDERLOADED(nbuckets)) {
00387             newlog2 = JS_CeilingLog2(ht->nentries);
00388             if (newlog2 < MINBUCKETSLOG2)
00389                 newlog2 = MINBUCKETSLOG2;
00390 
00391             /*  Check that we really shrink the table. */
00392             JS_ASSERT(JS_HASH_BITS - ht->shift > newlog2);
00393             Resize(ht, JS_HASH_BITS - newlog2);
00394         }
00395     }
00396     return (int)n;
00397 }
00398 
00399 #ifdef HASHMETER
00400 #include <math.h>
00401 #include <stdio.h>
00402 
00403 JS_PUBLIC_API(void)
00404 JS_HashTableDumpMeter(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
00405 {
00406     double sqsum, mean, variance, sigma;
00407     uint32 nchains, nbuckets, nentries;
00408     uint32 i, n, maxChain, maxChainLen;
00409     JSHashEntry *he;
00410 
00411     sqsum = 0;
00412     nchains = 0;
00413     maxChainLen = 0;
00414     nbuckets = NBUCKETS(ht);
00415     for (i = 0; i < nbuckets; i++) {
00416         he = ht->buckets[i];
00417         if (!he)
00418             continue;
00419         nchains++;
00420         for (n = 0; he; he = he->next)
00421             n++;
00422         sqsum += n * n;
00423         if (n > maxChainLen) {
00424             maxChainLen = n;
00425             maxChain = i;
00426         }
00427     }
00428     nentries = ht->nentries;
00429     mean = (double)nentries / nchains;
00430     variance = nchains * sqsum - nentries * nentries;
00431     if (variance < 0 || nchains == 1)
00432         variance = 0;
00433     else
00434         variance /= nchains * (nchains - 1);
00435     sigma = sqrt(variance);
00436 
00437     fprintf(fp, "\nHash table statistics:\n");
00438     fprintf(fp, "     number of lookups: %u\n", ht->nlookups);
00439     fprintf(fp, "     number of entries: %u\n", ht->nentries);
00440     fprintf(fp, "       number of grows: %u\n", ht->ngrows);
00441     fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);
00442     fprintf(fp, "   mean steps per hash: %g\n", (double)ht->nsteps
00443                                                 / ht->nlookups);
00444     fprintf(fp, "mean hash chain length: %g\n", mean);
00445     fprintf(fp, "    standard deviation: %g\n", sigma);
00446     fprintf(fp, " max hash chain length: %u\n", maxChainLen);
00447     fprintf(fp, "        max hash chain: [%u]\n", maxChain);
00448 
00449     for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
00450         if (dump(he, i, fp) != HT_ENUMERATE_NEXT)
00451             break;
00452 }
00453 #endif /* HASHMETER */
00454 
00455 JS_PUBLIC_API(int)
00456 JS_HashTableDump(JSHashTable *ht, JSHashEnumerator dump, FILE *fp)
00457 {
00458     int count;
00459 
00460     count = JS_HashTableEnumerateEntries(ht, dump, fp);
00461 #ifdef HASHMETER
00462     JS_HashTableDumpMeter(ht, dump, fp);
00463 #endif
00464     return count;
00465 }
00466 
00467 JS_PUBLIC_API(JSHashNumber)
00468 JS_HashString(const void *key)
00469 {
00470     JSHashNumber h;
00471     const unsigned char *s;
00472 
00473     h = 0;
00474     for (s = (const unsigned char *)key; *s; s++)
00475         h = (h >> (JS_HASH_BITS - 4)) ^ (h << 4) ^ *s;
00476     return h;
00477 }
00478 
00479 JS_PUBLIC_API(int)
00480 JS_CompareValues(const void *v1, const void *v2)
00481 {
00482     return v1 == v2;
00483 }