summaryrefslogtreecommitdiffstats
path: root/generic/tclHash.c
diff options
context:
space:
mode:
Diffstat (limited to 'generic/tclHash.c')
-rw-r--r--generic/tclHash.c249
1 files changed, 126 insertions, 123 deletions
diff --git a/generic/tclHash.c b/generic/tclHash.c
index 14de98a..861eb47 100644
--- a/generic/tclHash.c
+++ b/generic/tclHash.c
@@ -7,10 +7,10 @@
* 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.
+ * 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.22 2004/11/11 01:17:50 das Exp $
+ * RCS: @(#) $Id: tclHash.c,v 1.23 2005/07/21 14:38:32 dkf Exp $
*/
#include "tclInt.h"
@@ -25,18 +25,17 @@
#endif
/*
- * When there are this many entries per bucket, on average, rebuild
- * the hash table to make it larger.
+ * When there are this many entries per bucket, on average, rebuild the hash
+ * table to make it larger.
*/
#define REBUILD_MULTIPLIER 3
/*
- * The following macro takes a preliminary integer hash value and
- * produces an index into a hash tables bucket list. The idea is
- * to make it so that preliminary values that are arbitrarily similar
- * will end up in different buckets. The hash function was taken
- * from a random-number generator.
+ * The following macro takes a preliminary integer hash value and produces an
+ * index into a hash tables bucket list. The idea is to make it so that
+ * preliminary values that are arbitrarily similar will end up in different
+ * buckets. The hash function was taken from a random-number generator.
*/
#define RANDOM_INDEX(tablePtr, i) \
@@ -78,7 +77,7 @@ static unsigned int HashStringKey _ANSI_ARGS_((
Tcl_HashTable *tablePtr, VOID *keyPtr));
/*
- * Procedure prototypes for static procedures in this file:
+ * Function prototypes for static functions in this file:
*/
#if TCL_PRESERVE_BINARY_COMPATABILITY
@@ -116,15 +115,14 @@ Tcl_HashKeyType tclStringHashKeyType = {
AllocStringEntry, /* allocEntryProc */
NULL /* freeEntryProc */
};
-
/*
*----------------------------------------------------------------------
*
* Tcl_InitHashTable --
*
- * Given storage for a hash table, set up the fields to prepare
- * the hash table for use.
+ * Given storage for a hash table, set up the fields to prepare the hash
+ * table for use.
*
* Results:
* None.
@@ -139,18 +137,19 @@ Tcl_HashKeyType tclStringHashKeyType = {
#undef Tcl_InitHashTable
void
Tcl_InitHashTable(tablePtr, keyType)
- register Tcl_HashTable *tablePtr; /* Pointer to table record, which
- * is supplied by the caller. */
+ 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,
* or an integer >= 2. */
{
/*
- * Use a special value to inform the extended version that it must
- * not access any of the new fields in the Tcl_HashTable. If an
- * extension is rebuilt then any calls to this function will be
- * redirected to the extended version by a macro.
+ * Use a special value to inform the extended version that it must not
+ * access any of the new fields in the Tcl_HashTable. If an extension is
+ * rebuilt then any calls to this function will be redirected to the
+ * extended version by a macro.
*/
+
Tcl_InitCustomHashTable(tablePtr, keyType, (Tcl_HashKeyType *) -1);
}
@@ -159,9 +158,9 @@ Tcl_InitHashTable(tablePtr, keyType)
*
* Tcl_InitCustomHashTable --
*
- * Given storage for a hash table, set up the fields to prepare
- * the hash table for use. This is an extended version of
- * Tcl_InitHashTable which supports user defined keys.
+ * Given storage for a hash table, set up the fields to prepare the hash
+ * table for use. This is an extended version of Tcl_InitHashTable which
+ * supports user defined keys.
*
* Results:
* None.
@@ -175,13 +174,13 @@ Tcl_InitHashTable(tablePtr, keyType)
void
Tcl_InitCustomHashTable(tablePtr, keyType, typePtr)
- register Tcl_HashTable *tablePtr; /* Pointer to table record, which
- * is supplied by the caller. */
+ 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. */
+ * TCL_CUSTOM_PTR_KEYS, or an integer
+ * >= 2. */
Tcl_HashKeyType *typePtr; /* Pointer to structure which defines
* the behaviour of this table. */
{
@@ -210,14 +209,14 @@ Tcl_InitCustomHashTable(tablePtr, keyType, typePtr)
*/
} else if (typePtr != (Tcl_HashKeyType *) -1) {
/*
- * The caller is requesting a customized hash table so it must be
- * an extended version.
+ * The caller is requesting a customized hash table so it must be an
+ * extended version.
*/
+
tablePtr->typePtr = typePtr;
} else {
/*
- * The caller has not been rebuilt so the hash table is not
- * extended.
+ * The caller has not been rebuilt so the hash table is not extended.
*/
}
#else
@@ -225,6 +224,7 @@ Tcl_InitCustomHashTable(tablePtr, keyType, typePtr)
/*
* 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) {
@@ -238,10 +238,11 @@ Tcl_InitCustomHashTable(tablePtr, keyType, typePtr)
}
} 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.
+ * 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");
+
+ Tcl_Panic("Hash table is not compatible");
}
tablePtr->typePtr = typePtr;
#endif
@@ -255,8 +256,8 @@ Tcl_InitCustomHashTable(tablePtr, keyType, typePtr)
* Given a hash table 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.
+ * 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.
@@ -312,7 +313,7 @@ Tcl_FindHashEntry(tablePtr, key)
if (typePtr->compareKeysProc) {
Tcl_CompareHashKeysProc *compareKeysProc = typePtr->compareKeysProc;
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
- hPtr = hPtr->nextPtr) {
+ hPtr = hPtr->nextPtr) {
#if TCL_HASH_KEY_STORE_HASH
if (hash != (unsigned int) hPtr->hash) {
continue;
@@ -324,7 +325,7 @@ Tcl_FindHashEntry(tablePtr, key)
}
} else {
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
- hPtr = hPtr->nextPtr) {
+ hPtr = hPtr->nextPtr) {
#if TCL_HASH_KEY_STORE_HASH
if (hash != (unsigned int) hPtr->hash) {
continue;
@@ -344,15 +345,15 @@ Tcl_FindHashEntry(tablePtr, key)
*
* Tcl_CreateHashEntry --
*
- * Given a hash table with string keys, and a string key, find
- * the entry with a matching key. If there is no matching entry,
- * then create a new entry that does match.
+ * Given a hash table with string keys, and a string 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.
+ * 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.
@@ -365,8 +366,8 @@ Tcl_CreateHashEntry(tablePtr, key, newPtr)
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. */
+ int *newPtr; /* Store info here telling whether a new entry
+ * was created. */
{
register Tcl_HashEntry *hPtr;
Tcl_HashKeyType *typePtr;
@@ -411,7 +412,7 @@ Tcl_CreateHashEntry(tablePtr, key, newPtr)
if (typePtr->compareKeysProc) {
Tcl_CompareHashKeysProc *compareKeysProc = typePtr->compareKeysProc;
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
- hPtr = hPtr->nextPtr) {
+ hPtr = hPtr->nextPtr) {
#if TCL_HASH_KEY_STORE_HASH
if (hash != (unsigned int) hPtr->hash) {
continue;
@@ -424,7 +425,7 @@ Tcl_CreateHashEntry(tablePtr, key, newPtr)
}
} else {
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
- hPtr = hPtr->nextPtr) {
+ hPtr = hPtr->nextPtr) {
#if TCL_HASH_KEY_STORE_HASH
if (hash != (unsigned int) hPtr->hash) {
continue;
@@ -438,7 +439,7 @@ Tcl_CreateHashEntry(tablePtr, key, newPtr)
}
/*
- * Entry not found. Add a new one to the bucket.
+ * Entry not found. Add a new one to the bucket.
*/
*newPtr = 1;
@@ -467,8 +468,8 @@ Tcl_CreateHashEntry(tablePtr, key, newPtr)
tablePtr->numEntries++;
/*
- * If the table has exceeded a decent size, rebuild it with many
- * more buckets.
+ * If the table has exceeded a decent size, rebuild it with many more
+ * buckets.
*/
if (tablePtr->numEntries >= tablePtr->rebuildSize) {
@@ -488,10 +489,9 @@ Tcl_CreateHashEntry(tablePtr, key, newPtr)
* None.
*
* Side effects:
- * The entry given by entryPtr is deleted from its table and
- * should never again be used by the caller. It is up to the
- * caller to free the clientData field of the entry, if that
- * is relevant.
+ * The entry given by entryPtr is deleted from its table and should never
+ * again be used by the caller. It is up to the caller to free the
+ * clientData field of the entry, if that is relevant.
*
*----------------------------------------------------------------------
*/
@@ -565,8 +565,8 @@ Tcl_DeleteHashEntry(entryPtr)
*
* Tcl_DeleteHashTable --
*
- * Free up everything associated with a hash table except for
- * the record for the table itself.
+ * Free up everything associated with a hash table except for the record
+ * for the table itself.
*
* Results:
* None.
@@ -647,16 +647,14 @@ Tcl_DeleteHashTable(tablePtr)
*
* Tcl_FirstHashEntry --
*
- * Locate the first entry in a hash table and set up a record
- * that can be used to step through all the remaining entries
- * of the table.
+ * Locate the first entry in a hash table and set up a record that can be
+ * used to step through all the remaining entries of the table.
*
* Results:
- * The return value is a pointer to the first entry in tablePtr,
- * or NULL if tablePtr has no entries in it. The memory at
- * *searchPtr is initialized so that subsequent calls to
- * Tcl_NextHashEntry will return all of the entries in the table,
- * one at a time.
+ * The return value is a pointer to the first entry in tablePtr, or NULL
+ * if tablePtr has no entries in it. The memory at *searchPtr is
+ * initialized so that subsequent calls to Tcl_NextHashEntry will return
+ * all of the entries in the table, one at a time.
*
* Side effects:
* None.
@@ -666,9 +664,9 @@ Tcl_DeleteHashTable(tablePtr)
Tcl_HashEntry *
Tcl_FirstHashEntry(tablePtr, searchPtr)
- Tcl_HashTable *tablePtr; /* Table to search. */
- Tcl_HashSearch *searchPtr; /* Place to store information about
- * progress through the table. */
+ Tcl_HashTable *tablePtr; /* Table to search. */
+ Tcl_HashSearch *searchPtr; /* Place to store information about progress
+ * through the table. */
{
searchPtr->tablePtr = tablePtr;
searchPtr->nextIndex = 0;
@@ -682,12 +680,12 @@ Tcl_FirstHashEntry(tablePtr, searchPtr)
* Tcl_NextHashEntry --
*
* Once a hash table enumeration has been initiated by calling
- * Tcl_FirstHashEntry, this procedure may be called to return
- * successive elements of the table.
+ * Tcl_FirstHashEntry, this function may be called to return successive
+ * elements of the table.
*
* Results:
- * The return value is the next entry in the hash table being
- * enumerated, or NULL if the end of the table is reached.
+ * The return value is the next entry in the hash table being enumerated,
+ * or NULL if the end of the table is reached.
*
* Side effects:
* None.
@@ -697,10 +695,11 @@ Tcl_FirstHashEntry(tablePtr, searchPtr)
Tcl_HashEntry *
Tcl_NextHashEntry(searchPtr)
- register Tcl_HashSearch *searchPtr; /* Place to store information about
- * progress through the table. Must
- * have been initialized by calling
- * Tcl_FirstHashEntry. */
+ register Tcl_HashSearch *searchPtr;
+ /* Place to store information about progress
+ * through the table. Must have been
+ * initialized by calling
+ * Tcl_FirstHashEntry. */
{
Tcl_HashEntry *hPtr;
Tcl_HashTable *tablePtr = searchPtr->tablePtr;
@@ -723,13 +722,12 @@ Tcl_NextHashEntry(searchPtr)
*
* Tcl_HashStats --
*
- * Return statistics describing the layout of the hash table
- * in its hash buckets.
+ * Return statistics describing the layout of the hash table in its hash
+ * buckets.
*
* Results:
- * The return value is a malloc-ed string containing information
- * about tablePtr. It is the caller's responsibility to free
- * this string.
+ * The return value is a malloc-ed string containing information about
+ * tablePtr. It is the caller's responsibility to free this string.
*
* Side effects:
* None.
@@ -739,7 +737,7 @@ Tcl_NextHashEntry(searchPtr)
CONST char *
Tcl_HashStats(tablePtr)
- Tcl_HashTable *tablePtr; /* Table for which to produce stats. */
+ Tcl_HashTable *tablePtr; /* Table for which to produce stats. */
{
#define NUM_COUNTERS 10
int count[NUM_COUNTERS], overflow, i, j;
@@ -795,6 +793,7 @@ Tcl_HashStats(tablePtr)
/*
* 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 {
@@ -866,8 +865,8 @@ AllocArrayEntry(tablePtr, keyPtr)
* Compares two array keys.
*
* Results:
- * The return value is 0 if they are different and 1 if they are
- * the same.
+ * The return value is 0 if they are different and 1 if they are the
+ * same.
*
* Side effects:
* None.
@@ -901,8 +900,8 @@ CompareArrayKeys(keyPtr, hPtr)
*
* HashArrayKey --
*
- * Compute a one-word summary of an array, which can be
- * used to generate a hash index.
+ * Compute a one-word summary of an array, which can be used to generate
+ * a hash index.
*
* Results:
* The return value is a one-word summary of the information in
@@ -973,8 +972,8 @@ AllocStringEntry(tablePtr, keyPtr)
* Compares two string keys.
*
* Results:
- * The return value is 0 if they are different and 1 if they are
- * the same.
+ * The return value is 0 if they are different and 1 if they are the
+ * same.
*
* Side effects:
* None.
@@ -1010,12 +1009,11 @@ CompareStringKeys(keyPtr, hPtr)
*
* HashStringKey --
*
- * Compute a one-word summary of a text string, which can be
- * used to generate a hash index.
+ * Compute a one-word summary of a text string, which can be used to
+ * generate a hash index.
*
* Results:
- * The return value is a one-word summary of the information in
- * string.
+ * The return value is a one-word summary of the information in string.
*
* Side effects:
* None.
@@ -1033,19 +1031,20 @@ HashStringKey(tablePtr, keyPtr)
register int c;
/*
- * I tried a zillion different hash functions and asked many other
- * people for advice. Many people had their own favorite functions,
- * all different, but no-one had much idea why they were good ones.
- * I chose the one below (multiply by 9 and add new character)
- * because of the following reasons:
+ * I tried a zillion different hash functions and asked many other people
+ * for advice. Many people had their own favorite functions, all
+ * different, but no-one had much idea why they were good ones. I chose
+ * the one below (multiply by 9 and add new character) because of the
+ * following reasons:
*
- * 1. Multiplying by 10 is perfect for keys that are decimal strings,
- * and 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.
+ * 1. Multiplying by 10 is perfect for keys that are decimal strings, and
+ * 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.
*/
result = 0;
@@ -1062,12 +1061,11 @@ HashStringKey(tablePtr, keyPtr)
*
* BogusFind --
*
- * This procedure is invoked when an Tcl_FindHashEntry is called
- * on a table that has been deleted.
+ * This function is invoked when an Tcl_FindHashEntry is called on a
+ * table that has been deleted.
*
* Results:
- * If Tcl_Panic returns (which it shouldn't) this procedure returns
- * NULL.
+ * If Tcl_Panic returns (which it shouldn't) this function returns NULL.
*
* Side effects:
* Generates a panic.
@@ -1090,12 +1088,11 @@ BogusFind(tablePtr, key)
*
* BogusCreate --
*
- * This procedure is invoked when an Tcl_CreateHashEntry is called
- * on a table that has been deleted.
+ * This function 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.
+ * If panic returns (which it shouldn't) this function returns NULL.
*
* Side effects:
* Generates a panic.
@@ -1109,8 +1106,8 @@ BogusCreate(tablePtr, key, newPtr)
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. */
+ int *newPtr; /* Store info here telling whether a new entry
+ * was created. */
{
Tcl_Panic("called Tcl_CreateHashEntry on deleted table");
return NULL;
@@ -1122,17 +1119,15 @@ BogusCreate(tablePtr, key, newPtr)
*
* 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.
+ * This function 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.
+ * Memory gets reallocated and entries get re-hashed to new buckets.
*
*----------------------------------------------------------------------
*/
@@ -1166,8 +1161,8 @@ RebuildTable(tablePtr)
oldBuckets = tablePtr->buckets;
/*
- * Allocate and initialize the new bucket array, and set up
- * hashing constants for new array size.
+ * Allocate and initialize the new bucket array, and set up hashing
+ * constants for new array size.
*/
tablePtr->numBuckets *= 4;
@@ -1236,3 +1231,11 @@ RebuildTable(tablePtr)
}
}
}
+
+/*
+ * Local Variables:
+ * mode: c
+ * c-basic-offset: 4
+ * fill-column: 78
+ * End:
+ */