1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/*
* tclHash.c --
*
* Implementation of in-memory hash tables for Tcl and Tcl-based
* applications.
*
* 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.
*
* RCS: @(#) $Id: tclHash.c,v 1.39 2009/07/16 21:24:39 dgp Exp $
*/
#include "tclInt.h"
/*
* Prevent macros from clashing with function definitions.
*/
|
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
|
/*
* tclHash.c --
*
* Implementation of in-memory hash tables for Tcl and Tcl-based
* applications.
*
* 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.
*
* RCS: @(#) $Id: tclHash.c,v 1.40 2010/02/07 09:10:33 dkf Exp $
*/
#include "tclInt.h"
/*
* Prevent macros from clashing with function definitions.
*/
|
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
|
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static unsigned int
HashStringKey(
Tcl_HashTable *tablePtr, /* Hash table. */
void *keyPtr) /* Key from which to compute hash value. */
{
register const char *string = (const char *) keyPtr;
register unsigned int result;
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:
*
* 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;
for (c=*string++ ; c ; c=*string++) {
result += (result<<3) + c;
|
|
|
|
|
|
>
|
<
|
|
<
<
<
<
<
<
<
|
|
|
|
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
|
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static unsigned
HashStringKey(
Tcl_HashTable *tablePtr, /* Hash table. */
void *keyPtr) /* Key from which to compute hash value. */
{
register const char *string = (const char *) keyPtr;
register unsigned result = 0;
register int c;
/*
* 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 command and namespace names. It
* is also faster than Tcl's original algorithm on Intel x86, where there
* is a fast built-in multiply assembly instruction.
*
* Derived from Public Domain implementation by Landon Curt Noll at:
* http://www.isthe.com/chongo/src/fnv/hash_32.c
*/
#define FNV_32_PRIME ((unsigned) 0x01000193)
while ((c=*string++)) {
result = (result * FNV_32_PRIME) ^ c;
}
return result;
}
/*
*----------------------------------------------------------------------
*
|