OSX/libsecurity_smime/lib/plhash.c

   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(Boolean)
 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 }