The Tor Browser: nsprpub/lib/ds/plhash.c@8bccb770b82d

     1 /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */

     2 /* This Source Code Form is subject to the terms of the Mozilla Public

     3  * License, v. 2.0. If a copy of the MPL was not distributed with this

     4  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */

     6 /*

     7  * PL hash table package.

     8  */

     9 #include "plhash.h"

    10 #include "prbit.h"

    11 #include "prlog.h"

    12 #include "prmem.h"

    13 #include "prtypes.h"

    14 #include <stdlib.h>

    15 #include <string.h>

    17 /* Compute the number of buckets in ht */

    18 #define NBUCKETS(ht)    (1 << (PL_HASH_BITS - (ht)->shift))

    20 /* The smallest table has 16 buckets */

    21 #define MINBUCKETSLOG2  4

    22 #define MINBUCKETS      (1 << MINBUCKETSLOG2)

    24 /* Compute the maximum entries given n buckets that we will tolerate, ~90% */

    25 #define OVERLOADED(n)   ((n) - ((n) >> 3))

    27 /* Compute the number of entries below which we shrink the table by half */

    28 #define UNDERLOADED(n)  (((n) > MINBUCKETS) ? ((n) >> 2) : 0)

    30 /*

    31 ** Stubs for default hash allocator ops.

    32 */

    33 static void * PR_CALLBACK

    34 DefaultAllocTable(void *pool, PRSize size)

    35 {

    36     return PR_MALLOC(size);

    37 }

    39 static void PR_CALLBACK

    40 DefaultFreeTable(void *pool, void *item)

    41 {

    42     PR_Free(item);

    43 }

    45 static PLHashEntry * PR_CALLBACK

    46 DefaultAllocEntry(void *pool, const void *key)

    47 {

    48     return PR_NEW(PLHashEntry);

    49 }

    51 static void PR_CALLBACK

    52 DefaultFreeEntry(void *pool, PLHashEntry *he, PRUintn flag)

    53 {

    54     if (flag == HT_FREE_ENTRY)

    55         PR_Free(he);

    56 }

    58 static PLHashAllocOps defaultHashAllocOps = {

    59     DefaultAllocTable, DefaultFreeTable,

    60     DefaultAllocEntry, DefaultFreeEntry

    61 };

    63 PR_IMPLEMENT(PLHashTable *)

    64 PL_NewHashTable(PRUint32 n, PLHashFunction keyHash,

    65                 PLHashComparator keyCompare, PLHashComparator valueCompare,

    66                 const PLHashAllocOps *allocOps, void *allocPriv)

    67 {

    68     PLHashTable *ht;

    69     PRSize nb;

    71     if (n <= MINBUCKETS) {

    72         n = MINBUCKETSLOG2;

    73     } else {

    74         n = PR_CeilingLog2(n);

    75         if ((PRInt32)n < 0)

    76             return 0;

    77     }

    79     if (!allocOps) allocOps = &defaultHashAllocOps;

    81     ht = (PLHashTable*)((*allocOps->allocTable)(allocPriv, sizeof *ht));

    82     if (!ht)

    83 	return 0;

    84     memset(ht, 0, sizeof *ht);

    85     ht->shift = PL_HASH_BITS - n;

    86     n = 1 << n;

    87     nb = n * sizeof(PLHashEntry *);

    88     ht->buckets = (PLHashEntry**)((*allocOps->allocTable)(allocPriv, nb));

    89     if (!ht->buckets) {

    90         (*allocOps->freeTable)(allocPriv, ht);

    91         return 0;

    92     }

    93     memset(ht->buckets, 0, nb);

    95     ht->keyHash = keyHash;

    96     ht->keyCompare = keyCompare;

    97     ht->valueCompare = valueCompare;

    98     ht->allocOps = allocOps;

    99     ht->allocPriv = allocPriv;

   100     return ht;

   101 }

   103 PR_IMPLEMENT(void)

   104 PL_HashTableDestroy(PLHashTable *ht)

   105 {

   106     PRUint32 i, n;

   107     PLHashEntry *he, *next;

   108     const PLHashAllocOps *allocOps = ht->allocOps;

   109     void *allocPriv = ht->allocPriv;

   111     n = NBUCKETS(ht);

   112     for (i = 0; i < n; i++) {

   113         for (he = ht->buckets[i]; he; he = next) {

   114             next = he->next;

   115             (*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY);

   116         }

   117     }

   118 #ifdef DEBUG

   119     memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);

   120 #endif

   121     (*allocOps->freeTable)(allocPriv, ht->buckets);

   122 #ifdef DEBUG

   123     memset(ht, 0xDB, sizeof *ht);

   124 #endif

   125     (*allocOps->freeTable)(allocPriv, ht);

   126 }

   128 /*

   129 ** Multiplicative hash, from Knuth 6.4.

   130 */

   131 #define GOLDEN_RATIO    0x9E3779B9U  /* 2/(1+sqrt(5))*(2^32) */

   133 PR_IMPLEMENT(PLHashEntry **)

   134 PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key)

   135 {

   136     PLHashEntry *he, **hep, **hep0;

   137     PLHashNumber h;

   139 #ifdef HASHMETER

   140     ht->nlookups++;

   141 #endif

   142     h = keyHash * GOLDEN_RATIO;

   143     h >>= ht->shift;

   144     hep = hep0 = &ht->buckets[h];

   145     while ((he = *hep) != 0) {

   146         if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {

   147             /* Move to front of chain if not already there */

   148             if (hep != hep0) {

   149                 *hep = he->next;

   150                 he->next = *hep0;

   151                 *hep0 = he;

   152             }

   153             return hep0;

   154         }

   155         hep = &he->next;

   156 #ifdef HASHMETER

   157         ht->nsteps++;

   158 #endif

   159     }

   160     return hep;

   161 }

   163 /*

   164 ** Same as PL_HashTableRawLookup but doesn't reorder the hash entries.

   165 */

   166 PR_IMPLEMENT(PLHashEntry **)

   167 PL_HashTableRawLookupConst(PLHashTable *ht, PLHashNumber keyHash,

   168                            const void *key)

   169 {

   170     PLHashEntry *he, **hep;

   171     PLHashNumber h;

   173 #ifdef HASHMETER

   174     ht->nlookups++;

   175 #endif

   176     h = keyHash * GOLDEN_RATIO;

   177     h >>= ht->shift;

   178     hep = &ht->buckets[h];

   179     while ((he = *hep) != 0) {

   180         if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {

   181             break;

   182         }

   183         hep = &he->next;

   184 #ifdef HASHMETER

   185         ht->nsteps++;

   186 #endif

   187     }

   188     return hep;

   189 }

   191 PR_IMPLEMENT(PLHashEntry *)

   192 PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep,

   193                    PLHashNumber keyHash, const void *key, void *value)

   194 {

   195     PRUint32 i, n;

   196     PLHashEntry *he, *next, **oldbuckets;

   197     PRSize nb;

   199     /* Grow the table if it is overloaded */

   200     n = NBUCKETS(ht);

   201     if (ht->nentries >= OVERLOADED(n)) {

   202         oldbuckets = ht->buckets;

   203         nb = 2 * n * sizeof(PLHashEntry *);

   204         ht->buckets = (PLHashEntry**)

   205             ((*ht->allocOps->allocTable)(ht->allocPriv, nb));

   206         if (!ht->buckets) {

   207             ht->buckets = oldbuckets;

   208             return 0;

   209         }

   210         memset(ht->buckets, 0, nb);

   211 #ifdef HASHMETER

   212         ht->ngrows++;

   213 #endif

   214         ht->shift--;

   216         for (i = 0; i < n; i++) {

   217             for (he = oldbuckets[i]; he; he = next) {

   218                 next = he->next;

   219                 hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);

   220                 PR_ASSERT(*hep == 0);

   221                 he->next = 0;

   222                 *hep = he;

   223             }

   224         }

   225 #ifdef DEBUG

   226         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);

   227 #endif

   228         (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);

   229         hep = PL_HashTableRawLookup(ht, keyHash, key);

   230     }

   232     /* Make a new key value entry */

   233     he = (*ht->allocOps->allocEntry)(ht->allocPriv, key);

   234     if (!he)

   235 	return 0;

   236     he->keyHash = keyHash;

   237     he->key = key;

   238     he->value = value;

   239     he->next = *hep;

   240     *hep = he;

   241     ht->nentries++;

   242     return he;

   243 }

   245 PR_IMPLEMENT(PLHashEntry *)

   246 PL_HashTableAdd(PLHashTable *ht, const void *key, void *value)

   247 {

   248     PLHashNumber keyHash;

   249     PLHashEntry *he, **hep;

   251     keyHash = (*ht->keyHash)(key);

   252     hep = PL_HashTableRawLookup(ht, keyHash, key);

   253     if ((he = *hep) != 0) {

   254         /* Hit; see if values match */

   255         if ((*ht->valueCompare)(he->value, value)) {

   256             /* key,value pair is already present in table */

   257             return he;

   258         }

   259         if (he->value)

   260             (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE);

   261         he->value = value;

   262         return he;

   263     }

   264     return PL_HashTableRawAdd(ht, hep, keyHash, key, value);

   265 }

   267 PR_IMPLEMENT(void)

   268 PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he)

   269 {

   270     PRUint32 i, n;

   271     PLHashEntry *next, **oldbuckets;

   272     PRSize nb;

   274     *hep = he->next;

   275     (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY);

   277     /* Shrink table if it's underloaded */

   278     n = NBUCKETS(ht);

   279     if (--ht->nentries < UNDERLOADED(n)) {

   280         oldbuckets = ht->buckets;

   281         nb = n * sizeof(PLHashEntry*) / 2;

   282         ht->buckets = (PLHashEntry**)(

   283             (*ht->allocOps->allocTable)(ht->allocPriv, nb));

   284         if (!ht->buckets) {

   285             ht->buckets = oldbuckets;

   286             return;

   287         }

   288         memset(ht->buckets, 0, nb);

   289 #ifdef HASHMETER

   290         ht->nshrinks++;

   291 #endif

   292         ht->shift++;

   294         for (i = 0; i < n; i++) {

   295             for (he = oldbuckets[i]; he; he = next) {

   296                 next = he->next;

   297                 hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);

   298                 PR_ASSERT(*hep == 0);

   299                 he->next = 0;

   300                 *hep = he;

   301             }

   302         }

   303 #ifdef DEBUG

   304         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);

   305 #endif

   306         (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);

   307     }

   308 }

   310 PR_IMPLEMENT(PRBool)

   311 PL_HashTableRemove(PLHashTable *ht, const void *key)

   312 {

   313     PLHashNumber keyHash;

   314     PLHashEntry *he, **hep;

   316     keyHash = (*ht->keyHash)(key);

   317     hep = PL_HashTableRawLookup(ht, keyHash, key);

   318     if ((he = *hep) == 0)

   319         return PR_FALSE;

   321     /* Hit; remove element */

   322     PL_HashTableRawRemove(ht, hep, he);

   323     return PR_TRUE;

   324 }

   326 PR_IMPLEMENT(void *)

   327 PL_HashTableLookup(PLHashTable *ht, const void *key)

   328 {

   329     PLHashNumber keyHash;

   330     PLHashEntry *he, **hep;

   332     keyHash = (*ht->keyHash)(key);

   333     hep = PL_HashTableRawLookup(ht, keyHash, key);

   334     if ((he = *hep) != 0) {

   335         return he->value;

   336     }

   337     return 0;

   338 }

   340 /*

   341 ** Same as PL_HashTableLookup but doesn't reorder the hash entries.

   342 */

   343 PR_IMPLEMENT(void *)

   344 PL_HashTableLookupConst(PLHashTable *ht, const void *key)

   345 {

   346     PLHashNumber keyHash;

   347     PLHashEntry *he, **hep;

   349     keyHash = (*ht->keyHash)(key);

   350     hep = PL_HashTableRawLookupConst(ht, keyHash, key);

   351     if ((he = *hep) != 0) {

   352         return he->value;

   353     }

   354     return 0;

   355 }

   357 /*

   358 ** Iterate over the entries in the hash table calling func for each

   359 ** entry found. Stop if "f" says to (return value & PR_ENUMERATE_STOP).

   360 ** Return a count of the number of elements scanned.

   361 */

   362 PR_IMPLEMENT(int)

   363 PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg)

   364 {

   365     PLHashEntry *he, **hep;

   366     PRUint32 i, nbuckets;

   367     int rv, n = 0;

   368     PLHashEntry *todo = 0;

   370     nbuckets = NBUCKETS(ht);

   371     for (i = 0; i < nbuckets; i++) {

   372         hep = &ht->buckets[i];

   373         while ((he = *hep) != 0) {

   374             rv = (*f)(he, n, arg);

   375             n++;

   376             if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {

   377                 *hep = he->next;

   378                 if (rv & HT_ENUMERATE_REMOVE) {

   379                     he->next = todo;

   380                     todo = he;

   381                 }

   382             } else {

   383                 hep = &he->next;

   384             }

   385             if (rv & HT_ENUMERATE_STOP) {

   386                 goto out;

   387             }

   388         }

   389     }

   391 out:

   392     hep = &todo;

   393     while ((he = *hep) != 0) {

   394         PL_HashTableRawRemove(ht, hep, he);

   395     }

   396     return n;

   397 }

   399 #ifdef HASHMETER

   400 #include <math.h>

   401 #include <stdio.h>

   403 PR_IMPLEMENT(void)

   404 PL_HashTableDumpMeter(PLHashTable *ht, PLHashEnumerator dump, FILE *fp)

   405 {

   406     double mean, variance;

   407     PRUint32 nchains, nbuckets;

   408     PRUint32 i, n, maxChain, maxChainLen;

   409     PLHashEntry *he;

   411     variance = 0;

   412     nchains = 0;

   413     maxChainLen = 0;

   414     nbuckets = NBUCKETS(ht);

   415     for (i = 0; i < nbuckets; i++) {

   416         he = ht->buckets[i];

   417         if (!he)

   418             continue;

   419         nchains++;

   420         for (n = 0; he; he = he->next)

   421             n++;

   422         variance += n * n;

   423         if (n > maxChainLen) {

   424             maxChainLen = n;

   425             maxChain = i;

   426         }

   427     }

   428     mean = (double)ht->nentries / nchains;

   429     variance = fabs(variance / nchains - mean * mean);

   431     fprintf(fp, "\nHash table statistics:\n");

   432     fprintf(fp, "     number of lookups: %u\n", ht->nlookups);

   433     fprintf(fp, "     number of entries: %u\n", ht->nentries);

   434     fprintf(fp, "       number of grows: %u\n", ht->ngrows);

   435     fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);

   436     fprintf(fp, "   mean steps per hash: %g\n", (double)ht->nsteps

   437                                                 / ht->nlookups);

   438     fprintf(fp, "mean hash chain length: %g\n", mean);

   439     fprintf(fp, "    standard deviation: %g\n", sqrt(variance));

   440     fprintf(fp, " max hash chain length: %u\n", maxChainLen);

   441     fprintf(fp, "        max hash chain: [%u]\n", maxChain);

   443     for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)

   444         if ((*dump)(he, i, fp) != HT_ENUMERATE_NEXT)

   445             break;

   446 }

   447 #endif /* HASHMETER */

   449 PR_IMPLEMENT(int)

   450 PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp)

   451 {

   452     int count;

   454     count = PL_HashTableEnumerateEntries(ht, dump, fp);

   455 #ifdef HASHMETER

   456     PL_HashTableDumpMeter(ht, dump, fp);

   457 #endif

   458     return count;

   459 }

   461 PR_IMPLEMENT(PLHashNumber)

   462 PL_HashString(const void *key)

   463 {

   464     PLHashNumber h;

   465     const PRUint8 *s;

   467     h = 0;

   468     for (s = (const PRUint8*)key; *s; s++)

   469         h = PR_ROTATE_LEFT32(h, 4) ^ *s;

   470     return h;

   471 }

   473 PR_IMPLEMENT(int)

   474 PL_CompareStrings(const void *v1, const void *v2)

   475 {

   476     return strcmp((const char*)v1, (const char*)v2) == 0;

   477 }

   479 PR_IMPLEMENT(int)

   480 PL_CompareValues(const void *v1, const void *v2)

   481 {

   482     return v1 == v2;

   483 }

The Tor Browser / file revision

nsprpub/lib/ds/plhash.c@8bccb770b82d

nsprpub/lib/ds/plhash.c