source: trunk/kitgen/8.x/blt/generic/bltHash.c@ 201

/* 
 * bltHash.c --
 *
 *
 *      This module implements an in-memory hash table for the BLT
 *      toolkit.  Built upon the Tcl hash table, it adds pool
 *      allocation 64-bit address handling, improved array hash
 *      function.
 *
 * Copyright 2001 Silicon Metrics Corporation.
 *
 * Permission to use, copy, modify, and distribute this software and
 * its documentation for any purpose and without fee is hereby
 * granted, provided that the above copyright notice appear in all
 * copies and that both that the copyright notice and warranty
 * disclaimer appear in supporting documentation, and that the names
 * of Lucent Technologies any of their entities not be used in
 * advertising or publicity pertaining to distribution of the software
 * without specific, written prior permission.
 *
 * Silicon Metrics disclaims all warranties with regard to this
 * software, including all implied warranties of merchantability and
 * fitness.  In no event shall Lucent Technologies be liable for any
 * special, indirect or consequential damages or any damages
 * whatsoever resulting from loss of use, data or profits, whether in
 * an action of contract, negligence or other tortuous action, arising
 * out of or in connection with the use or performance of this
 * software.
 *
 * Bob Jenkins, 1996.  hash.c.  Public Domain.
 * Bob Jenkins, 1997.  lookup8.c.  Public Domain.
 *
 * Copyright (c) 1991-1993 The Regents of the University of California.
 * Copyright (c) 1994 Sun Microsystems, Inc.
 *
 * See the file "license.terms" for information on usage and redistribution
 * of this file, and for a DISCLAIMER OF ALL WARRANTIES.
 *
 * RCS: @(#) $Id: bltHash.c,v 1.10 2002/08/09 07:15:18 ghowlett Exp $
 */

#include "bltInt.h"

#include <stdio.h>
#include <string.h>
/* The following header is required for LP64 compilation */
#include <stdlib.h>

#include "bltHash.h"

/*
 * When there are this many entries per bucket, on average, rebuild
 * the hash table to make it larger.
 */

#define REBUILD_MULTIPLIER      3

#if (SIZEOF_VOID_P == 8)
#define RANDOM_INDEX            HashOneWord
#define DOWNSHIFT_START         62
#else 

/*
 * The following macro takes a preliminary integer hash value and
 * produces an index into a hash tables bucket list.  The idea is
 * to make it so that preliminary values that are arbitrarily similar
 * will end up in different buckets.  The hash function was taken
 * from a random-number generator.
 */
