home *** CD-ROM | disk | FTP | other *** search
/ Tools / WinSN5.0Ver.iso / NETSCAP.50 / WIN1998.ZIP / ns / nsprpub / lib / ds / plhash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1998-04-08  |  12.6 KB  |  478 lines
  1. /* -*- Mode: C++; tab-width: 4; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
  2. /*
  3.  * The contents of this file are subject to the Netscape Public License
  4.  * Version 1.0 (the "NPL"); you may not use this file except in
  5.  * compliance with the NPL.  You may obtain a copy of the NPL at
  6.  * http://www.mozilla.org/NPL/
  7.  * 
  8.  * Software distributed under the NPL is distributed on an "AS IS" basis,
  9.  * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the NPL
  10.  * for the specific language governing rights and limitations under the
  11.  * NPL.
  12.  * 
  13.  * The Initial Developer of this code under the NPL is Netscape
  14.  * Communications Corporation.  Portions created by Netscape are
  15.  * Copyright (C) 1998 Netscape Communications Corporation.  All Rights
  16.  * Reserved.
  17.  */
  18.  
  19. /*
  20.  * PL hash table package.
  21.  */
  22. #include "plhash.h"
  23. #include "prbit.h"
  24. #include "prlog.h"
  25. #include "prmem.h"
  26. #include "prtypes.h"
  27. #include <stdlib.h>
  28. #include <string.h>
  29.  
  30. /* Compute the number of buckets in ht */
  31. #define NBUCKETS(ht)    (1 << (PL_HASH_BITS - (ht)->shift))
  32.  
  33. /* The smallest table has 16 buckets */
  34. #define MINBUCKETSLOG2  4
  35. #define MINBUCKETS      (1 << MINBUCKETSLOG2)
  36.  
  37. /* Compute the maximum entries given n buckets that we will tolerate, ~90% */
  38. #define OVERLOADED(n)   ((n) - ((n) >> 3))
  39.  
  40. /* Compute the number of entries below which we shrink the table by half */
  41. #define UNDERLOADED(n)  (((n) > MINBUCKETS) ? ((n) >> 2) : 0)
  42.  
  43. /*
  44. ** Stubs for default hash allocator ops.
  45. */
  46. static void * PR_CALLBACK
  47. DefaultAllocTable(void *pool, PRSize size)
  48. {
  49. #if defined(XP_MAC)
  50. #pragma unused (pool)
  51. #endif
  52.  
  53.     return PR_MALLOC(size);
  54. }
  55.  
  56. static void PR_CALLBACK
  57. DefaultFreeTable(void *pool, void *item)
  58. {
  59. #if defined(XP_MAC)
  60. #pragma unused (pool)
  61. #endif
  62.  
  63.     PR_DELETE(item);
  64. }
  65.  
  66. static PLHashEntry * PR_CALLBACK
  67. DefaultAllocEntry(void *pool, const void *key)
  68. {
  69. #if defined(XP_MAC)
  70. #pragma unused (pool,key)
  71. #endif
  72.  
  73.     return PR_NEW(PLHashEntry);
  74. }
  75.  
  76. static void PR_CALLBACK
  77. DefaultFreeEntry(void *pool, PLHashEntry *he, PRUintn flag)
  78. {
  79. #if defined(XP_MAC)
  80. #pragma unused (pool)
  81. #endif
  82.  
  83.     if (flag == HT_FREE_ENTRY)
  84.         PR_DELETE(he);
  85. }
  86.  
  87. static PLHashAllocOps defaultHashAllocOps = {
  88.     DefaultAllocTable, DefaultFreeTable,
  89.     DefaultAllocEntry, DefaultFreeEntry
  90. };
  91.  
  92. PR_IMPLEMENT(PLHashTable *)
  93. PL_NewHashTable(PRUint32 n, PLHashFunction keyHash,
  94.                 PLHashComparator keyCompare, PLHashComparator valueCompare,
  95.                 PLHashAllocOps *allocOps, void *allocPriv)
  96. {
  97.     PLHashTable *ht;
  98.     PRUint32 nb;
  99.  
  100.     if (n <= MINBUCKETS) {
  101.         n = MINBUCKETSLOG2;
  102.     } else {
  103.         n = PR_CeilingLog2(n);
  104.         if ((PRInt32)n < 0)
  105.             return 0;
  106.     }
  107.  
  108.     if (!allocOps) allocOps = &defaultHashAllocOps;
  109.  
  110.     ht = (PLHashTable*)((*allocOps->allocTable)(allocPriv, sizeof *ht));
  111.     if (!ht)
  112.     return 0;
  113.     memset(ht, 0, sizeof *ht);
  114.     ht->shift = PL_HASH_BITS - n;
  115.     n = 1 << n;
  116. #if defined(XP_PC) && !defined(_WIN32)
  117.     if (n > 16000) {
  118.         (*allocOps->freeTable)(allocPriv, ht);
  119.         return 0;
  120.     }
  121. #endif  /* WIN16 */
  122.     nb = n * sizeof(PLHashEntry *);
  123.     ht->buckets = (PLHashEntry**)((*allocOps->allocTable)(allocPriv, nb));
  124.     if (!ht->buckets) {
  125.         (*allocOps->freeTable)(allocPriv, ht);
  126.         return 0;
  127.     }
  128.     memset(ht->buckets, 0, nb);
  129.  
  130.     ht->keyHash = keyHash;
  131.     ht->keyCompare = keyCompare;
  132.     ht->valueCompare = valueCompare;
  133.     ht->allocOps = allocOps;
  134.     ht->allocPriv = allocPriv;
  135.     return ht;
  136. }
  137.  
  138. PR_IMPLEMENT(void)
  139. PL_HashTableDestroy(PLHashTable *ht)
  140. {
  141.     PRUint32 i, n;
  142.     PLHashEntry *he, *next;
  143.     PLHashAllocOps *allocOps = ht->allocOps;
  144.     void *allocPriv = ht->allocPriv;
  145.  
  146.     n = NBUCKETS(ht);
  147.     for (i = 0; i < n; i++) {
  148.         for (he = ht->buckets[i]; he; he = next) {
  149.             next = he->next;
  150.             (*allocOps->freeEntry)(allocPriv, he, HT_FREE_ENTRY);
  151.         }
  152.     }
  153. #ifdef DEBUG
  154.     memset(ht->buckets, 0xDB, n * sizeof ht->buckets[0]);
  155. #endif
  156.     (*allocOps->freeTable)(allocPriv, ht->buckets);
  157. #ifdef DEBUG
  158.     memset(ht, 0xDB, sizeof *ht);
  159. #endif
  160.     (*allocOps->freeTable)(allocPriv, ht);
  161. }
  162.  
  163. /*
  164. ** Multiplicative hash, from Knuth 6.4.
  165. */
  166. #define GOLDEN_RATIO    0x9E3779B9U
  167.  
  168. PR_IMPLEMENT(PLHashEntry **)
  169. PL_HashTableRawLookup(PLHashTable *ht, PLHashNumber keyHash, const void *key)
  170. {
  171.     PLHashEntry *he, **hep, **hep0;
  172.     PLHashNumber h;
  173.  
  174. #ifdef HASHMETER
  175.     ht->nlookups++;
  176. #endif
  177.     h = keyHash * GOLDEN_RATIO;
  178.     h >>= ht->shift;
  179.     hep = hep0 = &ht->buckets[h];
  180.     while ((he = *hep) != 0) {
  181.         if (he->keyHash == keyHash && (*ht->keyCompare)(key, he->key)) {
  182.             /* Move to front of chain if not already there */
  183.             if (hep != hep0) {
  184.                 *hep = he->next;
  185.                 he->next = *hep0;
  186.                 *hep0 = he;
  187.             }
  188.             return hep0;
  189.         }
  190.         hep = &he->next;
  191. #ifdef HASHMETER
  192.         ht->nsteps++;
  193. #endif
  194.     }
  195.     return hep;
  196. }
  197.  
  198. PR_IMPLEMENT(PLHashEntry *)
  199. PL_HashTableRawAdd(PLHashTable *ht, PLHashEntry **hep,
  200.                    PLHashNumber keyHash, const void *key, void *value)
  201. {
  202.     PRUint32 i, n;
  203.     PLHashEntry *he, *next, **oldbuckets;
  204.     PRUint32 nb;
  205.  
  206.     /* Grow the table if it is overloaded */
  207.     n = NBUCKETS(ht);
  208.     if (ht->nentries >= OVERLOADED(n)) {
  209. #ifdef HASHMETER
  210.         ht->ngrows++;
  211. #endif
  212.         ht->shift--;
  213.         oldbuckets = ht->buckets;
  214. #if defined(XP_PC) && !defined(_WIN32)
  215.         if (2 * n > 16000)
  216.             return 0;
  217. #endif  /* WIN16 */
  218.         nb = 2 * n * sizeof(PLHashEntry *);
  219.         ht->buckets = (PLHashEntry**)
  220.             ((*ht->allocOps->allocTable)(ht->allocPriv, nb));
  221.         if (!ht->buckets) {
  222.             ht->buckets = oldbuckets;
  223.             return 0;
  224.         }
  225.         memset(ht->buckets, 0, nb);
  226.  
  227.         for (i = 0; i < n; i++) {
  228.             for (he = oldbuckets[i]; he; he = next) {
  229.                 next = he->next;
  230.                 hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);
  231.                 PR_ASSERT(*hep == 0);
  232.                 he->next = 0;
  233.                 *hep = he;
  234.             }
  235.         }
  236. #ifdef DEBUG
  237.         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
  238. #endif
  239.         (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
  240.         hep = PL_HashTableRawLookup(ht, keyHash, key);
  241.     }
  242.  
  243.     /* Make a new key value entry */
  244.     he = (*ht->allocOps->allocEntry)(ht->allocPriv, key);
  245.     if (!he)
  246.     return 0;
  247.     he->keyHash = keyHash;
  248.     he->key = key;
  249.     he->value = value;
  250.     he->next = *hep;
  251.     *hep = he;
  252.     ht->nentries++;
  253.     return he;
  254. }
  255.  
  256. PR_IMPLEMENT(PLHashEntry *)
  257. PL_HashTableAdd(PLHashTable *ht, const void *key, void *value)
  258. {
  259.     PLHashNumber keyHash;
  260.     PLHashEntry *he, **hep;
  261.  
  262.     keyHash = (*ht->keyHash)(key);
  263.     hep = PL_HashTableRawLookup(ht, keyHash, key);
  264.     if ((he = *hep) != 0) {
  265.         /* Hit; see if values match */
  266.         if ((*ht->valueCompare)(he->value, value)) {
  267.             /* key,value pair is already present in table */
  268.             return he;
  269.         }
  270.         if (he->value)
  271.             (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_VALUE);
  272.         he->value = value;
  273.         return he;
  274.     }
  275.     return PL_HashTableRawAdd(ht, hep, keyHash, key, value);
  276. }
  277.  
  278. PR_IMPLEMENT(void)
  279. PL_HashTableRawRemove(PLHashTable *ht, PLHashEntry **hep, PLHashEntry *he)
  280. {
  281.     PRUint32 i, n;
  282.     PLHashEntry *next, **oldbuckets;
  283.     PRUint32 nb;
  284.  
  285.     *hep = he->next;
  286.     (*ht->allocOps->freeEntry)(ht->allocPriv, he, HT_FREE_ENTRY);
  287.  
  288.     /* Shrink table if it's underloaded */
  289.     n = NBUCKETS(ht);
  290.     if (--ht->nentries < UNDERLOADED(n)) {
  291. #ifdef HASHMETER
  292.         ht->nshrinks++;
  293. #endif
  294.         ht->shift++;
  295.         oldbuckets = ht->buckets;
  296.         nb = n * sizeof(PLHashEntry*) / 2;
  297.         ht->buckets = (PLHashEntry**)(
  298.             (*ht->allocOps->allocTable)(ht->allocPriv, nb));
  299.         if (!ht->buckets) {
  300.             ht->buckets = oldbuckets;
  301.             return;
  302.         }
  303.         memset(ht->buckets, 0, nb);
  304.  
  305.         for (i = 0; i < n; i++) {
  306.             for (he = oldbuckets[i]; he; he = next) {
  307.                 next = he->next;
  308.                 hep = PL_HashTableRawLookup(ht, he->keyHash, he->key);
  309.                 PR_ASSERT(*hep == 0);
  310.                 he->next = 0;
  311.                 *hep = he;
  312.             }
  313.         }
  314. #ifdef DEBUG
  315.         memset(oldbuckets, 0xDB, n * sizeof oldbuckets[0]);
  316. #endif
  317.         (*ht->allocOps->freeTable)(ht->allocPriv, oldbuckets);
  318.     }
  319. }
  320.  
  321. PR_IMPLEMENT(PRBool)
  322. PL_HashTableRemove(PLHashTable *ht, const void *key)
  323. {
  324.     PLHashNumber keyHash;
  325.     PLHashEntry *he, **hep;
  326.  
  327.     keyHash = (*ht->keyHash)(key);
  328.     hep = PL_HashTableRawLookup(ht, keyHash, key);
  329.     if ((he = *hep) == 0)
  330.         return PR_FALSE;
  331.  
  332.     /* Hit; remove element */
  333.     PL_HashTableRawRemove(ht, hep, he);
  334.     return PR_TRUE;
  335. }
  336.  
  337. PR_IMPLEMENT(void *)
  338. PL_HashTableLookup(PLHashTable *ht, const void *key)
  339. {
  340.     PLHashNumber keyHash;
  341.     PLHashEntry *he, **hep;
  342.  
  343.     keyHash = (*ht->keyHash)(key);
  344.     hep = PL_HashTableRawLookup(ht, keyHash, key);
  345.     if ((he = *hep) != 0) {
  346.         return he->value;
  347.     }
  348.     return 0;
  349. }
  350.  
  351. /*
  352. ** Iterate over the entries in the hash table calling func for each
  353. ** entry found. Stop if "f" says to (return value & PR_ENUMERATE_STOP).
  354. ** Return a count of the number of elements scanned.
  355. */
  356. PR_IMPLEMENT(int)
  357. PL_HashTableEnumerateEntries(PLHashTable *ht, PLHashEnumerator f, void *arg)
  358. {
  359.     PLHashEntry *he, **hep;
  360.     PRUint32 i, nbuckets;
  361.     int rv, n = 0;
  362.     PLHashEntry *todo = 0;
  363.  
  364.     nbuckets = NBUCKETS(ht);
  365.     for (i = 0; i < nbuckets; i++) {
  366.         hep = &ht->buckets[i];
  367.         while ((he = *hep) != 0) {
  368.             rv = (*f)(he, n, arg);
  369.             n++;
  370.             if (rv & (HT_ENUMERATE_REMOVE | HT_ENUMERATE_UNHASH)) {
  371.                 *hep = he->next;
  372.                 if (rv & HT_ENUMERATE_REMOVE) {
  373.                     he->next = todo;
  374.                     todo = he;
  375.                 }
  376.             } else {
  377.                 hep = &he->next;
  378.             }
  379.             if (rv & HT_ENUMERATE_STOP) {
  380.                 goto out;
  381.             }
  382.         }
  383.     }
  384.  
  385. out:
  386.     hep = &todo;
  387.     while ((he = *hep) != 0) {
  388.         PL_HashTableRawRemove(ht, hep, he);
  389.     }
  390.     return n;
  391. }
  392.  
  393. #ifdef HASHMETER
  394. #include <math.h>
  395. #include <stdio.h>
  396.  
  397. PR_IMPLEMENT(void)
  398. PL_HashTableDumpMeter(PLHashTable *ht, PLHashEnumerator dump, FILE *fp)
  399. {
  400.     double mean, variance;
  401.     PRUint32 nchains, nbuckets;
  402.     PRUint32 i, n, maxChain, maxChainLen;
  403.     PLHashEntry *he;
  404.  
  405.     variance = 0;
  406.     nchains = 0;
  407.     maxChainLen = 0;
  408.     nbuckets = NBUCKETS(ht);
  409.     for (i = 0; i < nbuckets; i++) {
  410.         he = ht->buckets[i];
  411.         if (!he)
  412.             continue;
  413.         nchains++;
  414.         for (n = 0; he; he = he->next)
  415.             n++;
  416.         variance += n * n;
  417.         if (n > maxChainLen) {
  418.             maxChainLen = n;
  419.             maxChain = i;
  420.         }
  421.     }
  422.     mean = (double)ht->nentries / nchains;
  423.     variance = fabs(variance / nchains - mean * mean);
  424.  
  425.     fprintf(fp, "\nHash table statistics:\n");
  426.     fprintf(fp, "     number of lookups: %u\n", ht->nlookups);
  427.     fprintf(fp, "     number of entries: %u\n", ht->nentries);
  428.     fprintf(fp, "       number of grows: %u\n", ht->ngrows);
  429.     fprintf(fp, "     number of shrinks: %u\n", ht->nshrinks);
  430.     fprintf(fp, "   mean steps per hash: %g\n", (double)ht->nsteps
  431.                                                 / ht->nlookups);
  432.     fprintf(fp, "mean hash chain length: %g\n", mean);
  433.     fprintf(fp, "    standard deviation: %g\n", sqrt(variance));
  434.     fprintf(fp, " max hash chain length: %u\n", maxChainLen);
  435.     fprintf(fp, "        max hash chain: [%u]\n", maxChain);
  436.  
  437.     for (he = ht->buckets[maxChain], i = 0; he; he = he->next, i++)
  438.         if ((*dump)(he, i, fp) != HT_ENUMERATE_NEXT)
  439.             break;
  440. }
  441. #endif /* HASHMETER */
  442.  
  443. PR_IMPLEMENT(int)
  444. PL_HashTableDump(PLHashTable *ht, PLHashEnumerator dump, FILE *fp)
  445. {
  446.     int count;
  447.  
  448.     count = PL_HashTableEnumerateEntries(ht, dump, fp);
  449. #ifdef HASHMETER
  450.     PL_HashTableDumpMeter(ht, dump, fp);
  451. #endif
  452.     return count;
  453. }
  454.  
  455. PR_IMPLEMENT(PLHashNumber)
  456. PL_HashString(const void *key)
  457. {
  458.     PLHashNumber h;
  459.     const PRUint8 *s;
  460.  
  461.     h = 0;
  462.     for (s = (const PRUint8*)key; *s; s++)
  463.         h = (h >> 28) ^ (h << 4) ^ *s;
  464.     return h;
  465. }
  466.  
  467. PR_IMPLEMENT(int)
  468. PL_CompareStrings(const void *v1, const void *v2)
  469. {
  470.     return strcmp((const char*)v1, (const char*)v2) == 0;
  471. }
  472.  
  473. PR_IMPLEMENT(int)
  474. PL_CompareValues(const void *v1, const void *v2)
  475. {
  476.     return v1 == v2;
  477. }
  478.