diff options
Diffstat (limited to 'generic/tclHash.c')
| -rw-r--r-- | generic/tclHash.c | 249 |
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: + */ |