#define RANDOM_INDEX(tablePtr, i) \
    (((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask)
#define DOWNSHIFT_START 28
#endif

/*
 * Procedure prototypes for static procedures in this file:
 */
static Blt_Hash HashArray _ANSI_ARGS_((CONST void *key, size_t length));
static Blt_HashEntry *ArrayFind _ANSI_ARGS_((Blt_HashTable *tablePtr,
        CONST void *key));
static Blt_HashEntry *ArrayCreate _ANSI_ARGS_((Blt_HashTable *tablePtr,
        CONST void *key, int *newPtr));
static Blt_HashEntry *BogusFind _ANSI_ARGS_((Blt_HashTable *tablePtr,
        CONST void *key));
static Blt_HashEntry *BogusCreate _ANSI_ARGS_((Blt_HashTable *tablePtr,
        CONST void *key, int *newPtr));
static Blt_Hash HashString _ANSI_ARGS_((CONST char *string));
static void RebuildTable _ANSI_ARGS_((Blt_HashTable *tablePtr));
static Blt_HashEntry *StringFind _ANSI_ARGS_((Blt_HashTable *tablePtr,
        CONST void *key));
static Blt_HashEntry *StringCreate _ANSI_ARGS_((Blt_HashTable *tablePtr,
        CONST void *key, int *newPtr));
static Blt_HashEntry *OneWordFind _ANSI_ARGS_((Blt_HashTable *tablePtr,
        CONST void *key));
static Blt_HashEntry *OneWordCreate _ANSI_ARGS_((Blt_HashTable *tablePtr,
        CONST void *key, int *newPtr));

#if (SIZEOF_VOID_P == 8)
static Blt_Hash HashOneWord _ANSI_ARGS_((Blt_HashTable *tablePtr,
        CONST void *key));

#endif /* SIZEOF_VOID_P == 8 */

/*
 *----------------------------------------------------------------------
 *
 * HashString --
 *
 *      Compute a one-word summary of a text string, which can be
 *      used to generate a hash index.
 *
 * Results:
 *      The return value is a one-word summary of the information in
 *      string.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */
static Blt_Hash
HashString(register CONST char *string) /* String from which to
                                         * compute hash value. */
{
    register Blt_Hash result;
    register Blt_Hash c;

    /*
     * I tried a zillion different hash functions and asked many other
     * people for advice.  Many people had their own favorite functions,
     * all different, but no-one had much idea why they were good ones.
     * I chose the one below (multiply by 9 and add new character)
     * because of the following reasons:
     *
     * 1. Multiplying by 10 is perfect for keys that are decimal strings,
     *    and multiplying by 9 is just about as good.
     * 2. Times-9 is (shift-left-3) plus (old).  This means that each
     *    character's bits hang around in the low-order bits of the
     *    hash value for ever, plus they spread fairly rapidly up to
     *    the high-order bits to fill out the hash value.  This seems
     *    to work well both for decimal and non-decimal strings.
     */

    result = 0;
    while ((c = *string++) != 0) {
        result += (result << 3) + c;
    }
    return (Blt_Hash)result;
}

/*
 *----------------------------------------------------------------------
 *
 * StringFind --
 *
 *      Given a hash table with string keys, and a string key, find
 *      the entry with a matching key.
 *
 * Results:
 *      The return value is a token for the matching entry in the
 *      hash table, or NULL if there was no matching entry.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */
static Blt_HashEntry *
StringFind(
    Blt_HashTable *tablePtr,    /* Table in which to lookup entry. */
    CONST void *key)            /* Key to use to find matching entry. */
{
    Blt_Hash hval;
    register Blt_HashEntry *hPtr;
    size_t hindex;

    hval = HashString((char *)key);
    hindex = hval & tablePtr->mask;

    /*
     * Search all of the entries in the appropriate bucket.
     */

    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
            hPtr = hPtr->nextPtr) {
        if (hPtr->hval == hval) {
            register CONST char *p1, *p2;

            for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) {
                if (*p1 != *p2) {
                    break;
                }
                if (*p1 == '\0') {
                    return hPtr;
                }
            }
        }
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * StringCreate --
 *
 *      Given a hash table with string keys, and a string key, find
 *      the entry with a matching key.  If there is no matching entry,
 *      then create a new entry that does match.
 *
 * Results:
 *      The return value is a pointer to the matching entry.  If this
 *      is a newly-created entry, then *newPtr will be set to a non-zero
 *      value;  otherwise *newPtr will be set to 0.  If this is a new
 *      entry the value stored in the entry will initially be 0.
 *
 * Side effects:
 *      A new entry may be added to the hash table.
 *
 *----------------------------------------------------------------------
 */
static Blt_HashEntry *
StringCreate(
    Blt_HashTable *tablePtr,    /* Table in which to lookup entry. */
    CONST void *key,            /* Key to use to find or create matching
                                 * entry. */
    int *newPtr)                /* Store info here telling whether a new
                                 * entry was created. */
{
    Blt_Hash hval;
    Blt_HashEntry **bucketPtr;
    register Blt_HashEntry *hPtr;
    size_t size, hindex;

    hval = HashString(key);
    hindex = hval & tablePtr->mask;

    /*
     * Search all of the entries in this bucket.
     */

    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
            hPtr = hPtr->nextPtr) {
        if (hPtr->hval == hval) {
            register CONST char *p1, *p2;

            for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) {
                if (*p1 != *p2) {
                    break;
                }
                if (*p1 == '\0') {
                    *newPtr = FALSE;
                    return hPtr;
                }
            }
        }
    }

    /*
     * Entry not found.  Add a new one to the bucket.
     */

    *newPtr = TRUE;
    size = sizeof(Blt_HashEntry) + strlen(key) - sizeof(Blt_HashKey) + 1;
    if (tablePtr->hPool != NULL) {
        hPtr = Blt_PoolAllocItem(tablePtr->hPool, size);
    } else {
        hPtr = Blt_Malloc(size);
    }
    bucketPtr = tablePtr->buckets + hindex;
    hPtr->nextPtr = *bucketPtr;
    hPtr->hval = hval;
    hPtr->clientData = 0;
    strcpy(hPtr->key.string, key);
    *bucketPtr = hPtr;
    tablePtr->numEntries++;

    /*
     * If the table has exceeded a decent size, rebuild it with many
     * more buckets.
     */

    if (tablePtr->numEntries >= tablePtr->rebuildSize) {
        RebuildTable(tablePtr);
    }
    return hPtr;
}

#if (SIZEOF_VOID_P == 8)
/*
 *----------------------------------------------------------------------
 *
 * HashOneWord --
 *
 *      Compute a one-word hash value of a 64-bit word, which then can
 *      be used to generate a hash index.
 *
 *      From Knuth, it's a multiplicative hash.  Multiplies an unsigned
 *      64-bit value with the golden ratio (sqrt(5) - 1) / 2.  The
 *      downshift value is 64 - n, when n is the log2 of the size of
 *      the hash table.
 *              
 * Results:
 *      The return value is a one-word summary of the information in
 *      64 bit word.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */
static Blt_Hash
HashOneWord(
    Blt_HashTable *tablePtr,
    CONST void *key)
{
    uint64_t a0, a1;
    uint64_t y0, y1;
    uint64_t y2, y3; 
    uint64_t p1, p2;
    uint64_t result;
    /* Compute key * GOLDEN_RATIO in 128-bit arithmetic */
    a0 = (uint64_t)key & 0x00000000FFFFFFFF; 
    a1 = (uint64_t)key >> 32;
    
    y0 = a0 * 0x000000007f4a7c13;
    y1 = a0 * 0x000000009e3779b9; 
    y2 = a1 * 0x000000007f4a7c13;
    y3 = a1 * 0x000000009e3779b9; 
    y1 += y0 >> 32;             /* Can't carry */ 
    y1 += y2;                   /* Might carry */
    if (y1 < y2) {
        y3 += (1LL << 32);      /* Propagate */ 
    }

    /* 128-bit product: p1 = loword, p2 = hiword */
    p1 = ((y1 & 0x00000000FFFFFFFF) << 32) + (y0 & 0x00000000FFFFFFFF);
    p2 = y3 + (y1 >> 32);
    
    /* Left shift the value downward by the size of the table */
    if (tablePtr->downShift > 0) { 
        if (tablePtr->downShift < 64) { 
            result = ((p2 << (64 - tablePtr->downShift)) | 
                      (p1 >> (tablePtr->downShift & 63))); 
        } else { 
            result = p2 >> (tablePtr->downShift & 63); 
        } 
    } else { 
        result = p1;
    } 
    /* Finally mask off the high bits */
    return (Blt_Hash)(result & tablePtr->mask);
}

