diff options
Diffstat (limited to 'generic/tclHash.c')
-rw-r--r-- | generic/tclHash.c | 81 |
1 files changed, 17 insertions, 64 deletions
diff --git a/generic/tclHash.c b/generic/tclHash.c index 90be511..32c9aec 100644 --- a/generic/tclHash.c +++ b/generic/tclHash.c @@ -43,20 +43,7 @@ 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. - */ - -#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); -#endif +static TCL_HASH_TYPE HashArrayKey(Tcl_HashTable *tablePtr, void *keyPtr); /* * Prototypes for the string hash key methods. @@ -65,7 +52,7 @@ 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); +static TCL_HASH_TYPE HashStringKey(Tcl_HashTable *tablePtr, void *keyPtr); /* * Function prototypes for static functions in this file: @@ -321,12 +308,10 @@ CreateHashEntry( for (hPtr = tablePtr->buckets[index]; hPtr != NULL; hPtr = hPtr->nextPtr) { -#if TCL_HASH_KEY_STORE_HASH if (hash != PTR2UINT(hPtr->hash)) { continue; } -#endif - if (compareKeysProc((void *) key, hPtr)) { + if (((void *) key == hPtr) || compareKeysProc((void *) key, hPtr)) { if (newPtr) { *newPtr = 0; } @@ -336,11 +321,9 @@ 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; @@ -368,15 +351,9 @@ CreateHashEntry( } 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++; /* @@ -416,9 +393,7 @@ Tcl_DeleteHashEntry( const Tcl_HashKeyType *typePtr; Tcl_HashTable *tablePtr; Tcl_HashEntry **bucketPtr; -#if TCL_HASH_KEY_STORE_HASH int index; -#endif tablePtr = entryPtr->tablePtr; @@ -433,7 +408,6 @@ 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)); @@ -442,9 +416,6 @@ Tcl_DeleteHashEntry( } bucketPtr = &tablePtr->buckets[index]; -#else - bucketPtr = entryPtr->bucketPtr; -#endif if (*bucketPtr == entryPtr) { *bucketPtr = entryPtr->nextPtr; @@ -790,7 +761,7 @@ CompareArrayKeys( *---------------------------------------------------------------------- */ -static unsigned int +static TCL_HASH_TYPE HashArrayKey( Tcl_HashTable *tablePtr, /* Hash table. */ void *keyPtr) /* Key from which to compute hash value. */ @@ -803,7 +774,7 @@ HashArrayKey( count--, array++) { result += *array; } - return result; + return (TCL_HASH_TYPE) result; } /* @@ -886,7 +857,7 @@ CompareStringKeys( *---------------------------------------------------------------------- */ -static unsigned +static TCL_HASH_TYPE HashStringKey( Tcl_HashTable *tablePtr, /* Hash table. */ void *keyPtr) /* Key from which to compute hash value. */ @@ -932,7 +903,7 @@ HashStringKey( result += (result << 3) + UCHAR(c); } } - return result; + return (TCL_HASH_TYPE) result; } /* @@ -940,7 +911,7 @@ HashStringKey( * * BogusFind -- * - * This function is invoked when an Tcl_FindHashEntry is called on a + * This function is invoked when Tcl_FindHashEntry is called on a * table that has been deleted. * * Results: @@ -967,7 +938,7 @@ BogusFind( * * BogusCreate -- * - * This function is invoked when an Tcl_CreateHashEntry is called on a + * This function is invoked when Tcl_CreateHashEntry is called on a * table that has been deleted. * * Results: @@ -1014,12 +985,18 @@ static void RebuildTable( register Tcl_HashTable *tablePtr) /* Table to enlarge. */ { - int oldSize, count, index; - Tcl_HashEntry **oldBuckets; + int count, index, oldSize = tablePtr->numBuckets; + Tcl_HashEntry **oldBuckets = tablePtr->buckets; register Tcl_HashEntry **oldChainPtr, **newChainPtr; register Tcl_HashEntry *hPtr; const Tcl_HashKeyType *typePtr; + /* Avoid outgrowing capability of the memory allocators */ + if (oldSize > (int)(UINT_MAX / (4 * sizeof(Tcl_HashEntry *)))) { + tablePtr->rebuildSize = INT_MAX; + return; + } + if (tablePtr->keyType == TCL_STRING_KEYS) { typePtr = &tclStringHashKeyType; } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) { @@ -1031,9 +1008,6 @@ RebuildTable( typePtr = &tclArrayHashKeyType; } - oldSize = tablePtr->numBuckets; - oldBuckets = tablePtr->buckets; - /* * Allocate and initialize the new bucket array, and set up hashing * constants for new array size. @@ -1062,7 +1036,6 @@ 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)); @@ -1071,26 +1044,6 @@ RebuildTable( } hPtr->nextPtr = tablePtr->buckets[index]; tablePtr->buckets[index] = hPtr; -#else - void *key = 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 } } |