stk/Tcl/tclHash.c

922 lines
24 KiB
C
Raw Permalink Blame History

This file contains invisible Unicode characters

This file contains invisible Unicode characters that are indistinguishable to humans but may be processed differently by a computer. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.

/*
* tclHash.c --
*
* Implementation of in-memory hash tables for Tcl and Tcl-based
* applications.
*
* 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.
*
* SCCS: @(#) tclHash.c 1.16 96/04/29 10:30:49
*/
#include "tclInt.h"
/*
* When there are this many entries per bucket, on average, rebuild
* the hash table to make it larger.
*/
#define REBUILD_MULTIPLIER 3
/*
* 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)
/*
* Procedure prototypes for static procedures in this file:
*/
static Tcl_HashEntry * ArrayFind _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key));
static Tcl_HashEntry * ArrayCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key, int *newPtr));
static Tcl_HashEntry * BogusFind _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key));
static Tcl_HashEntry * BogusCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key, int *newPtr));
static unsigned int HashString _ANSI_ARGS_((CONST char *string));
static void RebuildTable _ANSI_ARGS_((Tcl_HashTable *tablePtr));
static Tcl_HashEntry * StringFind _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key));
static Tcl_HashEntry * StringCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key, int *newPtr));
static Tcl_HashEntry * OneWordFind _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key));
static Tcl_HashEntry * OneWordCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key, int *newPtr));
/*
*----------------------------------------------------------------------
*
* Tcl_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 Tcl_FindHashEntry and
* Tcl_CreateHashEntry.
*
*----------------------------------------------------------------------
*/
void
Tcl_InitHashTable(tablePtr, keyType)
register Tcl_HashTable *tablePtr; /* Pointer to table record, which
* is supplied by the caller. */
int keyType; /* Type of keys to use in table:
* TCL_STRING_KEYS, TCL_ONE_WORD_KEYS,
* or an integer >= 2. */
{
tablePtr->buckets = tablePtr->staticBuckets;
tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] = 0;
tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] = 0;
tablePtr->numBuckets = TCL_SMALL_HASH_TABLE;
tablePtr->numEntries = 0;
tablePtr->rebuildSize = TCL_SMALL_HASH_TABLE*REBUILD_MULTIPLIER;
tablePtr->downShift = 28;
tablePtr->mask = 3;
tablePtr->keyType = keyType;
if (keyType == TCL_STRING_KEYS) {
tablePtr->findProc = StringFind;
tablePtr->createProc = StringCreate;
} else if (keyType == TCL_ONE_WORD_KEYS) {
tablePtr->findProc = OneWordFind;
tablePtr->createProc = OneWordCreate;
} else {
tablePtr->findProc = ArrayFind;
tablePtr->createProc = ArrayCreate;
};
}
/*
*----------------------------------------------------------------------
*
* Tcl_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
Tcl_DeleteHashEntry(entryPtr)
Tcl_HashEntry *entryPtr;
{
register Tcl_HashEntry *prevPtr;
if (*entryPtr->bucketPtr == entryPtr) {
*entryPtr->bucketPtr = entryPtr->nextPtr;
} else {
for (prevPtr = *entryPtr->bucketPtr; ; prevPtr = prevPtr->nextPtr) {
if (prevPtr == NULL) {
panic("malformed bucket chain in Tcl_DeleteHashEntry");
}
if (prevPtr->nextPtr == entryPtr) {
prevPtr->nextPtr = entryPtr->nextPtr;
break;
}
}
}
entryPtr->tablePtr->numEntries--;
ckfree((char *) entryPtr);
}
/*
*----------------------------------------------------------------------
*
* Tcl_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
Tcl_DeleteHashTable(tablePtr)
register Tcl_HashTable *tablePtr; /* Table to delete. */
{
register Tcl_HashEntry *hPtr, *nextPtr;
int i;
/*
* Free up all the entries in the table.
*/
for (i = 0; i < tablePtr->numBuckets; i++) {
hPtr = tablePtr->buckets[i];
while (hPtr != NULL) {
nextPtr = hPtr->nextPtr;
ckfree((char *) hPtr);
hPtr = nextPtr;
}
}
/*
* Free up the bucket array, if it was dynamically allocated.
*/
if (tablePtr->buckets != tablePtr->staticBuckets) {
ckfree((char *) tablePtr->buckets);
}
/*
* Arrange for panics if the table is used again without
* re-initialization.
*/
tablePtr->findProc = BogusFind;
tablePtr->createProc = BogusCreate;
}
/*
*----------------------------------------------------------------------
*
* Tcl_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
* Tcl_NextHashEntry will return all of the entries in the table,
* one at a time.
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
Tcl_HashEntry *
Tcl_FirstHashEntry(tablePtr, searchPtr)
Tcl_HashTable *tablePtr; /* Table to search. */
Tcl_HashSearch *searchPtr; /* Place to store information about
* progress through the table. */
{
searchPtr->tablePtr = tablePtr;
searchPtr->nextIndex = 0;
searchPtr->nextEntryPtr = NULL;
return Tcl_NextHashEntry(searchPtr);
}
/*
*----------------------------------------------------------------------
*
* Tcl_NextHashEntry --
*
* Once a hash table enumeration has been initiated by calling
* Tcl_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.
*
*----------------------------------------------------------------------
*/
Tcl_HashEntry *
Tcl_NextHashEntry(searchPtr)
register Tcl_HashSearch *searchPtr; /* Place to store information about
* progress through the table. Must
* have been initialized by calling
* Tcl_FirstHashEntry. */
{
Tcl_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;
}
/*
*----------------------------------------------------------------------
*
* Tcl_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 *
Tcl_HashStats(tablePtr)
Tcl_HashTable *tablePtr; /* Table for which to produce stats. */
{
#define NUM_COUNTERS 10
int count[NUM_COUNTERS], overflow, i, j;
double average, tmp;
register Tcl_HashEntry *hPtr;
char *result, *p;
/*
* Compute a histogram of bucket usage.
*/
for (i = 0; i < NUM_COUNTERS; i++) {
count[i] = 0;
}
overflow = 0;
average = 0.0;
for (i = 0; i < tablePtr->numBuckets; i++) {
j = 0;
for (hPtr = tablePtr->buckets[i]; hPtr != NULL; hPtr = hPtr->nextPtr) {
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 = (char *) ckalloc((unsigned) ((NUM_COUNTERS*60) + 300));
sprintf(result, "%d entries in table, %d buckets\n",
tablePtr->numEntries, tablePtr->numBuckets);
p = result + strlen(result);
for (i = 0; i < NUM_COUNTERS; i++) {
sprintf(p, "number of buckets with %d entries: %d\n",
i, count[i]);
p += strlen(p);
}
sprintf(p, "number of buckets with %d or more entries: %d\n",
NUM_COUNTERS, overflow);
p += strlen(p);
sprintf(p, "average search distance for entry: %.1f", average);
return result;
}
/*
*----------------------------------------------------------------------
*
* 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 unsigned int
HashString(string)
register CONST char *string;/* String from which to compute hash value. */
{
register unsigned int result;
register int 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
* works well both for decimal and non-decimal strings.
*/
result = 0;
while (1) {
c = *string;
string++;
if (c == 0) {
break;
}
result += (result<<3) + c;
}
return 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 Tcl_HashEntry *
StringFind(tablePtr, key)
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */
CONST char *key; /* Key to use to find matching entry. */
{
register Tcl_HashEntry *hPtr;
register CONST char *p1, *p2;
int index;
index = HashString(key) & tablePtr->mask;
/*
* Search all of the entries in the appropriate bucket.
*/
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {
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 Tcl_HashEntry *
StringCreate(tablePtr, key, newPtr)
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */
CONST char *key; /* Key to use to find or create matching
* entry. */
int *newPtr; /* Store info here telling whether a new
* entry was created. */
{
register Tcl_HashEntry *hPtr;
register CONST char *p1, *p2;
int index;
index = HashString(key) & tablePtr->mask;
/*
* Search all of the entries in this bucket.
*/
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {
for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) {
if (*p1 != *p2) {
break;
}
if (*p1 == '\0') {
*newPtr = 0;
return hPtr;
}
}
}
/*
* Entry not found. Add a new one to the bucket.
*/
*newPtr = 1;
hPtr = (Tcl_HashEntry *) ckalloc((unsigned)
(sizeof(Tcl_HashEntry) + strlen(key) - (sizeof(hPtr->key) -1)));
hPtr->tablePtr = tablePtr;
hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;
hPtr->clientData = 0;
strcpy(hPtr->key.string, key);
*hPtr->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;
}
/*
*----------------------------------------------------------------------
*
* 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 Tcl_HashEntry *
OneWordFind(tablePtr, key)
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */
register CONST char *key; /* Key to use to find matching entry. */
{
register Tcl_HashEntry *hPtr;
int index;
index = RANDOM_INDEX(tablePtr, key);
/*
* Search all of the entries in the appropriate bucket.
*/
for (hPtr = tablePtr->buckets[index]; 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 Tcl_HashEntry *
OneWordCreate(tablePtr, key, newPtr)
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */
register CONST char *key; /* Key to use to find or create matching
* entry. */
int *newPtr; /* Store info here telling whether a new
* entry was created. */
{
register Tcl_HashEntry *hPtr;
int index;
index = RANDOM_INDEX(tablePtr, key);
/*
* Search all of the entries in this bucket.
*/
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {
if (hPtr->key.oneWordValue == key) {
*newPtr = 0;
return hPtr;
}
}
/*
* Entry not found. Add a new one to the bucket.
*/
*newPtr = 1;
hPtr = (Tcl_HashEntry *) ckalloc(sizeof(Tcl_HashEntry));
hPtr->tablePtr = tablePtr;
hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;
hPtr->clientData = 0;
hPtr->key.oneWordValue = (char *) key; /* CONST XXXX */
*hPtr->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;
}
/*
*----------------------------------------------------------------------
*
* 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 Tcl_HashEntry *
ArrayFind(tablePtr, key)
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */
CONST char *key; /* Key to use to find matching entry. */
{
register Tcl_HashEntry *hPtr;
int *arrayPtr = (int *) key;
register int *iPtr1, *iPtr2;
int index, count;
for (index = 0, count = tablePtr->keyType, iPtr1 = arrayPtr;
count > 0; count--, iPtr1++) {
index += *iPtr1;
}
index = RANDOM_INDEX(tablePtr, index);
/*
* Search all of the entries in the appropriate bucket.
*/
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {
for (iPtr1 = arrayPtr, iPtr2 = 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 Tcl_HashEntry *
ArrayCreate(tablePtr, key, newPtr)
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */
register CONST char *key; /* Key to use to find or create matching
* entry. */
int *newPtr; /* Store info here telling whether a new
* entry was created. */
{
register Tcl_HashEntry *hPtr;
int *arrayPtr = (int *) key;
register int *iPtr1, *iPtr2;
int index, count;
for (index = 0, count = tablePtr->keyType, iPtr1 = arrayPtr;
count > 0; count--, iPtr1++) {
index += *iPtr1;
}
index = RANDOM_INDEX(tablePtr, index);
/*
* Search all of the entries in the appropriate bucket.
*/
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {
for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words,
count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
if (count == 0) {
*newPtr = 0;
return hPtr;
}
if (*iPtr1 != *iPtr2) {
break;
}
}
}
/*
* Entry not found. Add a new one to the bucket.
*/
*newPtr = 1;
hPtr = (Tcl_HashEntry *) ckalloc((unsigned) (sizeof(Tcl_HashEntry)
+ (tablePtr->keyType*sizeof(int)) - 4));
hPtr->tablePtr = tablePtr;
hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;
hPtr->clientData = 0;
for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words, count = tablePtr->keyType;
count > 0; count--, iPtr1++, iPtr2++) {
*iPtr2 = *iPtr1;
}
*hPtr->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 Tcl_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 Tcl_HashEntry *
BogusFind(tablePtr, key)
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */
CONST char *key; /* Key to use to find matching entry. */
{
panic("called Tcl_FindHashEntry on deleted table");
return NULL;
}
/*
*----------------------------------------------------------------------
*
* BogusCreate --
*
* This procedure is invoked when an Tcl_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 Tcl_HashEntry *
BogusCreate(tablePtr, key, newPtr)
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */
CONST char *key; /* Key to use to find or create matching
* entry. */
int *newPtr; /* Store info here telling whether a new
* entry was created. */
{
panic("called Tcl_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(tablePtr)
register Tcl_HashTable *tablePtr; /* Table to enlarge. */
{
int oldSize, count, index;
Tcl_HashEntry **oldBuckets;
register Tcl_HashEntry **oldChainPtr, **newChainPtr;
register Tcl_HashEntry *hPtr;
oldSize = tablePtr->numBuckets;
oldBuckets = tablePtr->buckets;
/*
* Allocate and initialize the new bucket array, and set up
* hashing constants for new array size.
*/
tablePtr->numBuckets *= 4;
tablePtr->buckets = (Tcl_HashEntry **) ckalloc((unsigned)
(tablePtr->numBuckets * sizeof(Tcl_HashEntry *)));
for (count = tablePtr->numBuckets, newChainPtr = tablePtr->buckets;
count > 0; count--, newChainPtr++) {
*newChainPtr = NULL;
}
tablePtr->rebuildSize *= 4;
tablePtr->downShift -= 2;
tablePtr->mask = (tablePtr->mask << 2) + 3;
/*
* Rehash all of the existing entries into the new bucket array.
*/
for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) {
for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) {
*oldChainPtr = hPtr->nextPtr;
if (tablePtr->keyType == TCL_STRING_KEYS) {
index = HashString(hPtr->key.string) & tablePtr->mask;
} else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {
index = RANDOM_INDEX(tablePtr, hPtr->key.oneWordValue);
} else {
register int *iPtr;
int count;
for (index = 0, count = tablePtr->keyType,
iPtr = hPtr->key.words; count > 0; count--, iPtr++) {
index += *iPtr;
}
index = RANDOM_INDEX(tablePtr, index);
}
hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;
*hPtr->bucketPtr = hPtr;
}
}
/*
* Free up the old bucket array, if it was dynamically allocated.
*/
if (oldBuckets != tablePtr->staticBuckets) {
ckfree((char *) oldBuckets);
}
}