summaryrefslogtreecommitdiffstats
path: root/generic/tclHash.c
diff options
context:
space:
mode:
Diffstat (limited to 'generic/tclHash.c')
-rw-r--r--generic/tclHash.c161
1 files changed, 80 insertions, 81 deletions
diff --git a/generic/tclHash.c b/generic/tclHash.c
index a5f8953..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 unsigned int 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 unsigned int 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,7 +317,6 @@ 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
@@ -326,7 +324,7 @@ CreateHashEntry(
continue;
}
#endif
- if (compareKeysProc((void *) key, hPtr)) {
+ if (compareKeysProc((VOID *) key, hPtr)) {
if (newPtr) {
*newPtr = 0;
}
@@ -360,9 +358,9 @@ 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;
}
@@ -373,7 +371,7 @@ CreateHashEntry(
hPtr->nextPtr = tablePtr->buckets[index];
tablePtr->buckets[index] = hPtr;
#else
- hPtr->bucketPtr = &tablePtr->buckets[index];
+ hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;
*hPtr->bucketPtr = hPtr;
#endif
@@ -436,12 +434,12 @@ Tcl_DeleteHashEntry(
#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
@@ -462,9 +460,9 @@ Tcl_DeleteHashEntry(
tablePtr->numEntries--;
if (typePtr->freeEntryProc) {
- typePtr->freeEntryProc(entryPtr);
+ typePtr->freeEntryProc (entryPtr);
} else {
- ckfree(entryPtr);
+ ckfree((char *) entryPtr);
}
}
@@ -513,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;
}
@@ -529,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);
}
}
@@ -644,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.
@@ -674,8 +684,12 @@ Tcl_HashStats(
* Print out the histogram and a few other pieces of information.
*/
- result = ckalloc((NUM_COUNTERS * 60) + 300);
- sprintf(result, "%lu entries in table, %lu buckets\n",
+ 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);
for (i = 0; i < NUM_COUNTERS; i++) {
@@ -709,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;
@@ -723,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++) {
@@ -753,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;
@@ -793,7 +807,7 @@ CompareArrayKeys(
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;
@@ -825,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;
@@ -835,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;
@@ -860,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;
@@ -886,14 +900,14 @@ CompareStringKeys(
*----------------------------------------------------------------------
*/
-static unsigned
+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
@@ -903,34 +917,19 @@ 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 result;
}
@@ -1044,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++) {
@@ -1065,29 +1064,29 @@ RebuildTable(
#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 = Tcl_GetHashKey(tablePtr, hPtr);
+ 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);
+ index = RANDOM_INDEX (tablePtr, hash);
} else {
index = hash & tablePtr->mask;
}
} else {
- index = RANDOM_INDEX(tablePtr, key);
+ index = RANDOM_INDEX (tablePtr, key);
}
- hPtr->bucketPtr = &tablePtr->buckets[index];
+ hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;
*hPtr->bucketPtr = hPtr;
#endif
@@ -1102,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 18:25:35 (GMT)