summaryrefslogtreecommitdiffstats
path: root/generic/tclHash.c
diff options
context:
space:
mode:
authorericm <ericm>2000-07-20 20:33:24 (GMT)
committerericm <ericm>2000-07-20 20:33:24 (GMT)
commitda5f5e103ac30d423291eaf59b1ae03f87457aa3 (patch)
tree80753558bda4dc4a3e717cdf00236a8659462bd0 /generic/tclHash.c
parenta3b08d83c4950ebd5fe493e21133368255026472 (diff)
downloadtcl-da5f5e103ac30d423291eaf59b1ae03f87457aa3.zip
tcl-da5f5e103ac30d423291eaf59b1ae03f87457aa3.tar.gz
tcl-da5f5e103ac30d423291eaf59b1ae03f87457aa3.tar.bz2
* generic/tclStubInit.c:
* generic/tclObj.c: * generic/tclInt.h: * generic/tclHash.c: * generic/tclDecls.h: * generic/tcl.h: * generic/tcl.decls: * doc/Hash.3: Reverted patch from Paul Duffin to extend hash tables to allow custom key types, such as Tcl_Obj *'s, and others; it seems to break Tk.
Diffstat (limited to 'generic/tclHash.c')
-rw-r--r--generic/tclHash.c1216
1 files changed, 595 insertions, 621 deletions
diff --git a/generic/tclHash.c b/generic/tclHash.c
index 026f730..3e8d0d8 100644
--- a/generic/tclHash.c
+++ b/generic/tclHash.c
@@ -10,27 +10,19 @@
* See the file "license.terms" for information on usage and redistribution
* of this file, and for a DISCLAIMER OF ALL WARRANTIES.
*
- * RCS: @(#) $Id: tclHash.c,v 1.5 2000/07/19 22:15:30 ericm Exp $
+ * RCS: @(#) $Id: tclHash.c,v 1.6 2000/07/20 20:33:26 ericm Exp $
*/
#include "tclInt.h"
/*
- * Prevent macros from clashing with function definitions.
- */
-
-#if TCL_PRESERVE_BINARY_COMPATABILITY
-# undef Tcl_FindHashEntry
-# undef Tcl_CreateHashEntry
-#endif
-
-/*
* 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
@@ -43,86 +35,32 @@
(((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask)
/*
- * Prototypes for the array hash key methods.
- */
-
-static Tcl_HashEntry * AllocArrayEntry _ANSI_ARGS_((
- Tcl_HashTable *tablePtr,
- VOID *keyPtr));
-static int CompareArrayKeys _ANSI_ARGS_((
- VOID *keyPtr, Tcl_HashEntry *hPtr));
-static unsigned int HashArrayKey _ANSI_ARGS_((
- Tcl_HashTable *tablePtr,
- VOID *keyPtr));
-
-/*
- * Prototypes for the one word hash key methods.
- */
-
-#if 0
-static Tcl_HashEntry * AllocOneWordEntry _ANSI_ARGS_((
- Tcl_HashTable *tablePtr,
- VOID *keyPtr));
-static int CompareOneWordKeys _ANSI_ARGS_((
- VOID *keyPtr, Tcl_HashEntry *hPtr));
-static unsigned int HashOneWordKey _ANSI_ARGS_((
- Tcl_HashTable *tablePtr,
-#endif VOID *keyPtr));
-
-
-/*
- * Prototypes for the string hash key methods.
- */
-
-static Tcl_HashEntry * AllocStringEntry _ANSI_ARGS_((
- Tcl_HashTable *tablePtr,
- VOID *keyPtr));
-static int CompareStringKeys _ANSI_ARGS_((
- VOID *keyPtr, Tcl_HashEntry *hPtr));
-static unsigned int HashStringKey _ANSI_ARGS_((
- Tcl_HashTable *tablePtr,
- VOID *keyPtr));
-
-/*
* Procedure prototypes for static procedures in this file:
*/
-#if TCL_PRESERVE_BINARY_COMPATABILITY
+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));
-#endif
-
+static unsigned int HashString _ANSI_ARGS_((CONST char *string));
static void RebuildTable _ANSI_ARGS_((Tcl_HashTable *tablePtr));
-
-Tcl_HashKeyType tclArrayHashKeyType = {
- TCL_HASH_KEY_TYPE_VERSION, /* version */
- TCL_HASH_KEY_RANDOMIZE_HASH, /* flags */
- HashArrayKey, /* hashKeyProc */
- CompareArrayKeys, /* compareKeysProc */
- AllocArrayEntry, /* allocEntryProc */
- NULL /* freeEntryProc */
-};
-
-Tcl_HashKeyType tclOneWordHashKeyType = {
- TCL_HASH_KEY_TYPE_VERSION, /* version */
- 0, /* flags */
- NULL, /* HashOneWordKey, */ /* hashProc */
- NULL, /* CompareOneWordKey, */ /* compareProc */
- NULL, /* AllocOneWordKey, */ /* allocEntryProc */
- NULL /* FreeOneWordKey, */ /* freeEntryProc */
-};
-
-Tcl_HashKeyType tclStringHashKeyType = {
- TCL_HASH_KEY_TYPE_VERSION, /* version */
- 0, /* flags */
- HashStringKey, /* hashKeyProc */
- CompareStringKeys, /* compareKeysProc */
- AllocStringEntry, /* allocEntryProc */
- NULL /* freeEntryProc */
-};
-
+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));
+static unsigned int HashObj _ANSI_ARGS_((Tcl_Obj *objPtr));
+static Tcl_HashEntry * ObjFind _ANSI_ARGS_((Tcl_HashTable *tablePtr,
+ CONST char *key));
+static Tcl_HashEntry * ObjCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr,
+ CONST char *key, int *newPtr));
/*
*----------------------------------------------------------------------
@@ -142,7 +80,6 @@ Tcl_HashKeyType tclStringHashKeyType = {
*----------------------------------------------------------------------
*/
-#undef Tcl_InitHashTable
void
Tcl_InitHashTable(tablePtr, keyType)
register Tcl_HashTable *tablePtr; /* Pointer to table record, which
@@ -151,48 +88,8 @@ Tcl_InitHashTable(tablePtr, keyType)
* TCL_STRING_KEYS, TCL_ONE_WORD_KEYS,
* or an integer >= 2. */
{
- /*
- * Use a special value to inform the extended version that it must
- * not access any of the new fields in the Tcl_HashTable. If an
- * extension is rebuilt then any calls to this function will be
- * redirected to the extended version by a macro.
- */
- Tcl_InitHashTableEx(tablePtr, keyType, (Tcl_HashKeyType *) -1);
-}
-
-/*
- *----------------------------------------------------------------------
- *
- * Tcl_InitHashTableEx --
- *
- * Given storage for a hash table, set up the fields to prepare
- * the hash table for use. This is an extended version of
- * Tcl_InitHashTableEx which supports user defined keys.
- *
- * Results:
- * None.
- *
- * Side effects:
- * TablePtr is now ready to be passed to Tcl_FindHashEntry and
- * Tcl_CreateHashEntry.
- *
- *----------------------------------------------------------------------
- */
-
-void
-Tcl_InitHashTableEx(tablePtr, keyType, typePtr)
- 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,
- * TCL_CUSTOM_TYPE_KEYS,
- * TCL_CUSTOM_PTR_KEYS, or an
- * integer >= 2. */
- Tcl_HashKeyType *typePtr; /* Pointer to structure which defines
- * the behaviour of this table. */
-{
#if (TCL_SMALL_HASH_TABLE != 4)
- panic("Tcl_InitHashTableEx: TCL_SMALL_HASH_TABLE is %d, not 4\n",
+ panic("Tcl_InitHashTable: TCL_SMALL_HASH_TABLE is %d, not 4\n",
TCL_SMALL_HASH_TABLE);
#endif
@@ -205,280 +102,19 @@ Tcl_InitHashTableEx(tablePtr, keyType, typePtr)
tablePtr->downShift = 28;
tablePtr->mask = 3;
tablePtr->keyType = keyType;
-#if TCL_PRESERVE_BINARY_COMPATABILITY
- tablePtr->findProc = Tcl_FindHashEntry;
- tablePtr->createProc = Tcl_CreateHashEntry;
-
- if (typePtr == NULL) {
- /*
- * The caller has been rebuilt so the hash table is an extended
- * version.
- */
- } else if (typePtr != (Tcl_HashKeyType *) -1) {
- /*
- * The caller is requesting a customized hash table so it must be
- * an extended version.
- */
- tablePtr->typePtr = typePtr;
- } else {
- /*
- * The caller has not been rebuilt so the hash table is not
- * extended.
- */
- }
-#else
- if (typePtr == NULL) {
- /*
- * Use the key type to decide which key type is needed.
- */
- if (keyType == TCL_STRING_KEYS) {
- typePtr = &tclStringHashKeyType;
- } else if (keyType == TCL_ONE_WORD_KEYS) {
- typePtr = &tclOneWordHashKeyType;
- } else if (keyType == TCL_CUSTOM_TYPE_KEYS) {
- Tcl_Panic ("No type structure specified for TCL_CUSTOM_TYPE_KEYS");
- } else if (keyType == TCL_CUSTOM_PTR_KEYS) {
- Tcl_Panic ("No type structure specified for TCL_CUSTOM_PTR_KEYS");
- } else {
- typePtr = &tclArrayHashKeyType;
- }
- } else if (typePtr == (Tcl_HashKeyType *) -1) {
- /*
- * If the caller has not been rebuilt then we cannot continue as
- * the hash table is not an extended version.
- */
- Tcl_Panic ("Hash table is not compatible");
- }
- tablePtr->typePtr = typePtr;
-#endif
-}
-
-/*
- *----------------------------------------------------------------------
- *
- * Tcl_FindHashEntry --
- *
- * Given a hash table 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.
- *
- *----------------------------------------------------------------------
- */
-
-Tcl_HashEntry *
-Tcl_FindHashEntry(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;
- Tcl_HashKeyType *typePtr;
- unsigned int hash;
- int index;
-
-#if TCL_PRESERVE_BINARY_COMPATABILITY
- if (tablePtr->keyType == TCL_STRING_KEYS) {
- typePtr = &tclStringHashKeyType;
- } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {
- typePtr = &tclOneWordHashKeyType;
- } else if (tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
- || tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
- typePtr = tablePtr->typePtr;
+ if (keyType == TCL_OBJ_KEYS) {
+ tablePtr->findProc = ObjFind;
+ tablePtr->createProc = ObjCreate;
+ } else 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 {
- typePtr = &tclArrayHashKeyType;
- }
-#else
- typePtr = tablePtr->typePtr;
- if (typePtr == NULL) {
- Tcl_Panic("called Tcl_FindHashEntry on deleted table");
- return NULL;
- }
-#endif
-
- if (typePtr->hashKeyProc) {
- hash = typePtr->hashKeyProc (tablePtr, (VOID *) key);
- if (typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
- index = RANDOM_INDEX (tablePtr, hash);
- } else {
- index = hash & tablePtr->mask;
- }
- } else {
- hash = (unsigned int) key;
- index = RANDOM_INDEX (tablePtr, hash);
- }
-
- /*
- * Search all of the entries in the appropriate bucket.
- */
-
- if (typePtr->compareKeysProc) {
- for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
- hPtr = hPtr->nextPtr) {
-#if TCL_HASH_KEY_STORE_HASH
- if (hash != (unsigned int) hPtr->hash) {
- continue;
- }
-#endif
- if (typePtr->compareKeysProc ((VOID *) key, hPtr)) {
- return hPtr;
- }
- }
- } else {
- for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
- hPtr = hPtr->nextPtr) {
-#if TCL_HASH_KEY_STORE_HASH
- if (hash != (unsigned int) hPtr->hash) {
- continue;
- }
-#endif
- if (key == hPtr->key.oneWordValue) {
- return hPtr;
- }
- }
- }
-
- return NULL;
-}
-
-/*
- *----------------------------------------------------------------------
- *
- * Tcl_CreateHashEntry --
- *
- * 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.
- *
- *----------------------------------------------------------------------
- */
-
-Tcl_HashEntry *
-Tcl_CreateHashEntry(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;
- Tcl_HashKeyType *typePtr;
- unsigned int hash;
- int index;
-
-#if TCL_PRESERVE_BINARY_COMPATABILITY
- if (tablePtr->keyType == TCL_STRING_KEYS) {
- typePtr = &tclStringHashKeyType;
- } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {
- typePtr = &tclOneWordHashKeyType;
- } else if (tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
- || tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
- typePtr = tablePtr->typePtr;
- } else {
- typePtr = &tclArrayHashKeyType;
- }
-#else
- typePtr = tablePtr->typePtr;
- if (typePtr == NULL) {
- Tcl_Panic("called Tcl_CreateHashEntry on deleted table");
- return NULL;
- }
-#endif
-
- if (typePtr->hashKeyProc) {
- hash = typePtr->hashKeyProc (tablePtr, (VOID *) key);
- if (typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
- index = RANDOM_INDEX (tablePtr, hash);
- } else {
- index = hash & tablePtr->mask;
- }
- } else {
- hash = (unsigned int) key;
- index = RANDOM_INDEX (tablePtr, hash);
- }
-
- /*
- * Search all of the entries in the appropriate bucket.
- */
-
- if (typePtr->compareKeysProc) {
- for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
- hPtr = hPtr->nextPtr) {
-#if TCL_HASH_KEY_STORE_HASH
- if (hash != (unsigned int) hPtr->hash) {
- continue;
- }
-#endif
- if (typePtr->compareKeysProc ((VOID *) key, hPtr)) {
- *newPtr = 0;
- return hPtr;
- }
- }
- } else {
- for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
- hPtr = hPtr->nextPtr) {
-#if TCL_HASH_KEY_STORE_HASH
- if (hash != (unsigned int) hPtr->hash) {
- continue;
- }
-#endif
- if (key == hPtr->key.oneWordValue) {
- *newPtr = 0;
- return hPtr;
- }
- }
- }
-
- /*
- * Entry not found. Add a new one to the bucket.
- */
-
- *newPtr = 1;
- if (typePtr->allocEntryProc) {
- hPtr = typePtr->allocEntryProc (tablePtr, (VOID *) key);
- } else {
- hPtr = (Tcl_HashEntry *) ckalloc((unsigned) sizeof(Tcl_HashEntry));
- hPtr->key.oneWordValue = (char *) key;
- }
-
- hPtr->tablePtr = tablePtr;
-#if TCL_HASH_KEY_STORE_HASH
-# if TCL_PRESERVE_BINARY_COMPATABILITY
- hPtr->hash = (VOID *) hash;
-# else
- hPtr->hash = hash;
-# endif
- hPtr->nextPtr = tablePtr->buckets[index];
- tablePtr->buckets[index] = hPtr;
-#else
- hPtr->bucketPtr = &(tablePtr->buckets[index]);
- hPtr->nextPtr = *hPtr->bucketPtr;
- *hPtr->bucketPtr = hPtr;
-#endif
- hPtr->clientData = 0;
- 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;
+ tablePtr->findProc = ArrayFind;
+ tablePtr->createProc = ArrayCreate;
+ };
}
/*
@@ -505,47 +141,11 @@ Tcl_DeleteHashEntry(entryPtr)
Tcl_HashEntry *entryPtr;
{
register Tcl_HashEntry *prevPtr;
- Tcl_HashKeyType *typePtr;
- Tcl_HashTable *tablePtr;
- Tcl_HashEntry **bucketPtr;
-#if TCL_HASH_KEY_STORE_HASH
- int index;
-#endif
-
- tablePtr = entryPtr->tablePtr;
-#if TCL_PRESERVE_BINARY_COMPATABILITY
- if (tablePtr->keyType == TCL_STRING_KEYS) {
- typePtr = &tclStringHashKeyType;
- } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {
- typePtr = &tclOneWordHashKeyType;
- } else if (tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
- || tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
- typePtr = tablePtr->typePtr;
+ if (*entryPtr->bucketPtr == entryPtr) {
+ *entryPtr->bucketPtr = entryPtr->nextPtr;
} else {
- typePtr = &tclArrayHashKeyType;
- }
-#else
- typePtr = tablePtr->typePtr;
-#endif
-
-#if TCL_HASH_KEY_STORE_HASH
- if (typePtr->hashKeyProc == NULL
- || typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
- index = RANDOM_INDEX (tablePtr, entryPtr->hash);
- } else {
- index = ((unsigned int) entryPtr->hash) & tablePtr->mask;
- }
-
- bucketPtr = &(tablePtr->buckets[index]);
-#else
- bucketPtr = entryPtr->bucketPtr;
-#endif
-
- if (*bucketPtr == entryPtr) {
- *bucketPtr = entryPtr->nextPtr;
- } else {
- for (prevPtr = *bucketPtr; ; prevPtr = prevPtr->nextPtr) {
+ for (prevPtr = *entryPtr->bucketPtr; ; prevPtr = prevPtr->nextPtr) {
if (prevPtr == NULL) {
panic("malformed bucket chain in Tcl_DeleteHashEntry");
}
@@ -555,13 +155,12 @@ Tcl_DeleteHashEntry(entryPtr)
}
}
}
-
- tablePtr->numEntries--;
- if (typePtr->freeEntryProc) {
- typePtr->freeEntryProc (entryPtr);
- } else {
- ckfree((char *) entryPtr);
+
+ if (entryPtr->tablePtr->keyType == TCL_OBJ_KEYS) {
+ Tcl_DecrRefCount (entryPtr->key.objPtr);
}
+ entryPtr->tablePtr->numEntries--;
+ ckfree((char *) entryPtr);
}
/*
@@ -586,24 +185,8 @@ Tcl_DeleteHashTable(tablePtr)
register Tcl_HashTable *tablePtr; /* Table to delete. */
{
register Tcl_HashEntry *hPtr, *nextPtr;
- Tcl_HashKeyType *typePtr;
int i;
-#if TCL_PRESERVE_BINARY_COMPATABILITY
- if (tablePtr->keyType == TCL_STRING_KEYS) {
- typePtr = &tclStringHashKeyType;
- } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {
- typePtr = &tclOneWordHashKeyType;
- } else if (tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
- || tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
- typePtr = tablePtr->typePtr;
- } else {
- typePtr = &tclArrayHashKeyType;
- }
-#else
- typePtr = tablePtr->typePtr;
-#endif
-
/*
* Free up all the entries in the table.
*/
@@ -612,11 +195,10 @@ Tcl_DeleteHashTable(tablePtr)
hPtr = tablePtr->buckets[i];
while (hPtr != NULL) {
nextPtr = hPtr->nextPtr;
- if (typePtr->freeEntryProc) {
- typePtr->freeEntryProc (hPtr);
- } else {
- ckfree((char *) hPtr);
+ if (tablePtr->keyType == TCL_OBJ_KEYS) {
+ Tcl_DecrRefCount (hPtr->key.objPtr);
}
+ ckfree((char *) hPtr);
hPtr = nextPtr;
}
}
@@ -634,12 +216,8 @@ Tcl_DeleteHashTable(tablePtr)
* re-initialization.
*/
-#if TCL_PRESERVE_BINARY_COMPATABILITY
tablePtr->findProc = BogusFind;
tablePtr->createProc = BogusCreate;
-#else
- tablePtr->typePtr = NULL;
-#endif
}
/*
@@ -792,12 +370,14 @@ Tcl_HashStats(tablePtr)
/*
*----------------------------------------------------------------------
*
- * AllocArrayEntry --
+ * HashString --
*
- * Allocate space for a Tcl_HashEntry containing the array key.
+ * Compute a one-word summary of a text string, which can be
+ * used to generate a hash index.
*
* Results:
- * The return value is a pointer to the created entry.
+ * The return value is a one-word summary of the information in
+ * string.
*
* Side effects:
* None.
@@ -805,39 +385,52 @@ Tcl_HashStats(tablePtr)
*----------------------------------------------------------------------
*/
-static Tcl_HashEntry *
-AllocArrayEntry(tablePtr, keyPtr)
- Tcl_HashTable *tablePtr; /* Hash table. */
- VOID *keyPtr; /* Key to store in the hash table entry. */
+static unsigned int
+HashString(string)
+ register CONST char *string;/* String from which to compute hash value. */
{
- int *array = (int *) keyPtr;
- register int *iPtr1, *iPtr2;
- Tcl_HashEntry *hPtr;
- int count;
+ register unsigned int result;
+ register int c;
- count = tablePtr->keyType;
-
- hPtr = (Tcl_HashEntry *) ckalloc((unsigned) (sizeof(Tcl_HashEntry)
- + (count*sizeof(int)) - sizeof(hPtr->key)));
-
- for (iPtr1 = array, iPtr2 = hPtr->key.words;
- count > 0; count--, iPtr1++, iPtr2++) {
- *iPtr2 = *iPtr1;
- }
+ /*
+ * 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.
+ */
- return hPtr;
+ result = 0;
+ while (1) {
+ c = *string;
+ string++;
+ if (c == 0) {
+ break;
+ }
+ result += (result<<3) + c;
+ }
+ return result;
}
/*
*----------------------------------------------------------------------
*
- * CompareArrayKeys --
+ * StringFind --
*
- * Compares two array keys.
+ * Given a hash table with string keys, and a string key, find
+ * the entry with a matching key.
*
* Results:
- * The return value is 0 if they are different and 1 if they are
- * the same.
+ * 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.
@@ -845,38 +438,124 @@ AllocArrayEntry(tablePtr, keyPtr)
*----------------------------------------------------------------------
*/
-static int
-CompareArrayKeys(keyPtr, hPtr)
- VOID *keyPtr; /* New key to compare. */
- Tcl_HashEntry *hPtr; /* Existing key to compare. */
+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 CONST char *iPtr1 = (CONST char *) keyPtr;
- register CONST char *iPtr2 = (CONST char *) hPtr->key.words;
- Tcl_HashTable *tablePtr = hPtr->tablePtr;
- int count;
-
- for (count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
- if (count == 0) {
- return 1;
+ 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;
+ }
}
- if (*iPtr1 != *iPtr2) {
- break;
+ }
+ 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;
+ }
}
}
- return 0;
+
+ /*
+ * 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;
}
/*
*----------------------------------------------------------------------
*
- * HashArrayKey --
+ * OneWordFind --
*
- * Compute a one-word summary of an array, which can be
- * used to generate a hash index.
+ * 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 one-word summary of the information in
- * string.
+ * 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.
@@ -884,63 +563,111 @@ CompareArrayKeys(keyPtr, hPtr)
*----------------------------------------------------------------------
*/
-static unsigned int
-HashArrayKey(tablePtr, keyPtr)
- Tcl_HashTable *tablePtr; /* Hash table. */
- VOID *keyPtr; /* Key from which to compute hash value. */
+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 CONST char *array = (CONST char *) keyPtr;
- register unsigned int result;
- int count;
+ register Tcl_HashEntry *hPtr;
+ int index;
+
+ index = RANDOM_INDEX(tablePtr, key);
- for (result = 0, count = tablePtr->keyType; count > 0;
- count--, array++) {
- result += *array;
+ /*
+ * 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 result;
+ return NULL;
}
/*
*----------------------------------------------------------------------
*
- * AllocStringEntry --
+ * OneWordCreate --
*
- * Allocate space for a Tcl_HashEntry containing the string key.
+ * 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 created entry.
+ * 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:
- * None.
+ * A new entry may be added to the hash table.
*
*----------------------------------------------------------------------
*/
static Tcl_HashEntry *
-AllocStringEntry(tablePtr, keyPtr)
- Tcl_HashTable *tablePtr; /* Hash table. */
- VOID *keyPtr; /* Key to store in the hash table entry. */
+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. */
{
- CONST char *string = (CONST char *) keyPtr;
- Tcl_HashEntry *hPtr;
+ register Tcl_HashEntry *hPtr;
+ int index;
- hPtr = (Tcl_HashEntry *) ckalloc((unsigned)
- (sizeof(Tcl_HashEntry) + strlen(string) + 1 - sizeof(hPtr->key)));
- strcpy(hPtr->key.string, string);
+ 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;
}
/*
*----------------------------------------------------------------------
*
- * CompareStringKeys --
+ * ArrayFind --
*
- * Compares two string keys.
+ * Given a hash table with array-of-int keys, and a key, find
+ * the entry with a matching key.
*
* Results:
- * The return value is 0 if they are different and 1 if they are
- * the same.
+ * 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.
@@ -948,36 +675,198 @@ AllocStringEntry(tablePtr, keyPtr)
*----------------------------------------------------------------------
*/
-static int
-CompareStringKeys(keyPtr, hPtr)
- VOID *keyPtr; /* New key to compare. */
- Tcl_HashEntry *hPtr; /* Existing key to compare. */
+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 CONST char *p1 = (CONST char *) keyPtr;
- register CONST char *p2 = (CONST char *) hPtr->key.string;
+ register Tcl_HashEntry *hPtr;
+ int *arrayPtr = (int *) key;
+ register int *iPtr1, *iPtr2;
+ int index, count;
- for (;; p1++, p2++) {
- if (*p1 != *p2) {
- break;
+ 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;
+ }
}
- if (*p1 == '\0') {
- return 1;
+ }
+ 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;
+ }
}
}
- return 0;
+
+ /*
+ * 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;
}
/*
*----------------------------------------------------------------------
*
- * HashStringKey --
+ * BogusFind --
*
- * Compute a one-word summary of a text string, which can be
- * used to generate a hash index.
+ * 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;
+}
+
+/*
+ *----------------------------------------------------------------------
+ *
+ * HashObj --
+ *
+ * Compute a one-word summary of the string representation of the
+ * Tcl_Obj, which can be used to generate a hash index.
*
* Results:
* The return value is a one-word summary of the information in
- * string.
+ * the string representation of the Tcl_Obj.
*
* Side effects:
* None.
@@ -986,14 +875,17 @@ CompareStringKeys(keyPtr, hPtr)
*/
static unsigned int
-HashStringKey(tablePtr, keyPtr)
- Tcl_HashTable *tablePtr; /* Hash table. */
- VOID *keyPtr; /* Key from which to compute hash value. */
+HashObj(objPtr)
+ Tcl_Obj *objPtr;
{
- register CONST char *string = (CONST char *) keyPtr;
+ register CONST char *string;
+ register int length;
register unsigned int result;
register int c;
+ string = Tcl_GetStringFromObj (objPtr, NULL);
+ length = objPtr->length;
+
/*
* I tried a zillion different hash functions and asked many other
* people for advice. Many people had their own favorite functions,
@@ -1011,10 +903,11 @@ HashStringKey(tablePtr, keyPtr)
*/
result = 0;
- while (1) {
+ while (length) {
c = *string;
string++;
- if (c == 0) {
+ length--;
+ if (length == 0) {
break;
}
result += (result<<3) + c;
@@ -1022,66 +915,174 @@ HashStringKey(tablePtr, keyPtr)
return result;
}
-#if TCL_PRESERVE_BINARY_COMPATABILITY
/*
*----------------------------------------------------------------------
*
- * BogusFind --
+ * ObjFind --
*
- * This procedure is invoked when an Tcl_FindHashEntry is called
- * on a table that has been deleted.
+ * Given a hash table with string keys, and a string key, find
+ * the entry with a matching key.
*
* Results:
- * If panic returns (which it shouldn't) this procedure returns
- * NULL.
+ * The return value is a token for the matching entry in the
+ * hash table, or NULL if there was no matching entry.
*
* Side effects:
- * Generates a panic.
+ * None.
*
*----------------------------------------------------------------------
*/
- /* ARGSUSED */
static Tcl_HashEntry *
-BogusFind(tablePtr, key)
+ObjFind(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");
+ Tcl_Obj *objPtr = (Tcl_Obj *) key;
+ register Tcl_HashEntry *hPtr;
+ register CONST char *p1, *p2;
+ register int l1, l2;
+ int index;
+
+ index = HashObj(objPtr) & tablePtr->mask;
+
+ /*
+ * Search all of the entries in the appropriate bucket.
+ */
+
+ for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
+ hPtr = hPtr->nextPtr) {
+ /*
+ * If the object pointers are the same then they match.
+ */
+ if (objPtr == hPtr->key.objPtr) {
+ return hPtr;
+ }
+
+ p1 = Tcl_GetStringFromObj (objPtr, (int *) 0);
+ l1 = objPtr->length;
+ p2 = Tcl_GetStringFromObj (hPtr->key.objPtr, (int *) 0);
+ l2 = hPtr->key.objPtr->length;
+
+ /*
+ * If the lengths are different then they do not match.
+ */
+ if (l1 != l2) {
+ continue;
+ }
+
+ for (;; p1++, p2++, l1--) {
+ if (*p1 != *p2) {
+ break;
+ }
+ if (l1 == 0) {
+ return hPtr;
+ }
+ }
+ }
return NULL;
}
/*
*----------------------------------------------------------------------
*
- * BogusCreate --
+ * ObjCreate --
*
- * This procedure is invoked when an Tcl_CreateHashEntry is called
- * on a table that has been deleted.
+ * 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:
- * If panic returns (which it shouldn't) this procedure returns
- * NULL.
+ * 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:
- * Generates a panic.
+ * A new entry may be added to the hash table.
*
*----------------------------------------------------------------------
*/
- /* ARGSUSED */
static Tcl_HashEntry *
-BogusCreate(tablePtr, key, newPtr)
+ObjCreate(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;
+ Tcl_Obj *objPtr = (Tcl_Obj *) key;
+ register Tcl_HashEntry *hPtr;
+ register CONST char *p1, *p2;
+ register int l1, l2;
+ int index;
+
+ index = HashObj(objPtr) & tablePtr->mask;
+
+ /*
+ * Search all of the entries in this bucket.
+ */
+
+ for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
+ hPtr = hPtr->nextPtr) {
+ /*
+ * If the object pointers are the same then they match.
+ */
+ if (objPtr == hPtr->key.objPtr) {
+ *newPtr = 0;
+ return hPtr;
+ }
+
+ p1 = Tcl_GetStringFromObj (objPtr, (int *) 0);
+ l1 = objPtr->length;
+ p2 = Tcl_GetStringFromObj (hPtr->key.objPtr, (int *) 0);
+ l2 = hPtr->key.objPtr->length;
+
+ /*
+ * If the lengths are different then they do not match.
+ */
+ if (l1 != l2) {
+ continue;
+ }
+
+ for (;; p1++, p2++, l1--) {
+ if (*p1 != *p2) {
+ break;
+ }
+ if (l1 == 0) {
+ *newPtr = 0;
+ return hPtr;
+ }
+ }
+ }
+
+ /*
+ * Entry not found. Add a new one to the bucket.
+ */
+
+ *newPtr = 1;
+ hPtr = (Tcl_HashEntry *)
+ Tcl_Alloc((unsigned) sizeof(Tcl_HashEntry));
+ hPtr->tablePtr = tablePtr;
+ hPtr->bucketPtr = &(tablePtr->buckets[index]);
+ hPtr->nextPtr = *hPtr->bucketPtr;
+ hPtr->clientData = 0;
+ hPtr->key.objPtr = objPtr;
+ Tcl_IncrRefCount (objPtr);
+ *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;
}
-#endif
/*
*----------------------------------------------------------------------
@@ -1111,8 +1112,6 @@ RebuildTable(tablePtr)
Tcl_HashEntry **oldBuckets;
register Tcl_HashEntry **oldChainPtr, **newChainPtr;
register Tcl_HashEntry *hPtr;
- Tcl_HashKeyType *typePtr;
- VOID *key;
oldSize = tablePtr->numBuckets;
oldBuckets = tablePtr->buckets;
@@ -1133,21 +1132,6 @@ RebuildTable(tablePtr)
tablePtr->downShift -= 2;
tablePtr->mask = (tablePtr->mask << 2) + 3;
-#if TCL_PRESERVE_BINARY_COMPATABILITY
- if (tablePtr->keyType == TCL_STRING_KEYS) {
- typePtr = &tclStringHashKeyType;
- } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {
- typePtr = &tclOneWordHashKeyType;
- } else if (tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
- || tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
- typePtr = tablePtr->typePtr;
- } else {
- typePtr = &tclArrayHashKeyType;
- }
-#else
- typePtr = tablePtr->typePtr;
-#endif
-
/*
* Rehash all of the existing entries into the new bucket array.
*/
@@ -1155,35 +1139,25 @@ RebuildTable(tablePtr)
for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) {
for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) {
*oldChainPtr = hPtr->nextPtr;
-
- key = (VOID *) Tcl_GetHashKey (tablePtr, hPtr);
-
-#if TCL_HASH_KEY_STORE_HASH
- if (typePtr->hashKeyProc == NULL
- || typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
- index = RANDOM_INDEX (tablePtr, hPtr->hash);
+ if (tablePtr->keyType == TCL_OBJ_KEYS) {
+ index = HashObj(hPtr->key.objPtr) & tablePtr->mask;
+ } else 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 {
- index = ((unsigned int) hPtr->hash) & tablePtr->mask;
- }
- hPtr->nextPtr = tablePtr->buckets[index];
- tablePtr->buckets[index] = hPtr;
-#else
- if (typePtr->hashKeyProc) {
- unsigned int hash;
- hash = typePtr->hashKeyProc (tablePtr, (VOID *) key);
- if (typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
- index = RANDOM_INDEX (tablePtr, hash);
- } else {
- index = hash & tablePtr->mask;
+ register int *iPtr;
+ int count;
+
+ for (index = 0, count = tablePtr->keyType,
+ iPtr = hPtr->key.words; count > 0; count--, iPtr++) {
+ index += *iPtr;
}
- } else {
- index = RANDOM_INDEX (tablePtr, key);
+ index = RANDOM_INDEX(tablePtr, index);
}
-
hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;
*hPtr->bucketPtr = hPtr;
-#endif
}
}