#include "tclInt.h"
#if TCL_PRESERVE_BINARY_COMPATABILITY
# undef Tcl_FindHashEntry
# undef Tcl_CreateHashEntry
#endif
#define REBUILD_MULTIPLIER 3
#define RANDOM_INDEX(tablePtr, i) \
(((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask)
static Tcl_HashEntry * AllocArrayEntry _ANSI_ARGS_((
Tcl_HashTable *tablePtr,
VOID *keyPtr));
static int CompareArrayKeys _ANSI_ARGS_((
VOID *keyPtr, Tcl_HashEntry *hPtr));
static unsigned int HashArrayKey _ANSI_ARGS_((
Tcl_HashTable *tablePtr,
VOID *keyPtr));
#if 0
static Tcl_HashEntry * AllocOneWordEntry _ANSI_ARGS_((
Tcl_HashTable *tablePtr,
VOID *keyPtr));
static int CompareOneWordKeys _ANSI_ARGS_((
VOID *keyPtr, Tcl_HashEntry *hPtr));
static unsigned int HashOneWordKey _ANSI_ARGS_((
Tcl_HashTable *tablePtr,
VOID *keyPtr));
#endif
static Tcl_HashEntry * AllocStringEntry _ANSI_ARGS_((
Tcl_HashTable *tablePtr,
VOID *keyPtr));
static int CompareStringKeys _ANSI_ARGS_((
VOID *keyPtr, Tcl_HashEntry *hPtr));
static unsigned int HashStringKey _ANSI_ARGS_((
Tcl_HashTable *tablePtr,
VOID *keyPtr));
#if TCL_PRESERVE_BINARY_COMPATABILITY
static Tcl_HashEntry * BogusFind _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key));
static Tcl_HashEntry * BogusCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr,
CONST char *key, int *newPtr));
#endif
static void RebuildTable _ANSI_ARGS_((Tcl_HashTable *tablePtr));
Tcl_HashKeyType tclArrayHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION,
TCL_HASH_KEY_RANDOMIZE_HASH,
HashArrayKey,
CompareArrayKeys,
AllocArrayEntry,
NULL
};
Tcl_HashKeyType tclOneWordHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION,
0,
NULL,
NULL,
NULL,
NULL
};
Tcl_HashKeyType tclStringHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION,
0,
HashStringKey,
CompareStringKeys,
AllocStringEntry,
NULL
};
#undef Tcl_InitHashTable
void
Tcl_InitHashTable(tablePtr, keyType)
register Tcl_HashTable *tablePtr;
int keyType;
{
Tcl_InitCustomHashTable(tablePtr, keyType, (Tcl_HashKeyType *) -1);
}
void
Tcl_InitCustomHashTable(tablePtr, keyType, typePtr)
register Tcl_HashTable *tablePtr;
int keyType;
Tcl_HashKeyType *typePtr;
{
#if (TCL_SMALL_HASH_TABLE != 4)
panic("Tcl_InitCustomHashTable: TCL_SMALL_HASH_TABLE is %d, not 4\n",
TCL_SMALL_HASH_TABLE);
#endif
tablePtr->buckets = tablePtr->staticBuckets;
tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] = 0;
tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] = 0;
tablePtr->numBuckets = TCL_SMALL_HASH_TABLE;
tablePtr->numEntries = 0;
tablePtr->rebuildSize = TCL_SMALL_HASH_TABLE*REBUILD_MULTIPLIER;
tablePtr->downShift = 28;
tablePtr->mask = 3;
tablePtr->keyType = keyType;
#if TCL_PRESERVE_BINARY_COMPATABILITY
tablePtr->findProc = Tcl_FindHashEntry;
tablePtr->createProc = Tcl_CreateHashEntry;
if (typePtr == NULL) {
} else if (typePtr != (Tcl_HashKeyType *) -1) {
tablePtr->typePtr = typePtr;
} else {
}
#else
if (typePtr == NULL) {
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) {
Tcl_Panic ("Hash table is not compatible");
}
tablePtr->typePtr = typePtr;
#endif
}
Tcl_HashEntry *
Tcl_FindHashEntry(tablePtr, key)
Tcl_HashTable *tablePtr;
CONST char *key;
{
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);
}
if (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 (typePtr->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 NULL;
}
Tcl_HashEntry *
Tcl_CreateHashEntry(tablePtr, key, newPtr)
Tcl_HashTable *tablePtr;
CONST char *key;
int *newPtr;
{
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_CreateHashEntry 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);
}
if (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 (typePtr->compareKeysProc ((VOID *) key, hPtr)) {
*newPtr = 0;
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) {
*newPtr = 0;
return hPtr;
}
}
}
*newPtr = 1;
if (typePtr->allocEntryProc) {
hPtr = typePtr->allocEntryProc (tablePtr, (VOID *) key);
} else {
hPtr = (Tcl_HashEntry *) ckalloc((unsigned) sizeof(Tcl_HashEntry));
hPtr->key.oneWordValue = (char *) key;
}
hPtr->tablePtr = tablePtr;
#if TCL_HASH_KEY_STORE_HASH
# if TCL_PRESERVE_BINARY_COMPATABILITY
hPtr->hash = (VOID *) hash;
# else
hPtr->hash = hash;
# endif
hPtr->nextPtr = tablePtr->buckets[index];
tablePtr->buckets[index] = hPtr;
#else
hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;
*hPtr->bucketPtr = hPtr;
#endif
hPtr->clientData = 0;
tablePtr->numEntries++;
if (tablePtr->numEntries >= tablePtr->rebuildSize) {
RebuildTable(tablePtr);
}
return hPtr;
}
void
Tcl_DeleteHashEntry(entryPtr)
Tcl_HashEntry *entryPtr;
{
register Tcl_HashEntry *prevPtr;
Tcl_HashKeyType *typePtr;
Tcl_HashTable *tablePtr;
Tcl_HashEntry **bucketPtr;
#if TCL_HASH_KEY_STORE_HASH
int index;
#endif
tablePtr = entryPtr->tablePtr;
#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;
#endif
#if TCL_HASH_KEY_STORE_HASH
if (typePtr->hashKeyProc == NULL
|| typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
index = RANDOM_INDEX (tablePtr, entryPtr->hash);
} else {
index = ((unsigned int) entryPtr->hash) & tablePtr->mask;
}
bucketPtr = &(tablePtr->buckets[index]);
#else
bucketPtr = entryPtr->bucketPtr;
#endif
if (*bucketPtr == entryPtr) {
*bucketPtr = entryPtr->nextPtr;
} else {
for (prevPtr = *bucketPtr; ; prevPtr = prevPtr->nextPtr) {
if (prevPtr == NULL) {
panic("malformed bucket chain in Tcl_DeleteHashEntry");
}
if (prevPtr->nextPtr == entryPtr) {
prevPtr->nextPtr = entryPtr->nextPtr;
break;
}
}
}
tablePtr->numEntries--;
if (typePtr->freeEntryProc) {
typePtr->freeEntryProc (entryPtr);
} else {
ckfree((char *) entryPtr);
}
}
void
Tcl_DeleteHashTable(tablePtr)
register Tcl_HashTable *tablePtr;
{
register Tcl_HashEntry *hPtr, *nextPtr;
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) {
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;
#endif
for (i = 0; i < tablePtr->numBuckets; i++) {
hPtr = tablePtr->buckets[i];
while (hPtr != NULL) {
nextPtr = hPtr->nextPtr;
if (typePtr->freeEntryProc) {
typePtr->freeEntryProc (hPtr);
} else {
ckfree((char *) hPtr);
}
hPtr = nextPtr;
}
}
if (tablePtr->buckets != tablePtr->staticBuckets) {
ckfree((char *) tablePtr->buckets);
}
#if TCL_PRESERVE_BINARY_COMPATABILITY
tablePtr->findProc = BogusFind;
tablePtr->createProc = BogusCreate;
#else
tablePtr->typePtr = NULL;
#endif
}
Tcl_HashEntry *
Tcl_FirstHashEntry(tablePtr, searchPtr)
Tcl_HashTable *tablePtr;
Tcl_HashSearch *searchPtr;
{
searchPtr->tablePtr = tablePtr;
searchPtr->nextIndex = 0;
searchPtr->nextEntryPtr = NULL;
return Tcl_NextHashEntry(searchPtr);
}
Tcl_HashEntry *
Tcl_NextHashEntry(searchPtr)
register Tcl_HashSearch *searchPtr;
{
Tcl_HashEntry *hPtr;
while (searchPtr->nextEntryPtr == NULL) {
if (searchPtr->nextIndex >= searchPtr->tablePtr->numBuckets) {
return NULL;
}
searchPtr->nextEntryPtr =
searchPtr->tablePtr->buckets[searchPtr->nextIndex];
searchPtr->nextIndex++;
}
hPtr = searchPtr->nextEntryPtr;
searchPtr->nextEntryPtr = hPtr->nextPtr;
return hPtr;
}
CONST char *
Tcl_HashStats(tablePtr)
Tcl_HashTable *tablePtr;
{
#define NUM_COUNTERS 10
int count[NUM_COUNTERS], overflow, i, j;
double average, tmp;
register Tcl_HashEntry *hPtr;
char *result, *p;
for (i = 0; i < NUM_COUNTERS; i++) {
count[i] = 0;
}
overflow = 0;
average = 0.0;
for (i = 0; i < tablePtr->numBuckets; i++) {
j = 0;
for (hPtr = tablePtr->buckets[i]; hPtr != NULL; hPtr = hPtr->nextPtr) {
j++;
}
if (j < NUM_COUNTERS) {
count[j]++;
} else {
overflow++;
}
tmp = j;
average += (tmp+1.0)*(tmp/tablePtr->numEntries)/2.0;
}
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++) {
sprintf(p, "number of buckets with %d entries: %d\n",
i, count[i]);
p += strlen(p);
}
sprintf(p, "number of buckets with %d or more entries: %d\n",
NUM_COUNTERS, overflow);
p += strlen(p);
sprintf(p, "average search distance for entry: %.1f", average);
return result;
}
static Tcl_HashEntry *
AllocArrayEntry(tablePtr, keyPtr)
Tcl_HashTable *tablePtr;
VOID *keyPtr;
{
int *array = (int *) keyPtr;
register int *iPtr1, *iPtr2;
Tcl_HashEntry *hPtr;
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);
for (iPtr1 = array, iPtr2 = hPtr->key.words;
count > 0; count--, iPtr1++, iPtr2++) {
*iPtr2 = *iPtr1;
}
return hPtr;
}
static int
CompareArrayKeys(keyPtr, hPtr)
VOID *keyPtr;
Tcl_HashEntry *hPtr;
{
register CONST int *iPtr1 = (CONST int *) keyPtr;
register CONST int *iPtr2 = (CONST int *) hPtr->key.words;
Tcl_HashTable *tablePtr = hPtr->tablePtr;
int count;
for (count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {
if (count == 0) {
return 1;
}
if (*iPtr1 != *iPtr2) {
break;
}
}
return 0;
}
static unsigned int
HashArrayKey(tablePtr, keyPtr)
Tcl_HashTable *tablePtr;
VOID *keyPtr;
{
register CONST int *array = (CONST int *) keyPtr;
register unsigned int result;
int count;
for (result = 0, count = tablePtr->keyType; count > 0;
count--, array++) {
result += *array;
}
return result;
}
static Tcl_HashEntry *
AllocStringEntry(tablePtr, keyPtr)
Tcl_HashTable *tablePtr;
VOID *keyPtr;
{
CONST char *string = (CONST char *) keyPtr;
Tcl_HashEntry *hPtr;
unsigned int size;
size = sizeof(Tcl_HashEntry) + strlen(string) + 1 - sizeof(hPtr->key);
if (size < sizeof(Tcl_HashEntry))
size = sizeof(Tcl_HashEntry);
hPtr = (Tcl_HashEntry *) ckalloc(size);
strcpy(hPtr->key.string, string);
return hPtr;
}
static int
CompareStringKeys(keyPtr, hPtr)
VOID *keyPtr;
Tcl_HashEntry *hPtr;
{
register CONST char *p1 = (CONST char *) keyPtr;
register CONST char *p2 = (CONST char *) hPtr->key.string;
for (;; p1++, p2++) {
if (*p1 != *p2) {
break;
}
if (*p1 == '\0') {
return 1;
}
}
return 0;
}
static unsigned int
HashStringKey(tablePtr, keyPtr)
Tcl_HashTable *tablePtr;
VOID *keyPtr;
{
register CONST char *string = (CONST char *) keyPtr;
register unsigned int result;
register int c;
result = 0;
while (1) {
c = *string;
string++;
if (c == 0) {
break;
}
result += (result<<3) + c;
}
return result;
}
#if TCL_PRESERVE_BINARY_COMPATABILITY
static Tcl_HashEntry *
BogusFind(tablePtr, key)
Tcl_HashTable *tablePtr;
CONST char *key;
{
panic("called Tcl_FindHashEntry on deleted table");
return NULL;
}
static Tcl_HashEntry *
BogusCreate(tablePtr, key, newPtr)
Tcl_HashTable *tablePtr;
CONST char *key;
int *newPtr;
{
panic("called Tcl_CreateHashEntry on deleted table");
return NULL;
}
#endif
static void
RebuildTable(tablePtr)
register Tcl_HashTable *tablePtr;
{
int oldSize, count, index;
Tcl_HashEntry **oldBuckets;
register Tcl_HashEntry **oldChainPtr, **newChainPtr;
register Tcl_HashEntry *hPtr;
Tcl_HashKeyType *typePtr;
VOID *key;
oldSize = tablePtr->numBuckets;
oldBuckets = tablePtr->buckets;
tablePtr->numBuckets *= 4;
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;
tablePtr->downShift -= 2;
tablePtr->mask = (tablePtr->mask << 2) + 3;
#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;
#endif
for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) {
for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) {
*oldChainPtr = hPtr->nextPtr;
key = (VOID *) Tcl_GetHashKey (tablePtr, hPtr);
#if TCL_HASH_KEY_STORE_HASH
if (typePtr->hashKeyProc == NULL
|| typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
index = RANDOM_INDEX (tablePtr, hPtr->hash);
} else {
index = ((unsigned int) hPtr->hash) & tablePtr->mask;
}
hPtr->nextPtr = tablePtr->buckets[index];
tablePtr->buckets[index] = hPtr;
#else
if (typePtr->hashKeyProc) {
unsigned int hash;
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 {
index = RANDOM_INDEX (tablePtr, key);
}
hPtr->bucketPtr = &(tablePtr->buckets[index]);
hPtr->nextPtr = *hPtr->bucketPtr;
*hPtr->bucketPtr = hPtr;
#endif
}
}
if (oldBuckets != tablePtr->staticBuckets) {
ckfree((char *) oldBuckets);
}
}