Back to index

lightning-sunbird  0.9+nobinonly
plhash.c
Go to the documentation of this file.
00001 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
00002 /* ***** BEGIN LICENSE BLOCK *****
00003  * Version: MPL 1.1/GPL 2.0/LGPL 2.1
00004  *
00005  * The contents of this file are subject to the Mozilla Public License Version
00006  * 1.1 (the "License"); you may not use this file except in compliance with
00007  * the License. You may obtain a copy of the License at
00008  * http://www.mozilla.org/MPL/
00009  *
00010  * Software distributed under the License is distributed on an "AS IS" basis,
00011  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License
00012  * for the specific language governing rights and limitations under the
00013  * License.
00014  *
00015  * The Original Code is the Netscape Portable Runtime (NSPR).
00016  *
00017  * The Initial Developer of the Original Code is
00018  * Netscape Communications Corporation.
00019  * Portions created by the Initial Developer are Copyright (C) 1998-2000
00020  * the Initial Developer. All Rights Reserved.
00021  *
00022  * Contributor(s):
00023  *
00024  * Alternatively, the contents of this file may be used under the terms of
00025  * either the GNU General Public License Version 2 or later (the "GPL"), or
00026  * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),
00027  * in which case the provisions of the GPL or the LGPL are applicable instead
00028  * of those above. If you wish to allow use of your version of this file only
00029  * under the terms of either the GPL or the LGPL, and not to allow others to
00030  * use your version of this file under the terms of the MPL, indicate your
00031  * decision by deleting the provisions above and replace them with the notice
00032  * and other provisions required by the GPL or the LGPL. If you do not delete
00033  * the provisions above, a recipient may use your version of this file under
00034  * the terms of any one of the MPL, the GPL or the LGPL.
00035  *
00036  * ***** END LICENSE BLOCK ***** */
00037 
00038 /*
00039  * PL hash table package.
00040  */
00041 #include "plhash.h"
00042 #include "prbit.h"
00043 #include "prlog.h"
00044 #include "prmem.h"
00045 #include "prtypes.h"
00046 #include <stdlib.h>
00047 #include <string.h>
00048 
00049 /* Compute the number of buckets in ht */
00050 #define NBUCKETS(ht)    (1 << (PL_HASH_BITS - (ht)->shift))
00051 
00052 /* The smallest table has 16 buckets */
00053 #define MINBUCKETSLOG2  4
00054 #define MINBUCKETS      (1 << MINBUCKETSLOG2)
00055 
00056 /* Compute the maximum entries given n buckets that we will tolerate, ~90% */
00057 #define OVERLOADED(n)   ((n) - ((n) >> 3))
00058 
00059 /* Compute the number of entries below which we shrink the table by half */
00060 #define UNDERLOADED(n)  (((n) > MINBUCKETS) ? ((n) >> 2) : 0)
00061 
00062 /*
00063 ** Stubs for default hash allocator ops.
00064 */
00065 static void * PR_CALLBACK
00066 DefaultAllocTable(void *pool, PRSize size)
00067 {
00068 #if defined(XP_MAC)
00069 #pragma unused (pool)
00070 #endif
00071 
00072     return PR_MALLOC(size);
00073 }
00074 
00075 static void PR_CALLBACK
00076 DefaultFreeTable(void *pool, void *item)
00077 {
00078 #if defined(XP_MAC)
00079 #pragma unused (pool)
00080 #endif
00081 
00082     PR_Free(item);
00083 }
00084 
00085 static PLHashEntry * PR_CALLBACK
00086 DefaultAllocEntry(void *pool, const void *key)
00087 {
00088 #if defined(XP_MAC)
00089 #pragma unused (pool,key)
00090 #endif
00091 
00092     return PR_NEW(PLHashEntry);
00093 }
00094 
00095 static void PR_CALLBACK
00096 DefaultFreeEntry(void *pool, PLHashEntry *he, PRUintn flag)
00097 {
00098 #if defined(XP_MAC)
00099 #pragma unused (pool)
00100 #endif
00101 
00102     if (flag == HT_FREE_ENTRY)
00103         PR_Free(he);
00104 }
00105 
00106 static PLHashAllocOps defaultHashAllocOps = {
00107     DefaultAllocTable, DefaultFreeTable,
00108     DefaultAllocEntry, DefaultFreeEntry
00109 };
00110 
00111 PR_IMPLEMENT(PLHashTable *)
00112 PL_NewHashTable(PRUint32 n, PLHashFunction keyHash,
00113                 PLHashComparator keyCompare, PLHashComparator valueCompare,
00114                 const PLHashAllocOps *allocOps, void *allocPriv)
00115 {
00116     PLHashTable *ht;
00117     PRSize nb;
00118 
00119     if (n <= MINBUCKETS) {
00120         n = MINBUCKETSLOG2;
00121     } else {
00122         n = PR_CeilingLog2(n);
00123         if ((PRInt32)n < 0)
00124             return 0;
00125     }
00126 
00127     if (!allocOps) allocOps = &defaultHashAllocOps;
00128 
00129     ht = (PLHashTable*)((*allocOps->allocTable)(allocPriv, sizeof *ht));
00130     if (!ht)
00131        return 0;
00132     memset(ht, 0, sizeof *ht);
00133     ht->shift = PL_HASH_BITS - n;
00134     n = 1 << n;
00135 #if defined(WIN16)
00136     if (n > 16000) {
00137         (*allocOps->freeTable)(allocPriv, ht);
00138         return 0;
00139     }
00140 #endif  /* WIN16 */
00141     nb = n * sizeof(PLHashEntry *);
00142     ht->buckets = (PLHashEntry**)((*allocOps->allocTable)(allocPriv, nb));
00143     if (!ht->buckets) {
00144         (*allocOps->freeTable)(allocPriv, ht);
00145         return 0;
00146     }
00147     memset(ht->buckets, 0, nb);
00148 
00149     ht->keyHash = keyHash;
00150     ht->keyCompare = keyCompare;
00151     ht->valueCompare = valueCompare;
00152     ht->allocOps = allocOps;
00153     ht->allocPriv = allocPriv;
00154     return ht;
00155 }
00156 
00157 PR_IMPLEMENT(void)
00158 PL_HashTableDestroy(PLHashTable *ht)
00159 {
00160     PRUint32 i, n;
00161     PLHashEntry *he, *next;
00162     const PLHashAllocOps *allocOps = ht->allocOps;
00163     void *allocPriv = ht->allocPriv;
00164 
00165     n = NBUCKETS(ht);
00166     for (i = 0; i < n; i++) {
00167         for (he = ht->buckets[i]; he; he = next) {
00168             next = he->next;
00169             (*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY);
00170         }
00171     }
00172 #ifdef DEBUG
00173     memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
00174 #endif
00175     (*allocOps->freeTable)(allocPriv, ht->buckets);
00176 #ifdef DEBUG
00177     memset(ht, 0xDB, sizeof *ht);
00178 #endif
00179     (*allocOps->freeTable)(allocPriv, ht);
00180 }
00181 
00182 /*
00183 ** Multiplicative hash, from Knuth 6.4.
00184 */
00185 #define GOLDEN_RATIO    0x9E3779B9U  /* 2/(1+sqrt(5))*(2^32) */
00186 
00187 PR_IMPLEMENT(PLHashEntry **)
00188 PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key)
00189 {
00190     PLHashEntry *he, **hep, **hep0;
00191     PLHashNumber h;
00192 
00193 #ifdef HASHMETER
00194     ht->nlookups++;
00195 #endif
00196     h = keyHash * GOLDEN_RATIO;
00197     h >>= ht->shift;
00198     hep = hep0 = &ht->buckets[h];
00199     while ((he = *hep) != 0) {
00200         if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {
00201             /* Move to front of chain if not already there */
00202             if (hep != hep0) {
00203                 *hep = he->next;
00204                 he->next = *hep0;
00205                 *hep0 = he;
00206             }
00207             return hep0;
00208         }
00209         hep = &he->next;
00210 #ifdef HASHMETER
00211         ht->nsteps++;
00212 #endif
00213     }
00214     return hep;
00215 }
00216 
00217 /*
00218 ** Same as PL_HashTableRawLookup but doesn't reorder the hash entries.
00219 */
00220 PR_IMPLEMENT(PLHashEntry **)
00221 PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash,
00222                            const void *key)
00223 {
00224     PLHashEntry *he, **hep;
00225     PLHashNumber h;
00226 
00227 #ifdef HASHMETER
00228     ht->nlookups++;
00229 #endif
00230     h = keyHash * GOLDEN_RATIO;
00231     h >>= ht->shift;
00232     hep = &ht->buckets[h];
00233     while ((he = *hep) != 0) {
00234         if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {
00235             break;
00236         }
00237         hep = &he->next;
00238 #ifdef HASHMETER
00239         ht->nsteps++;
00240 #endif
00241     }
00242     return hep;
00243 }
00244 
00245 PR_IMPLEMENT(PLHashEntry *)
00246 PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep,
00247                    PLHashNumber keyHash, const void *key, void *value)
00248 {
00249     PRUint32 i, n;
00250     PLHashEntry *he, *next, **oldbuckets;
00251     PRSize nb;
00252 
00253     /* Grow the table if it is overloaded */
00254     n = NBUCKETS(ht);
00255     if (ht->nentries >= OVERLOADED(n)) {
00256         oldbuckets = ht->buckets;
00257 #if defined(WIN16)
00258         if (2 * n > 16000)
00259             return 0;
00260 #endif  /* WIN16 */
00261         nb = 2 * n * sizeof(PLHashEntry *);
00262         ht->buckets = (PLHashEntry**)
00263             ((*ht->allocOps->allocTable)(ht->allocPriv, nb));
00264         if (!ht->buckets) {
00265             ht->buckets = oldbuckets;
00266             return 0;
00267         }
00268         memset(ht->buckets, 0, nb);
00269 #ifdef HASHMETER
00270         ht->ngrows++;
00271 #endif
00272         ht->shift--;
00273 
00274         for (i = 0; i < n; i++) {
00275             for (he = oldbuckets[i]; he; he = next) {
00276                 next = he->next;
00277                 hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);
00278                 PR_ASSERT(*hep == 0);
00279                 he->next = 0;
00280                 *hep = he;
00281             }
00282         }
00283 #ifdef DEBUG
00284         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
00285 #endif
00286         (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
00287         hep = PL_HashTableRawLookup(ht, keyHash, key);
00288     }
00289 
00290     /* Make a new key value entry */
00291     he = (*ht->allocOps->allocEntry)(ht->allocPriv, key);
00292     if (!he)
00293        return 0;
00294     he->keyHash = keyHash;
00295     he->key = key;
00296     he->value = value;
00297     he->next = *hep;
00298     *hep = he;
00299     ht->nentries++;
00300     return he;
00301 }
00302 
00303 PR_IMPLEMENT(PLHashEntry *)
00304 PL_HashTableAdd(PLHashTable *ht, const void *key, void *value)
00305 {
00306     PLHashNumber keyHash;
00307     PLHashEntry *he, **hep;
00308 
00309     keyHash = (*ht->keyHash)(key);
00310     hep = PL_HashTableRawLookup(ht, keyHash, key);
00311     if ((he = *hep) != 0) {
00312         /* Hit; see if values match */
00313         if ((*ht->valueCompare)(he->value, value)) {
00314             /* key,value pair is already present in table */
00315             return he;
00316         }
00317         if (he->value)
00318             (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE);
00319         he->value = value;
00320         return he;
00321     }
00322     return PL_HashTableRawAdd(ht, hep, keyHash, key, value);
00323 }
00324 
00325 PR_IMPLEMENT(void)
00326 PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he)
00327 {
00328     PRUint32 i, n;
00329     PLHashEntry *next, **oldbuckets;
00330     PRSize nb;
00331 
00332     *hep = he->next;
00333     (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY);
00334 
00335     /* Shrink table if it's underloaded */
00336     n = NBUCKETS(ht);
00337     if (--ht->nentries < UNDERLOADED(n)) {
00338         oldbuckets = ht->buckets;
00339         nb = n * sizeof(PLHashEntry*) / 2;
00340         ht->buckets = (PLHashEntry**)(
00341             (*ht->allocOps->allocTable)(ht->allocPriv, nb));
00342         if (!ht->buckets) {
00343             ht->buckets = oldbuckets;
00344             return;
00345         }
00346         memset(ht->buckets, 0, nb);
00347 #ifdef HASHMETER
00348         ht->nshrinks++;
00349 #endif
00350         ht->shift++;
00351 
00352         for (i = 0; i < n; i++) {
00353             for (he = oldbuckets[i]; he; he = next) {
00354                 next = he->next;
00355                 hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);
00356                 PR_ASSERT(*hep == 0);
00357                 he->next = 0;
00358                 *hep = he;
00359             }
00360         }
00361 #ifdef DEBUG
00362         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
00363 #endif
00364         (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
00365     }
00366 }
00367 
00368 PR_IMPLEMENT(PRBool)
00369 PL_HashTableRemove(PLHashTable *ht, const void *key)
00370 {
00371     PLHashNumber keyHash;
00372     PLHashEntry *he, **hep;
00373 
00374     keyHash = (*ht->keyHash)(key);
00375     hep = PL_HashTableRawLookup(ht, keyHash, key);
00376     if ((he = *hep) == 0)
00377         return PR_FALSE;
00378 
00379     /* Hit; remove element */
00380     PL_HashTableRawRemove(ht, hep, he);
00381     return PR_TRUE;
00382 }
00383 
00384 PR_IMPLEMENT(void *)
00385 PL_HashTableLookup(PLHashTable *ht, const void *key)
00386 {
00387     PLHashNumber keyHash;
00388     PLHashEntry *he, **hep;
00389 
00390     keyHash = (*ht->keyHash)(key);
00391     hep = PL_HashTableRawLookup(ht, keyHash, key);
00392     if ((he = *hep) != 0) {
00393         return he->value;
00394     }
00395     return 0;
00396 }
00397 
00398 /*
00399 ** Same as PL_HashTableLookup but doesn't reorder the hash entries.
00400 */
00401 PR_IMPLEMENT(void *)
00402 PL_HashTableLookupConst(PLHashTable *ht, const void *key)
00403 {
00404     PLHashNumber keyHash;
00405     PLHashEntry *he, **hep;
00406 
00407     keyHash = (*ht->keyHash)(key);
00408     hep = PL_HashTableRawLookupConst(ht, keyHash, key);
00409     if ((he = *hep) != 0) {
00410         return he->value;
00411     }
00412     return 0;
00413 }
00414 
00415 /*
00416 ** Iterate over the entries in the hash table calling func for each
00417 ** entry found. Stop if "f" says to (return value & PR_ENUMERATE_STOP).
00418 ** Return a count of the number of elements scanned.
00419 */
00420 PR_IMPLEMENT(int)
00421 PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg)
00422 {
00423     PLHashEntry *he, **hep;
00424     PRUint32 i, nbuckets;
00425     int rv, n = 0;
00426     PLHashEntry *todo = 0;
00427 
00428     nbuckets = NBUCKETS(ht);
00429     for (i = 0; i < nbuckets; i++) {
00430         hep = &ht->buckets[i];
00431         while ((he = *hep) != 0) {
00432             rv = (*f)(he, n, arg);
00433             n++;
00434             if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {
00435                 *hep = he->next;
00436                 if (rv & HT_ENUMERATE_REMOVE) {
00437                     he->next = todo;
00438                     todo = he;
00439                 }
00440             } else {
00441                 hep = &he->next;
00442             }
00443             if (rv & HT_ENUMERATE_STOP) {
00444                 goto out;
00445             }
00446         }
00447     }
00448 
00449 out:
00450     hep = &todo;
00451     while ((he = *hep) != 0) {
00452         PL_HashTableRawRemove(ht, hep, he);
00453     }
00454     return n;
00455 }
00456 
00457 #ifdef HASHMETER
00458 #include <math.h>
00459 #include <stdio.h>
00460 
00461 PR_IMPLEMENT(void)
00462 PL_HashTableDumpMeter(PLHashTable *ht, PLHashEnumerator dump, FILE *fp)
00463 {
00464     double mean, variance;
00465     PRUint32 nchains, nbuckets;
00466     PRUint32 i, n, maxChain, maxChainLen;
00467     PLHashEntry *he;
00468 
00469     variance = 0;
00470     nchains = 0;
00471     maxChainLen = 0;
00472     nbuckets = NBUCKETS(ht);
00473     for (i = 0; i < nbuckets; i++) {
00474         he = ht->buckets[i];
00475         if (!he)
00476             continue;
00477         nchains++;
00478         for (n = 0; he; he = he->next)
00479             n++;
00480         variance += n * n;
00481         if (n > maxChainLen) {
00482             maxChainLen = n;
00483             maxChain = i;
00484         }
00485     }
00486     mean = (double)ht->nentries / nchains;
00487     variance = fabs(variance / nchains - mean * mean);
00488 
00489     fprintf(fp, "\nHash table statistics:\n");
00490     fprintf(fp, "     number of lookups: %u\n", ht->nlookups);
00491     fprintf(fp, "     number of entries: %u\n", ht->nentries);
00492     fprintf(fp, "       number of grows: %u\n", ht->ngrows);
00493     fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);
00494     fprintf(fp, "   mean steps per hash: %g\n", (double)ht->nsteps
00495                                                 / ht->nlookups);
00496     fprintf(fp, "mean hash chain length: %g\n", mean);
00497     fprintf(fp, "    standard deviation: %g\n", sqrt(variance));
00498     fprintf(fp, " max hash chain length: %u\n", maxChainLen);
00499     fprintf(fp, "        max hash chain: [%u]\n", maxChain);
00500 
00501     for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
00502         if ((*dump)(he, i, fp) != HT_ENUMERATE_NEXT)
00503             break;
00504 }
00505 #endif /* HASHMETER */
00506 
00507 PR_IMPLEMENT(int)
00508 PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp)
00509 {
00510     int count;
00511 
00512     count = PL_HashTableEnumerateEntries(ht, dump, fp);
00513 #ifdef HASHMETER
00514     PL_HashTableDumpMeter(ht, dump, fp);
00515 #endif
00516     return count;
00517 }
00518 
00519 PR_IMPLEMENT(PLHashNumber)
00520 PL_HashString(const void *key)
00521 {
00522     PLHashNumber h;
00523     const PRUint8 *s;
00524 
00525     h = 0;
00526     for (s = (const PRUint8*)key; *s; s++)
00527         h = (h >> 28) ^ (h << 4) ^ *s;
00528     return h;
00529 }
00530 
00531 PR_IMPLEMENT(int)
00532 PL_CompareStrings(const void *v1, const void *v2)
00533 {
00534     return strcmp((const char*)v1, (const char*)v2) == 0;
00535 }
00536 
00537 PR_IMPLEMENT(int)
00538 PL_CompareValues(const void *v1, const void *v2)
00539 {
00540     return v1 == v2;
00541 }