#endif /* SIZEOF_VOID_P == 8 */

/*
 *----------------------------------------------------------------------
 *
 * OneWordFind --
 *
 *      Given a hash table with one-word keys, and a one-word key,
 *      find the entry with a matching key.
 *
 * Results:
 *      The return value is a token for the matching entry in the
 *      hash table, or NULL if there was no matching entry.
 *
 * Side effects:
 *      None.
 *
 *---------------------------------------------------------------------- 
 */
static Blt_HashEntry *
OneWordFind(
    Blt_HashTable *tablePtr,    /* Table in which to lookup entry. */
    register CONST void *key)   /* Key to use to find matching entry. */
{
    register Blt_HashEntry *hPtr;
    size_t hindex;

    hindex = RANDOM_INDEX(tablePtr, key);

    /*
     * Search all of the entries in the appropriate bucket.
     */
    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
            hPtr = hPtr->nextPtr) {
        if (hPtr->key.oneWordValue == key) {
            return hPtr;
        }
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * OneWordCreate --
 *
 *      Given a hash table with one-word keys, and a one-word key, find
 *      the entry with a matching key.  If there is no matching entry,
 *      then create a new entry that does match.
 *
 * Results:
 *      The return value is a pointer to the matching entry.  If this
 *      is a newly-created entry, then *newPtr will be set to a non-zero
 *      value;  otherwise *newPtr will be set to 0.  If this is a new
 *      entry the value stored in the entry will initially be 0.
 *
 * Side effects:
 *      A new entry may be added to the hash table.
 *
 *----------------------------------------------------------------------
 */
static Blt_HashEntry *
OneWordCreate(
    Blt_HashTable *tablePtr,    /* Table in which to lookup entry. */
    CONST void *key,            /* Key to use to find or create matching
                                 * entry. */
    int *newPtr)                /* Store info here telling whether a new
                                 * entry was created. */
{
    Blt_HashEntry **bucketPtr;
    register Blt_HashEntry *hPtr;
    size_t hindex;

    hindex = RANDOM_INDEX(tablePtr, key);

    /*
     * Search all of the entries in this bucket.
     */
    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
            hPtr = hPtr->nextPtr) {
        if (hPtr->key.oneWordValue == key) {
            *newPtr = FALSE;
            return hPtr;
        }
    }

    /*
     * Entry not found.  Add a new one to the bucket.
     */

    *newPtr = TRUE;
    if (tablePtr->hPool != NULL) {
        hPtr = Blt_PoolAllocItem(tablePtr->hPool, sizeof(Blt_HashEntry));
    } else {
        hPtr = Blt_Malloc(sizeof(Blt_HashEntry));
    }   
    bucketPtr = tablePtr->buckets + hindex;
    hPtr->nextPtr = *bucketPtr;
    hPtr->hval = (Blt_Hash)key;
    hPtr->clientData = 0;
    hPtr->key.oneWordValue = (void *)key;       /* CONST XXXX */
    *bucketPtr = hPtr;
    tablePtr->numEntries++;

    /*
     * If the table has exceeded a decent size, rebuild it with many
     * more buckets.
     */

    if (tablePtr->numEntries >= tablePtr->rebuildSize) {
        RebuildTable(tablePtr);
    }
    return hPtr;
}


#if (SIZEOF_VOID_P == 4)
/*
 * --------------------------------------------------------------------
 *
 * MIX32 -- 
 *
 *      Bob Jenkins, 1996.  Public Domain.
 *
 *      Mix 3 32/64-bit values reversibly.  For every delta with one or
 *      two bit set, and the deltas of all three high bits or all
 *      three low bits, whether the original value of a,b,c is almost
 *      all zero or is uniformly distributed, If mix() is run
 *      forward or backward, at least 32 bits in a,b,c have at least
 *      1/4 probability of changing.  * If mix() is run forward, every
 *      bit of c will change between 1/3 and 2/3 of the time.  (Well,
 *      22/100 and 78/100 for some 2-bit deltas.)  mix() was built out
 *      of 36 single-cycle latency instructions in a structure that
 *      could supported 2x parallelism, like so:
 *
 *              a -= b; 
 *              a -= c; x = (c>>13);
 *              b -= c; a ^= x;
 *              b -= a; x = (a<<8);
 *              c -= a; b ^= x;
 *              c -= b; x = (b>>13);
 *              ...
 *
 *       Unfortunately, superscalar Pentiums and Sparcs can't take
 *       advantage of that parallelism.  They've also turned some of
 *       those single-cycle latency instructions into multi-cycle
 *       latency instructions.  Still, this is the fastest good hash I
 *       could find.  There were about 2^^68 to choose from.  I only
 *       looked at a billion or so.
 *
 * -------------------------------------------------------------------- 
 */
