summaryrefslogtreecommitdiffstats
path: root/generic/tclHash.c
diff options
context:
space:
mode:
Diffstat (limited to 'generic/tclHash.c')
-rw-r--r--generic/tclHash.c196
1 files changed, 116 insertions, 80 deletions
diff --git a/generic/tclHash.c b/generic/tclHash.c
index 78ad514..256b073 100644
--- a/generic/tclHash.c
+++ b/generic/tclHash.c
@@ -35,27 +35,25 @@
*/
#define RANDOM_INDEX(tablePtr, i) \
- ((((i)*1103515245L) >> (tablePtr)->downShift) & (tablePtr)->mask)
+ (((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask)
/*
* Prototypes for the array hash key methods.
*/
-static Tcl_HashEntry * AllocArrayEntry(Tcl_HashTable *tablePtr, void *keyPtr);
-static int CompareArrayKeys(void *keyPtr, Tcl_HashEntry *hPtr);
-static TCL_HASH_TYPE HashArrayKey(Tcl_HashTable *tablePtr, void *keyPtr);
+static Tcl_HashEntry * AllocArrayEntry(Tcl_HashTable *tablePtr, VOID *keyPtr);
+static int CompareArrayKeys(VOID *keyPtr, Tcl_HashEntry *hPtr);
+static unsigned int HashArrayKey(Tcl_HashTable *tablePtr, VOID *keyPtr);
/*
- * Prototypes for the one word hash key methods. Not actually declared because
- * this is a critical path that is implemented in the core hash table access
- * function.
+ * Prototypes for the one word hash key methods.
*/
#if 0
static Tcl_HashEntry * AllocOneWordEntry(Tcl_HashTable *tablePtr,
- void *keyPtr);
-static int CompareOneWordKeys(void *keyPtr, Tcl_HashEntry *hPtr);
-static unsigned int HashOneWordKey(Tcl_HashTable *tablePtr, void *keyPtr);
+ VOID *keyPtr);
+static int CompareOneWordKeys(VOID *keyPtr, Tcl_HashEntry *hPtr);
+static unsigned int HashOneWordKey(Tcl_HashTable *tablePtr, VOID *keyPtr);
#endif
/*
@@ -63,9 +61,9 @@ static unsigned int HashOneWordKey(Tcl_HashTable *tablePtr, void *keyPtr);
*/
static Tcl_HashEntry * AllocStringEntry(Tcl_HashTable *tablePtr,
- void *keyPtr);
-static int CompareStringKeys(void *keyPtr, Tcl_HashEntry *hPtr);
-static TCL_HASH_TYPE HashStringKey(Tcl_HashTable *tablePtr, void *keyPtr);
+ VOID *keyPtr);
+static int CompareStringKeys(VOID *keyPtr, Tcl_HashEntry *hPtr);
+static unsigned int HashStringKey(Tcl_HashTable *tablePtr, VOID *keyPtr);
/*
* Function prototypes for static functions in this file:
@@ -79,7 +77,7 @@ static Tcl_HashEntry * CreateHashEntry(Tcl_HashTable *tablePtr, const char *key,
static Tcl_HashEntry * FindHashEntry(Tcl_HashTable *tablePtr, const char *key);
static void RebuildTable(Tcl_HashTable *tablePtr);
-const Tcl_HashKeyType tclArrayHashKeyType = {
+Tcl_HashKeyType tclArrayHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION, /* version */
TCL_HASH_KEY_RANDOMIZE_HASH, /* flags */
HashArrayKey, /* hashKeyProc */
@@ -88,7 +86,7 @@ const Tcl_HashKeyType tclArrayHashKeyType = {
NULL /* freeEntryProc */
};
-const Tcl_HashKeyType tclOneWordHashKeyType = {
+Tcl_HashKeyType tclOneWordHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION, /* version */
0, /* flags */
NULL, /* HashOneWordKey, */ /* hashProc */
@@ -97,7 +95,7 @@ const Tcl_HashKeyType tclOneWordHashKeyType = {
NULL /* FreeOneWordKey, */ /* freeEntryProc */
};
-const Tcl_HashKeyType tclStringHashKeyType = {
+Tcl_HashKeyType tclStringHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION, /* version */
0, /* flags */
HashStringKey, /* hashKeyProc */
@@ -124,6 +122,7 @@ const Tcl_HashKeyType tclStringHashKeyType = {
*----------------------------------------------------------------------
*/
+#undef Tcl_InitHashTable
void
Tcl_InitHashTable(
register Tcl_HashTable *tablePtr,
@@ -140,7 +139,7 @@ Tcl_InitHashTable(
* extended version by a macro.
*/
- Tcl_InitCustomHashTable(tablePtr, keyType, (const Tcl_HashKeyType *) -1);
+ Tcl_InitCustomHashTable(tablePtr, keyType, (Tcl_HashKeyType *) -1);
}
/*
@@ -171,7 +170,7 @@ Tcl_InitCustomHashTable(
* TCL_STRING_KEYS, TCL_ONE_WORD_KEYS,
* TCL_CUSTOM_TYPE_KEYS, TCL_CUSTOM_PTR_KEYS,
* or an integer >= 2. */
- const Tcl_HashKeyType *typePtr) /* Pointer to structure which defines the
+ Tcl_HashKeyType *typePtr) /* Pointer to structure which defines the
* behaviour of this table. */
{
#if (TCL_SMALL_HASH_TABLE != 4)
@@ -230,7 +229,7 @@ Tcl_InitCustomHashTable(
Tcl_HashEntry *
Tcl_FindHashEntry(
Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */
- const void *key) /* Key to use to find matching entry. */
+ const char *key) /* Key to use to find matching entry. */
{
return (*((tablePtr)->findProc))(tablePtr, key);
}
@@ -268,7 +267,7 @@ FindHashEntry(
Tcl_HashEntry *
Tcl_CreateHashEntry(
Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */
- const void *key, /* Key to use to find or create matching
+ const char *key, /* Key to use to find or create matching
* entry. */
int *newPtr) /* Store info here telling whether a new entry
* was created. */
@@ -301,15 +300,15 @@ CreateHashEntry(
}
if (typePtr->hashKeyProc) {
- hash = typePtr->hashKeyProc(tablePtr, (void *) key);
+ hash = typePtr->hashKeyProc(tablePtr, (VOID *) key);
if (typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
- index = RANDOM_INDEX(tablePtr, hash);
+ index = RANDOM_INDEX (tablePtr, hash);
} else {
index = hash & tablePtr->mask;
}
} else {
hash = PTR2UINT(key);
- index = RANDOM_INDEX(tablePtr, hash);
+ index = RANDOM_INDEX (tablePtr, hash);
}
/*
@@ -318,13 +317,14 @@ CreateHashEntry(
if (typePtr->compareKeysProc) {
Tcl_CompareHashKeysProc *compareKeysProc = typePtr->compareKeysProc;
-
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {
+#if TCL_HASH_KEY_STORE_HASH
if (hash != PTR2UINT(hPtr->hash)) {
continue;
}
- if (((void *) key == hPtr) || compareKeysProc((void *) key, hPtr)) {
+#endif
+ if (compareKeysProc((VOID *) key, hPtr)) {
if (newPtr) {
*newPtr = 0;
}
@@ -334,9 +334,11 @@ CreateHashEntry(
} else {
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {
+#if TCL_HASH_KEY_STORE_HASH
if (hash != PTR2UINT(hPtr->hash)) {
continue;
}
+#endif
if (key == hPtr->key.oneWordValue) {
if (newPtr) {
*newPtr = 0;
@@ -356,17 +358,23 @@ CreateHashEntry(
*newPtr = 1;
if (typePtr->allocEntryProc) {
- hPtr = typePtr->allocEntryProc(tablePtr, (void *) key);
+ hPtr = typePtr->allocEntryProc(tablePtr, (VOID *) key);
} else {
- hPtr = ckalloc(sizeof(Tcl_HashEntry));
+ hPtr = (Tcl_HashEntry *) ckalloc((unsigned) sizeof(Tcl_HashEntry));
hPtr->key.oneWordValue = (char *) key;
hPtr->clientData = 0;
}
hPtr->tablePtr = tablePtr;
+#if TCL_HASH_KEY_STORE_HASH
hPtr->hash = UINT2PTR(hash);
hPtr->nextPtr = tablePtr->buckets[index];
tablePtr->buckets[index] = hPtr;
+#else
+ hPtr->bucketPtr = &(tablePtr->buckets[index]);
+ hPtr->nextPtr = *hPtr->bucketPtr;
+ *hPtr->bucketPtr = hPtr;
+#endif
tablePtr->numEntries++;
/*
@@ -406,7 +414,9 @@ Tcl_DeleteHashEntry(
const Tcl_HashKeyType *typePtr;
Tcl_HashTable *tablePtr;
Tcl_HashEntry **bucketPtr;
+#if TCL_HASH_KEY_STORE_HASH
int index;
+#endif
tablePtr = entryPtr->tablePtr;
@@ -421,14 +431,18 @@ Tcl_DeleteHashEntry(
typePtr = &tclArrayHashKeyType;
}
+#if TCL_HASH_KEY_STORE_HASH
if (typePtr->hashKeyProc == NULL
|| typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
- index = RANDOM_INDEX(tablePtr, PTR2INT(entryPtr->hash));
+ index = RANDOM_INDEX(tablePtr, PTR2UINT(entryPtr->hash));
} else {
index = PTR2UINT(entryPtr->hash) & tablePtr->mask;
}
- bucketPtr = &tablePtr->buckets[index];
+ bucketPtr = &(tablePtr->buckets[index]);
+#else
+ bucketPtr = entryPtr->bucketPtr;
+#endif
if (*bucketPtr == entryPtr) {
*bucketPtr = entryPtr->nextPtr;
@@ -446,9 +460,9 @@ Tcl_DeleteHashEntry(
tablePtr->numEntries--;
if (typePtr->freeEntryProc) {
- typePtr->freeEntryProc(entryPtr);
+ typePtr->freeEntryProc (entryPtr);
} else {
- ckfree(entryPtr);
+ ckfree((char *) entryPtr);
}
}
@@ -497,9 +511,9 @@ Tcl_DeleteHashTable(
while (hPtr != NULL) {
nextPtr = hPtr->nextPtr;
if (typePtr->freeEntryProc) {
- typePtr->freeEntryProc(hPtr);
+ typePtr->freeEntryProc (hPtr);
} else {
- ckfree(hPtr);
+ ckfree((char *) hPtr);
}
hPtr = nextPtr;
}
@@ -513,7 +527,7 @@ Tcl_DeleteHashTable(
if (typePtr->flags & TCL_HASH_KEY_SYSTEM_HASH) {
TclpSysFree((char *) tablePtr->buckets);
} else {
- ckfree(tablePtr->buckets);
+ ckfree((char *) tablePtr->buckets);
}
}
@@ -628,6 +642,18 @@ Tcl_HashStats(
double average, tmp;
register Tcl_HashEntry *hPtr;
char *result, *p;
+ const Tcl_HashKeyType *typePtr;
+
+ 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;
+ }
/*
* Compute a histogram of bucket usage.
@@ -658,7 +684,11 @@ Tcl_HashStats(
* Print out the histogram and a few other pieces of information.
*/
- result = ckalloc((NUM_COUNTERS * 60) + 300);
+ if (typePtr->flags & TCL_HASH_KEY_SYSTEM_HASH) {
+ result = (char *) TclpSysAlloc((unsigned) (NUM_COUNTERS*60) + 300, 0);
+ } else {
+ 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);
@@ -693,7 +723,7 @@ Tcl_HashStats(
static Tcl_HashEntry *
AllocArrayEntry(
Tcl_HashTable *tablePtr, /* Hash table. */
- void *keyPtr) /* Key to store in the hash table entry. */
+ VOID *keyPtr) /* Key to store in the hash table entry. */
{
int *array = (int *) keyPtr;
register int *iPtr1, *iPtr2;
@@ -707,7 +737,7 @@ AllocArrayEntry(
if (size < sizeof(Tcl_HashEntry)) {
size = sizeof(Tcl_HashEntry);
}
- hPtr = ckalloc(size);
+ hPtr = (Tcl_HashEntry *) ckalloc(size);
for (iPtr1 = array, iPtr2 = hPtr->key.words;
count > 0; count--, iPtr1++, iPtr2++) {
@@ -737,7 +767,7 @@ AllocArrayEntry(
static int
CompareArrayKeys(
- void *keyPtr, /* New key to compare. */
+ VOID *keyPtr, /* New key to compare. */
Tcl_HashEntry *hPtr) /* Existing key to compare. */
{
register const int *iPtr1 = (const int *) keyPtr;
@@ -774,10 +804,10 @@ CompareArrayKeys(
*----------------------------------------------------------------------
*/
-static TCL_HASH_TYPE
+static unsigned int
HashArrayKey(
Tcl_HashTable *tablePtr, /* Hash table. */
- void *keyPtr) /* Key from which to compute hash value. */
+ VOID *keyPtr) /* Key from which to compute hash value. */
{
register const int *array = (const int *) keyPtr;
register unsigned int result;
@@ -787,7 +817,7 @@ HashArrayKey(
count--, array++) {
result += *array;
}
- return (TCL_HASH_TYPE) result;
+ return result;
}
/*
@@ -809,7 +839,7 @@ HashArrayKey(
static Tcl_HashEntry *
AllocStringEntry(
Tcl_HashTable *tablePtr, /* Hash table. */
- void *keyPtr) /* Key to store in the hash table entry. */
+ VOID *keyPtr) /* Key to store in the hash table entry. */
{
const char *string = (const char *) keyPtr;
Tcl_HashEntry *hPtr;
@@ -819,7 +849,7 @@ AllocStringEntry(
if (size < sizeof(hPtr->key)) {
allocsize = sizeof(hPtr->key);
}
- hPtr = ckalloc(TclOffset(Tcl_HashEntry, key) + allocsize);
+ hPtr = (Tcl_HashEntry *) ckalloc(sizeof(Tcl_HashEntry) + allocsize - sizeof(hPtr->key));
memcpy(hPtr->key.string, string, size);
hPtr->clientData = 0;
return hPtr;
@@ -844,7 +874,7 @@ AllocStringEntry(
static int
CompareStringKeys(
- void *keyPtr, /* New key to compare. */
+ VOID *keyPtr, /* New key to compare. */
Tcl_HashEntry *hPtr) /* Existing key to compare. */
{
register const char *p1 = (const char *) keyPtr;
@@ -870,14 +900,14 @@ CompareStringKeys(
*----------------------------------------------------------------------
*/
-static TCL_HASH_TYPE
+static unsigned int
HashStringKey(
Tcl_HashTable *tablePtr, /* Hash table. */
- void *keyPtr) /* Key from which to compute hash value. */
+ VOID *keyPtr) /* Key from which to compute hash value. */
{
- register const char *string = keyPtr;
+ register const char *string = (const char *) keyPtr;
register unsigned int result;
- register char c;
+ register int c;
/*
* I tried a zillion different hash functions and asked many other people
@@ -887,36 +917,21 @@ HashStringKey(
* following reasons:
*
* 1. Multiplying by 10 is perfect for keys that are decimal strings, and
- * multiplying by 9 is just about as good.
+ * 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, but isn't strong against maliciously-chosen
- * keys.
- *
- * Note that this function is very weak against malicious strings; it's
- * very easy to generate multiple keys that have the same hashcode. On the
- * other hand, that hardly ever actually occurs and this function *is*
- * very cheap, even by comparison with industry-standard hashes like FNV.
- * If real strength of hash is required though, use a custom hash based on
- * Bob Jenkins's lookup3(), but be aware that it's significantly slower.
- * Since Tcl command and namespace names are usually reasonably-named (the
- * main use for string hashes in modern Tcl) speed is far more important
- * than strength.
- *
- * See also HashString in tclLiteral.c.
- * See also TclObjHashKey in tclObj.c.
- *
- * See [tcl-Feature Request #2958832]
+ * 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, but isn't strong against maliciously-chosen
+ * keys.
*/
- if ((result = UCHAR(*string)) != 0) {
- while ((c = *++string) != 0) {
- result += (result << 3) + UCHAR(c);
- }
+ result = 0;
+
+ for (c=*string++ ; c ; c=*string++) {
+ result += (result<<3) + c;
}
- return (TCL_HASH_TYPE) result;
+ return result;
}
/*
@@ -924,7 +939,7 @@ HashStringKey(
*
* BogusFind --
*
- * This function is invoked when Tcl_FindHashEntry is called on a
+ * This function is invoked when an Tcl_FindHashEntry is called on a
* table that has been deleted.
*
* Results:
@@ -951,7 +966,7 @@ BogusFind(
*
* BogusCreate --
*
- * This function is invoked when Tcl_CreateHashEntry is called on a
+ * This function is invoked when an Tcl_CreateHashEntry is called on a
* table that has been deleted.
*
* Results:
@@ -1028,8 +1043,8 @@ RebuildTable(
tablePtr->buckets = (Tcl_HashEntry **) TclpSysAlloc((unsigned)
(tablePtr->numBuckets * sizeof(Tcl_HashEntry *)), 0);
} else {
- tablePtr->buckets =
- ckalloc(tablePtr->numBuckets * sizeof(Tcl_HashEntry *));
+ tablePtr->buckets = (Tcl_HashEntry **) ckalloc((unsigned)
+ (tablePtr->numBuckets * sizeof(Tcl_HashEntry *)));
}
for (count = tablePtr->numBuckets, newChainPtr = tablePtr->buckets;
count > 0; count--, newChainPtr++) {
@@ -1046,14 +1061,35 @@ RebuildTable(
for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) {
for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) {
*oldChainPtr = hPtr->nextPtr;
+#if TCL_HASH_KEY_STORE_HASH
if (typePtr->hashKeyProc == NULL
|| typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
- index = RANDOM_INDEX(tablePtr, PTR2INT(hPtr->hash));
+ index = RANDOM_INDEX (tablePtr, PTR2UINT(hPtr->hash));
} else {
index = PTR2UINT(hPtr->hash) & tablePtr->mask;
}
hPtr->nextPtr = tablePtr->buckets[index];
tablePtr->buckets[index] = hPtr;
+#else
+ VOID *key = (VOID *) Tcl_GetHashKey(tablePtr, hPtr);
+
+ if (typePtr->hashKeyProc) {
+ unsigned int hash;
+
+ hash = typePtr->hashKeyProc(tablePtr, key);
+ if (typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
+ index = RANDOM_INDEX (tablePtr, hash);
+ } else {
+ index = hash & tablePtr->mask;
+ }
+ } else {
+ index = RANDOM_INDEX (tablePtr, key);
+ }
+
+ hPtr->bucketPtr = &(tablePtr->buckets[index]);
+ hPtr->nextPtr = *hPtr->bucketPtr;
+ *hPtr->bucketPtr = hPtr;
+#endif
}
}
@@ -1065,7 +1101,7 @@ RebuildTable(
if (typePtr->flags & TCL_HASH_KEY_SYSTEM_HASH) {
TclpSysFree((char *) oldBuckets);
} else {
- ckfree(oldBuckets);
+ ckfree((char *) oldBuckets);
}
}
}
generated by cgit v0.12 at 2025-12-18 09:23:57 (GMT)