source: branches/1.7/src/objects/RpHash.c @ 6708

Last change on this file since 6708 was 5679, checked in by ldelgass, 9 years ago

Full merge 1.3 branch to uq branch to sync. Fixed partial subdirectory merge
by removing mergeinfo from lang/python/Rappture directory.

  • Property svn:eol-style set to native
File size: 39.2 KB
Line 
1
2/*
3 * bltHash.c --
4 *
5 *
6 * This module implements an in-memory hash table for the BLT
7 * toolkit.  Built upon the Tcl hash table, it adds pool
8 * allocation 64-bit address handling, improved array hash
9 * function.
10 *
11 * Copyright 2001 Silicon Metrics Corporation.
12 *
13 * Permission to use, copy, modify, and distribute this software and
14 * its documentation for any purpose and without fee is hereby
15 * granted, provided that the above copyright notice appear in all
16 * copies and that both that the copyright notice and warranty
17 * disclaimer appear in supporting documentation, and that the names
18 * of Lucent Technologies any of their entities not be used in
19 * advertising or publicity pertaining to distribution of the software
20 * without specific, written prior permission.
21 *
22 * Silicon Metrics disclaims all warranties with regard to this
23 * software, including all implied warranties of merchantability and
24 * fitness.  In no event shall Lucent Technologies be liable for any
25 * special, indirect or consequential damages or any damages
26 * whatsoever resulting from loss of use, data or profits, whether in
27 * an action of contract, negligence or other tortuous action, arising
28 * out of or in connection with the use or performance of this
29 * software.
30 *
31 * Bob Jenkins, 1996.  hash.c.  Public Domain.
32 * Bob Jenkins, 1997.  lookup8.c.  Public Domain.
33 *
34 * Copyright (c) 1991-1993 The Regents of the University of California.
35 * Copyright (c) 1994 Sun Microsystems, Inc.
36 *
37 * See the file "license.terms" for information on usage and redistribution
38 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
39 *
40 * RCS: @(#) $Id: bltHash.c,v 1.10 2002/08/09 07:15:18 ghowlett Exp $
41 */
42
43#include <RpInt.h>
44
45#include <stdio.h>
46#include <string.h>
47/* The following header is required for LP64 compilation */
48#include <stdlib.h>
49
50#include "RpHash.h"
51
52/*
53 * When there are this many entries per bucket, on average, rebuild
54 * the hash table to make it larger.
55 */
56
57#define REBUILD_MULTIPLIER  3
58
59#if (SIZEOF_VOID_P == 8)
60#define RANDOM_INDEX        HashOneWord
61#define DOWNSHIFT_START     62
62#else
63
64/*
65 * The following macro takes a preliminary integer hash value and
66 * produces an index into a hash tables bucket list.  The idea is
67 * to make it so that preliminary values that are arbitrarily similar
68 * will end up in different buckets.  The hash function was taken
69 * from a random-number generator.
70 */
71#define RANDOM_INDEX(tablePtr, i) \
72    (((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask)
73#define DOWNSHIFT_START     28
74#endif
75
76/*
77 * Procedure prototypes for static procedures in this file:
78 */
79static Rp_Hash HashArray _ANSI_ARGS_((CONST void *key, size_t length));
80static Rp_HashEntry *ArrayFind _ANSI_ARGS_((Rp_HashTable *tablePtr,
81    CONST void *key));
82static Rp_HashEntry *ArrayCreate _ANSI_ARGS_((Rp_HashTable *tablePtr,
83    CONST void *key, int *newPtr));
84static Rp_HashEntry *BogusFind _ANSI_ARGS_((Rp_HashTable *tablePtr,
85    CONST void *key));
86static Rp_HashEntry *BogusCreate _ANSI_ARGS_((Rp_HashTable *tablePtr,
87    CONST void *key, int *newPtr));
88static Rp_Hash HashString _ANSI_ARGS_((CONST char *string));
89static void RebuildTable _ANSI_ARGS_((Rp_HashTable *tablePtr));
90static Rp_HashEntry *StringFind _ANSI_ARGS_((Rp_HashTable *tablePtr,
91    CONST void *key));
92static Rp_HashEntry *StringCreate _ANSI_ARGS_((Rp_HashTable *tablePtr,
93    CONST void *key, int *newPtr));
94static Rp_HashEntry *OneWordFind _ANSI_ARGS_((Rp_HashTable *tablePtr,
95    CONST void *key));
96static Rp_HashEntry *OneWordCreate _ANSI_ARGS_((Rp_HashTable *tablePtr,
97    CONST void *key, int *newPtr));
98
99#if (SIZEOF_VOID_P == 8)
100static Rp_Hash HashOneWord _ANSI_ARGS_((Rp_HashTable *tablePtr,
101    CONST void *key));
102
103#endif /* SIZEOF_VOID_P == 8 */
104
105/*
106 *----------------------------------------------------------------------
107 *
108 * HashString --
109 *
110 *  Compute a one-word summary of a text string, which can be
111 *  used to generate a hash index.
112 *
113 * Results:
114 *  The return value is a one-word summary of the information in
115 *  string.
116 *
117 * Side effects:
118 *  None.
119 *
120 *----------------------------------------------------------------------
121 */
122static Rp_Hash
123HashString(register CONST char *string) /* String from which to
124                                         * compute hash value. */
125{
126    register Rp_Hash result;
127    register Rp_Hash c;
128
129    /*
130     * I tried a zillion different hash functions and asked many other
131     * people for advice.  Many people had their own favorite functions,
132     * all different, but no-one had much idea why they were good ones.
133     * I chose the one below (multiply by 9 and add new character)
134     * because of the following reasons:
135     *
136     * 1. Multiplying by 10 is perfect for keys that are decimal strings,
137     *    and multiplying by 9 is just about as good.
138     * 2. Times-9 is (shift-left-3) plus (old).  This means that each
139     *    character's bits hang around in the low-order bits of the
140     *    hash value for ever, plus they spread fairly rapidly up to
141     *    the high-order bits to fill out the hash value.  This seems
142     *    to work well both for decimal and non-decimal strings.
143     */
144
145    result = 0;
146    while ((c = *string++) != 0) {
147        result += (result << 3) + c;
148    }
149    return (Rp_Hash)result;
150}
151
152/*
153 *----------------------------------------------------------------------
154 *
155 * StringFind --
156 *
157 *      Given a hash table with string keys, and a string key, find
158 *      the entry with a matching key.
159 *
160 * Results:
161 *      The return value is a token for the matching entry in the
162 *      hash table, or NULL if there was no matching entry.
163 *
164 * Side effects:
165 *      None.
166 *
167 *----------------------------------------------------------------------
168 */
169static Rp_HashEntry *
170StringFind(
171    Rp_HashTable *tablePtr, /* Table in which to lookup entry. */
172    CONST void *key)        /* Key to use to find matching entry. */
173{
174    Rp_Hash hval;
175    register Rp_HashEntry *hPtr;
176    size_t hindex;
177
178    hval = HashString((char *)key);
179    hindex = hval & tablePtr->mask;
180
181    /*
182     * Search all of the entries in the appropriate bucket.
183     */
184
185    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
186        hPtr = hPtr->nextPtr) {
187        if (hPtr->hval == hval) {
188            register CONST char *p1, *p2;
189
190            for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) {
191                if (*p1 != *p2) {
192                    break;
193                }
194                if (*p1 == '\0') {
195                    return hPtr;
196                }
197            }
198        }
199    }
200    return NULL;
201}
202
203/*
204 *----------------------------------------------------------------------
205 *
206 * StringCreate --
207 *
208 *  Given a hash table with string keys, and a string key, find
209 *  the entry with a matching key.  If there is no matching entry,
210 *  then create a new entry that does match.
211 *
212 * Results:
213 *  The return value is a pointer to the matching entry.  If this
214 *  is a newly-created entry, then *newPtr will be set to a non-zero
215 *  value;  otherwise *newPtr will be set to 0.  If this is a new
216 *  entry the value stored in the entry will initially be 0.
217 *
218 * Side effects:
219 *  A new entry may be added to the hash table.
220 *
221 *----------------------------------------------------------------------
222 */
223static Rp_HashEntry *
224StringCreate(
225    Rp_HashTable *tablePtr, /* Table in which to lookup entry. */
226    CONST void *key,        /* Key to use to find or create matching
227                             * entry. */
228    int *newPtr)            /* Store info here telling whether a new
229                             * entry was created. */
230{
231    Rp_Hash hval;
232    Rp_HashEntry **bucketPtr;
233    register Rp_HashEntry *hPtr;
234    size_t size, hindex;
235
236    hval = HashString(key);
237    hindex = hval & tablePtr->mask;
238
239    /*
240     * Search all of the entries in this bucket.
241     */
242
243    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
244        hPtr = hPtr->nextPtr) {
245        if (hPtr->hval == hval) {
246            register CONST char *p1, *p2;
247
248            for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) {
249                if (*p1 != *p2) {
250                    break;
251                }
252                if (*p1 == '\0') {
253                    *newPtr = FALSE;
254                    return hPtr;
255                }
256            }
257        }
258    }
259
260    /*
261     * Entry not found.  Add a new one to the bucket.
262     */
263
264    *newPtr = TRUE;
265    size = sizeof(Rp_HashEntry) + strlen(key) - sizeof(Rp_HashKey) + 1;
266    if (tablePtr->hPool != NULL) {
267        hPtr = Rp_PoolAllocItem(tablePtr->hPool, size);
268    } else {
269        hPtr = Rp_Malloc(size);
270    }
271    bucketPtr = tablePtr->buckets + hindex;
272    hPtr->nextPtr = *bucketPtr;
273    hPtr->hval = hval;
274    hPtr->clientData = 0;
275    strcpy(hPtr->key.string, key);
276    *bucketPtr = hPtr;
277    tablePtr->numEntries++;
278
279    /*
280     * If the table has exceeded a decent size, rebuild it with many
281     * more buckets.
282     */
283
284    if (tablePtr->numEntries >= tablePtr->rebuildSize) {
285        RebuildTable(tablePtr);
286    }
287    return hPtr;
288}
289
290#if (SIZEOF_VOID_P == 8)
291/*
292 *----------------------------------------------------------------------
293 *
294 * HashOneWord --
295 *
296 *  Compute a one-word hash value of a 64-bit word, which then can
297 *  be used to generate a hash index.
298 *
299 *  From Knuth, it's a multiplicative hash.  Multiplies an unsigned
300 *  64-bit value with the golden ratio (sqrt(5) - 1) / 2.  The
301 *  downshift value is 64 - n, when n is the log2 of the size of
302 *  the hash table.
303 *
304 * Results:
305 *  The return value is a one-word summary of the information in
306 *  64 bit word.
307 *
308 * Side effects:
309 *  None.
310 *
311 *----------------------------------------------------------------------
312 */
313static Rp_Hash
314HashOneWord(
315    Rp_HashTable *tablePtr,
316    CONST void *key)
317{
318    uint64_t a0, a1;
319    uint64_t y0, y1;
320    uint64_t y2, y3;
321    uint64_t p1, p2;
322    uint64_t result;
323    /* Compute key * GOLDEN_RATIO in 128-bit arithmetic */
324    a0 = (uint64_t)key & 0x00000000FFFFFFFF;
325    a1 = (uint64_t)key >> 32;
326
327    y0 = a0 * 0x000000007f4a7c13;
328    y1 = a0 * 0x000000009e3779b9;
329    y2 = a1 * 0x000000007f4a7c13;
330    y3 = a1 * 0x000000009e3779b9;
331    y1 += y0 >> 32;     /* Can't carry */
332    y1 += y2;           /* Might carry */
333    if (y1 < y2) {
334        y3 += (1LL << 32);  /* Propagate */
335    }
336
337    /* 128-bit product: p1 = loword, p2 = hiword */
338    p1 = ((y1 & 0x00000000FFFFFFFF) << 32) + (y0 & 0x00000000FFFFFFFF);
339    p2 = y3 + (y1 >> 32);
340
341    /* Left shift the value downward by the size of the table */
342    if (tablePtr->downShift > 0) {
343        if (tablePtr->downShift < 64) {
344            result = ((p2 << (64 - tablePtr->downShift)) |
345                      (p1 >> (tablePtr->downShift & 63)));
346        } else {
347            result = p2 >> (tablePtr->downShift & 63);
348        }
349    } else {
350        result = p1;
351    }
352    /* Finally mask off the high bits */
353    return (Rp_Hash)(result & tablePtr->mask);
354}
355
356#endif /* SIZEOF_VOID_P == 8 */
357
358/*
359 *----------------------------------------------------------------------
360 *
361 * OneWordFind --
362 *
363 *  Given a hash table with one-word keys, and a one-word key,
364 *  find the entry with a matching key.
365 *
366 * Results:
367 *  The return value is a token for the matching entry in the
368 *  hash table, or NULL if there was no matching entry.
369 *
370 * Side effects:
371 *  None.
372 *
373 *----------------------------------------------------------------------
374 */
375static Rp_HashEntry *
376OneWordFind(
377    Rp_HashTable *tablePtr,     /* Table in which to lookup entry. */
378    register CONST void *key)   /* Key to use to find matching entry. */
379{
380    register Rp_HashEntry *hPtr;
381    size_t hindex;
382
383    hindex = RANDOM_INDEX(tablePtr, key);
384
385    /*
386     * Search all of the entries in the appropriate bucket.
387     */
388    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
389        hPtr = hPtr->nextPtr) {
390        if (hPtr->key.oneWordValue == key) {
391            return hPtr;
392        }
393    }
394    return NULL;
395}
396
397/*
398 *----------------------------------------------------------------------
399 *
400 * OneWordCreate --
401 *
402 *  Given a hash table with one-word keys, and a one-word key, find
403 *  the entry with a matching key.  If there is no matching entry,
404 *  then create a new entry that does match.
405 *
406 * Results:
407 *  The return value is a pointer to the matching entry.  If this
408 *  is a newly-created entry, then *newPtr will be set to a non-zero
409 *  value;  otherwise *newPtr will be set to 0.  If this is a new
410 *  entry the value stored in the entry will initially be 0.
411 *
412 * Side effects:
413 *  A new entry may be added to the hash table.
414 *
415 *----------------------------------------------------------------------
416 */
417static Rp_HashEntry *
418OneWordCreate(
419    Rp_HashTable *tablePtr, /* Table in which to lookup entry. */
420    CONST void *key,        /* Key to use to find or create matching
421                             * entry. */
422    int *newPtr)            /* Store info here telling whether a new
423                             * entry was created. */
424{
425    Rp_HashEntry **bucketPtr;
426    register Rp_HashEntry *hPtr;
427    size_t hindex;
428
429    hindex = RANDOM_INDEX(tablePtr, key);
430
431    /*
432     * Search all of the entries in this bucket.
433     */
434    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
435        hPtr = hPtr->nextPtr) {
436        if (hPtr->key.oneWordValue == key) {
437            *newPtr = FALSE;
438            return hPtr;
439        }
440    }
441
442    /*
443     * Entry not found.  Add a new one to the bucket.
444     */
445
446    *newPtr = TRUE;
447    if (tablePtr->hPool != NULL) {
448        hPtr = Rp_PoolAllocItem(tablePtr->hPool, sizeof(Rp_HashEntry));
449    } else {
450        hPtr = Rp_Malloc(sizeof(Rp_HashEntry));
451    }
452    bucketPtr = tablePtr->buckets + hindex;
453    hPtr->nextPtr = *bucketPtr;
454    hPtr->hval = (Rp_Hash)key;
455    hPtr->clientData = 0;
456    hPtr->key.oneWordValue = (void *)key;   /* CONST XXXX */
457    *bucketPtr = hPtr;
458    tablePtr->numEntries++;
459
460    /*
461     * If the table has exceeded a decent size, rebuild it with many
462     * more buckets.
463     */
464
465    if (tablePtr->numEntries >= tablePtr->rebuildSize) {
466        RebuildTable(tablePtr);
467    }
468    return hPtr;
469}
470
471
472#if (SIZEOF_VOID_P == 4)
473/*
474 * --------------------------------------------------------------------
475 *
476 * MIX32 --
477 *
478 *      Bob Jenkins, 1996.  Public Domain.
479 *
480 *  Mix 3 32/64-bit values reversibly.  For every delta with one or
481 *  two bit set, and the deltas of all three high bits or all
482 *  three low bits, whether the original value of a,b,c is almost
483 *  all zero or is uniformly distributed, If mix() is run
484 *  forward or backward, at least 32 bits in a,b,c have at least
485 *  1/4 probability of changing.  * If mix() is run forward, every
486 *  bit of c will change between 1/3 and 2/3 of the time.  (Well,
487 *  22/100 and 78/100 for some 2-bit deltas.)  mix() was built out
488 *  of 36 single-cycle latency instructions in a structure that
489 *  could supported 2x parallelism, like so:
490 *
491 *      a -= b;
492 *      a -= c; x = (c>>13);
493 *      b -= c; a ^= x;
494 *      b -= a; x = (a<<8);
495 *      c -= a; b ^= x;
496 *      c -= b; x = (b>>13);
497 *      ...
498 *
499 *   Unfortunately, superscalar Pentiums and Sparcs can't take
500 *   advantage of that parallelism.  They've also turned some of
501 *   those single-cycle latency instructions into multi-cycle
502 *   latency instructions.  Still, this is the fastest good hash I
503 *   could find.  There were about 2^^68 to choose from.  I only
504 *   looked at a billion or so.
505 *
506 * --------------------------------------------------------------------
507 */
508#define MIX32(a,b,c) \
509        a -= b, a -= c, a ^= (c >> 13), \
510        b -= c, b -= a, b ^= (a <<  8), \
511        c -= a, c -= b, c ^= (b >> 13), \
512        a -= b, a -= c, a ^= (c >> 12), \
513        b -= c, b -= a, b ^= (a << 16), \
514        c -= a, c -= b, c ^= (b >>  5), \
515        a -= b, a -= c, a ^= (c >>  3), \
516        b -= c, b -= a, b ^= (a << 10), \
517        c -= a, c -= b, c ^= (b >> 15)
518
519#define GOLDEN_RATIO32  0x9e3779b9      /* An arbitrary value */
520
521/*
522 * --------------------------------------------------------------------
523 *
524 * HashArray --
525 *
526 *      Bob Jenkins, 1996.  Public Domain.
527 *
528 *  This works on all machines.  Length has to be measured in
529 *  unsigned longs instead of bytes.  It requires that
530 *
531 *    o The key be an array of unsigned ints.
532 *    o All your machines have the same endianness
533 *    o The length be the number of unsigned ints in the key.
534 *
535 * --------------------------------------------------------------------
536 */
537static Rp_Hash
538HashArray(
539    CONST void *key,
540    size_t length)      /* Length of the key in 32-bit words */
541{
542    register uint32_t a, b, c, len;
543    register uint32_t *arrayPtr = (uint32_t *)key;
544    /* Set up the internal state */
545    len = length;
546    a = b = GOLDEN_RATIO32; /* An arbitrary value */
547    c = 0;                  /* Previous hash value */
548
549    while (len >= 3) {      /* Handle most of the key */
550        a += arrayPtr[0];
551        b += arrayPtr[1];
552        c += arrayPtr[2];
553        MIX32(a, b, c);
554        arrayPtr += 3; len -= 3;
555    }
556    c += length;
557    /* And now the last 2 words */
558    /* Note that all the case statements fall through */
559    switch(len) {
560        /* c is reserved for the length */
561    case 2 : b += arrayPtr[1];
562    case 1 : a += arrayPtr[0];
563        /* case 0: nothing left to add */
564    }
565    MIX32(a, b, c);
566    return (Rp_Hash)c;
567}
568#endif /* SIZEOF_VOID_P == 4 */
569
570#if (SIZEOF_VOID_P == 8)
571
572/*
573 * --------------------------------------------------------------------
574 *
575 * MIX64 --
576 *
577 *  Bob Jenkins, January 4 1997, Public Domain.  You can use
578 *  this free for any purpose.  It has no warranty.
579 *
580 *  Returns a 64-bit value.  Every bit of the key affects every
581 *  bit of the return value.  No funnels.  Every 1-bit and 2-bit
582 *  delta achieves avalanche.  About 41+5len instructions.
583 *
584 *  The best hash table sizes are powers of 2.  There is no need
585 *  to do mod a prime (mod is sooo slow!).  If you need less than
586 *  64 bits, use a bitmask.  For example, if you need only 10
587 *  bits, do h = (h & hashmask(10)); In which case, the hash table
588 *  should have hashsize(10) elements.
589 *
590 *  By Bob Jenkins, Jan 4 1997.  bob_jenkins@burtleburtle.net.
591 *  You may use this code any way you wish, private, educational,
592 *  or commercial, as long as this whole comment accompanies it.
593 *
594 *  See http://burtleburtle.net/bob/hash/evahash.html
595 *  Use for hash table lookup, or anything where one collision in
596 *  2^^64 * is acceptable.  Do NOT use for cryptographic purposes.
597 *
598 * --------------------------------------------------------------------
599 */
600
601#define MIX64(a,b,c) \
602        a -= b, a -= c, a ^= (c >> 43), \
603        b -= c, b -= a, b ^= (a <<  9), \
604        c -= a, c -= b, c ^= (b >>  8), \
605        a -= b, a -= c, a ^= (c >> 38), \
606        b -= c, b -= a, b ^= (a << 23), \
607        c -= a, c -= b, c ^= (b >>  5), \
608        a -= b, a -= c, a ^= (c >> 35), \
609        b -= c, b -= a, b ^= (a << 49), \
610        c -= a, c -= b, c ^= (b >> 11), \
611        a -= b, a -= c, a ^= (c >> 12), \
612        b -= c, b -= a, b ^= (a << 18), \
613        c -= a, c -= b, c ^= (b >> 22)
614
615#define GOLDEN_RATIO64  0x9e3779b97f4a7c13LL
616
617/*
618 * --------------------------------------------------------------------
619 *
620 * HashArray --
621 *
622 *  Bob Jenkins, January 4 1997, Public Domain.  You can use
623 *  this free for any purpose.  It has no warranty.
624 *
625 *  This works on all machines.  The length has to be measured in
626 *  64 bit words, instead of bytes.  It requires that
627 *
628 *    o The key be an array of 64 bit words (unsigned longs).
629 *    o All your machines have the same endianness.
630 *    o The length be the number of 64 bit words in the key.
631 *
632 * --------------------------------------------------------------------
633 */
634static Rp_Hash
635HashArray(
636    CONST void *key,
637    size_t length)      /* Length of key in 32-bit words. */
638{
639    register uint64_t a, b, c, len;
640    register uint32_t *iPtr = (uint32_t *)key;
641
642#ifdef WORDS_BIGENDIAN
643#define PACK(a,b)   ((uint64_t)(b) | ((uint64_t)(a) << 32))
644#else
645#define PACK(a,b)   ((uint64_t)(a) | ((uint64_t)(b) << 32))
646#endif
647    /* Set up the internal state */
648    len = length;           /* Length is the number of 64-bit words. */
649    a = b = GOLDEN_RATIO64; /* An arbitrary value */
650    c = 0;                  /* Previous hash value */
651
652    while (len >= 6) {      /* Handle most of the key */
653        a += PACK(iPtr[0], iPtr[1]);
654        b += PACK(iPtr[2], iPtr[3]);
655        c += PACK(iPtr[4], iPtr[5]);
656        MIX64(a,b,c);
657        iPtr += 6; len -= 6;
658    }
659    c += length;
660    /* And now the last 2 words */
661    /* Note that all the case statements fall through */
662    switch(len) {
663        /* c is reserved for the length */
664    case 5 :
665    case 4 :
666        a += PACK(iPtr[0], iPtr[1]);
667        b += PACK(iPtr[2], iPtr[3]);
668        iPtr += 4; len -= 4;
669        break;
670    case 3 :
671    case 2 :
672        a += PACK(iPtr[0], iPtr[1]);
673        iPtr += 2; len -= 2;
674 /* case 0: nothing left to add */
675    }
676    if (len > 0) {
677        b += iPtr[0];
678    }
679    MIX64(a,b,c);
680    return (Rp_Hash)c;
681}
682#endif /* SIZEOF_VOID_P == 8 */
683
684/*
685 *----------------------------------------------------------------------
686 *
687 * ArrayFind --
688 *
689 *  Given a hash table with array-of-int keys, and a key, find
690 *  the entry with a matching key.
691 *
692 * Results:
693 *  The return value is a token for the matching entry in the
694 *  hash table, or NULL if there was no matching entry.
695 *
696 * Side effects:
697 *  None.
698 *
699 *----------------------------------------------------------------------
700 */
701static Rp_HashEntry *
702ArrayFind(
703    Rp_HashTable *tablePtr, /* Table in which to lookup entry. */
704    CONST void *key)        /* Key to use to find matching entry. */
705{
706    Rp_Hash hval;
707    register Rp_HashEntry *hPtr;
708    size_t hindex;
709
710    hval = HashArray(key, tablePtr->keyType);
711    hindex = hval & tablePtr->mask;
712    /*
713     * Search all of the entries in the appropriate bucket.
714     */
715
716    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
717        hPtr = hPtr->nextPtr) {
718        if (hPtr->hval == hval) {
719            register unsigned int *iPtr1, *iPtr2;
720            unsigned int count;
721
722            for (iPtr1 = (uint32_t *)key, iPtr2 = (uint32_t *)hPtr->key.words,
723                 count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
724                if (count == 0) {
725                    return hPtr;
726                }
727                if (*iPtr1 != *iPtr2) {
728                    break;
729                }
730            }
731        }
732    }
733    return NULL;
734}
735
736/*
737 *----------------------------------------------------------------------
738 *
739 * ArrayCreate --
740 *
741 *  Given a hash table with one-word keys, and a one-word key, find
742 *  the entry with a matching key.  If there is no matching entry,
743 *  then create a new entry that does match.
744 *
745 * Results:
746 *  The return value is a pointer to the matching entry.  If this
747 *  is a newly-created entry, then *newPtr will be set to a non-zero
748 *  value;  otherwise *newPtr will be set to 0.  If this is a new
749 *  entry the value stored in the entry will initially be 0.
750 *
751 * Side effects:
752 *  A new entry may be added to the hash table.
753 *
754 *----------------------------------------------------------------------
755 */
756static Rp_HashEntry *
757ArrayCreate(
758    Rp_HashTable *tablePtr,     /* Table in which to lookup entry. */
759    register CONST void *key,   /* Key to use to find or create matching
760                                 * entry. */
761    int *newPtr)                /* Store info here telling whether a new
762                                 * entry was created. */
763{
764    Rp_Hash hval;
765    Rp_HashEntry **bucketPtr;
766    int count;
767    register Rp_HashEntry *hPtr;
768    register uint32_t *iPtr1, *iPtr2;
769    size_t size, hindex;
770
771    hval = HashArray(key, tablePtr->keyType);
772    hindex = hval & tablePtr->mask;
773
774    /*
775     * Search all of the entries in the appropriate bucket.
776     */
777    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
778        hPtr = hPtr->nextPtr) {
779        if (hPtr->hval == hval) {
780            for (iPtr1 = (uint32_t *)key, iPtr2 = (uint32_t *)hPtr->key.words,
781                 count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
782                if (count == 0) {
783                    *newPtr = FALSE;
784                    return hPtr;
785                }
786                if (*iPtr1 != *iPtr2) {
787                    break;
788                }
789            }
790        }
791    }
792
793    /*
794     * Entry not found.  Add a new one to the bucket.
795     */
796    *newPtr = TRUE;
797    /* We assume here that the size of the key is at least 2 words */
798    size = sizeof(Rp_HashEntry) + tablePtr->keyType * sizeof(uint32_t) -
799        sizeof(Rp_HashKey);
800    if (tablePtr->hPool != NULL) {
801        hPtr = Rp_PoolAllocItem(tablePtr->hPool, size);
802    } else {
803        hPtr = Rp_Malloc(size);
804    }
805    bucketPtr = tablePtr->buckets + hindex;
806    hPtr->nextPtr = *bucketPtr;
807    hPtr->hval = hval;
808    hPtr->clientData = 0;
809    count = tablePtr->keyType;
810    for (iPtr1 = (uint32_t *)key, iPtr2 = (uint32_t *)hPtr->key.words;
811         count > 0; count--, iPtr1++, iPtr2++) {
812        *iPtr2 = *iPtr1;
813    }
814    *bucketPtr = hPtr;
815    tablePtr->numEntries++;
816
817    /*
818     * If the table has exceeded a decent size, rebuild it with many
819     * more buckets.
820     */
821    if (tablePtr->numEntries >= tablePtr->rebuildSize) {
822        RebuildTable(tablePtr);
823    }
824    return hPtr;
825}
826
827/*
828 *----------------------------------------------------------------------
829 *
830 * BogusFind --
831 *
832 *  This procedure is invoked when an Rp_FindHashEntry is called
833 *  on a table that has been deleted.
834 *
835 * Results:
836 *  If panic returns (which it shouldn't) this procedure returns
837 *  NULL.
838 *
839 * Side effects:
840 *  Generates a panic.
841 *
842 *----------------------------------------------------------------------
843 */
844/* ARGSUSED */
845static Rp_HashEntry *
846BogusFind(
847    Rp_HashTable *tablePtr, /* Table in which to lookup entry. */
848    CONST void *key)        /* Key to use to find matching entry. */
849{
850    Rp_Panic("called Rp_FindHashEntry on deleted table");
851    return NULL;
852}
853
854/*
855 *----------------------------------------------------------------------
856 *
857 * BogusCreate --
858 *
859 *  This procedure is invoked when an Rp_CreateHashEntry is called
860 *  on a table that has been deleted.
861 *
862 * Results:
863 *  If panic returns (which it shouldn't) this procedure returns
864 *  NULL.
865 *
866 * Side effects:
867 *  Generates a panic.
868 *
869 *----------------------------------------------------------------------
870 */
871/* ARGSUSED */
872static Rp_HashEntry *
873BogusCreate(
874    Rp_HashTable *tablePtr, /* Table in which to lookup entry. */
875    CONST void *key,        /* Key to use to find or create matching
876                             * entry. */
877    int *newPtr)            /* Store info here telling whether a new
878                             * entry was created. */
879{
880    Rp_Panic("called Rp_CreateHashEntry on deleted table");
881    return NULL;
882}
883
884/*
885 *----------------------------------------------------------------------
886 *
887 * RebuildTable --
888 *
889 *  This procedure is invoked when the ratio of entries to hash
890 *  buckets becomes too large.  It creates a new table with a
891 *  larger bucket array and moves all of the entries into the
892 *  new table.
893 *
894 * Results:
895 *  None.
896 *
897 * Side effects:
898 *  Memory gets reallocated and entries get re-hashed to new
899 *  buckets.
900 *
901 *----------------------------------------------------------------------
902 */
903static void
904RebuildTable(Rp_HashTable *tablePtr) /* Table to enlarge. */
905{
906    Rp_HashEntry **bucketPtr, **oldBuckets;
907    register Rp_HashEntry **oldChainPtr, **endPtr;
908    register Rp_HashEntry *hPtr, *nextPtr;
909    size_t hindex;
910
911    oldBuckets = tablePtr->buckets;
912    endPtr = tablePtr->buckets + tablePtr->numBuckets;
913    /*
914     * Allocate and initialize the new bucket array, and set up
915     * hashing constants for new array size.
916     */
917    tablePtr->numBuckets <<= 2;
918    tablePtr->buckets = Rp_Calloc(tablePtr->numBuckets,
919                           sizeof(Rp_HashEntry *));
920    tablePtr->rebuildSize <<= 2;
921    tablePtr->downShift -= 2;
922    tablePtr->mask = tablePtr->numBuckets - 1;
923
924    /*
925     * Move all of the existing entries into the new bucket array,
926     * based on their hash values.
927     */
928    if (tablePtr->keyType == RP_ONE_WORD_KEYS) {
929    /*
930     * RP_ONE_WORD_KEYS are handled slightly differently because
931     * they use the current table size (number of buckets) to be
932     * distributed.
933     */
934        for (oldChainPtr = oldBuckets; oldChainPtr < endPtr; oldChainPtr++) {
935            for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = nextPtr) {
936                nextPtr = hPtr->nextPtr;
937                hindex = RANDOM_INDEX(tablePtr, hPtr->key.oneWordValue);
938                bucketPtr = tablePtr->buckets + hindex;
939                hPtr->nextPtr = *bucketPtr;
940                *bucketPtr = hPtr;
941            }
942        }
943    } else {
944        for (oldChainPtr = oldBuckets; oldChainPtr < endPtr; oldChainPtr++) {
945            for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = nextPtr) {
946                nextPtr = hPtr->nextPtr;
947                hindex = hPtr->hval & tablePtr->mask;
948                bucketPtr = tablePtr->buckets + hindex;
949                hPtr->nextPtr = *bucketPtr;
950                *bucketPtr = hPtr;
951            }
952        }
953    }
954
955    /*
956     * Free up the old bucket array, if it was dynamically allocated.
957     */
958    if (oldBuckets != tablePtr->staticBuckets) {
959        Rp_Free(oldBuckets);
960    }
961}
962
963
964/* Public hash table routines */
965
966/*
967 *----------------------------------------------------------------------
968 *
969 * Rp_InitHashTable --
970 *
971 *  Given storage for a hash table, set up the fields to prepare
972 *  the hash table for use.
973 *
974 * Results:
975 *  None.
976 *
977 * Side effects:
978 *  TablePtr is now ready to be passed to Rp_FindHashEntry and
979 *  Rp_CreateHashEntry.
980 *
981 *----------------------------------------------------------------------
982 */
983void
984Rp_InitHashTable(
985    register Rp_HashTable *tablePtr,    /* Pointer to table record, which
986                                         * is supplied by the caller. */
987    size_t keyType)                     /* Type of keys to use in table. */
988{
989#if (RP_SMALL_HASH_TABLE != 4)
990    Rp_Panic("Rp_InitHashTable: RP_SMALL_HASH_TABLE is %d, not 4\n",
991        RP_SMALL_HASH_TABLE);
992#endif
993    tablePtr->buckets = tablePtr->staticBuckets;
994    tablePtr->numBuckets = RP_SMALL_HASH_TABLE;
995    tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] = 0;
996    tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] = 0;
997    tablePtr->numEntries = 0;
998    tablePtr->rebuildSize = RP_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
999    tablePtr->downShift = DOWNSHIFT_START;
1000
1001    /* The number of buckets is always a power of 2, so we can
1002     * generate the mask by simply subtracting 1 from the number of
1003     * buckets. */
1004    tablePtr->mask = (Rp_Hash)(tablePtr->numBuckets - 1);
1005    tablePtr->keyType = keyType;
1006
1007    switch (keyType) {
1008    case RP_STRING_KEYS:    /* NUL terminated string keys. */
1009        tablePtr->findProc = StringFind;
1010        tablePtr->createProc = StringCreate;
1011        break;
1012
1013    case RP_ONE_WORD_KEYS:  /* 32 or 64 bit atomic keys. */
1014        tablePtr->findProc = OneWordFind;
1015        tablePtr->createProc = OneWordCreate;
1016        break;
1017
1018    default:                /* Structures/arrays. */
1019        if (keyType == 0) {
1020            Rp_Panic("Rp_InitHashTable: Key size can't be %d, must be > 0\n",
1021              keyType);
1022        }
1023        tablePtr->findProc = ArrayFind;
1024        tablePtr->createProc = ArrayCreate;
1025        break;
1026    }
1027    tablePtr->hPool = NULL;
1028}
1029
1030/*
1031 *----------------------------------------------------------------------
1032 *
1033 * Rp_InitHashTableWithPool --
1034 *
1035 *  Given storage for a hash table, set up the fields to prepare
1036 *  the hash table for use.  The only difference between this
1037 *  routine and Rp_InitHashTable is that is uses a pool allocator
1038 *  to allocate memory for hash table entries.  The type of pool
1039 *  is either fixed or variable size (string) keys.
1040 *
1041 * Results:
1042 *  None.
1043 *
1044 * Side effects:
1045 *  TablePtr is now ready to be passed to Rp_FindHashEntry and
1046 *  Rp_CreateHashEntry.
1047 *
1048 *----------------------------------------------------------------------
1049 */
1050void
1051Rp_InitHashTableWithPool(
1052    register Rp_HashTable *tablePtr,    /* Pointer to table record, which
1053                                         * is supplied by the caller. */
1054    size_t keyType)                     /* Type of keys to use in table. */
1055{
1056    Rp_InitHashTable(tablePtr, keyType);
1057    if (keyType == RP_STRING_KEYS) {
1058        tablePtr->hPool = Rp_PoolCreate(RP_VARIABLE_SIZE_ITEMS);
1059    } else {
1060        tablePtr->hPool = Rp_PoolCreate(RP_FIXED_SIZE_ITEMS);
1061    }
1062}
1063
1064/*
1065 *----------------------------------------------------------------------
1066 *
1067 * Rp_DeleteHashEntry --
1068 *
1069 *  Remove a single entry from a hash table.
1070 *
1071 * Results:
1072 *  None.
1073 *
1074 * Side effects:
1075 *  The entry given by entryPtr is deleted from its table and
1076 *  should never again be used by the caller.  It is up to the
1077 *  caller to free the clientData field of the entry, if that
1078 *  is relevant.
1079 *
1080 *----------------------------------------------------------------------
1081 */
1082void
1083Rp_DeleteHashEntry(
1084    Rp_HashTable *tablePtr,
1085    Rp_HashEntry *entryPtr)
1086{
1087    register Rp_HashEntry *prevPtr;
1088    Rp_HashEntry **bucketPtr;
1089    size_t hindex;
1090
1091    if (tablePtr->keyType == RP_ONE_WORD_KEYS) {
1092        hindex = RANDOM_INDEX(tablePtr, (CONST void *)entryPtr->hval);
1093    } else {
1094        hindex = (entryPtr->hval & tablePtr->mask);
1095    }
1096    bucketPtr = tablePtr->buckets + hindex;
1097    if (*bucketPtr == entryPtr) {
1098        *bucketPtr = entryPtr->nextPtr;
1099    } else {
1100        for (prevPtr = *bucketPtr; /*empty*/; prevPtr = prevPtr->nextPtr) {
1101            if (prevPtr == NULL) {
1102                Rp_Panic("malformed bucket chain in Rp_DeleteHashEntry");
1103            }
1104            if (prevPtr->nextPtr == entryPtr) {
1105                prevPtr->nextPtr = entryPtr->nextPtr;
1106                break;
1107            }
1108        }
1109    }
1110    tablePtr->numEntries--;
1111    if (tablePtr->hPool != NULL) {
1112        Rp_PoolFreeItem(tablePtr->hPool, (char *)entryPtr);
1113    } else {
1114        Rp_Free(entryPtr);
1115    }
1116}
1117
1118/*
1119 *----------------------------------------------------------------------
1120 *
1121 * Rp_DeleteHashTable --
1122 *
1123 *  Free up everything associated with a hash table except for
1124 *  the record for the table itself.
1125 *
1126 * Results:
1127 *  None.
1128 *
1129 * Side effects:
1130 *  The hash table is no longer useable.
1131 *
1132 *----------------------------------------------------------------------
1133 */
1134void
1135Rp_DeleteHashTable(Rp_HashTable *tablePtr)      /* Table to delete. */
1136{
1137    /*
1138     * Free up all the entries in the table.
1139     */
1140    if (tablePtr->hPool != NULL) {
1141        Rp_PoolDestroy(tablePtr->hPool);
1142        tablePtr->hPool = NULL;
1143    } else {
1144        register Rp_HashEntry *hPtr, *nextPtr;
1145        size_t i;
1146
1147        for (i = 0; i < tablePtr->numBuckets; i++) {
1148            hPtr = tablePtr->buckets[i];
1149            while (hPtr != NULL) {
1150                nextPtr = hPtr->nextPtr;
1151                Rp_Free(hPtr);
1152                hPtr = nextPtr;
1153            }
1154        }
1155    }
1156
1157    /*
1158     * Free up the bucket array, if it was dynamically allocated.
1159     */
1160    if (tablePtr->buckets != tablePtr->staticBuckets) {
1161        Rp_Free(tablePtr->buckets);
1162    }
1163
1164    /*
1165     * Arrange for panics if the table is used again without
1166     * re-initialization.
1167     */
1168
1169    tablePtr->findProc = BogusFind;
1170    tablePtr->createProc = BogusCreate;
1171}
1172
1173/*
1174 *----------------------------------------------------------------------
1175 *
1176 * Rp_FirstHashEntry --
1177 *
1178 *  Locate the first entry in a hash table and set up a record
1179 *  that can be used to step through all the remaining entries
1180 *  of the table.
1181 *
1182 * Results:
1183 *  The return value is a pointer to the first entry in tablePtr,
1184 *  or NULL if tablePtr has no entries in it.  The memory at
1185 *  *searchPtr is initialized so that subsequent calls to
1186 *  Rp_NextHashEntry will return all of the entries in the table,
1187 *  one at a time.
1188 *
1189 * Side effects:
1190 *  None.
1191 *
1192 *----------------------------------------------------------------------
1193 */
1194Rp_HashEntry *
1195Rp_FirstHashEntry(
1196    Rp_HashTable *tablePtr,         /* Table to search. */
1197    Rp_HashSearch *searchPtr)       /* Place to store information about
1198                                     * progress through the table. */
1199{
1200    searchPtr->tablePtr = tablePtr;
1201    searchPtr->nextIndex = 0;
1202    searchPtr->nextEntryPtr = NULL;
1203    return Rp_NextHashEntry(searchPtr);
1204}
1205
1206/*
1207 *----------------------------------------------------------------------
1208 *
1209 * Rp_NextHashEntry --
1210 *
1211 *  Once a hash table enumeration has been initiated by calling
1212 *  Rp_FirstHashEntry, this procedure may be called to return
1213 *  successive elements of the table.
1214 *
1215 * Results:
1216 *  The return value is the next entry in the hash table being
1217 *  enumerated, or NULL if the end of the table is reached.
1218 *
1219 * Side effects:
1220 *  None.
1221 *
1222 *----------------------------------------------------------------------
1223 */
1224Rp_HashEntry *
1225Rp_NextHashEntry(Rp_HashSearch *searchPtr)
1226{
1227    Rp_HashEntry *hPtr;
1228
1229    while (searchPtr->nextEntryPtr == NULL) {
1230        if (searchPtr->nextIndex >= searchPtr->tablePtr->numBuckets) {
1231            return NULL;
1232        }
1233        searchPtr->nextEntryPtr =
1234                searchPtr->tablePtr->buckets[searchPtr->nextIndex];
1235        searchPtr->nextIndex++;
1236    }
1237    hPtr = searchPtr->nextEntryPtr;
1238    searchPtr->nextEntryPtr = hPtr->nextPtr;
1239    return hPtr;
1240}
1241
1242/*
1243 *----------------------------------------------------------------------
1244 *
1245 * Rp_HashStats --
1246 *
1247 *  Return statistics describing the layout of the hash table
1248 *  in its hash buckets.
1249 *
1250 * Results:
1251 *  The return value is a malloc-ed string containing information
1252 *  about tablePtr.  It is the caller's responsibility to free
1253 *  this string.
1254 *
1255 * Side effects:
1256 *  None.
1257 *
1258 *----------------------------------------------------------------------
1259 */
1260char *
1261Rp_HashStats(Rp_HashTable *tablePtr) /* Table for which to produce stats. */
1262{
1263#define NUM_COUNTERS 10
1264    size_t count[NUM_COUNTERS], overflow, i, j, max;
1265    double average, tmp;
1266    register Rp_HashEntry *hPtr;
1267    Rp_HashEntry **bucketPtr, **endPtr;
1268    char *result, *p;
1269
1270    /*
1271     * Compute a histogram of bucket usage.
1272     */
1273    for (i = 0; i < NUM_COUNTERS; i++) {
1274        count[i] = 0;
1275    }
1276    overflow = 0;
1277    average = 0.0;
1278    max = 0;
1279    endPtr = tablePtr->buckets + tablePtr->numBuckets;
1280    for (bucketPtr = tablePtr->buckets; bucketPtr < endPtr; bucketPtr++) {
1281        j = 0;
1282        for (hPtr = *bucketPtr; hPtr != NULL; hPtr = hPtr->nextPtr) {
1283            j++;
1284        }
1285        if (j > max) {
1286            max = j;
1287        }
1288        if (j < NUM_COUNTERS) {
1289            count[j]++;
1290        } else {
1291            overflow++;
1292        }
1293        tmp = j;
1294        average += (tmp+1.0)*(tmp/tablePtr->numEntries)/2.0;
1295    }
1296
1297    /*
1298     * Print out the histogram and a few other pieces of information.
1299     */
1300    result = Rp_Malloc((unsigned) ((NUM_COUNTERS*60) + 300));
1301#if SIZEOF_VOID_P == 8
1302    sprintf(result, "%ld entries in table, %ld buckets\n",
1303            tablePtr->numEntries, tablePtr->numBuckets);
1304#else
1305    sprintf(result, "%d entries in table, %d buckets\n",
1306            tablePtr->numEntries, tablePtr->numBuckets);
1307#endif
1308    p = result + strlen(result);
1309    for (i = 0; i < NUM_COUNTERS; i++) {
1310#if SIZEOF_VOID_P == 8
1311        sprintf(p, "number of buckets with %ld entries: %ld\n",
1312                i, count[i]);
1313#else
1314        sprintf(p, "number of buckets with %d entries: %d\n",
1315                i, count[i]);
1316#endif
1317        p += strlen(p);
1318    }
1319#if SIZEOF_VOID_P == 8
1320    sprintf(p, "number of buckets with %d or more entries: %ld\n",
1321            NUM_COUNTERS, overflow);
1322#else
1323    sprintf(p, "number of buckets with %d or more entries: %d\n",
1324            NUM_COUNTERS, overflow);
1325#endif
1326    p += strlen(p);
1327    sprintf(p, "average search distance for entry: %.2f\n", average);
1328    p += strlen(p);
1329#if SIZEOF_VOID_P == 8
1330    sprintf(p, "maximum search distance for entry: %ld", max);
1331#else
1332    sprintf(p, "maximum search distance for entry: %d", max);
1333#endif
1334    return result;
1335}
Note: See TracBrowser for help on using the repository browser.