summaryrefslogtreecommitdiffstats
path: root/generic/tclHash.c
diff options
context:
space:
mode:
Diffstat (limited to 'generic/tclHash.c')
-rw-r--r--generic/tclHash.c1216
1 files changed, 621 insertions, 595 deletions
diff --git a/generic/tclHash.c b/generic/tclHash.c
index 3e8d0d8..0171216 100644
--- a/generic/tclHash.c
+++ b/generic/tclHash.c
@@ -10,19 +10,27 @@
* 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.6 2000/07/20 20:33:26 ericm Exp $
+ * RCS: @(#) $Id: tclHash.c,v 1.7 2000/07/22 01:53:24 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
@@ -35,32 +43,86 @@
(((((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:
*/
-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));
+#if TCL_PRESERVE_BINARY_COMPATABILITY
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));
+#endif
+
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));
-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));
+
+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 */
+};
+
/*
*----------------------------------------------------------------------
@@ -80,6 +142,7 @@ static Tcl_HashEntry * ObjCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr,
*----------------------------------------------------------------------
*/
+#undef Tcl_InitHashTable
void
Tcl_InitHashTable(tablePtr, keyType)
register Tcl_HashTable *tablePtr; /* Pointer to table record, which
@@ -88,8 +151,48 @@ 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_InitHashTable: TCL_SMALL_HASH_TABLE is %d, not 4\n",
+ panic("Tcl_InitHashTableEx: TCL_SMALL_HASH_TABLE is %d, not 4\n",
TCL_SMALL_HASH_TABLE);
#endif
@@ -102,19 +205,280 @@ Tcl_InitHashTable(tablePtr, keyType)
tablePtr->downShift = 28;
tablePtr->mask = 3;
tablePtr->keyType = keyType;
- 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;
+#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;
} else {
- tablePtr->findProc = ArrayFind;
- tablePtr->createProc = ArrayCreate;
- };
+ 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;
}
/*
@@ -141,11 +505,47 @@ 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 (*entryPtr->bucketPtr == entryPtr) {
- *entryPtr->bucketPtr = entryPtr->nextPtr;
+#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 {
- for (prevPtr = *entryPtr->bucketPtr; ; prevPtr = prevPtr->nextPtr) {
+ 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) {
if (prevPtr == NULL) {
panic("malformed bucket chain in Tcl_DeleteHashEntry");
}
@@ -155,12 +555,13 @@ Tcl_DeleteHashEntry(entryPtr)
}
}
}
-
- if (entryPtr->tablePtr->keyType == TCL_OBJ_KEYS) {
- Tcl_DecrRefCount (entryPtr->key.objPtr);
+
+ tablePtr->numEntries--;
+ if (typePtr->freeEntryProc) {
+ typePtr->freeEntryProc (entryPtr);
+ } else {
+ ckfree((char *) entryPtr);
}
- entryPtr->tablePtr->numEntries--;
- ckfree((char *) entryPtr);
}
/*
@@ -185,8 +586,24 @@ 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.
*/
@@ -195,10 +612,11 @@ Tcl_DeleteHashTable(tablePtr)
hPtr = tablePtr->buckets[i];
while (hPtr != NULL) {
nextPtr = hPtr->nextPtr;
- if (tablePtr->keyType == TCL_OBJ_KEYS) {
- Tcl_DecrRefCount (hPtr->key.objPtr);
+ if (typePtr->freeEntryProc) {
+ typePtr->freeEntryProc (hPtr);
+ } else {
+ ckfree((char *) hPtr);
}
- ckfree((char *) hPtr);
hPtr = nextPtr;
}
}
@@ -216,8 +634,12 @@ Tcl_DeleteHashTable(tablePtr)
* re-initialization.
*/
+#if TCL_PRESERVE_BINARY_COMPATABILITY
tablePtr->findProc = BogusFind;
tablePtr->createProc = BogusCreate;
+#else
+ tablePtr->typePtr = NULL;
+#endif
}
/*
@@ -370,14 +792,12 @@ Tcl_HashStats(tablePtr)
/*
*----------------------------------------------------------------------
*
- * HashString --
+ * AllocArrayEntry --
*
- * Compute a one-word summary of a text string, which can be
- * used to generate a hash index.
+ * Allocate space for a Tcl_HashEntry containing the array key.
*
* Results:
- * The return value is a one-word summary of the information in
- * string.
+ * The return value is a pointer to the created entry.
*
* Side effects:
* None.
@@ -385,52 +805,39 @@ Tcl_HashStats(tablePtr)
*----------------------------------------------------------------------
*/
-static unsigned int
-HashString(string)
- register CONST char *string;/* String from which to compute hash value. */
+static Tcl_HashEntry *
+AllocArrayEntry(tablePtr, keyPtr)
+ Tcl_HashTable *tablePtr; /* Hash table. */
+ VOID *keyPtr; /* Key to store in the hash table entry. */
{
- 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.
- */
+ int *array = (int *) keyPtr;
+ register int *iPtr1, *iPtr2;
+ Tcl_HashEntry *hPtr;
+ int count;
- result = 0;
- while (1) {
- c = *string;
- string++;
- if (c == 0) {
- break;
- }
- result += (result<<3) + 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;
}
- return result;
+
+ return hPtr;
}
/*
*----------------------------------------------------------------------
*
- * StringFind --
+ * CompareArrayKeys --
*
- * Given a hash table with string keys, and a string key, find
- * the entry with a matching key.
+ * Compares two array keys.
*
* Results:
- * The return value is a token for the matching entry in the
- * hash table, or NULL if there was no matching entry.
+ * The return value is 0 if they are different and 1 if they are
+ * the same.
*
* Side effects:
* None.
@@ -438,124 +845,38 @@ HashString(string)
*----------------------------------------------------------------------
*/
-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. */
+static int
+CompareArrayKeys(keyPtr, hPtr)
+ VOID *keyPtr; /* New key to compare. */
+ Tcl_HashEntry *hPtr; /* Existing key to compare. */
{
- 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;
- }
+ register CONST int *iPtr1 = (CONST int *) keyPtr;
+ register CONST int *iPtr2 = (CONST int *) hPtr->key.words;
+ Tcl_HashTable *tablePtr = hPtr->tablePtr;
+ int count;
+
+ for (count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
+ if (count == 0) {
+ return 1;
}
- }
- 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;
- }
+ if (*iPtr1 != *iPtr2) {
+ break;
}
}
-
- /*
- * 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;
+ return 0;
}
/*
*----------------------------------------------------------------------
*
- * OneWordFind --
+ * HashArrayKey --
*
- * Given a hash table with one-word keys, and a one-word key, find
- * the entry with a matching key.
+ * Compute a one-word summary of an array, which can be
+ * used to generate a hash index.
*
* Results:
- * The return value is a token for the matching entry in the
- * hash table, or NULL if there was no matching entry.
+ * The return value is a one-word summary of the information in
+ * string.
*
* Side effects:
* None.
@@ -563,111 +884,63 @@ StringCreate(tablePtr, key, newPtr)
*----------------------------------------------------------------------
*/
-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. */
+static unsigned int
+HashArrayKey(tablePtr, keyPtr)
+ Tcl_HashTable *tablePtr; /* Hash table. */
+ VOID *keyPtr; /* Key from which to compute hash value. */
{
- register Tcl_HashEntry *hPtr;
- int index;
-
- index = RANDOM_INDEX(tablePtr, key);
-
- /*
- * Search all of the entries in the appropriate bucket.
- */
+ register CONST int *array = (CONST int *) keyPtr;
+ register unsigned int result;
+ int count;
- for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
- hPtr = hPtr->nextPtr) {
- if (hPtr->key.oneWordValue == key) {
- return hPtr;
- }
+ for (result = 0, count = tablePtr->keyType; count > 0;
+ count--, array++) {
+ result += *array;
}
- return NULL;
+ return result;
}
/*
*----------------------------------------------------------------------
*
- * OneWordCreate --
+ * AllocStringEntry --
*
- * 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.
+ * Allocate space for a Tcl_HashEntry containing the string key.
*
* 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.
+ * The return value is a pointer to the created entry.
*
* Side effects:
- * A new entry may be added to the hash table.
+ * None.
*
*----------------------------------------------------------------------
*/
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. */
+AllocStringEntry(tablePtr, keyPtr)
+ Tcl_HashTable *tablePtr; /* Hash table. */
+ VOID *keyPtr; /* Key to store in the hash table entry. */
{
- 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++;
+ CONST char *string = (CONST char *) keyPtr;
+ Tcl_HashEntry *hPtr;
- /*
- * If the table has exceeded a decent size, rebuild it with many
- * more buckets.
- */
+ hPtr = (Tcl_HashEntry *) ckalloc((unsigned)
+ (sizeof(Tcl_HashEntry) + strlen(string) + 1 - sizeof(hPtr->key)));
+ strcpy(hPtr->key.string, string);
- if (tablePtr->numEntries >= tablePtr->rebuildSize) {
- RebuildTable(tablePtr);
- }
return hPtr;
}
/*
*----------------------------------------------------------------------
*
- * ArrayFind --
+ * CompareStringKeys --
*
- * Given a hash table with array-of-int keys, and a key, find
- * the entry with a matching key.
+ * Compares two string keys.
*
* Results:
- * The return value is a token for the matching entry in the
- * hash table, or NULL if there was no matching entry.
+ * The return value is 0 if they are different and 1 if they are
+ * the same.
*
* Side effects:
* None.
@@ -675,198 +948,36 @@ OneWordCreate(tablePtr, key, newPtr)
*----------------------------------------------------------------------
*/
-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. */
+static int
+CompareStringKeys(keyPtr, hPtr)
+ VOID *keyPtr; /* New key to compare. */
+ Tcl_HashEntry *hPtr; /* Existing key to compare. */
{
- 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);
+ register CONST char *p1 = (CONST char *) keyPtr;
+ register CONST char *p2 = (CONST char *) hPtr->key.string;
- /*
- * 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;
- }
+ for (;; p1++, p2++) {
+ if (*p1 != *p2) {
+ 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;
- }
+ if (*p1 == '\0') {
+ return 1;
}
}
-
- /*
- * 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;
+ return 0;
}
/*
*----------------------------------------------------------------------
*
- * BogusFind --
+ * HashStringKey --
*
- * 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.
+ * 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
- * the string representation of the Tcl_Obj.
+ * string.
*
* Side effects:
* None.
@@ -875,17 +986,14 @@ BogusCreate(tablePtr, key, newPtr)
*/
static unsigned int
-HashObj(objPtr)
- Tcl_Obj *objPtr;
+HashStringKey(tablePtr, keyPtr)
+ Tcl_HashTable *tablePtr; /* Hash table. */
+ VOID *keyPtr; /* Key from which to compute hash value. */
{
- register CONST char *string;
- register int length;
+ register CONST char *string = (CONST char *) keyPtr;
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,
@@ -903,11 +1011,10 @@ HashObj(objPtr)
*/
result = 0;
- while (length) {
+ while (1) {
c = *string;
string++;
- length--;
- if (length == 0) {
+ if (c == 0) {
break;
}
result += (result<<3) + c;
@@ -915,174 +1022,66 @@ HashObj(objPtr)
return result;
}
+#if TCL_PRESERVE_BINARY_COMPATABILITY
/*
*----------------------------------------------------------------------
*
- * ObjFind --
+ * BogusFind --
*
- * Given a hash table with string keys, and a string key, find
- * the entry with a matching key.
+ * This procedure is invoked when an Tcl_FindHashEntry is called
+ * on a table that has been deleted.
*
* Results:
- * The return value is a token for the matching entry in the
- * hash table, or NULL if there was no matching entry.
+ * If panic returns (which it shouldn't) this procedure returns
+ * NULL.
*
* Side effects:
- * None.
+ * Generates a panic.
*
*----------------------------------------------------------------------
*/
+ /* ARGSUSED */
static Tcl_HashEntry *
-ObjFind(tablePtr, key)
+BogusFind(tablePtr, key)
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */
CONST char *key; /* Key to use to find matching entry. */
{
- 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;
- }
- }
- }
+ panic("called Tcl_FindHashEntry on deleted table");
return NULL;
}
/*
*----------------------------------------------------------------------
*
- * ObjCreate --
+ * BogusCreate --
*
- * 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.
+ * This procedure is invoked when an Tcl_CreateHashEntry is called
+ * on a table that has been deleted.
*
* 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.
+ * If panic returns (which it shouldn't) this procedure returns
+ * NULL.
*
* Side effects:
- * A new entry may be added to the hash table.
+ * Generates a panic.
*
*----------------------------------------------------------------------
*/
+ /* ARGSUSED */
static Tcl_HashEntry *
-ObjCreate(tablePtr, key, newPtr)
+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. */
{
- 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;
+ panic("called Tcl_CreateHashEntry on deleted table");
+ return NULL;
}
+#endif
/*
*----------------------------------------------------------------------
@@ -1112,6 +1111,8 @@ 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;
@@ -1132,6 +1133,21 @@ 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.
*/
@@ -1139,25 +1155,35 @@ RebuildTable(tablePtr)
for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) {
for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) {
*oldChainPtr = hPtr->nextPtr;
- 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 {
- register int *iPtr;
- int count;
- for (index = 0, count = tablePtr->keyType,
- iPtr = hPtr->key.words; count > 0; count--, iPtr++) {
- index += *iPtr;
+ 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);
+ } 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;
}
- index = RANDOM_INDEX(tablePtr, index);
+ } else {
+ index = RANDOM_INDEX (tablePtr, key);
}
+
hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;
*hPtr->bucketPtr = hPtr;
+#endif
}
}