#define MIX32(a,b,c) \
        a -= b, a -= c, a ^= (c >> 13), \
        b -= c, b -= a, b ^= (a <<  8), \
        c -= a, c -= b, c ^= (b >> 13), \
        a -= b, a -= c, a ^= (c >> 12), \
        b -= c, b -= a, b ^= (a << 16), \
        c -= a, c -= b, c ^= (b >>  5), \
        a -= b, a -= c, a ^= (c >>  3), \
        b -= c, b -= a, b ^= (a << 10), \
        c -= a, c -= b, c ^= (b >> 15)

#define GOLDEN_RATIO32  0x9e3779b9      /* An arbitrary value */

/*
 * --------------------------------------------------------------------
 *
 * HashArray --
 *
 *      Bob Jenkins, 1996.  Public Domain.
 *
 *      This works on all machines.  Length has to be measured in
 *      unsigned longs instead of bytes.  It requires that
 *
 *        o The key be an array of unsigned ints.
 *        o All your machines have the same endianness
 *        o The length be the number of unsigned ints in the key.
 *
 * --------------------------------------------------------------------
 */
static Blt_Hash
HashArray(
    CONST void *key, 
    size_t length)              /* Length of the key in 32-bit words */
{
    register uint32_t a, b, c, len;
    register uint32_t *arrayPtr = (uint32_t *)key;
    /* Set up the internal state */
    len = length;
    a = b = GOLDEN_RATIO32;     /* An arbitrary value */
    c = 0;                      /* Previous hash value */

    while (len >= 3) {          /* Handle most of the key */
        a += arrayPtr[0];
        b += arrayPtr[1];
        c += arrayPtr[2];
        MIX32(a, b, c);
        arrayPtr += 3; len -= 3;
    }
    c += length;                
    /* And now the last 2 words */
    /* Note that all the case statements fall through */
    switch(len) {
        /* c is reserved for the length */
    case 2 : b += arrayPtr[1];
    case 1 : a += arrayPtr[0];
        /* case 0: nothing left to add */
    }
    MIX32(a, b, c);
    return (Blt_Hash)c;
}
#endif /* SIZEOF_VOID_P == 4 */

#if (SIZEOF_VOID_P == 8)

/* 
 * --------------------------------------------------------------------
 *
 * MIX64 --
 *
 *      Bob Jenkins, January 4 1997, Public Domain.  You can use
 *      this free for any purpose.  It has no warranty.
 *
 *      Returns a 64-bit value.  Every bit of the key affects every
 *      bit of the return value.  No funnels.  Every 1-bit and 2-bit
 *      delta achieves avalanche.  About 41+5len instructions.
 *
 *      The best hash table sizes are powers of 2.  There is no need
 *      to do mod a prime (mod is sooo slow!).  If you need less than
 *      64 bits, use a bitmask.  For example, if you need only 10
 *      bits, do h = (h & hashmask(10)); In which case, the hash table
 *      should have hashsize(10) elements.
 *
 *      By Bob Jenkins, Jan 4 1997.  bob_jenkins@burtleburtle.net.
 *      You may use this code any way you wish, private, educational,
 *      or commercial, as long as this whole comment accompanies it.
 * 
 *      See http://burtleburtle.net/bob/hash/evahash.html
 *      Use for hash table lookup, or anything where one collision in
 *      2^^64 * is acceptable.  Do NOT use for cryptographic purposes.
 *
 * --------------------------------------------------------------------
 */

#define MIX64(a,b,c) \
        a -= b, a -= c, a ^= (c >> 43), \
        b -= c, b -= a, b ^= (a <<  9), \
        c -= a, c -= b, c ^= (b >>  8), \
        a -= b, a -= c, a ^= (c >> 38), \
        b -= c, b -= a, b ^= (a << 23), \
        c -= a, c -= b, c ^= (b >>  5), \
        a -= b, a -= c, a ^= (c >> 35), \
        b -= c, b -= a, b ^= (a << 49), \
        c -= a, c -= b, c ^= (b >> 11), \
        a -= b, a -= c, a ^= (c >> 12), \
        b -= c, b -= a, b ^= (a << 18), \
        c -= a, c -= b, c ^= (b >> 22)

#define GOLDEN_RATIO64  0x9e3779b97f4a7c13LL

/*
 * --------------------------------------------------------------------
 *
 * HashArray --
 *
 *      Bob Jenkins, January 4 1997, Public Domain.  You can use
 *      this free for any purpose.  It has no warranty.
 *
 *      This works on all machines.  The length has to be measured in
 *      64 bit words, instead of bytes.  It requires that
 *
 *        o The key be an array of 64 bit words (unsigned longs).
 *        o All your machines have the same endianness.
 *        o The length be the number of 64 bit words in the key.
 *
 * --------------------------------------------------------------------
 */
