From 85d00a55b79e0beebaf4875584cf7391abd05392 Mon Sep 17 00:00:00 2001 From: dkf Date: Tue, 16 Feb 2010 14:09:06 +0000 Subject: Update literal table to use FNV hash function. --- ChangeLog | 43 +++++++++-------- generic/tclLiteral.c | 132 +++++++++++++++++++++++++++------------------------ 2 files changed, 93 insertions(+), 82 deletions(-) diff --git a/ChangeLog b/ChangeLog index 8e47e77..9b1b4d7 100644 --- a/ChangeLog +++ b/ChangeLog @@ -1,24 +1,29 @@ +2010-02-16 Donal K. Fellows + + * generic/tclLiteral.c (HashString): Missed updating to FNV in one + place; the literal table (a copy of the hash table code...) + 2010-02-15 Jan Nijtmans - * tools/genStubs.tcl reverted earlier rename from tcl*Stubs to - * generic/tclBasic.c tcl*ConstStubs, it's not necessary at all. - * generic/tclOO.c - * generic/tclTomMathInterface.c - * generic/tclStubInit.c (regenerated) - * generic/tclOOStubInit.c (regenerated) - * generic/tclEnsemble.c Fix signed-unsigned mismatch - * win/tclWinInt.h make tclWinProcs "const" - * win/tclWin32Dll.c - * win/tclWinFCmd.c Eliminate all internal Tcl_WinUtfToTChar - * win/tclWinFile.c and Tcl_WinTCharToUtf calls, needed - * win/tclWinInit.c for mslu support. - * win/tclWinLoad.c - * win/tclWinPipe.c - * win/tclWinSerial.c - * win/.cvsignore - * compat/unicows/readme.txt Add first part of mslu support - * compat/unicows/license.txt See [Feature Request #2819611] - * compat/unicows/unicows.lib + * tools/genStubs.tcl: Reverted earlier rename from tcl*Stubs to + * generic/tclBasic.c: tcl*ConstStubs, it's not necessary at all. + * generic/tclOO.c: + * generic/tclTomMathInterface.c: + * generic/tclStubInit.c: (regenerated) + * generic/tclOOStubInit.c: (regenerated) + * generic/tclEnsemble.c:Fix signed-unsigned mismatch + * win/tclWinInt.h: make tclWinProcs "const" + * win/tclWin32Dll.c: + * win/tclWinFCmd.c: Eliminate all internal Tcl_WinUtfToTChar + * win/tclWinFile.c: and Tcl_WinTCharToUtf calls, needed + * win/tclWinInit.c: for mslu support. + * win/tclWinLoad.c: + * win/tclWinPipe.c: + * win/tclWinSerial.c: + * win/.cvsignore: + * compat/unicows/readme.txt: [FRQ 2819611]: Add first part of MSLU + * compat/unicows/license.txt: support. + * compat/unicows/unicows.lib: 2010-02-15 Donal K. Fellows diff --git a/generic/tclLiteral.c b/generic/tclLiteral.c index 10a18f8..cda9caf 100644 --- a/generic/tclLiteral.c +++ b/generic/tclLiteral.c @@ -13,7 +13,7 @@ * See the file "license.terms" for information on usage and redistribution of * this file, and for a DISCLAIMER OF ALL WARRANTIES. * - * RCS: @(#) $Id: tclLiteral.c,v 1.37 2009/10/28 21:03:19 dgp Exp $ + * RCS: @(#) $Id: tclLiteral.c,v 1.38 2010/02/16 14:09:07 dkf Exp $ */ #include "tclInt.h" @@ -33,7 +33,7 @@ static int AddLocalLiteralEntry(CompileEnv *envPtr, Tcl_Obj *objPtr, int localHash); static void ExpandLocalLiteralArray(CompileEnv *envPtr); -static unsigned int HashString(const char *bytes, int length); +static unsigned HashString(const char *bytes, int length); static void RebuildLiteralTable(LiteralTable *tablePtr); /* @@ -61,7 +61,7 @@ TclInitLiteralTable( * supplied by the caller. */ { #if (TCL_SMALL_HASH_TABLE != 4) - Tcl_Panic("TclInitLiteralTable: TCL_SMALL_HASH_TABLE is %d, not 4", + Tcl_Panic("%s: TCL_SMALL_HASH_TABLE is %d, not 4", "TclInitLiteralTable", TCL_SMALL_HASH_TABLE); #endif @@ -99,12 +99,12 @@ TclCleanupLiteralTable( * cleaned. */ { int i; - LiteralEntry* entryPtr; /* Pointer to the current entry in the hash + LiteralEntry *entryPtr; /* Pointer to the current entry in the hash * table of literals. */ - LiteralEntry* nextPtr; /* Pointer to the next entry in the bucket. */ - Tcl_Obj* objPtr; /* Pointer to a literal object whose internal + LiteralEntry *nextPtr; /* Pointer to the next entry in the bucket. */ + Tcl_Obj *objPtr; /* Pointer to a literal object whose internal * rep is being freed. */ - const Tcl_ObjType* typePtr; /* Pointer to the object's type. */ + const Tcl_ObjType *typePtr; /* Pointer to the object's type. */ int didOne; /* Flag for whether we've removed a literal in * the current bucket. */ @@ -131,7 +131,8 @@ TclCleanupLiteralTable( typePtr = objPtr->typePtr; if ((typePtr != NULL) && (typePtr->freeIntRepProc != NULL)) { if (objPtr->bytes == NULL) { - Tcl_Panic("literal without a string rep"); + Tcl_Panic("%s: literal without a string rep", + "TclCleanupLiteralTable"); } objPtr->typePtr = NULL; typePtr->freeIntRepProc(objPtr); @@ -243,9 +244,10 @@ TclDeleteLiteralTable( Tcl_Obj * TclCreateLiteral( Interp *iPtr, - char *bytes, - int length, - unsigned int hash, /* The string's hash. If -1, it will be + char *bytes, /* The start of the string. Note that this is + * not a NUL-terminated string. */ + int length, /* Number of bytes in the string. */ + unsigned hash, /* The string's hash. If -1, it will be * computed here. */ int *newPtr, Namespace *nsPtr, @@ -312,8 +314,8 @@ TclCreateLiteral( #ifdef TCL_COMPILE_DEBUG if (TclLookupLiteralEntry((Tcl_Interp *) iPtr, objPtr) != NULL) { - Tcl_Panic("TclRegisterLiteral: literal \"%.*s\" found globally but shouldn't be", - (length>60? 60 : length), bytes); + Tcl_Panic("%s: literal \"%.*s\" found globally but shouldn't be", + "TclRegisterLiteral" (length>60? 60 : length), bytes); } #endif @@ -350,8 +352,8 @@ TclCreateLiteral( } } if (!found) { - Tcl_Panic("TclRegisterLiteral: literal \"%.*s\" wasn't global", - (length>60? 60 : length), bytes); + Tcl_Panic("%s: literal \"%.*s\" wasn't global", + "TclRegisterLiteral", (length>60? 60 : length), bytes); } } #endif /*TCL_COMPILE_DEBUG*/ @@ -414,10 +416,10 @@ TclRegisterLiteral( * namespaces. */ { Interp *iPtr = envPtr->iPtr; - LiteralTable *localTablePtr = &(envPtr->localLitTable); + LiteralTable *localTablePtr = &envPtr->localLitTable; LiteralEntry *globalPtr, *localPtr; Tcl_Obj *objPtr; - unsigned int hash; + unsigned hash; int localHash, objIndex, new; Namespace *nsPtr; @@ -467,14 +469,15 @@ TclRegisterLiteral( * Is it in the interpreter's global literal table? If not, create it. */ - objPtr = TclCreateLiteral(iPtr, bytes, length, hash, &new, nsPtr, - flags, &globalPtr); + objPtr = TclCreateLiteral(iPtr, bytes, length, hash, &new, nsPtr, flags, + &globalPtr); objIndex = AddLocalLiteralEntry(envPtr, objPtr, localHash); #ifdef TCL_COMPILE_DEBUG if (globalPtr->refCount < 1) { - Tcl_Panic("TclRegisterLiteral: global literal \"%.*s\" had bad refCount %d", - (length>60? 60 : length), bytes, globalPtr->refCount); + Tcl_Panic("%s: global literal \"%.*s\" had bad refCount %d", + "TclRegisterLiteral", (length>60? 60 : length), bytes, + globalPtr->refCount); } TclVerifyLocalLiteralTable(envPtr); #endif /*TCL_COMPILE_DEBUG*/ @@ -507,7 +510,7 @@ TclLookupLiteralEntry( * TclRegisterLiteral. */ { Interp *iPtr = (Interp *) interp; - LiteralTable *globalTablePtr = &(iPtr->literalTable); + LiteralTable *globalTablePtr = &iPtr->literalTable; register LiteralEntry *entryPtr; const char *bytes; int length, globalHash; @@ -553,12 +556,12 @@ TclHideLiteral( * array. */ { LiteralEntry **nextPtrPtr, *entryPtr, *lPtr; - LiteralTable *localTablePtr = &(envPtr->localLitTable); + LiteralTable *localTablePtr = &envPtr->localLitTable; int localHash, length; const char *bytes; Tcl_Obj *newObjPtr; - lPtr = &(envPtr->literalArrayPtr[index]); + lPtr = &envPtr->literalArrayPtr[index]; /* * To avoid unwanted sharing we need to copy the object and remove it from @@ -626,7 +629,7 @@ TclAddLiteralObj( objIndex = envPtr->literalArrayNext; envPtr->literalArrayNext++; - lPtr = &(envPtr->literalArrayPtr[objIndex]); + lPtr = &envPtr->literalArrayPtr[objIndex]; lPtr->objPtr = objPtr; Tcl_IncrRefCount(objPtr); lPtr->refCount = -1; /* i.e., unused */ @@ -664,7 +667,7 @@ AddLocalLiteralEntry( Tcl_Obj *objPtr, /* The literal to add to the CompileEnv. */ int localHash) /* Hash value for the literal's string. */ { - register LiteralTable *localTablePtr = &(envPtr->localLitTable); + register LiteralTable *localTablePtr = &envPtr->localLitTable; LiteralEntry *localPtr; int objIndex; @@ -705,8 +708,8 @@ AddLocalLiteralEntry( if (!found) { bytes = Tcl_GetStringFromObj(objPtr, &length); - Tcl_Panic("AddLocalLiteralEntry: literal \"%.*s\" wasn't found locally", - (length>60? 60 : length), bytes); + Tcl_Panic("%s: literal \"%.*s\" wasn't found locally", + "AddLocalLiteralEntry", (length>60? 60 : length), bytes); } } #endif /*TCL_COMPILE_DEBUG*/ @@ -744,7 +747,7 @@ ExpandLocalLiteralArray( * 0 and (envPtr->literalArrayNext - 1) [inclusive]. */ - LiteralTable *localTablePtr = &(envPtr->localLitTable); + LiteralTable *localTablePtr = &envPtr->localLitTable; int currElems = envPtr->literalArrayNext; size_t currBytes = (currElems * sizeof(LiteralEntry)); LiteralEntry *currArrayPtr = envPtr->literalArrayPtr; @@ -752,13 +755,14 @@ ExpandLocalLiteralArray( int i; if (envPtr->mallocedLiteralArray) { - newArrayPtr = (LiteralEntry *) ckrealloc( - (char *)currArrayPtr, 2 * currBytes); + newArrayPtr = (LiteralEntry *) + ckrealloc((char *)currArrayPtr, 2 * currBytes); } else { /* * envPtr->literalArrayPtr isn't a ckalloc'd pointer, so we must - * code a ckrealloc equivalent for ourselves + * code a ckrealloc equivalent for ourselves. */ + newArrayPtr = (LiteralEntry *) ckalloc(2 * currBytes); memcpy(newArrayPtr, currArrayPtr, currBytes); envPtr->mallocedLiteralArray = 1; @@ -817,7 +821,7 @@ TclReleaseLiteral( * TclRegisterLiteral. */ { Interp *iPtr = (Interp *) interp; - LiteralTable *globalTablePtr = &(iPtr->literalTable); + LiteralTable *globalTablePtr = &iPtr->literalTable; register LiteralEntry *entryPtr, *prevPtr; const char *bytes; int length, index; @@ -885,33 +889,28 @@ TclReleaseLiteral( *---------------------------------------------------------------------- */ -static unsigned int +static unsigned HashString( register const char *bytes, /* String for which to compute hash value. */ int length) /* Number of bytes in the string. */ { - register unsigned int result; - register int i; + unsigned result = 0x811c9dc5; + const char *last = bytes + length; /* - * 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: + * This is the (32-bit) Fowler/Noll/Vo hash algorithm. This has the + * property of being a reasonably good non-cryptographic hash function for + * short string words, i.e., virtually all names used in practice. It is + * also faster than Tcl's original algorithm on Intel x86, where there is + * a fast built-in multiply assembly instruction. * - * 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. + * Derived from Public Domain implementation by Landon Curt Noll at: + * http://www.isthe.com/chongo/src/fnv/hash_32.c */ - result = 0; - for (i=0 ; imask); *oldChainPtr = entryPtr->nextPtr; - bucketPtr = &(tablePtr->buckets[index]); + bucketPtr = &tablePtr->buckets[index]; entryPtr->nextPtr = *bucketPtr; *bucketPtr = entryPtr; } @@ -1086,7 +1085,7 @@ TclVerifyLocalLiteralTable( CompileEnv *envPtr) /* Points to CompileEnv whose literal table is * to be validated. */ { - register LiteralTable *localTablePtr = &(envPtr->localLitTable); + register LiteralTable *localTablePtr = &envPtr->localLitTable; register LiteralEntry *localPtr; char *bytes; register int i; @@ -1099,23 +1098,27 @@ TclVerifyLocalLiteralTable( count++; if (localPtr->refCount != -1) { bytes = Tcl_GetStringFromObj(localPtr->objPtr, &length); - Tcl_Panic("TclVerifyLocalLiteralTable: local literal \"%.*s\" had bad refCount %d", + Tcl_Panic("%s: local literal \"%.*s\" had bad refCount %d", + "TclVerifyLocalLiteralTable", (length>60? 60 : length), bytes, localPtr->refCount); } if (TclLookupLiteralEntry((Tcl_Interp *) envPtr->iPtr, localPtr->objPtr) == NULL) { bytes = Tcl_GetStringFromObj(localPtr->objPtr, &length); - Tcl_Panic("TclVerifyLocalLiteralTable: local literal \"%.*s\" is not global", + Tcl_Panic("%s: local literal \"%.*s\" is not global", + "TclVerifyLocalLiteralTable", (length>60? 60 : length), bytes); } if (localPtr->objPtr->bytes == NULL) { - Tcl_Panic("TclVerifyLocalLiteralTable: literal has NULL string rep"); + Tcl_Panic("%s: literal has NULL string rep", + "TclVerifyLocalLiteralTable"); } } } if (count != localTablePtr->numEntries) { - Tcl_Panic("TclVerifyLocalLiteralTable: local literal table had %d entries, should be %d", - count, localTablePtr->numEntries); + Tcl_Panic("%s: local literal table had %d entries, should be %d", + "TclVerifyLocalLiteralTable", count, + localTablePtr->numEntries); } } @@ -1140,7 +1143,7 @@ TclVerifyGlobalLiteralTable( Interp *iPtr) /* Points to interpreter whose global literal * table is to be validated. */ { - register LiteralTable *globalTablePtr = &(iPtr->literalTable); + register LiteralTable *globalTablePtr = &iPtr->literalTable; register LiteralEntry *globalPtr; char *bytes; register int i; @@ -1153,17 +1156,20 @@ TclVerifyGlobalLiteralTable( count++; if (globalPtr->refCount < 1) { bytes = Tcl_GetStringFromObj(globalPtr->objPtr, &length); - Tcl_Panic("TclVerifyGlobalLiteralTable: global literal \"%.*s\" had bad refCount %d", + Tcl_Panic("%s: global literal \"%.*s\" had bad refCount %d", + "TclVerifyGlobalLiteralTable", (length>60? 60 : length), bytes, globalPtr->refCount); } if (globalPtr->objPtr->bytes == NULL) { - Tcl_Panic("TclVerifyGlobalLiteralTable: literal has NULL string rep"); + Tcl_Panic("%s: literal has NULL string rep", + "TclVerifyGlobalLiteralTable"); } } } if (count != globalTablePtr->numEntries) { - Tcl_Panic("TclVerifyGlobalLiteralTable: global literal table had %d entries, should be %d", - count, globalTablePtr->numEntries); + Tcl_Panic("%s: global literal table had %d entries, should be %d", + "TclVerifyGlobalLiteralTable", count, + globalTablePtr->numEntries); } } #endif /*TCL_COMPILE_DEBUG*/ -- cgit v0.12