summaryrefslogtreecommitdiffstats
path: root/generic/tclHash.c
diff options
context:
space:
mode:
Diffstat (limited to 'generic/tclHash.c')
-rw-r--r--generic/tclHash.c921
1 files changed, 921 insertions, 0 deletions
diff --git a/generic/tclHash.c b/generic/tclHash.c
new file mode 100644
index 0000000..e20275a
--- /dev/null
+++ b/generic/tclHash.c
@@ -0,0 +1,921 @@
+/*
+ * 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);
+ }
+}