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