*	is a newly-created entry, then *newPtr will be set to a non-zero *	value;  otherwise *newPtr will be set to 0.  If this is a new *	entry the value stored in the entry will initially be 0. * * Side effects: *	A new entry may be added to the hash table. * *---------------------------------------------------------------------- */static Tcl_HashEntry *StringCreate(tablePtr, key, newPtr)    Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */    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;    register char *p1, *p2;    int index;    index = HashString(key) & tablePtr->mask;    /*     * Search all of the entries in this bucket.     */    for (hPtr = tablePtr->buckets[index]; hPtr != NULL;	    hPtr = hPtr->nextPtr) {	for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) {	    if (*p1 != *p2) {		break;	    }	    if (*p1 == '\0') {		*newPtr = 0;		return hPtr;	    }	}    }    /*     * Entry not found.  Add a new one to the bucket.     */    *newPtr = 1;    hPtr = (Tcl_HashEntry *) ckalloc((unsigned)	    (sizeof(Tcl_HashEntry) + strlen(key) - (sizeof(hPtr->key) -1)));    hPtr->tablePtr = tablePtr;    hPtr->bucketPtr = &(tablePtr->buckets[index]);    hPtr->nextPtr = *hPtr->bucketPtr;    hPtr->clientData = 0;    strcpy(hPtr->key.string, key);    *hPtr->bucketPtr = hPtr;    tablePtr->numEntries++;    /*     * If the table has exceeded a decent size, rebuild it with many     * more buckets.     */    if (tablePtr->numEntries >= tablePtr->rebuildSize) {	RebuildTable(tablePtr);    }    return hPtr;}/* *---------------------------------------------------------------------- * * OneWordFind -- * *	Given a hash table with one-word keys, and a one-word key, find *	the entry with a matching key. * * Results: *	The return value is a token for the matching entry in the *	hash table, or NULL if there was no matching entry. * * Side effects: *	None. * *---------------------------------------------------------------------- */static Tcl_HashEntry *OneWordFind(tablePtr, key)    Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */    register char *key;		/* Key to use to find matching entry. */{    register Tcl_HashEntry *hPtr;    int index;    index = RANDOM_INDEX(tablePtr, key);    /*     * Search all of the entries in the appropriate bucket.     */    for (hPtr = tablePtr->buckets[index]; hPtr != NULL;	    hPtr = hPtr->nextPtr) {	if (hPtr->key.oneWordValue == key) {	    return hPtr;	}    }    return NULL;}/* *---------------------------------------------------------------------- * * OneWordCreate -- * *	Given a hash table with one-word keys, and a one-word key, find *	the entry with a matching key.  If there is no matching entry, *	then create a new entry that does match. * * Results: *	The return value is a pointer to the matching entry.  If this *	is a newly-created entry, then *newPtr will be set to a non-zero *	value;  otherwise *newPtr will be set to 0.  If this is a new *	entry the value stored in the entry will initially be 0. * * Side effects: *	A new entry may be added to the hash table. * *---------------------------------------------------------------------- */static Tcl_HashEntry *OneWordCreate(tablePtr, key, newPtr)    Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */    register 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;    int index;    index = RANDOM_INDEX(tablePtr, key);    /*     * Search all of the entries in this bucket.     */    for (hPtr = tablePtr->buckets[index]; hPtr != NULL;	    hPtr = hPtr->nextPtr) {	if (hPtr->key.oneWordValue == key) {	    *newPtr = 0;	    return hPtr;	}    }    /*     * Entry not found.  Add a new one to the bucket.     */    *newPtr = 1;    hPtr = (Tcl_HashEntry *) ckalloc(sizeof(Tcl_HashEntry));    hPtr->tablePtr = tablePtr;    hPtr->bucketPtr = &(tablePtr->buckets[index]);    hPtr->nextPtr = *hPtr->bucketPtr;    hPtr->clientData = 0;    hPtr->key.oneWordValue = key;    *hPtr->bucketPtr = hPtr;    tablePtr->numEntries++;    /*     * If the table has exceeded a decent size, rebuild it with many     * more buckets.     */    if (tablePtr->numEntries >= tablePtr->rebuildSize) {	RebuildTable(tablePtr);    }    return hPtr;}/* *---------------------------------------------------------------------- * * ArrayFind -- * *	Given a hash table with array-of-int keys, and a key, find *	the entry with a matching key. * * Results: *	The return value is a token for the matching entry in the *	hash table, or NULL if there was no matching entry. * * Side effects: *	None. * *---------------------------------------------------------------------- */static Tcl_HashEntry *ArrayFind(tablePtr, key)    Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */    char *key;			/* Key to use to find matching entry. */{    register Tcl_HashEntry *hPtr;    int *arrayPtr = (int *) key;    register int *iPtr1, *iPtr2;    int index, count;    for (index = 0, count = tablePtr->keyType, iPtr1 = arrayPtr;	    count > 0; count--, iPtr1++) {	index += *iPtr1;    }    index = RANDOM_INDEX(tablePtr, index);    /*     * Search all of the entries in the appropriate bucket.     */    for (hPtr = tablePtr->buckets[index]; hPtr != NULL;	    hPtr = hPtr->nextPtr) {	for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words,		count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {	    if (count == 0) {		return hPtr;	    }	    if (*iPtr1 != *iPtr2) {		break;	    }	}    }    return NULL;}/* *---------------------------------------------------------------------- * * ArrayCreate -- * *	Given a hash table with one-word keys, and a one-word key, find *	the entry with a matching key.  If there is no matching entry, *	then create a new entry that does match. * * Results: *	The return value is a pointer to the matching entry.  If this *	is a newly-created entry, then *newPtr will be set to a non-zero *	value;  otherwise *newPtr will be set to 0.  If this is a new *	entry the value stored in the entry will initially be 0. * * Side effects: *	A new entry may be added to the hash table. * *---------------------------------------------------------------------- */static Tcl_HashEntry *ArrayCreate(tablePtr, key, newPtr)    Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */    register 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;    int *arrayPtr = (int *) key;    register int *iPtr1, *iPtr2;    int index, count;    for (index = 0, count = tablePtr->keyType, iPtr1 = arrayPtr;	    count > 0; count--, iPtr1++) {	index += *iPtr1;    }    index = RANDOM_INDEX(tablePtr, index);    /*     * Search all of the entries in the appropriate bucket.     */    for (hPtr = tablePtr->buckets[index]; hPtr != NULL;	    hPtr = hPtr->nextPtr) {	for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words,		count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) {	    if (count == 0) {		*newPtr = 0;		return hPtr;	    }	    if (*iPtr1 != *iPtr2) {		break;	    }	}    }    /*     * Entry not found.  Add a new one to the bucket.     */    *newPtr = 1;    hPtr = (Tcl_HashEntry *) ckalloc((unsigned) (sizeof(Tcl_HashEntry)	    + (tablePtr->keyType*sizeof(int)) - 4));    hPtr->tablePtr = tablePtr;    hPtr->bucketPtr = &(tablePtr->buckets[index]);    hPtr->nextPtr = *hPtr->bucketPtr;    hPtr->clientData = 0;    for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words, count = tablePtr->keyType;	    count > 0; count--, iPtr1++, iPtr2++) {	*iPtr2 = *iPtr1;    }    *hPtr->bucketPtr = hPtr;    tablePtr->numEntries++;    /*     * If the table has exceeded a decent size, rebuild it with many     * more buckets.     */    if (tablePtr->numEntries >= tablePtr->rebuildSize) {	RebuildTable(tablePtr);    }    return hPtr;}/* *---------------------------------------------------------------------- * * BogusFind -- * *	This procedure is invoked when an Tcl_FindHashEntry is called *	on a table that has been deleted. * * Results: *	If panic returns (which it shouldn't) this procedure returns *	NULL. * * Side effects: *	Generates a panic. * *---------------------------------------------------------------------- */	/* ARGSUSED */static Tcl_HashEntry *BogusFind(tablePtr, key)    Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */    char *key;			/* Key to use to find matching entry. */{    panic("called Tcl_FindHashEntry on deleted table");    return NULL;}/* *---------------------------------------------------------------------- * * BogusCreate -- * *	This procedure is invoked when an Tcl_CreateHashEntry is called *	on a table that has been deleted. * * Results: *	If panic returns (which it shouldn't) this procedure returns *	NULL. * * Side effects: *	Generates a panic. * *---------------------------------------------------------------------- */	/* ARGSUSED */static Tcl_HashEntry *BogusCreate(tablePtr, key, newPtr)    Tcl_HashTable *tablePtr;	/* Table in which to lookup entry. */    char *key;			/* Key to use to find or create matching				 * entry. */    int *newPtr;		/* Store info here telling whether a new				 * entry was created. */{    panic("called Tcl_CreateHashEntry on deleted table");    return NULL;}/* *---------------------------------------------------------------------- * * RebuildTable -- * *	This procedure is invoked when the ratio of entries to hash *	buckets becomes too large.  It creates a new table with a *	larger bucket array and moves all of the entries into the *	new table. * * Results: *	None. * * Side effects: *	Memory gets reallocated and entries get re-hashed to new *	buckets. * *---------------------------------------------------------------------- */static voidRebuildTable(tablePtr)    register Tcl_HashTable *tablePtr;	/* Table to enlarge. */{    int oldSize, count, index;    Tcl_HashEntry **oldBuckets;    register Tcl_HashEntry **oldChainPtr, **newChainPtr;    register Tcl_HashEntry *hPtr;    oldSize = tablePtr->numBuckets;    oldBuckets = tablePtr->buckets;    /*     * Allocate and initialize the new bucket array, and set up     * hashing constants for new array size.     */    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;    /*     * Rehash all of the existing entries into the new bucket array.     */    for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) {	for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) {	    *oldChainPtr = hPtr->nextPtr;	    if (tablePtr->keyType == TCL_STRING_KEYS) {		index = HashString(hPtr->key.string) & tablePtr->mask;	    } else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {		index = RANDOM_INDEX(tablePtr, hPtr->key.oneWordValue);	    } else {		register int *iPtr;		int count;		for (index = 0, count = tablePtr->keyType,			iPtr = hPtr->key.words; count > 0; count--, iPtr++) {		    index += *iPtr;		}		index = RANDOM_INDEX(tablePtr, index);	    }	    hPtr->bucketPtr = &(tablePtr->buckets[index]);	    hPtr->nextPtr = *hPtr->bucketPtr;	    *hPtr->bucketPtr = hPtr;	}    }    /*     * Free up the old bucket array, if it was dynamically allocated.     */    if (oldBuckets != tablePtr->staticBuckets) {	ckfree((char *) oldBuckets);    }}#elsestatic const char file_name[] = "tclHash.c";#endif /* EXCLUDE_TCL */