Back to index

lightning-sunbird  0.9+nobinonly
jsj_hash.c
Go to the documentation of this file.
00001 /* -*- Mode: C; tab-width: 8; indent-tabs-mode: nil; c-basic-offset: 2 -*-
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  * This is a copy of the NSPR hash-table library, but it has been slightly
00042  * modified to allow an additional argument to be passed into the hash
00043  * key-comparison function.  This is used to maintain thread-safety by
00044  * passing in a JNIEnv pointer to the key-comparison function rather
00045  * than storing it in a global.  All types,function names, etc. have
00046  * been renamed from their original NSPR names to protect the innocent.
00047  */
00048 
00049 #include <stdlib.h>
00050 #include <string.h>
00051 
00052 #include "jsj_hash.h"
00053 #include "jstypes.h"
00054 #include "jsutil.h"
00055 #include "jsbit.h"
00056 
00057 
00058 /* Compute the number of buckets in ht */
00059 #define NBUCKETS(ht)    (1 << (JSJ_HASH_BITS - (ht)->shift))
00060 
00061 /* The smallest table has 16 buckets */
00062 #define MINBUCKETSLOG2  4
00063 #define MINBUCKETS      (1 << MINBUCKETSLOG2)
00064 
00065 /* Compute the maximum entries given n buckets that we will tolerate, ~90% */
00066 #define OVERLOADED(n)   ((n) - ((n) >> 3))
00067 
00068 /* Compute the number of entries below which we shrink the table by half */
00069 #define UNDERLOADED(n)  (((n) > MINBUCKETS) ? ((n) >> 2) : 0)
00070 
00071 /*
00072 ** Stubs for default hash allocator ops.
00073 */
00074 static void *
00075 DefaultAllocTable(void *pool, size_t size)
00076 {
00077     return malloc(size);
00078 }
00079 
00080 static void
00081 DefaultFreeTable(void *pool, void *item)
00082 {
00083     free(item);
00084 }
00085 
00086 static JSJHashEntry *
00087 DefaultAllocEntry(void *pool, const void *key)
00088 {
00089     return malloc(sizeof(JSJHashEntry));
00090 }
00091 
00092 static void
00093 DefaultFreeEntry(void *pool, JSJHashEntry *he, JSUintn flag)
00094 {
00095     if (flag == HT_FREE_ENTRY)
00096         free(he);
00097 }
00098 
00099 static JSJHashAllocOps defaultHashAllocOps = {
00100     DefaultAllocTable, DefaultFreeTable,
00101     DefaultAllocEntry, DefaultFreeEntry
00102 };
00103 
00104 JS_EXPORT_API(JSJHashTable *)
00105 JSJ_NewHashTable(JSUint32 n, JSJHashFunction keyHash,
00106                 JSJHashComparator keyCompare, JSJHashComparator valueCompare,
00107                 JSJHashAllocOps *allocOps, void *allocPriv)
00108 {
00109     JSJHashTable *ht;
00110     JSUint32 nb;
00111 
00112     if (n <= MINBUCKETS) {
00113         n = MINBUCKETSLOG2;
00114     } else {
00115         n = JS_CeilingLog2(n);
00116         if ((JSInt32)n < 0)
00117             return 0;
00118     }
00119 
00120     if (!allocOps) allocOps = &defaultHashAllocOps;
00121 
00122     ht = (*allocOps->allocTable)(allocPriv, sizeof *ht);
00123     if (!ht)
00124     return 0;
00125     memset(ht, 0, sizeof *ht);
00126     ht->shift = JSJ_HASH_BITS - n;
00127     n = 1 << n;
00128 #if (defined(XP_WIN) || defined(XP_OS2)) && !defined(_WIN32)
00129     if (n > 16000) {
00130         (*allocOps->freeTable)(allocPriv, ht);
00131         return 0;
00132     }
00133 #endif  /* WIN16 */
00134     nb = n * sizeof(JSJHashEntry *);
00135     ht->buckets = (*allocOps->allocTable)(allocPriv, nb);
00136     if (!ht->buckets) {
00137         (*allocOps->freeTable)(allocPriv, ht);
00138         return 0;
00139     }
00140     memset(ht->buckets, 0, nb);
00141 
00142     ht->keyHash = keyHash;
00143     ht->keyCompare = keyCompare;
00144     ht->valueCompare = valueCompare;
00145     ht->allocOps = allocOps;
00146     ht->allocPriv = allocPriv;
00147     return ht;
00148 }
00149 
00150 JS_EXPORT_API(void)
00151 JSJ_HashTableDestroy(JSJHashTable *ht)
00152 {
00153     JSUint32 i, n;
00154     JSJHashEntry *he, *next;
00155     JSJHashAllocOps *allocOps = ht->allocOps;
00156     void *allocPriv = ht->allocPriv;
00157 
00158     n = NBUCKETS(ht);
00159     for (i = 0; i < n; i++) {
00160         for (he = ht->buckets[i]; he; he = next) {
00161             next = he->next;
00162             (*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY);
00163         }
00164     }
00165 #ifdef DEBUG
00166     memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
00167 #endif
00168     (*allocOps->freeTable)(allocPriv, ht->buckets);
00169 #ifdef DEBUG
00170     memset(ht, 0xDB, sizeof *ht);
00171 #endif
00172     (*allocOps->freeTable)(allocPriv, ht);
00173 }
00174 
00175 /*
00176 ** Multiplicative hash, from Knuth 6.4.
00177 */
00178 #define GOLDEN_RATIO    0x9E3779B9U
00179 
00180 JS_EXPORT_API(JSJHashEntry **)
00181 JSJ_HashTableRawLookup(JSJHashTable *ht, JSJHashNumber keyHash, const void *key, void *arg)
00182 {
00183     JSJHashEntry *he, **hep, **hep0;
00184     JSJHashNumber h;
00185 
00186 #ifdef HASHMETER
00187     ht->nlookups++;
00188 #endif
00189     h = keyHash * GOLDEN_RATIO;
00190     h >>= ht->shift;
00191     hep = hep0 = &ht->buckets[h];
00192     while ((he = *hep) != 0) {
00193         if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key, arg)) {
00194             /* Move to front of chain if not already there */
00195             if (hep != hep0) {
00196                 *hep = he->next;
00197                 he->next = *hep0;
00198                 *hep0 = he;
00199             }
00200             return hep0;
00201         }
00202         hep = &he->next;
00203 #ifdef HASHMETER
00204         ht->nsteps++;
00205 #endif
00206     }
00207     return hep;
00208 }
00209 
00210 JS_EXPORT_API(JSJHashEntry *)
00211 JSJ_HashTableRawAdd(JSJHashTable *ht, JSJHashEntry **hep,
00212                     JSJHashNumber keyHash, const void *key, void *value,
00213                     void *arg)
00214 {
00215     JSUint32 i, n;
00216     JSJHashEntry *he, *next, **oldbuckets;
00217     JSUint32 nb;
00218 
00219     /* Grow the table if it is overloaded */
00220     n = NBUCKETS(ht);
00221     if (ht->nentries >= OVERLOADED(n)) {
00222 #ifdef HASHMETER
00223         ht->ngrows++;
00224 #endif
00225         ht->shift--;
00226         oldbuckets = ht->buckets;
00227 #if (defined(XP_WIN) || defined(XP_OS2)) && !defined(_WIN32)
00228         if (2 * n > 16000)
00229             return 0;
00230 #endif  /* WIN16 */
00231         nb = 2 * n * sizeof(JSJHashEntry *);
00232         ht->buckets = (*ht->allocOps->allocTable)(ht->allocPriv, nb);
00233         if (!ht->buckets) {
00234             ht->buckets = oldbuckets;
00235             return 0;
00236         }
00237         memset(ht->buckets, 0, nb);
00238 
00239         for (i = 0; i < n; i++) {
00240             for (he = oldbuckets[i]; he; he = next) {
00241                 next = he->next;
00242                 hep = JSJ_HashTableRawLookup(ht, he->keyHash, he->key, arg);
00243                 JS_ASSERT(*hep == 0);
00244                 he->next = 0;
00245                 *hep = he;
00246             }
00247         }
00248 #ifdef DEBUG
00249         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
00250 #endif
00251         (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
00252         hep = JSJ_HashTableRawLookup(ht, keyHash, key, arg);
00253     }
00254 
00255     /* Make a new key value entry */
00256     he = (*ht->allocOps->allocEntry)(ht->allocPriv, key);
00257     if (!he)
00258     return 0;
00259     he->keyHash = keyHash;
00260     he->key = key;
00261     he->value = value;
00262     he->next = *hep;
00263     *hep = he;
00264     ht->nentries++;
00265     return he;
00266 }
00267 
00268 JS_EXPORT_API(JSJHashEntry *)
00269 JSJ_HashTableAdd(JSJHashTable *ht, const void *key, void *value, void *arg)
00270 {
00271     JSJHashNumber keyHash;
00272     JSJHashEntry *he, **hep;
00273 
00274     keyHash = (*ht->keyHash)(key, arg);
00275     hep = JSJ_HashTableRawLookup(ht, keyHash, key, arg);
00276     if ((he = *hep) != 0) {
00277         /* Hit; see if values match */
00278         if ((*ht->valueCompare)(he->value, value, arg)) {
00279             /* key,value pair is already present in table */
00280             return he;
00281         }
00282         if (he->value)
00283             (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE);
00284         he->value = value;
00285         return he;
00286     }
00287     return JSJ_HashTableRawAdd(ht, hep, keyHash, key, value, arg);
00288 }
00289 
00290 JS_EXPORT_API(void)
00291 JSJ_HashTableRawRemove(JSJHashTable *ht, JSJHashEntry **hep, JSJHashEntry *he, void *arg)
00292 {
00293     JSUint32 i, n;
00294     JSJHashEntry *next, **oldbuckets;
00295     JSUint32 nb;
00296 
00297     *hep = he->next;
00298     (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY);
00299 
00300     /* Shrink table if it's underloaded */
00301     n = NBUCKETS(ht);
00302     if (--ht->nentries < UNDERLOADED(n)) {
00303 #ifdef HASHMETER
00304         ht->nshrinks++;
00305 #endif
00306         ht->shift++;
00307         oldbuckets = ht->buckets;
00308         nb = n * sizeof(JSJHashEntry*) / 2;
00309         ht->buckets = (*ht->allocOps->allocTable)(ht->allocPriv, nb);
00310         if (!ht->buckets) {
00311             ht->buckets = oldbuckets;
00312             return;
00313         }
00314         memset(ht->buckets, 0, nb);
00315 
00316         for (i = 0; i < n; i++) {
00317             for (he = oldbuckets[i]; he; he = next) {
00318                 next = he->next;
00319                 hep = JSJ_HashTableRawLookup(ht, he->keyHash, he->key, arg);
00320                 JS_ASSERT(*hep == 0);
00321                 he->next = 0;
00322                 *hep = he;
00323             }
00324         }
00325 #ifdef DEBUG
00326         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
00327 #endif
00328         (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
00329     }
00330 }
00331 
00332 JS_EXPORT_API(JSBool)
00333 JSJ_HashTableRemove(JSJHashTable *ht, const void *key, void *arg)
00334 {
00335     JSJHashNumber keyHash;
00336     JSJHashEntry *he, **hep;
00337 
00338     keyHash = (*ht->keyHash)(key, arg);
00339     hep = JSJ_HashTableRawLookup(ht, keyHash, key, arg);
00340     if ((he = *hep) == 0)
00341         return JS_FALSE;
00342 
00343     /* Hit; remove element */
00344     JSJ_HashTableRawRemove(ht, hep, he, arg);
00345     return JS_TRUE;
00346 }
00347 
00348 JS_EXPORT_API(void *)
00349 JSJ_HashTableLookup(JSJHashTable *ht, const void *key, void *arg)
00350 {
00351     JSJHashNumber keyHash;
00352     JSJHashEntry *he, **hep;
00353 
00354     keyHash = (*ht->keyHash)(key, arg);
00355     hep = JSJ_HashTableRawLookup(ht, keyHash, key, arg);
00356     if ((he = *hep) != 0) {
00357         return he->value;
00358     }
00359     return 0;
00360 }
00361 
00362 /*
00363 ** Iterate over the entries in the hash table calling func for each
00364 ** entry found. Stop if "f" says to (return value & JS_ENUMERATE_STOP).
00365 ** Return a count of the number of elements scanned.
00366 */
00367 JS_EXPORT_API(int)
00368 JSJ_HashTableEnumerateEntries(JSJHashTable *ht, JSJHashEnumerator f, void *arg)
00369 {
00370     JSJHashEntry *he, **hep;
00371     JSUint32 i, nbuckets;
00372     int rv, n = 0;
00373     JSJHashEntry *todo = 0;
00374 
00375     nbuckets = NBUCKETS(ht);
00376     for (i = 0; i < nbuckets; i++) {
00377         hep = &ht->buckets[i];
00378         while ((he = *hep) != 0) {
00379             rv = (*f)(he, n, arg);
00380             n++;
00381             if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {
00382                 *hep = he->next;
00383                 if (rv & HT_ENUMERATE_REMOVE) {
00384                     he->next = todo;
00385                     todo = he;
00386                 }
00387             } else {
00388                 hep = &he->next;
00389             }
00390             if (rv & HT_ENUMERATE_STOP) {
00391                 goto out;
00392             }
00393         }
00394     }
00395 
00396 out:
00397     hep = &todo;
00398     while ((he = *hep) != 0) {
00399         JSJ_HashTableRawRemove(ht, hep, he, arg);
00400     }
00401     return n;
00402 }
00403 
00404 #ifdef HASHMETER
00405 #include <math.h>
00406 #include <stdio.h>
00407 
00408 JS_EXPORT_API(void)
00409 JSJ_HashTableDumpMeter(JSJHashTable *ht, JSJHashEnumerator dump, FILE *fp)
00410 {
00411     double mean, variance;
00412     JSUint32 nchains, nbuckets;
00413     JSUint32 i, n, maxChain, maxChainLen;
00414     JSJHashEntry *he;
00415 
00416     variance = 0;
00417     nchains = 0;
00418     maxChainLen = 0;
00419     nbuckets = NBUCKETS(ht);
00420     for (i = 0; i < nbuckets; i++) {
00421         he = ht->buckets[i];
00422         if (!he)
00423             continue;
00424         nchains++;
00425         for (n = 0; he; he = he->next)
00426             n++;
00427         variance += n * n;
00428         if (n > maxChainLen) {
00429             maxChainLen = n;
00430             maxChain = i;
00431         }
00432     }
00433     mean = (double)ht->nentries / nchains;
00434     variance = fabs(variance / nchains - mean * mean);
00435 
00436     fprintf(fp, "\nHash table statistics:\n");
00437     fprintf(fp, "     number of lookups: %u\n", ht->nlookups);
00438     fprintf(fp, "     number of entries: %u\n", ht->nentries);
00439     fprintf(fp, "       number of grows: %u\n", ht->ngrows);
00440     fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);
00441     fprintf(fp, "   mean steps per hash: %g\n", (double)ht->nsteps
00442                                                 / ht->nlookups);
00443     fprintf(fp, "mean hash chain length: %g\n", mean);
00444     fprintf(fp, "    standard deviation: %g\n", sqrt(variance));
00445     fprintf(fp, " max hash chain length: %u\n", maxChainLen);
00446     fprintf(fp, "        max hash chain: [%u]\n", maxChain);
00447 
00448     for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
00449         if ((*dump)(he, i, fp) != HT_ENUMERATE_NEXT)
00450             break;
00451 }
00452 #endif /* HASHMETER */
00453 
00454 JS_EXPORT_API(int)
00455 JSJ_HashTableDump(JSJHashTable *ht, JSJHashEnumerator dump, FILE *fp)
00456 {
00457     int count;
00458 
00459     count = JSJ_HashTableEnumerateEntries(ht, dump, fp);
00460 #ifdef HASHMETER
00461     JSJ_HashTableDumpMeter(ht, dump, fp);
00462 #endif
00463     return count;
00464 }
00465 
00466 JS_EXPORT_API(JSJHashNumber)
00467 JSJ_HashString(const void *key)
00468 {
00469     JSJHashNumber h;
00470     const unsigned char *s;
00471 
00472     h = 0;
00473     for (s = key; *s; s++)
00474         h = (h >> 28) ^ (h << 4) ^ *s;
00475     return h;
00476 }
00477 
00478 JS_EXPORT_API(int)
00479 JSJ_CompareStrings(const void *v1, const void *v2)
00480 {
00481     return strcmp(v1, v2) == 0;
00482 }
00483 
00484 JS_EXPORT_API(int)
00485 JSJ_CompareValues(const void *v1, const void *v2)
00486 {
00487     return v1 == v2;
00488 }