diff options
Diffstat (limited to 'generic/tclHash.c')
| -rw-r--r-- | generic/tclHash.c | 420 |
1 files changed, 151 insertions, 269 deletions
diff --git a/generic/tclHash.c b/generic/tclHash.c index 04159d8..90be511 100644 --- a/generic/tclHash.c +++ b/generic/tclHash.c @@ -9,8 +9,6 @@ * * 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.24 2005/10/31 15:59:41 dkf Exp $ */ #include "tclInt.h" @@ -19,10 +17,8 @@ * Prevent macros from clashing with function definitions. */ -#if TCL_PRESERVE_BINARY_COMPATABILITY -# undef Tcl_FindHashEntry -# undef Tcl_CreateHashEntry -#endif +#undef Tcl_FindHashEntry +#undef Tcl_CreateHashEntry /* * When there are this many entries per bucket, on average, rebuild the hash @@ -39,25 +35,27 @@ */ #define RANDOM_INDEX(tablePtr, i) \ - (((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask) + ((((i)*1103515245L) >> (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. + * 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. */ #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 /* @@ -65,23 +63,23 @@ 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: */ -#if TCL_PRESERVE_BINARY_COMPATABILITY -static Tcl_HashEntry * BogusFind(Tcl_HashTable *tablePtr, CONST char *key); -static Tcl_HashEntry * BogusCreate(Tcl_HashTable *tablePtr, CONST char *key, +static Tcl_HashEntry * BogusFind(Tcl_HashTable *tablePtr, const char *key); +static Tcl_HashEntry * BogusCreate(Tcl_HashTable *tablePtr, const char *key, int *newPtr); -#endif - +static Tcl_HashEntry * CreateHashEntry(Tcl_HashTable *tablePtr, const char *key, + int *newPtr); +static Tcl_HashEntry * FindHashEntry(Tcl_HashTable *tablePtr, const char *key); static void RebuildTable(Tcl_HashTable *tablePtr); -Tcl_HashKeyType tclArrayHashKeyType = { +const Tcl_HashKeyType tclArrayHashKeyType = { TCL_HASH_KEY_TYPE_VERSION, /* version */ TCL_HASH_KEY_RANDOMIZE_HASH, /* flags */ HashArrayKey, /* hashKeyProc */ @@ -90,7 +88,7 @@ Tcl_HashKeyType tclArrayHashKeyType = { NULL /* freeEntryProc */ }; -Tcl_HashKeyType tclOneWordHashKeyType = { +const Tcl_HashKeyType tclOneWordHashKeyType = { TCL_HASH_KEY_TYPE_VERSION, /* version */ 0, /* flags */ NULL, /* HashOneWordKey, */ /* hashProc */ @@ -99,7 +97,7 @@ Tcl_HashKeyType tclOneWordHashKeyType = { NULL /* FreeOneWordKey, */ /* freeEntryProc */ }; -Tcl_HashKeyType tclStringHashKeyType = { +const Tcl_HashKeyType tclStringHashKeyType = { TCL_HASH_KEY_TYPE_VERSION, /* version */ 0, /* flags */ HashStringKey, /* hashKeyProc */ @@ -126,7 +124,6 @@ Tcl_HashKeyType tclStringHashKeyType = { *---------------------------------------------------------------------- */ -#undef Tcl_InitHashTable void Tcl_InitHashTable( register Tcl_HashTable *tablePtr, @@ -143,7 +140,7 @@ Tcl_InitHashTable( * extended version by a macro. */ - Tcl_InitCustomHashTable(tablePtr, keyType, (Tcl_HashKeyType *) -1); + Tcl_InitCustomHashTable(tablePtr, keyType, (const Tcl_HashKeyType *) -1); } /* @@ -174,11 +171,11 @@ Tcl_InitCustomHashTable( * 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 + const Tcl_HashKeyType *typePtr) /* Pointer to structure which defines the * behaviour of this table. */ { #if (TCL_SMALL_HASH_TABLE != 4) - Tcl_Panic("Tcl_InitCustomHashTable: TCL_SMALL_HASH_TABLE is %d, not 4\n", + Tcl_Panic("Tcl_InitCustomHashTable: TCL_SMALL_HASH_TABLE is %d, not 4", TCL_SMALL_HASH_TABLE); #endif @@ -191,9 +188,8 @@ Tcl_InitCustomHashTable( tablePtr->downShift = 28; tablePtr->mask = 3; tablePtr->keyType = keyType; -#if TCL_PRESERVE_BINARY_COMPATABILITY - tablePtr->findProc = Tcl_FindHashEntry; - tablePtr->createProc = Tcl_CreateHashEntry; + tablePtr->findProc = FindHashEntry; + tablePtr->createProc = CreateHashEntry; if (typePtr == NULL) { /* @@ -212,33 +208,6 @@ Tcl_InitCustomHashTable( * 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 } /* @@ -261,77 +230,19 @@ Tcl_InitCustomHashTable( Tcl_HashEntry * Tcl_FindHashEntry( Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */ - CONST char *key) /* Key to use to find matching entry. */ + const void *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 { - 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) { - Tcl_CompareHashKeysProc *compareKeysProc = 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 (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 (*((tablePtr)->findProc))(tablePtr, key); +} - return NULL; +static Tcl_HashEntry * +FindHashEntry( + Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */ + const char *key) /* Key to use to find matching entry. */ +{ + return CreateHashEntry(tablePtr, key, NULL); } + /* *---------------------------------------------------------------------- @@ -357,17 +268,27 @@ Tcl_FindHashEntry( Tcl_HashEntry * Tcl_CreateHashEntry( Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */ - CONST char *key, /* Key to use to find or create matching + const void *key, /* Key to use to find or create matching + * entry. */ + int *newPtr) /* Store info here telling whether a new entry + * was created. */ +{ + return (*((tablePtr)->createProc))(tablePtr, key, newPtr); +} + +static Tcl_HashEntry * +CreateHashEntry( + 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; + const 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) { @@ -378,24 +299,17 @@ Tcl_CreateHashEntry( } 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); + 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 = (unsigned int) key; - index = RANDOM_INDEX (tablePtr, hash); + hash = PTR2UINT(key); + index = RANDOM_INDEX(tablePtr, hash); } /* @@ -404,15 +318,18 @@ Tcl_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 != (unsigned int) hPtr->hash) { + if (hash != PTR2UINT(hPtr->hash)) { continue; } #endif - if (compareKeysProc ((VOID *) key, hPtr)) { - *newPtr = 0; + if (compareKeysProc((void *) key, hPtr)) { + if (newPtr) { + *newPtr = 0; + } return hPtr; } } @@ -420,44 +337,46 @@ Tcl_CreateHashEntry( for (hPtr = tablePtr->buckets[index]; hPtr != NULL; hPtr = hPtr->nextPtr) { #if TCL_HASH_KEY_STORE_HASH - if (hash != (unsigned int) hPtr->hash) { + if (hash != PTR2UINT(hPtr->hash)) { continue; } #endif if (key == hPtr->key.oneWordValue) { - *newPtr = 0; + if (newPtr) { + *newPtr = 0; + } return hPtr; } } } + if (!newPtr) { + return NULL; + } + /* * Entry not found. Add a new one to the bucket. */ *newPtr = 1; if (typePtr->allocEntryProc) { - hPtr = typePtr->allocEntryProc (tablePtr, (VOID *) key); + hPtr = typePtr->allocEntryProc(tablePtr, (void *) key); } else { - hPtr = (Tcl_HashEntry *) ckalloc((unsigned) sizeof(Tcl_HashEntry)); + hPtr = ckalloc(sizeof(Tcl_HashEntry)); hPtr->key.oneWordValue = (char *) key; + hPtr->clientData = 0; } hPtr->tablePtr = tablePtr; #if TCL_HASH_KEY_STORE_HASH -# if TCL_PRESERVE_BINARY_COMPATABILITY - hPtr->hash = (VOID *) hash; -# else - hPtr->hash = hash; -# endif + hPtr->hash = UINT2PTR(hash); 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 - hPtr->clientData = 0; tablePtr->numEntries++; /* @@ -494,7 +413,7 @@ Tcl_DeleteHashEntry( Tcl_HashEntry *entryPtr) { register Tcl_HashEntry *prevPtr; - Tcl_HashKeyType *typePtr; + const Tcl_HashKeyType *typePtr; Tcl_HashTable *tablePtr; Tcl_HashEntry **bucketPtr; #if TCL_HASH_KEY_STORE_HASH @@ -503,7 +422,6 @@ Tcl_DeleteHashEntry( tablePtr = entryPtr->tablePtr; -#if TCL_PRESERVE_BINARY_COMPATABILITY if (tablePtr->keyType == TCL_STRING_KEYS) { typePtr = &tclStringHashKeyType; } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) { @@ -514,19 +432,16 @@ Tcl_DeleteHashEntry( } 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); + index = RANDOM_INDEX(tablePtr, PTR2INT(entryPtr->hash)); } else { - index = ((unsigned int) entryPtr->hash) & tablePtr->mask; + index = PTR2UINT(entryPtr->hash) & tablePtr->mask; } - bucketPtr = &(tablePtr->buckets[index]); + bucketPtr = &tablePtr->buckets[index]; #else bucketPtr = entryPtr->bucketPtr; #endif @@ -547,9 +462,9 @@ Tcl_DeleteHashEntry( tablePtr->numEntries--; if (typePtr->freeEntryProc) { - typePtr->freeEntryProc (entryPtr); + typePtr->freeEntryProc(entryPtr); } else { - ckfree((char *) entryPtr); + ckfree(entryPtr); } } @@ -575,10 +490,9 @@ Tcl_DeleteHashTable( register Tcl_HashTable *tablePtr) /* Table to delete. */ { register Tcl_HashEntry *hPtr, *nextPtr; - Tcl_HashKeyType *typePtr; + const 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) { @@ -589,9 +503,6 @@ Tcl_DeleteHashTable( } else { typePtr = &tclArrayHashKeyType; } -#else - typePtr = tablePtr->typePtr; -#endif /* * Free up all the entries in the table. @@ -602,9 +513,9 @@ Tcl_DeleteHashTable( while (hPtr != NULL) { nextPtr = hPtr->nextPtr; if (typePtr->freeEntryProc) { - typePtr->freeEntryProc (hPtr); + typePtr->freeEntryProc(hPtr); } else { - ckfree((char *) hPtr); + ckfree(hPtr); } hPtr = nextPtr; } @@ -618,7 +529,7 @@ Tcl_DeleteHashTable( if (typePtr->flags & TCL_HASH_KEY_SYSTEM_HASH) { TclpSysFree((char *) tablePtr->buckets); } else { - ckfree((char *) tablePtr->buckets); + ckfree(tablePtr->buckets); } } @@ -627,12 +538,8 @@ Tcl_DeleteHashTable( * re-initialization. */ -#if TCL_PRESERVE_BINARY_COMPATABILITY tablePtr->findProc = BogusFind; tablePtr->createProc = BogusCreate; -#else - tablePtr->typePtr = NULL; -#endif } /* @@ -728,7 +635,7 @@ Tcl_NextHashEntry( *---------------------------------------------------------------------- */ -CONST char * +char * Tcl_HashStats( Tcl_HashTable *tablePtr) /* Table for which to produce stats. */ { @@ -737,26 +644,6 @@ Tcl_HashStats( double average, tmp; register Tcl_HashEntry *hPtr; char *result, *p; - Tcl_HashKeyType *typePtr; - -#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_HashStats on deleted table"); - return NULL; - } -#endif /* * Compute a histogram of bucket usage. @@ -787,11 +674,7 @@ Tcl_HashStats( * Print out the histogram and a few other pieces of information. */ - 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); - } + result = ckalloc((NUM_COUNTERS * 60) + 300); sprintf(result, "%d entries in table, %d buckets\n", tablePtr->numEntries, tablePtr->numBuckets); p = result + strlen(result); @@ -826,7 +709,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; @@ -840,12 +723,13 @@ AllocArrayEntry( if (size < sizeof(Tcl_HashEntry)) { size = sizeof(Tcl_HashEntry); } - hPtr = (Tcl_HashEntry *) ckalloc(size); + hPtr = ckalloc(size); for (iPtr1 = array, iPtr2 = hPtr->key.words; count > 0; count--, iPtr1++, iPtr2++) { *iPtr2 = *iPtr1; } + hPtr->clientData = 0; return hPtr; } @@ -869,11 +753,11 @@ 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; - register CONST int *iPtr2 = (CONST int *) hPtr->key.words; + register const int *iPtr1 = (const int *) keyPtr; + register const int *iPtr2 = (const int *) hPtr->key.words; Tcl_HashTable *tablePtr = hPtr->tablePtr; int count; @@ -909,9 +793,9 @@ 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 const int *array = (const int *) keyPtr; register unsigned int result; int count; @@ -941,19 +825,19 @@ 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; + const char *string = (const char *) keyPtr; Tcl_HashEntry *hPtr; - unsigned int size; + unsigned int size, allocsize; - size = sizeof(Tcl_HashEntry) + strlen(string) + 1 - sizeof(hPtr->key); - if (size < sizeof(Tcl_HashEntry)) { - size = sizeof(Tcl_HashEntry); + allocsize = size = strlen(string) + 1; + if (size < sizeof(hPtr->key)) { + allocsize = sizeof(hPtr->key); } - hPtr = (Tcl_HashEntry *) ckalloc(size); - strcpy(hPtr->key.string, string); - + hPtr = ckalloc(TclOffset(Tcl_HashEntry, key) + allocsize); + memcpy(hPtr->key.string, string, size); + hPtr->clientData = 0; return hPtr; } @@ -976,25 +860,13 @@ 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; - register CONST char *p2 = (CONST char *) hPtr->key.string; + register const char *p1 = (const char *) keyPtr; + register const char *p2 = (const char *) hPtr->key.string; -#ifdef TCL_COMPARE_HASHES_WITH_STRCMP return !strcmp(p1, p2); -#else - for (;; p1++, p2++) { - if (*p1 != *p2) { - break; - } - if (*p1 == '\0') { - return 1; - } - } - return 0; -#endif /* TCL_COMPARE_HASHES_WITH_STRCMP */ } /* @@ -1014,14 +886,14 @@ CompareStringKeys( *---------------------------------------------------------------------- */ -static unsigned int +static unsigned 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 = (CONST char *) keyPtr; + register const char *string = keyPtr; register unsigned int result; - register int c; + register char c; /* * I tried a zillion different hash functions and asked many other people @@ -1031,24 +903,38 @@ 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. + * 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] */ - result = 0; - - for (c=*string++ ; c ; c=*string++) { - result += (result<<3) + c; + if ((result = UCHAR(*string)) != 0) { + while ((c = *++string) != 0) { + result += (result << 3) + UCHAR(c); + } } return result; } -#if TCL_PRESERVE_BINARY_COMPATABILITY /* *---------------------------------------------------------------------- * @@ -1070,9 +956,9 @@ HashStringKey( static Tcl_HashEntry * BogusFind( Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */ - CONST char *key) /* Key to use to find matching entry. */ + const char *key) /* Key to use to find matching entry. */ { - Tcl_Panic("called Tcl_FindHashEntry on deleted table"); + Tcl_Panic("called %s on deleted table", "Tcl_FindHashEntry"); return NULL; } @@ -1097,15 +983,14 @@ BogusFind( static Tcl_HashEntry * BogusCreate( Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */ - CONST char *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. */ { - Tcl_Panic("called Tcl_CreateHashEntry on deleted table"); + Tcl_Panic("called %s on deleted table", "Tcl_CreateHashEntry"); return NULL; } -#endif /* *---------------------------------------------------------------------- @@ -1133,9 +1018,8 @@ RebuildTable( Tcl_HashEntry **oldBuckets; register Tcl_HashEntry **oldChainPtr, **newChainPtr; register Tcl_HashEntry *hPtr; - Tcl_HashKeyType *typePtr; + const Tcl_HashKeyType *typePtr; -#if TCL_PRESERVE_BINARY_COMPATABILITY if (tablePtr->keyType == TCL_STRING_KEYS) { typePtr = &tclStringHashKeyType; } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) { @@ -1146,9 +1030,6 @@ RebuildTable( } else { typePtr = &tclArrayHashKeyType; } -#else - typePtr = tablePtr->typePtr; -#endif oldSize = tablePtr->numBuckets; oldBuckets = tablePtr->buckets; @@ -1163,8 +1044,8 @@ RebuildTable( tablePtr->buckets = (Tcl_HashEntry **) TclpSysAlloc((unsigned) (tablePtr->numBuckets * sizeof(Tcl_HashEntry *)), 0); } else { - tablePtr->buckets = (Tcl_HashEntry **) ckalloc((unsigned) - (tablePtr->numBuckets * sizeof(Tcl_HashEntry *))); + tablePtr->buckets = + ckalloc(tablePtr->numBuckets * sizeof(Tcl_HashEntry *)); } for (count = tablePtr->numBuckets, newChainPtr = tablePtr->buckets; count > 0; count--, newChainPtr++) { @@ -1184,28 +1065,29 @@ RebuildTable( #if TCL_HASH_KEY_STORE_HASH if (typePtr->hashKeyProc == NULL || typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) { - index = RANDOM_INDEX (tablePtr, hPtr->hash); + index = RANDOM_INDEX(tablePtr, PTR2INT(hPtr->hash)); } else { - index = ((unsigned int) hPtr->hash) & tablePtr->mask; + index = PTR2UINT(hPtr->hash) & tablePtr->mask; } hPtr->nextPtr = tablePtr->buckets[index]; tablePtr->buckets[index] = hPtr; #else - VOID *key = (VOID *) Tcl_GetHashKey (tablePtr, hPtr); + void *key = Tcl_GetHashKey(tablePtr, hPtr); if (typePtr->hashKeyProc) { unsigned int hash; - hash = typePtr->hashKeyProc (tablePtr, (VOID *) key); + + 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 @@ -1220,7 +1102,7 @@ RebuildTable( if (typePtr->flags & TCL_HASH_KEY_SYSTEM_HASH) { TclpSysFree((char *) oldBuckets); } else { - ckfree((char *) oldBuckets); + ckfree(oldBuckets); } } } |