static Blt_Hash
HashArray(
    CONST void *key, 
    size_t length)              /* Length of key in 32-bit words. */
{
    register uint64_t a, b, c, len;
    register uint32_t *iPtr = (uint32_t *)key;

#ifdef WORDS_BIGENDIAN
#define PACK(a,b)       ((uint64_t)(b) | ((uint64_t)(a) << 32))
#else
#define PACK(a,b)       ((uint64_t)(a) | ((uint64_t)(b) << 32))
#endif
    /* Set up the internal state */
    len = length;               /* Length is the number of 64-bit words. */
    a = b = GOLDEN_RATIO64;     /* An arbitrary value */
    c = 0;                      /* Previous hash value */

    while (len >= 6) {          /* Handle most of the key */
        a += PACK(iPtr[0], iPtr[1]);
        b += PACK(iPtr[2], iPtr[3]);
        c += PACK(iPtr[4], iPtr[5]);
        MIX64(a,b,c);
        iPtr += 6; len -= 6;
    }
    c += length;                
    /* And now the last 2 words */
    /* Note that all the case statements fall through */
    switch(len) {
        /* c is reserved for the length */
    case 5 : 
    case 4 : 
        a += PACK(iPtr[0], iPtr[1]);
        b += PACK(iPtr[2], iPtr[3]);
        iPtr += 4; len -= 4;
        break;
    case 3 : 
    case 2 : 
        a += PACK(iPtr[0], iPtr[1]);
        iPtr += 2; len -= 2;
 /* case 0: nothing left to add */
    }
    if (len > 0) {              
        b += iPtr[0];
    }
    MIX64(a,b,c);
    return (Blt_Hash)c;
}
#endif /* SIZEOF_VOID_P == 8 */

/*
 *----------------------------------------------------------------------
 *
 * ArrayFind --
 *
 *      Given a hash table with array-of-int keys, and a key, find
 *      the entry with a matching key.
 *
 * Results:
 *      The return value is a token for the matching entry in the
 *      hash table, or NULL if there was no matching entry.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */
static Blt_HashEntry *
ArrayFind(
    Blt_HashTable *tablePtr,    /* Table in which to lookup entry. */
    CONST void *key)            /* Key to use to find matching entry. */
{
    Blt_Hash hval;
    register Blt_HashEntry *hPtr;
    size_t hindex;

    hval = HashArray(key, tablePtr->keyType);
    hindex = hval & tablePtr->mask;
    /*
     * Search all of the entries in the appropriate bucket.
     */

    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
            hPtr = hPtr->nextPtr) {
        if (hPtr->hval == hval) {
            register unsigned int *iPtr1, *iPtr2;
            unsigned int count;

            for (iPtr1 = (uint32_t *)key, iPtr2 = (uint32_t *)hPtr->key.words,
                     count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
                if (count == 0) {
                    return hPtr;
                }
                if (*iPtr1 != *iPtr2) {
                    break;
                }
            }
        }
    }
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * ArrayCreate --
 *
 *      Given a hash table with one-word keys, and a one-word key, find
 *      the entry with a matching key.  If there is no matching entry,
 *      then create a new entry that does match.
 *
 * Results:
 *      The return value is a pointer to the matching entry.  If this
 *      is a newly-created entry, then *newPtr will be set to a non-zero
 *      value;  otherwise *newPtr will be set to 0.  If this is a new
 *      entry the value stored in the entry will initially be 0.
 *
 * Side effects:
 *      A new entry may be added to the hash table.
 *
 *----------------------------------------------------------------------
 */
