Diff
Not logged in
Home Timeline Branches Tags Tickets Wiki Login
Annotate Patch Unified Diff

Differences From Artifact [7498d6e8e3]:

To Artifact [382729b76b]:

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.20 2004/06/08 18:52:02 dkf 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.21 2004/10/06 13:43:53 dkf Exp $
 */

#include "tclInt.h"

/*
 * Prevent macros from clashing with function definitions.
 */
︙︙
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

    (((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask)

/*
 * Prototypes for the array hash key methods.
 */

static Tcl_HashEntry *	AllocArrayEntry _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr,
			    VOID *keyPtr));
static int		CompareArrayKeys _ANSI_ARGS_((
			    VOID *keyPtr, Tcl_HashEntry *hPtr));
static unsigned int	HashArrayKey _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr,
			    VOID *keyPtr));

/*
 * Prototypes for the one word hash key methods.
 */

#if 0
static Tcl_HashEntry *	AllocOneWordEntry _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr,
			    VOID *keyPtr));
static int		CompareOneWordKeys _ANSI_ARGS_((
			    VOID *keyPtr, Tcl_HashEntry *hPtr));
static unsigned int	HashOneWordKey _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr,
			    VOID *keyPtr));
#endif

/*
 * Prototypes for the string hash key methods.
 */

static Tcl_HashEntry *	AllocStringEntry _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr,
			    VOID *keyPtr));
static int		CompareStringKeys _ANSI_ARGS_((
			    VOID *keyPtr, Tcl_HashEntry *hPtr));
static unsigned int	HashStringKey _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr,
			    VOID *keyPtr));

/*
 * Procedure prototypes for static procedures in this file:
 */

#if TCL_PRESERVE_BINARY_COMPATABILITY
static Tcl_HashEntry *	BogusFind _ANSI_ARGS_((Tcl_HashTable *tablePtr,








|
<



|
<







|
<



|
<







|
<



|
<








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

    (((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask)

/*
 * Prototypes for the array hash key methods.
 */

static Tcl_HashEntry *	AllocArrayEntry _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr, VOID *keyPtr));

static int		CompareArrayKeys _ANSI_ARGS_((
			    VOID *keyPtr, Tcl_HashEntry *hPtr));
static unsigned int	HashArrayKey _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr, VOID *keyPtr));


/*
 * Prototypes for the one word hash key methods.
 */

#if 0
static Tcl_HashEntry *	AllocOneWordEntry _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr, VOID *keyPtr));

static int		CompareOneWordKeys _ANSI_ARGS_((
			    VOID *keyPtr, Tcl_HashEntry *hPtr));
static unsigned int	HashOneWordKey _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr, VOID *keyPtr));

#endif

/*
 * Prototypes for the string hash key methods.
 */

static Tcl_HashEntry *	AllocStringEntry _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr, VOID *keyPtr));

static int		CompareStringKeys _ANSI_ARGS_((
			    VOID *keyPtr, Tcl_HashEntry *hPtr));
static unsigned int	HashStringKey _ANSI_ARGS_((
			    Tcl_HashTable *tablePtr, VOID *keyPtr));


/*
 * Procedure prototypes for static procedures in this file:
 */

