diff options
Diffstat (limited to 'generic/tclHash.c')
| -rw-r--r-- | generic/tclHash.c | 328 |
1 files changed, 197 insertions, 131 deletions
diff --git a/generic/tclHash.c b/generic/tclHash.c index 385b9e4..256b073 100644 --- a/generic/tclHash.c +++ b/generic/tclHash.c @@ -4,8 +4,8 @@ * Implementation of in-memory hash tables for Tcl and Tcl-based * applications. * - * Copyright © 1991-1993 The Regents of the University of California. - * Copyright © 1994 Sun Microsystems, Inc. + * Copyright (c) 1991-1993 The Regents of the University of California. + * Copyright (c) 1994 Sun Microsystems, Inc. * * See the file "license.terms" for information on usage and redistribution of * this file, and for a DISCLAIMER OF ALL WARRANTIES. @@ -35,24 +35,35 @@ */ #define RANDOM_INDEX(tablePtr, i) \ - ((((i)*1103515245UL) >> (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. + */ + +#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 /* * Prototypes for the string hash key methods. */ 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: @@ -66,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 */ @@ -75,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 */ @@ -84,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 */ @@ -111,9 +122,10 @@ const Tcl_HashKeyType tclStringHashKeyType = { *---------------------------------------------------------------------- */ +#undef Tcl_InitHashTable void Tcl_InitHashTable( - Tcl_HashTable *tablePtr, + register Tcl_HashTable *tablePtr, /* Pointer to table record, which is supplied * by the caller. */ int keyType) /* Type of keys to use in table: @@ -127,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); } /* @@ -151,14 +163,14 @@ Tcl_InitHashTable( void Tcl_InitCustomHashTable( - Tcl_HashTable *tablePtr, + 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. */ - 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) @@ -217,9 +229,9 @@ 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, (const char *)key); + return (*((tablePtr)->findProc))(tablePtr, key); } static Tcl_HashEntry * @@ -255,12 +267,12 @@ 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. */ { - return (*((tablePtr)->createProc))(tablePtr, (const char *)key, newPtr); + return (*((tablePtr)->createProc))(tablePtr, key, newPtr); } static Tcl_HashEntry * @@ -271,9 +283,10 @@ CreateHashEntry( int *newPtr) /* Store info here telling whether a new entry * was created. */ { - Tcl_HashEntry *hPtr; + register Tcl_HashEntry *hPtr; const Tcl_HashKeyType *typePtr; - TCL_HASH_TYPE hash, index; + unsigned int hash; + int index; if (tablePtr->keyType == TCL_STRING_KEYS) { typePtr = &tclStringHashKeyType; @@ -287,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); } /* @@ -304,16 +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 keys pointers or values are equal */ - if ((key == hPtr->key.oneWordValue) - || compareKeysProc((void *) key, hPtr) - ) { +#endif + if (compareKeysProc((VOID *) key, hPtr)) { if (newPtr) { *newPtr = 0; } @@ -323,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; @@ -345,17 +358,23 @@ CreateHashEntry( *newPtr = 1; if (typePtr->allocEntryProc) { - hPtr = typePtr->allocEntryProc(tablePtr, (void *) key); + hPtr = typePtr->allocEntryProc(tablePtr, (VOID *) key); } else { - hPtr = (Tcl_HashEntry *)ckalloc(sizeof(Tcl_HashEntry)); + hPtr = (Tcl_HashEntry *) ckalloc((unsigned) sizeof(Tcl_HashEntry)); hPtr->key.oneWordValue = (char *) key; - Tcl_SetHashValue(hPtr, NULL); + 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++; /* @@ -391,11 +410,13 @@ void Tcl_DeleteHashEntry( Tcl_HashEntry *entryPtr) { - Tcl_HashEntry *prevPtr; + register Tcl_HashEntry *prevPtr; const Tcl_HashKeyType *typePtr; Tcl_HashTable *tablePtr; Tcl_HashEntry **bucketPtr; - TCL_HASH_TYPE index; +#if TCL_HASH_KEY_STORE_HASH + int index; +#endif tablePtr = entryPtr->tablePtr; @@ -410,6 +431,7 @@ 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, PTR2UINT(entryPtr->hash)); @@ -417,7 +439,10 @@ Tcl_DeleteHashEntry( 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; @@ -435,9 +460,9 @@ Tcl_DeleteHashEntry( tablePtr->numEntries--; if (typePtr->freeEntryProc) { - typePtr->freeEntryProc(entryPtr); + typePtr->freeEntryProc (entryPtr); } else { - ckfree(entryPtr); + ckfree((char *) entryPtr); } } @@ -460,9 +485,9 @@ Tcl_DeleteHashEntry( void Tcl_DeleteHashTable( - Tcl_HashTable *tablePtr) /* Table to delete. */ + register Tcl_HashTable *tablePtr) /* Table to delete. */ { - Tcl_HashEntry *hPtr, *nextPtr; + register Tcl_HashEntry *hPtr, *nextPtr; const Tcl_HashKeyType *typePtr; int i; @@ -486,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; } @@ -502,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); } } @@ -568,7 +593,7 @@ Tcl_FirstHashEntry( Tcl_HashEntry * Tcl_NextHashEntry( - Tcl_HashSearch *searchPtr) + register Tcl_HashSearch *searchPtr) /* Place to store information about progress * through the table. Must have been * initialized by calling @@ -613,11 +638,22 @@ Tcl_HashStats( Tcl_HashTable *tablePtr) /* Table for which to produce stats. */ { #define NUM_COUNTERS 10 - int i; - TCL_HASH_TYPE count[NUM_COUNTERS], overflow, j; + int count[NUM_COUNTERS], overflow, i, j; double average, tmp; - Tcl_HashEntry *hPtr; + 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. @@ -648,19 +684,23 @@ Tcl_HashStats( * Print out the histogram and a few other pieces of information. */ - result = (char *)ckalloc((NUM_COUNTERS * 60) + 300); - snprintf(result, 60, "%" TCL_SIZE_MODIFIER "u entries in table, %" TCL_SIZE_MODIFIER "u 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++) { - snprintf(p, 60, "number of buckets with %" TCL_SIZE_MODIFIER "u entries: %" TCL_SIZE_MODIFIER "u\n", + sprintf(p, "number of buckets with %d entries: %d\n", i, count[i]); p += strlen(p); } - snprintf(p, 60, "number of buckets with %d or more entries: %" TCL_SIZE_MODIFIER "u\n", + sprintf(p, "number of buckets with %d or more entries: %d\n", NUM_COUNTERS, overflow); p += strlen(p); - snprintf(p, 60, "average search distance for entry: %.1f", average); + sprintf(p, "average search distance for entry: %.1f", average); return result; } @@ -683,19 +723,27 @@ 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; Tcl_HashEntry *hPtr; - TCL_HASH_TYPE count = tablePtr->keyType * sizeof(int); - TCL_HASH_TYPE size = offsetof(Tcl_HashEntry, key) + count; + int count; + unsigned int size; + + count = tablePtr->keyType; + size = sizeof(Tcl_HashEntry) + (count*sizeof(int)) - sizeof(hPtr->key); if (size < sizeof(Tcl_HashEntry)) { size = sizeof(Tcl_HashEntry); } - hPtr = (Tcl_HashEntry *)ckalloc(size); + hPtr = (Tcl_HashEntry *) ckalloc(size); - memcpy(hPtr->key.string, keyPtr, count); - Tcl_SetHashValue(hPtr, NULL); + for (iPtr1 = array, iPtr2 = hPtr->key.words; + count > 0; count--, iPtr1++, iPtr2++) { + *iPtr2 = *iPtr1; + } + hPtr->clientData = 0; return hPtr; } @@ -719,12 +767,23 @@ AllocArrayEntry( static int CompareArrayKeys( - void *keyPtr, /* New key to compare. */ + VOID *keyPtr, /* New key to compare. */ Tcl_HashEntry *hPtr) /* Existing key to compare. */ { - size_t count = hPtr->tablePtr->keyType * sizeof(int); + register const int *iPtr1 = (const int *) keyPtr; + register const int *iPtr2 = (const int *) hPtr->key.words; + Tcl_HashTable *tablePtr = hPtr->tablePtr; + int count; - return !memcmp(keyPtr, hPtr->key.string, count); + for (count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) { + if (count == 0) { + return 1; + } + if (*iPtr1 != *iPtr2) { + break; + } + } + return 0; } /* @@ -745,13 +804,13 @@ 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. */ { - const int *array = (const int *) keyPtr; - TCL_HASH_TYPE result; + register const int *array = (const int *) keyPtr; + register unsigned int result; int count; for (result = 0, count = tablePtr->keyType; count > 0; @@ -779,21 +838,20 @@ HashArrayKey( static Tcl_HashEntry * AllocStringEntry( - TCL_UNUSED(Tcl_HashTable *), - void *keyPtr) /* Key to store in the hash table entry. */ + Tcl_HashTable *tablePtr, /* Hash table. */ + VOID *keyPtr) /* Key to store in the hash table entry. */ { const char *string = (const char *) keyPtr; Tcl_HashEntry *hPtr; - size_t size, allocsize; + unsigned int size, allocsize; allocsize = size = strlen(string) + 1; if (size < sizeof(hPtr->key)) { allocsize = sizeof(hPtr->key); } - hPtr = (Tcl_HashEntry *)ckalloc(offsetof(Tcl_HashEntry, key) + allocsize); - memset(hPtr, 0, offsetof(Tcl_HashEntry, key) + allocsize); + hPtr = (Tcl_HashEntry *) ckalloc(sizeof(Tcl_HashEntry) + allocsize - sizeof(hPtr->key)); memcpy(hPtr->key.string, string, size); - Tcl_SetHashValue(hPtr, NULL); + hPtr->clientData = 0; return hPtr; } @@ -816,10 +874,13 @@ AllocStringEntry( static int CompareStringKeys( - void *keyPtr, /* New key to compare. */ + VOID *keyPtr, /* New key to compare. */ Tcl_HashEntry *hPtr) /* Existing key to compare. */ { - return !strcmp((char *)keyPtr, hPtr->key.string); + register const char *p1 = (const char *) keyPtr; + register const char *p2 = (const char *) hPtr->key.string; + + return !strcmp(p1, p2); } /* @@ -839,14 +900,14 @@ CompareStringKeys( *---------------------------------------------------------------------- */ -static TCL_HASH_TYPE +static unsigned int HashStringKey( - TCL_UNUSED(Tcl_HashTable *), - void *keyPtr) /* Key from which to compute hash value. */ + Tcl_HashTable *tablePtr, /* Hash table. */ + VOID *keyPtr) /* Key from which to compute hash value. */ { - const char *string = (const char *)keyPtr; - TCL_HASH_TYPE result; - char c; + register const char *string = (const char *) keyPtr; + register unsigned int result; + register int c; /* * I tried a zillion different hash functions and asked many other people @@ -856,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; } @@ -893,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: @@ -905,10 +951,11 @@ HashStringKey( *---------------------------------------------------------------------- */ + /* ARGSUSED */ static Tcl_HashEntry * BogusFind( - TCL_UNUSED(Tcl_HashTable *), - TCL_UNUSED(const char *)) + Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */ + const char *key) /* Key to use to find matching entry. */ { Tcl_Panic("called %s on deleted table", "Tcl_FindHashEntry"); return NULL; @@ -919,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: @@ -931,11 +978,14 @@ BogusFind( *---------------------------------------------------------------------- */ + /* ARGSUSED */ static Tcl_HashEntry * BogusCreate( - TCL_UNUSED(Tcl_HashTable *), - TCL_UNUSED(const char *), - TCL_UNUSED(int *)) + 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_Panic("called %s on deleted table", "Tcl_CreateHashEntry"); return NULL; @@ -961,20 +1011,14 @@ BogusCreate( static void RebuildTable( - Tcl_HashTable *tablePtr) /* Table to enlarge. */ + register Tcl_HashTable *tablePtr) /* Table to enlarge. */ { - TCL_HASH_TYPE count, index, oldSize = tablePtr->numBuckets; - Tcl_HashEntry **oldBuckets = tablePtr->buckets; - Tcl_HashEntry **oldChainPtr, **newChainPtr; - Tcl_HashEntry *hPtr; + int oldSize, count, index; + Tcl_HashEntry **oldBuckets; + register Tcl_HashEntry **oldChainPtr, **newChainPtr; + register Tcl_HashEntry *hPtr; const Tcl_HashKeyType *typePtr; - /* Avoid outgrowing capability of the memory allocators */ - if (oldSize > 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) { @@ -986,6 +1030,9 @@ 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. @@ -993,20 +1040,18 @@ RebuildTable( tablePtr->numBuckets *= 4; if (typePtr->flags & TCL_HASH_KEY_SYSTEM_HASH) { - tablePtr->buckets = (Tcl_HashEntry **)TclpSysAlloc( - tablePtr->numBuckets * sizeof(Tcl_HashEntry *), 0); + tablePtr->buckets = (Tcl_HashEntry **) TclpSysAlloc((unsigned) + (tablePtr->numBuckets * sizeof(Tcl_HashEntry *)), 0); } else { - tablePtr->buckets = - (Tcl_HashEntry **)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++) { *newChainPtr = NULL; } tablePtr->rebuildSize *= 4; - if (tablePtr->downShift > 1) { - tablePtr->downShift -= 2; - } + tablePtr->downShift -= 2; tablePtr->mask = (tablePtr->mask << 2) + 3; /* @@ -1016,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, PTR2UINT(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 } } @@ -1035,7 +1101,7 @@ RebuildTable( if (typePtr->flags & TCL_HASH_KEY_SYSTEM_HASH) { TclpSysFree((char *) oldBuckets); } else { - ckfree(oldBuckets); + ckfree((char *) oldBuckets); } } } |