| ︙ | | |
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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
|
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
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 array hash key methods.
*/
static Tcl_HashEntry * AllocArrayEntry(Tcl_HashTable *tablePtr, void *keyPtr);
static int CompareArrayKeys(void *keyPtr, Tcl_HashEntry *hPtr);
static unsigned int HashArrayKey(Tcl_HashTable *tablePtr, void *keyPtr);
static size_t 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.
*/
#if 0
static Tcl_HashEntry * AllocOneWordEntry(Tcl_HashTable *tablePtr,
void *keyPtr);
static int CompareOneWordKeys(void *keyPtr, Tcl_HashEntry *hPtr);
static unsigned int HashOneWordKey(Tcl_HashTable *tablePtr, void *keyPtr);
static size_t HashOneWordKey(Tcl_HashTable *tablePtr, const void *keyPtr);
#endif
/*
* 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 unsigned int HashStringKey(Tcl_HashTable *tablePtr, void *keyPtr);
static size_t HashStringKey(Tcl_HashTable *tablePtr, void *keyPtr);
/*
* Function prototypes for static functions in this file:
*/
static Tcl_HashEntry * BogusFind(Tcl_HashTable *tablePtr, const char *key);
static Tcl_HashEntry * BogusCreate(Tcl_HashTable *tablePtr, const char *key,
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 char *key,
static Tcl_HashEntry * CreateHashEntry(Tcl_HashTable *tablePtr, const void *key,
int *newPtr);
static Tcl_HashEntry * FindHashEntry(Tcl_HashTable *tablePtr, const char *key);
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, /* version */
TCL_HASH_KEY_TYPE_VERSION_2, /* version */
TCL_HASH_KEY_RANDOMIZE_HASH, /* flags */
HashArrayKey, /* hashKeyProc */
CompareArrayKeys, /* compareKeysProc */
AllocArrayEntry, /* allocEntryProc */
NULL /* freeEntryProc */
};
const Tcl_HashKeyType tclOneWordHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION, /* version */
TCL_HASH_KEY_TYPE_VERSION_2, /* version */
0, /* flags */
NULL, /* HashOneWordKey, */ /* hashProc */
NULL, /* CompareOneWordKey, */ /* compareProc */
NULL, /* AllocOneWordKey, */ /* allocEntryProc */
NULL /* FreeOneWordKey, */ /* freeEntryProc */
};
const Tcl_HashKeyType tclStringHashKeyType = {
TCL_HASH_KEY_TYPE_VERSION, /* version */
TCL_HASH_KEY_TYPE_VERSION_2, /* version */
0, /* flags */
HashStringKey, /* hashKeyProc */
CompareStringKeys, /* compareKeysProc */
AllocStringEntry, /* allocEntryProc */
NULL /* freeEntryProc */
};
|
| ︙ | | |
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
|
-
+
|
*/
}
}
static Tcl_HashEntry *
FindHashEntry(
Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */
const char *key) /* Key to use to find matching entry. */
const void *key) /* Key to use to find matching entry. */
{
return CreateHashEntry(tablePtr, key, NULL);
}
/*
*----------------------------------------------------------------------
|
| ︙ | | |
232
233
234
235
236
237
238
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
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
|
232
233
234
235
236
237
238
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
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
|
-
+
-
-
+
+
+
+
+
+
-
+
+
-
+
-
+
-
+
|
*
*----------------------------------------------------------------------
*/
static Tcl_HashEntry *
CreateHashEntry(
Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */
const char *key, /* Key to use to find or create matching
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;
unsigned int hash;
int index;
size_t hash;
size_t index;
if (tablePtr->keyType == TCL_STRING_KEYS) {
typePtr = &tclStringHashKeyType;
} else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {
typePtr = &tclOneWordHashKeyType;
} else if (tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
|| tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
typePtr = tablePtr->typePtr;
} else {
typePtr = &tclArrayHashKeyType;
}
if (typePtr->hashKeyProc) {
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);
hash = typePtr->hashKeyProc(tablePtr, (void *) key);
}
if (typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
index = RANDOM_INDEX(tablePtr, hash);
} else {
index = hash & tablePtr->mask;
}
} else {
hash = PTR2UINT(key);
hash = (size_t)(key);
index = RANDOM_INDEX(tablePtr, hash);
}
/*
* Search all of the entries in the appropriate bucket.
*/
if (typePtr->compareKeysProc) {
Tcl_CompareHashKeysProc *compareKeysProc = typePtr->compareKeysProc;
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {
if (hash != PTR2UINT(hPtr->hash)) {
if (hash != hPtr->hash) {
continue;
}
if (((void *) key == hPtr) || compareKeysProc((void *) key, hPtr)) {
if (newPtr) {
*newPtr = 0;
}
return hPtr;
}
}
} else {
for (hPtr = tablePtr->buckets[index]; hPtr != NULL;
hPtr = hPtr->nextPtr) {
if (hash != PTR2UINT(hPtr->hash)) {
if (hash != hPtr->hash) {
continue;
}
if (key == hPtr->key.oneWordValue) {
if (newPtr) {
*newPtr = 0;
}
return hPtr;
|
| ︙ | | |
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
|
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
|
-
+
-
+
|
*/
*newPtr = 1;
if (typePtr->allocEntryProc) {
hPtr = typePtr->allocEntryProc(tablePtr, (void *) key);
} else {
hPtr = ckalloc(sizeof(Tcl_HashEntry));
hPtr->key.oneWordValue = (char *) key;
hPtr->key.oneWordValue = key;
hPtr->clientData = 0;
}
hPtr->tablePtr = tablePtr;
hPtr->hash = UINT2PTR(hash);
hPtr->hash = hash;
hPtr->nextPtr = tablePtr->buckets[index];
tablePtr->buckets[index] = hPtr;
tablePtr->numEntries++;
/*
* If the table has exceeded a decent size, rebuild it with many more
* buckets.
|
| ︙ | | |
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
|
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
|
-
+
-
+
-
+
|
Tcl_DeleteHashEntry(
Tcl_HashEntry *entryPtr)
{
register Tcl_HashEntry *prevPtr;
const Tcl_HashKeyType *typePtr;
Tcl_HashTable *tablePtr;
Tcl_HashEntry **bucketPtr;
int index;
size_t index;
tablePtr = entryPtr->tablePtr;
if (tablePtr->keyType == TCL_STRING_KEYS) {
typePtr = &tclStringHashKeyType;
} else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {
typePtr = &tclOneWordHashKeyType;
} else if (tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
|| tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
typePtr = tablePtr->typePtr;
} else {
typePtr = &tclArrayHashKeyType;
}
if (typePtr->hashKeyProc == NULL
|| typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
index = RANDOM_INDEX(tablePtr, PTR2INT(entryPtr->hash));
index = RANDOM_INDEX(tablePtr, entryPtr->hash);
} else {
index = PTR2UINT(entryPtr->hash) & tablePtr->mask;
index = entryPtr->hash & tablePtr->mask;
}
bucketPtr = &tablePtr->buckets[index];
if (*bucketPtr == entryPtr) {
*bucketPtr = entryPtr->nextPtr;
} else {
|
| ︙ | | |
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
|
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
|
-
+
|
void
Tcl_DeleteHashTable(
register Tcl_HashTable *tablePtr) /* Table to delete. */
{
register Tcl_HashEntry *hPtr, *nextPtr;
const Tcl_HashKeyType *typePtr;
int i;
size_t i;
if (tablePtr->keyType == TCL_STRING_KEYS) {
typePtr = &tclStringHashKeyType;
} else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) {
typePtr = &tclOneWordHashKeyType;
} else if (tablePtr->keyType == TCL_CUSTOM_TYPE_KEYS
|| tablePtr->keyType == TCL_CUSTOM_PTR_KEYS) {
|
| ︙ | | |
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
|
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
|
-
+
|
*/
char *
Tcl_HashStats(
Tcl_HashTable *tablePtr) /* Table for which to produce stats. */
{
#define NUM_COUNTERS 10
int count[NUM_COUNTERS], overflow, i, j;
size_t count[NUM_COUNTERS], overflow, i, j;
double average, tmp;
register Tcl_HashEntry *hPtr;
char *result, *p;
/*
* Compute a histogram of bucket usage.
*/
|
| ︙ | | |
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
|
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
|
-
-
+
+
-
-
+
+
-
-
+
+
|
}
/*
* Print out the histogram and a few other pieces of information.
*/
result = ckalloc((NUM_COUNTERS * 60) + 300);
sprintf(result, "%d entries in table, %d buckets\n",
tablePtr->numEntries, tablePtr->numBuckets);
sprintf(result, "%" TCL_LL_MODIFIER "d entries in table, %" TCL_LL_MODIFIER "d buckets\n",
(Tcl_WideInt)tablePtr->numEntries, (Tcl_WideInt)tablePtr->numBuckets);
p = result + strlen(result);
for (i = 0; i < NUM_COUNTERS; i++) {
sprintf(p, "number of buckets with %d entries: %d\n",
i, count[i]);
sprintf(p, "number of buckets with %d entries: %" TCL_LL_MODIFIER "d\n",
(int)i, (Tcl_WideInt)count[i]);
p += strlen(p);
}
sprintf(p, "number of buckets with %d or more entries: %d\n",
NUM_COUNTERS, overflow);
sprintf(p, "number of buckets with %d or more entries: %" TCL_LL_MODIFIER "d\n",
NUM_COUNTERS, (Tcl_WideInt)overflow);
p += strlen(p);
sprintf(p, "average search distance for entry: %.1f", average);
return result;
}
/*
*----------------------------------------------------------------------
|
| ︙ | | |
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
|
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
|
-
+
|
Tcl_HashTable *tablePtr, /* Hash table. */
void *keyPtr) /* Key to store in the hash table entry. */
{
int *array = (int *) keyPtr;
register int *iPtr1, *iPtr2;
Tcl_HashEntry *hPtr;
int count;
unsigned int size;
size_t size;
count = tablePtr->keyType;
size = sizeof(Tcl_HashEntry) + (count*sizeof(int)) - sizeof(hPtr->key);
if (size < sizeof(Tcl_HashEntry)) {
size = sizeof(Tcl_HashEntry);
}
|
| ︙ | | |
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
|
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
|
-
+
-
+
|
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static unsigned int
static size_t
HashArrayKey(
Tcl_HashTable *tablePtr, /* Hash table. */
void *keyPtr) /* Key from which to compute hash value. */
{
register const int *array = (const int *) keyPtr;
register unsigned int result;
register size_t result;
int count;
for (result = 0, count = tablePtr->keyType; count > 0;
count--, array++) {
result += *array;
}
return result;
|
| ︙ | | |
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
|
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
|
-
+
-
+
|
*/
static Tcl_HashEntry *
AllocStringEntry(
Tcl_HashTable *tablePtr, /* Hash table. */
void *keyPtr) /* Key to store in the hash table entry. */
{
const char *string = (const char *) keyPtr;
const char *string = keyPtr;
Tcl_HashEntry *hPtr;
unsigned int size, allocsize;
size_t size, allocsize;
allocsize = size = strlen(string) + 1;
if (size < sizeof(hPtr->key)) {
allocsize = sizeof(hPtr->key);
}
hPtr = ckalloc(TclOffset(Tcl_HashEntry, key) + allocsize);
memcpy(hPtr->key.string, string, size);
|
| ︙ | | |
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
|
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
|
-
-
+
+
|
*/
static int
CompareStringKeys(
void *keyPtr, /* New key to compare. */
Tcl_HashEntry *hPtr) /* Existing key to compare. */
{
register const char *p1 = (const char *) keyPtr;
register const char *p2 = (const char *) hPtr->key.string;
register const char *p1 = keyPtr;
register const char *p2 = hPtr->key.string;
return !strcmp(p1, p2);
}
/*
*----------------------------------------------------------------------
*
|
| ︙ | | |
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
|
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
|
-
+
-
+
|
*
* Side effects:
* None.
*
*----------------------------------------------------------------------
*/
static unsigned
static size_t
HashStringKey(
Tcl_HashTable *tablePtr, /* Hash table. */
void *keyPtr) /* Key from which to compute hash value. */
{
register const char *string = keyPtr;
register unsigned int result;
register size_t 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
|
| ︙ | | |
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
|
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
|
-
+
|
*----------------------------------------------------------------------
*/
/* ARGSUSED */
static Tcl_HashEntry *
BogusFind(
Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */
const char *key) /* Key to use to find matching entry. */
const void *key) /* Key to use to find matching entry. */
{
Tcl_Panic("called %s on deleted table", "Tcl_FindHashEntry");
return NULL;
}
/*
*----------------------------------------------------------------------
|
| ︙ | | |
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
|
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
|
-
+
|
*----------------------------------------------------------------------
*/
/* ARGSUSED */
static Tcl_HashEntry *
BogusCreate(
Tcl_HashTable *tablePtr, /* Table in which to lookup entry. */
const char *key, /* Key to use to find or create matching
const void *key, /* Key to use to find or create matching
* entry. */
int *newPtr) /* Store info here telling whether a new entry
* was created. */
{
Tcl_Panic("called %s on deleted table", "Tcl_CreateHashEntry");
return NULL;
}
|
| ︙ | | |
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
|
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
|
-
+
|
*----------------------------------------------------------------------
*/
static void
RebuildTable(
register Tcl_HashTable *tablePtr) /* Table to enlarge. */
{
int oldSize, count, index;
size_t oldSize, count, 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;
|
| ︙ | | |
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
|
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
|
-
-
+
+
|
/*
* Allocate and initialize the new bucket array, and set up hashing
* constants for new array size.
*/
tablePtr->numBuckets *= 4;
if (typePtr->flags & TCL_HASH_KEY_SYSTEM_HASH) {
tablePtr->buckets = (Tcl_HashEntry **) TclpSysAlloc((unsigned)
(tablePtr->numBuckets * sizeof(Tcl_HashEntry *)), 0);
tablePtr->buckets = (Tcl_HashEntry **) TclpSysAlloc(
tablePtr->numBuckets * sizeof(Tcl_HashEntry *), 0);
} else {
tablePtr->buckets =
ckalloc(tablePtr->numBuckets * sizeof(Tcl_HashEntry *));
}
for (count = tablePtr->numBuckets, newChainPtr = tablePtr->buckets;
count > 0; count--, newChainPtr++) {
*newChainPtr = NULL;
|
| ︙ | | |
1001
1002
1003
1004
1005
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
|
1006
1007
1008
1009
1010
1011
1012
1013
1014
1015
1016
1017
1018
1019
1020
1021
1022
|
-
+
-
+
|
*/
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, PTR2INT(hPtr->hash));
index = RANDOM_INDEX(tablePtr, hPtr->hash);
} else {
index = PTR2UINT(hPtr->hash) & tablePtr->mask;
index = hPtr->hash & tablePtr->mask;
}
hPtr->nextPtr = tablePtr->buckets[index];
tablePtr->buckets[index] = hPtr;
}
}
/*
|
| ︙ | | |