| ︙ | | |
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
|
-
+
-
+
|
* 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) \
((((i)*1103515245L) >> (tablePtr)->downShift) & (tablePtr)->mask)
((((i)*1103515245L) >> (tablePtr)->downShift) & (tablePtr)->mask1)
/*
* Prototypes for the array hash key methods.
*/
static Tcl_HashEntry * AllocArrayEntry(Tcl_HashTable *tablePtr, void *keyPtr);
static int CompareArrayKeys(void *keyPtr, Tcl_HashEntry *hPtr);
static size_t HashArrayKey(Tcl_HashTable *tablePtr, void *keyPtr);
static TCL_HASH_TYPE HashArrayKey(Tcl_HashTable *tablePtr, void *keyPtr);
/*
* Prototypes for the one word hash key methods. Not actually declared because
* this is a critical path that is implemented in the core hash table access
* function.
*/
|
| ︙ | | |
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
|
-
+
-
+
-
+
-
+
|
/*
* Prototypes for the string hash key methods.
*/
static Tcl_HashEntry * AllocStringEntry(Tcl_HashTable *tablePtr,
void *keyPtr);
static int CompareStringKeys(void *keyPtr, Tcl_HashEntry *hPtr);
static size_t HashStringKey(Tcl_HashTable *tablePtr, void *keyPtr);
static TCL_HASH_TYPE HashStringKey(Tcl_HashTable *tablePtr, void *keyPtr);
/*
* Function prototypes for static functions in this file:
*/
static Tcl_HashEntry * BogusFind(Tcl_HashTable *tablePtr, const void *key);
static Tcl_HashEntry * BogusCreate(Tcl_HashTable *tablePtr, const void *key,
int *newPtr);
static Tcl_HashEntry * CreateHashEntry(Tcl_HashTable *tablePtr, const void *key,
int *newPtr);
static Tcl_HashEntry * FindHashEntry(Tcl_HashTable *tablePtr, const void *key);
static void RebuildTable(Tcl_HashTable *tablePtr);
const Tcl_HashKeyType tclArrayHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION_2, /* version */
TCL_HASH_KEY_TYPE_VERSION, /* version */
TCL_HASH_KEY_RANDOMIZE_HASH, /* flags */
HashArrayKey, /* hashKeyProc */
CompareArrayKeys, /* compareKeysProc */
AllocArrayEntry, /* allocEntryProc */
NULL /* freeEntryProc */
};
const Tcl_HashKeyType tclOneWordHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION_2, /* version */
TCL_HASH_KEY_TYPE_VERSION, /* version */
0, /* flags */
NULL, /* HashOneWordKey, */ /* hashProc */
NULL, /* CompareOneWordKey, */ /* compareProc */
NULL, /* AllocOneWordKey, */ /* allocEntryProc */
NULL /* FreeOneWordKey, */ /* freeEntryProc */
};
const Tcl_HashKeyType tclStringHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION_2, /* version */
TCL_HASH_KEY_TYPE_VERSION, /* version */
0, /* flags */
HashStringKey, /* hashKeyProc */
CompareStringKeys, /* compareKeysProc */
AllocStringEntry, /* allocEntryProc */
NULL /* freeEntryProc */
};
|
| ︙ | | |
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
|
-
+
|
tablePtr->buckets = tablePtr->staticBuckets;
tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] = 0;
tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] = 0;
tablePtr->numBuckets = TCL_SMALL_HASH_TABLE;
tablePtr->numEntries = 0;
tablePtr->rebuildSize = TCL_SMALL_HASH_TABLE*REBUILD_MULTIPLIER;
tablePtr->downShift = 28;
tablePtr->mask = 3;
tablePtr->mask1 = 3;
tablePtr->keyType = keyType;
tablePtr->findProc = FindHashEntry;
tablePtr->createProc = CreateHashEntry;
if (typePtr == NULL) {
/*
* The caller has been rebuilt so the hash table is an extended
|
| ︙ | | |
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
|
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
|
-
-
+
-
-
-
-
-
+
-
-
+
|
const void *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;
const Tcl_HashKeyType *typePtr;
size_t hash;
size_t index;
if (typePtr->version == TCL_HASH_KEY_TYPE_VERSION) {
hash = ((unsigned int (*)(Tcl_HashTable *, void *))
typePtr->hashKeyProc)(tablePtr, (void *) key);
} else {
hash = typePtr->hashKeyProc(tablePtr, (void *) key);
}
index = hash & tablePtr->mask;
index = hash & tablePtr->mask1;
}
} else {
hash = (size_t)(key);
index = RANDOM_INDEX(tablePtr, hash);
}
/*
|
| ︙ | | |
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
|
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
|
-
+
|
typePtr = &tclArrayHashKeyType;
}
if (typePtr->hashKeyProc == NULL
|| typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
index = RANDOM_INDEX(tablePtr, entryPtr->hash);
} else {
index = entryPtr->hash & tablePtr->mask;
index = entryPtr->hash & tablePtr->mask1;
}
bucketPtr = &tablePtr->buckets[index];
if (*bucketPtr == entryPtr) {
*bucketPtr = entryPtr->nextPtr;
} else {
|
| ︙ | | |
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
|
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
|
-
+
-
+
|
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static size_t
static TCL_HASH_TYPE
HashArrayKey(
Tcl_HashTable *tablePtr, /* Hash table. */
void *keyPtr) /* Key from which to compute hash value. */
{
register const int *array = (const int *) keyPtr;
register size_t result;
register TCL_HASH_TYPE result;
int count;
for (result = 0, count = tablePtr->keyType; count > 0;
count--, array++) {
result += *array;
}
return result;
|
| ︙ | | |
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
|
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
|
-
+
-
+
|
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static size_t
static TCL_HASH_TYPE
HashStringKey(
Tcl_HashTable *tablePtr, /* Hash table. */
void *keyPtr) /* Key from which to compute hash value. */
{
register const char *string = keyPtr;
register size_t result;
register TCL_HASH_TYPE result;
register char 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
|
| ︙ | | |
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
|
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
|
-
+
+
|
*----------------------------------------------------------------------
*/
static void
RebuildTable(
register Tcl_HashTable *tablePtr) /* Table to enlarge. */
{
size_t oldSize, count, index;
size_t oldSize, count;
TCL_HASH_TYPE index;
Tcl_HashEntry **oldBuckets;
register Tcl_HashEntry **oldChainPtr, **newChainPtr;
register Tcl_HashEntry *hPtr;
const Tcl_HashKeyType *typePtr;
if (tablePtr->keyType == TCL_STRING_KEYS) {
typePtr = &tclStringHashKeyType;
|
| ︙ | | |
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
|
990
991
992
993
994
995
996
997
998
999
1000
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
|
-
+
-
+
|
}
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;
tablePtr->mask1 = (tablePtr->mask1 << 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 (typePtr->hashKeyProc == NULL
|| typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
index = RANDOM_INDEX(tablePtr, hPtr->hash);
} else {
index = hPtr->hash & tablePtr->mask;
index = hPtr->hash & tablePtr->mask1;
}
hPtr->nextPtr = tablePtr->buckets[index];
tablePtr->buckets[index] = hPtr;
}
}
/*
|
| ︙ | | |