static Blt_HashEntry *
ArrayCreate(
    Blt_HashTable *tablePtr,    /* Table in which to lookup entry. */
    register CONST void *key,   /* Key to use to find or create matching
                                 * entry. */
    int *newPtr)                /* Store info here telling whether a new
                                 * entry was created. */
{
    Blt_Hash hval;
    Blt_HashEntry **bucketPtr;
    int count;
    register Blt_HashEntry *hPtr;
    register uint32_t *iPtr1, *iPtr2;
    size_t size, hindex;

    hval = HashArray(key, tablePtr->keyType);
    hindex = hval & tablePtr->mask;

    /*
     * Search all of the entries in the appropriate bucket.
     */
    for (hPtr = tablePtr->buckets[hindex]; hPtr != NULL;
            hPtr = hPtr->nextPtr) {
        if (hPtr->hval == hval) {
            for (iPtr1 = (uint32_t *)key, iPtr2 = (uint32_t *)hPtr->key.words,
                     count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
                if (count == 0) {
                    *newPtr = FALSE;
                    return hPtr;
                }
                if (*iPtr1 != *iPtr2) {
                    break;
                }
            }
        }
    }

    /*
     * Entry not found.  Add a new one to the bucket.
     */
    *newPtr = TRUE;
    /* We assume here that the size of the key is at least 2 words */
    size = sizeof(Blt_HashEntry) + tablePtr->keyType * sizeof(uint32_t) - 
        sizeof(Blt_HashKey);
    if (tablePtr->hPool != NULL) {
        hPtr = Blt_PoolAllocItem(tablePtr->hPool, size);
    } else {
        hPtr = Blt_Malloc(size);
    }
    bucketPtr = tablePtr->buckets + hindex;
    hPtr->nextPtr = *bucketPtr;
    hPtr->hval = hval;
    hPtr->clientData = 0;
    count = tablePtr->keyType;
    for (iPtr1 = (uint32_t *)key, iPtr2 = (uint32_t *)hPtr->key.words; 
         count > 0; count--, iPtr1++, iPtr2++) {
        *iPtr2 = *iPtr1;
    }
    *bucketPtr = hPtr;
    tablePtr->numEntries++;

    /*
     * If the table has exceeded a decent size, rebuild it with many
     * more buckets.
     */
    if (tablePtr->numEntries >= tablePtr->rebuildSize) {
        RebuildTable(tablePtr);
    }
    return hPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * BogusFind --
 *
 *      This procedure is invoked when an Blt_FindHashEntry is called
 *      on a table that has been deleted.
 *
 * Results:
 *      If panic returns (which it shouldn't) this procedure returns
 *      NULL.
 *
 * Side effects:
 *      Generates a panic.
 *
 *----------------------------------------------------------------------
 */
/* ARGSUSED */
static Blt_HashEntry *
BogusFind(
    Blt_HashTable *tablePtr,    /* Table in which to lookup entry. */
    CONST void *key)            /* Key to use to find matching entry. */
{
    Blt_Panic("called Blt_FindHashEntry on deleted table");
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * BogusCreate --
 *
 *      This procedure is invoked when an Blt_CreateHashEntry is called
 *      on a table that has been deleted.
 *
 * Results:
 *      If panic returns (which it shouldn't) this procedure returns
 *      NULL.
 *
 * Side effects:
 *      Generates a panic.
 *
 *----------------------------------------------------------------------
 */
/* ARGSUSED */
static Blt_HashEntry *
BogusCreate(
    Blt_HashTable *tablePtr,    /* Table in which to lookup entry. */
    CONST void *key,            /* Key to use to find or create matching
                                 * entry. */
    int *newPtr)                /* Store info here telling whether a new
                                 * entry was created. */
{
    Blt_Panic("called Blt_CreateHashEntry on deleted table");
    return NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * RebuildTable --
 *
 *      This procedure is invoked when the ratio of entries to hash
 *      buckets becomes too large.  It creates a new table with a
 *      larger bucket array and moves all of the entries into the
 *      new table.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      Memory gets reallocated and entries get re-hashed to new
 *      buckets.
 *
 *----------------------------------------------------------------------
 */
static void
RebuildTable(Blt_HashTable *tablePtr) /* Table to enlarge. */
{
    Blt_HashEntry **bucketPtr, **oldBuckets;
    register Blt_HashEntry **oldChainPtr, **endPtr;
    register Blt_HashEntry *hPtr, *nextPtr;
    size_t hindex;

    oldBuckets = tablePtr->buckets;
    endPtr = tablePtr->buckets + tablePtr->numBuckets;
    /*
     * Allocate and initialize the new bucket array, and set up
     * hashing constants for new array size.
     */
    tablePtr->numBuckets <<= 2;
    tablePtr->buckets = Blt_Calloc(tablePtr->numBuckets, 
                                   sizeof(Blt_HashEntry *));
    tablePtr->rebuildSize <<= 2;
    tablePtr->downShift -= 2;
    tablePtr->mask = tablePtr->numBuckets - 1;

    /*
     * Move all of the existing entries into the new bucket array,
     * based on their hash values.  
     */
    if (tablePtr->keyType == BLT_ONE_WORD_KEYS) {
        /* 
         * BLT_ONE_WORD_KEYS are handled slightly differently because
         * they use the current table size (number of buckets) to be
         * distributed.
         */
        for (oldChainPtr = oldBuckets; oldChainPtr < endPtr; oldChainPtr++) {
            for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = nextPtr) {
                nextPtr = hPtr->nextPtr;
                hindex = RANDOM_INDEX(tablePtr, hPtr->key.oneWordValue);
                bucketPtr = tablePtr->buckets + hindex;
                hPtr->nextPtr = *bucketPtr;
                *bucketPtr = hPtr;
            }
        }
    } else {
        for (oldChainPtr = oldBuckets; oldChainPtr < endPtr; oldChainPtr++) {
            for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = nextPtr) {
                nextPtr = hPtr->nextPtr;
                hindex = hPtr->hval & tablePtr->mask;
                bucketPtr = tablePtr->buckets + hindex;
                hPtr->nextPtr = *bucketPtr;
                *bucketPtr = hPtr;
            }
        }
    }

    /*
     * Free up the old bucket array, if it was dynamically allocated.
     */
    if (oldBuckets != tablePtr->staticBuckets) {
        Blt_Free(oldBuckets);
    }
}



/* Public hash table routines */

/*
 *----------------------------------------------------------------------
 *
 * Blt_InitHashTable --
 *
 *      Given storage for a hash table, set up the fields to prepare
 *      the hash table for use.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      TablePtr is now ready to be passed to Blt_FindHashEntry and
 *      Blt_CreateHashEntry.
 *
 *----------------------------------------------------------------------
 */
void
Blt_InitHashTable(
    register Blt_HashTable *tablePtr,   /* Pointer to table record, which
                                         * is supplied by the caller. */
    size_t keyType)                     /* Type of keys to use in table. */
{
#if (BLT_SMALL_HASH_TABLE != 4) 
    Blt_Panic("Blt_InitHashTable: BLT_SMALL_HASH_TABLE is %d, not 4\n",
            BLT_SMALL_HASH_TABLE);
#endif
    tablePtr->buckets = tablePtr->staticBuckets;
    tablePtr->numBuckets = BLT_SMALL_HASH_TABLE;
    tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] = 0;
    tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] = 0;
    tablePtr->numEntries = 0;
    tablePtr->rebuildSize = BLT_SMALL_HASH_TABLE * REBUILD_MULTIPLIER;
    tablePtr->downShift = DOWNSHIFT_START;

    /* The number of buckets is always a power of 2, so we can
     * generate the mask by simply subtracting 1 from the number of
     * buckets. */
    tablePtr->mask = (Blt_Hash)(tablePtr->numBuckets - 1);
    tablePtr->keyType = keyType;

    switch (keyType) {
    case BLT_STRING_KEYS:       /* NUL terminated string keys. */
        tablePtr->findProc = StringFind;
        tablePtr->createProc = StringCreate;
        break;

    case BLT_ONE_WORD_KEYS:     /* 32 or 64 bit atomic keys. */
        tablePtr->findProc = OneWordFind;
        tablePtr->createProc = OneWordCreate;
        break;

    default:                    /* Structures/arrays. */
        if (keyType == 0) {
            Blt_Panic("Blt_InitHashTable: Key size can't be %d, must be > 0\n",
                  keyType);
        }
        tablePtr->findProc = ArrayFind;
        tablePtr->createProc = ArrayCreate;
        break;
    }
    tablePtr->hPool = NULL;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_InitHashTableWithPool --
 *
 *      Given storage for a hash table, set up the fields to prepare
 *      the hash table for use.  The only difference between this 
 *      routine and Blt_InitHashTable is that is uses a pool allocator
 *      to allocate memory for hash table entries.  The type of pool
 *      is either fixed or variable size (string) keys.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      TablePtr is now ready to be passed to Blt_FindHashEntry and
 *      Blt_CreateHashEntry.
 *
 *----------------------------------------------------------------------
 */
void
Blt_InitHashTableWithPool(
    register Blt_HashTable *tablePtr,   /* Pointer to table record, which
                                         * is supplied by the caller. */
    size_t keyType)                     /* Type of keys to use in table. */
{
    Blt_InitHashTable(tablePtr, keyType);
    if (keyType == BLT_STRING_KEYS) {
        tablePtr->hPool = Blt_PoolCreate(BLT_VARIABLE_SIZE_ITEMS);
    } else {
        tablePtr->hPool = Blt_PoolCreate(BLT_FIXED_SIZE_ITEMS);
    }
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_DeleteHashEntry --
 *
 *      Remove a single entry from a hash table.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      The entry given by entryPtr is deleted from its table and
 *      should never again be used by the caller.  It is up to the
 *      caller to free the clientData field of the entry, if that
 *      is relevant.
 *
 *----------------------------------------------------------------------
 */
void
Blt_DeleteHashEntry(
    Blt_HashTable *tablePtr,
    Blt_HashEntry *entryPtr)
{
    register Blt_HashEntry *prevPtr;
    Blt_HashEntry **bucketPtr;
    size_t hindex;

    if (tablePtr->keyType == BLT_ONE_WORD_KEYS) {
        hindex = RANDOM_INDEX(tablePtr, (CONST void *)entryPtr->hval);
    } else {
        hindex = (entryPtr->hval & tablePtr->mask);
    }   
    bucketPtr = tablePtr->buckets + hindex;
    if (*bucketPtr == entryPtr) {
        *bucketPtr = entryPtr->nextPtr;
    } else {
        for (prevPtr = *bucketPtr; /*empty*/; prevPtr = prevPtr->nextPtr) {
            if (prevPtr == NULL) {
                Blt_Panic("malformed bucket chain in Blt_DeleteHashEntry");
            }
            if (prevPtr->nextPtr == entryPtr) {
                prevPtr->nextPtr = entryPtr->nextPtr;
                break;
            }
        }
    }
    tablePtr->numEntries--;
    if (tablePtr->hPool != NULL) {
        Blt_PoolFreeItem(tablePtr->hPool, (char *)entryPtr);
    } else {
        Blt_Free(entryPtr);
    }
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_DeleteHashTable --
 *
 *      Free up everything associated with a hash table except for
 *      the record for the table itself.
 *
 * Results:
 *      None.
 *
 * Side effects:
 *      The hash table is no longer useable.
 *
 *----------------------------------------------------------------------
 */
void
Blt_DeleteHashTable(Blt_HashTable *tablePtr)    /* Table to delete. */
{
    /*
     * Free up all the entries in the table.
     */
    if (tablePtr->hPool != NULL) {
        Blt_PoolDestroy(tablePtr->hPool);
        tablePtr->hPool = NULL;
    } else {
        register Blt_HashEntry *hPtr, *nextPtr;
        size_t i;

        for (i = 0; i < tablePtr->numBuckets; i++) {
            hPtr = tablePtr->buckets[i];
            while (hPtr != NULL) {
                nextPtr = hPtr->nextPtr;
                Blt_Free(hPtr);
                hPtr = nextPtr;
            }
        }
    }
    
    /*
     * Free up the bucket array, if it was dynamically allocated.
     */
    if (tablePtr->buckets != tablePtr->staticBuckets) {
        Blt_Free(tablePtr->buckets);
    }

    /*
     * Arrange for panics if the table is used again without
     * re-initialization.
     */

    tablePtr->findProc = BogusFind;
    tablePtr->createProc = BogusCreate;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_FirstHashEntry --
 *
 *      Locate the first entry in a hash table and set up a record
 *      that can be used to step through all the remaining entries
 *      of the table.
 *
 * Results:
 *      The return value is a pointer to the first entry in tablePtr,
 *      or NULL if tablePtr has no entries in it.  The memory at
 *      *searchPtr is initialized so that subsequent calls to
 *      Blt_NextHashEntry will return all of the entries in the table,
 *      one at a time.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */
Blt_HashEntry *
Blt_FirstHashEntry(
    Blt_HashTable *tablePtr,            /* Table to search. */
    Blt_HashSearch *searchPtr)          /* Place to store information about
                                         * progress through the table. */
{
    searchPtr->tablePtr = tablePtr;
    searchPtr->nextIndex = 0;
    searchPtr->nextEntryPtr = NULL;
    return Blt_NextHashEntry(searchPtr);
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_NextHashEntry --
 *
 *      Once a hash table enumeration has been initiated by calling
 *      Blt_FirstHashEntry, this procedure may be called to return
 *      successive elements of the table.
 *
 * Results:
 *      The return value is the next entry in the hash table being
 *      enumerated, or NULL if the end of the table is reached.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */
Blt_HashEntry *
Blt_NextHashEntry(Blt_HashSearch *searchPtr)
{
    Blt_HashEntry *hPtr;

    while (searchPtr->nextEntryPtr == NULL) {
        if (searchPtr->nextIndex >= searchPtr->tablePtr->numBuckets) {
            return NULL;
        }
        searchPtr->nextEntryPtr =
                searchPtr->tablePtr->buckets[searchPtr->nextIndex];
        searchPtr->nextIndex++;
    }
    hPtr = searchPtr->nextEntryPtr;
    searchPtr->nextEntryPtr = hPtr->nextPtr;
    return hPtr;
}

/*
 *----------------------------------------------------------------------
 *
 * Blt_HashStats --
 *
 *      Return statistics describing the layout of the hash table
 *      in its hash buckets.
 *
 * Results:
 *      The return value is a malloc-ed string containing information
 *      about tablePtr.  It is the caller's responsibility to free
 *      this string.
 *
 * Side effects:
 *      None.
 *
 *----------------------------------------------------------------------
 */
char *
Blt_HashStats(Blt_HashTable *tablePtr) /* Table for which to produce stats. */
{
#define NUM_COUNTERS 10
    size_t count[NUM_COUNTERS], overflow, i, j, max;
    double average, tmp;
    register Blt_HashEntry *hPtr;
    Blt_HashEntry **bucketPtr, **endPtr;
    char *result, *p;

    /*
     * Compute a histogram of bucket usage.
     */
    for (i = 0; i < NUM_COUNTERS; i++) {
        count[i] = 0;
    }
    overflow = 0;
    average = 0.0;
    max = 0;
    endPtr = tablePtr->buckets + tablePtr->numBuckets;
    for (bucketPtr = tablePtr->buckets; bucketPtr < endPtr; bucketPtr++) {
        j = 0;
        for (hPtr = *bucketPtr; hPtr != NULL; hPtr = hPtr->nextPtr) {
            j++;
        }
        if (j > max) {
            max = j;
        }
        if (j < NUM_COUNTERS) {
            count[j]++;
        } else {
            overflow++;
        }
        tmp = j;
        average += (tmp+1.0)*(tmp/tablePtr->numEntries)/2.0;
    }

    /*
     * Print out the histogram and a few other pieces of information.
     */
    result = Blt_Malloc((unsigned) ((NUM_COUNTERS*60) + 300));
#if SIZEOF_VOID_P == 8
    sprintf(result, "%ld entries in table, %ld buckets\n",
            tablePtr->numEntries, tablePtr->numBuckets);
#else 
    sprintf(result, "%d entries in table, %d buckets\n",
            tablePtr->numEntries, tablePtr->numBuckets);
#endif
    p = result + strlen(result);
    for (i = 0; i < NUM_COUNTERS; i++) {
#if SIZEOF_VOID_P == 8
        sprintf(p, "number of buckets with %ld entries: %ld\n",
                i, count[i]);
#else 
        sprintf(p, "number of buckets with %d entries: %d\n",
                i, count[i]);
#endif
        p += strlen(p);
    }
#if SIZEOF_VOID_P == 8
    sprintf(p, "number of buckets with %d or more entries: %ld\n",
            NUM_COUNTERS, overflow);
#else 
    sprintf(p, "number of buckets with %d or more entries: %d\n",
            NUM_COUNTERS, overflow);
#endif
    p += strlen(p);
    sprintf(p, "average search distance for entry: %.2f\n", average);
    p += strlen(p);
#if SIZEOF_VOID_P == 8
    sprintf(p, "maximum search distance for entry: %ld", max);
#else
    sprintf(p, "maximum search distance for entry: %d", max);
#endif
    return result;
}