#if TCL_PRESERVE_BINARY_COMPATABILITY
static Tcl_HashEntry *	BogusFind _ANSI_ARGS_((Tcl_HashTable *tablePtr,
︙︙
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
    if (typePtr == NULL) {








|








276
277
278
279
280
281
282
283
284
285
286
287
288
289
290


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
    if (typePtr == NULL) {
︙︙
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
    if (typePtr == NULL) {








|








374
375
376
377
378
379
380
381
382
383
384
385
386
387
388


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
    if (typePtr == NULL) {
︙︙
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
#endif
    
#if TCL_HASH_KEY_STORE_HASH
    if (typePtr->hashKeyProc == NULL
	|| typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
	index = RANDOM_INDEX (tablePtr, entryPtr->hash);
    } else {
	index = ((unsigned int) entryPtr->hash) & tablePtr->mask;
    }

    bucketPtr = &(tablePtr->buckets[index]);
#else








|










|








510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
#endif
    
#if TCL_HASH_KEY_STORE_HASH
    if (typePtr->hashKeyProc == NULL
	    || typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
	index = RANDOM_INDEX (tablePtr, entryPtr->hash);
    } else {
	index = ((unsigned int) entryPtr->hash) & tablePtr->mask;
    }

    bucketPtr = &(tablePtr->buckets[index]);
#else
︙︙
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
#endif








|








585
586
587
588
589
590
591
592
593
594
595
596
597
598
599


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
#endif
︙︙
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
    if (typePtr == NULL) {








|








747
748
749
750
751
752
753
754
755
756
757
758
759
760
761


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
    if (typePtr == NULL) {
︙︙
842
843
844
845
846
847
848
849
850
851
852

853
854
855
856
857
858
859

    int *array = (int *) keyPtr;
    register int *iPtr1, *iPtr2;
    Tcl_HashEntry *hPtr;
    int count;
    unsigned int size;

    count = tablePtr->keyType;
    
    size = sizeof(Tcl_HashEntry) + (count*sizeof(int)) - sizeof(hPtr->key);
    if (size < sizeof(Tcl_HashEntry))
	size = sizeof(Tcl_HashEntry);

    hPtr = (Tcl_HashEntry *) ckalloc(size);
    
    for (iPtr1 = array, iPtr2 = hPtr->key.words;
	    count > 0; count--, iPtr1++, iPtr2++) {
	*iPtr2 = *iPtr1;
    }









|

|

>








836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854

    int *array = (int *) keyPtr;
    register int *iPtr1, *iPtr2;
    Tcl_HashEntry *hPtr;
    int count;
    unsigned int size;

    count = tablePtr->keyType;

    size = sizeof(Tcl_HashEntry) + (count*sizeof(int)) - sizeof(hPtr->key);
    if (size < sizeof(Tcl_HashEntry)) {
	size = sizeof(Tcl_HashEntry);
    }
    hPtr = (Tcl_HashEntry *) ckalloc(size);
    
    for (iPtr1 = array, iPtr2 = hPtr->key.words;
	    count > 0; count--, iPtr1++, iPtr2++) {
	*iPtr2 = *iPtr1;
    }
︙︙
954
955
956
957
958
959
960
961
962

963
964
965
966
967
968
969

    VOID *keyPtr;		/* Key to store in the hash table entry. */
{
    CONST char *string = (CONST char *) keyPtr;
    Tcl_HashEntry *hPtr;
    unsigned int size;

    size = sizeof(Tcl_HashEntry) + strlen(string) + 1 - sizeof(hPtr->key);
    if (size < sizeof(Tcl_HashEntry))
	size = sizeof(Tcl_HashEntry);

    hPtr = (Tcl_HashEntry *) ckalloc(size);
    strcpy(hPtr->key.string, string);

    return hPtr;
}

/*








|

>








949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965

    VOID *keyPtr;		/* Key to store in the hash table entry. */
{
    CONST char *string = (CONST char *) keyPtr;
    Tcl_HashEntry *hPtr;
    unsigned int size;

    size = sizeof(Tcl_HashEntry) + strlen(string) + 1 - sizeof(hPtr->key);
    if (size < sizeof(Tcl_HashEntry)) {
	size = sizeof(Tcl_HashEntry);
    }
    hPtr = (Tcl_HashEntry *) ckalloc(size);
    strcpy(hPtr->key.string, string);

    return hPtr;
}

/*
︙︙
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160
1161
1162
1163
1164


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
#endif








|








1146
1147
1148
1149
1150
1151
1152
1153
1154
1155
1156
1157
1158
1159
1160


#if TCL_PRESERVE_BINARY_COMPATABILITY
    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;
    }
#else
    typePtr = tablePtr->typePtr;
#endif
︙︙
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202
1203
1204
1205
1206

     */

    for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) {
	for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) {
	    *oldChainPtr = hPtr->nextPtr;
#if TCL_HASH_KEY_STORE_HASH
	    if (typePtr->hashKeyProc == NULL
		|| typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
		index = RANDOM_INDEX (tablePtr, hPtr->hash);
	    } else {
		index = ((unsigned int) hPtr->hash) & tablePtr->mask;
	    }
	    hPtr->nextPtr = tablePtr->buckets[index];
	    tablePtr->buckets[index] = hPtr;
#else








|








1188
1189
1190
1191
1192
1193
1194
1195
1196
1197
1198
1199
1200
1201
1202

     */

    for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) {
	for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) {
	    *oldChainPtr = hPtr->nextPtr;
#if TCL_HASH_KEY_STORE_HASH
	    if (typePtr->hashKeyProc == NULL
		    || typePtr->flags & TCL_HASH_KEY_RANDOMIZE_HASH) {
		index = RANDOM_INDEX (tablePtr, hPtr->hash);
	    } else {
		index = ((unsigned int) hPtr->hash) & tablePtr->mask;
	    }
	    hPtr->nextPtr = tablePtr->buckets[index];
	    tablePtr->buckets[index] = hPtr;
#else
︙︙
This page was created in about 0.025s by Fossil version [1205ec86cb] 2025-04-30 16:57:32