-
Notifications
You must be signed in to change notification settings - Fork 1
/
Copy pathtclhash.h
147 lines (130 loc) · 4.85 KB
/
tclhash.h
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
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
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
/*
* tclHash.h --
*
* This header file declares the facilities provided by the
* Tcl hash table procedures.
*
* Copyright 1991 Regents of the University of California
* Permission to use, copy, modify, and distribute this
* software and its documentation for any purpose and without
* fee is hereby granted, provided that the above copyright
* notice appear in all copies. The University of California
* makes no representations about the suitability of this
* software for any purpose. It is provided "as is" without
* express or implied warranty.
*
* $Header: /sprite/src/lib/tcl/RCS/tclHash.h,v 1.3 91/08/27 11:36:04 ouster Exp $ SPRITE (Berkeley)
*/
#ifndef _TCLHASH
#define _TCLHASH
#ifndef _TCL
#include <tcl.h>
#endif
/*
* Structure definition for an entry in a hash table. No-one outside
* Tcl should access any of these fields directly; use the macros
* defined below.
*/
typedef struct Tcl_HashEntry {
struct Tcl_HashEntry *nextPtr; /* Pointer to next entry in this
* hash bucket, or NULL for end of
* chain. */
struct Tcl_HashTable *tablePtr; /* Pointer to table containing entry. */
struct Tcl_HashEntry **bucketPtr; /* Pointer to bucket that points to
* first entry in this entry's chain:
* used for deleting the entry. */
ClientData clientData; /* Application stores something here
* with Tcl_SetHashValue. */
union { /* Key has one of these forms: */
char *oneWordValue; /* One-word value for key. */
int words[1]; /* Multiple integer words for key.
* The actual size will be as large
* as necessary for this table's
* keys. */
char string[4]; /* String for key. The actual size
* will be as large as needed to hold
* the key. */
} key; /* MUST BE LAST FIELD IN RECORD!! */
} Tcl_HashEntry;
/*
* Structure definition for a hash table. Must be in tcl.h so clients
* can allocate space for these structures, but clients should never
* access any fields in this structure.
*/
#define TCL_SMALL_HASH_TABLE 4
typedef struct Tcl_HashTable {
Tcl_HashEntry **buckets; /* Pointer to bucket array. Each
* element points to first entry in
* bucket's hash chain, or NULL. */
Tcl_HashEntry *staticBuckets[TCL_SMALL_HASH_TABLE];
/* Bucket array used for small tables
* (to avoid mallocs and frees). */
int numBuckets; /* Total number of buckets allocated
* at **bucketPtr. */
int numEntries; /* Total number of entries present
* in table. */
int rebuildSize; /* Enlarge table when numEntries gets
* to be this large. */
int downShift; /* Shift count used in hashing
* function. Designed to use high-
* order bits of randomized keys. */
int mask; /* Mask value used in hashing
* function. */
int keyType; /* Type of keys used in this table.
* It's either TCL_STRING_KEYS,
* TCL_ONE_WORD_KEYS, or an integer
* giving the number of ints in a
*/
Tcl_HashEntry *(*findProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
char *key));
Tcl_HashEntry *(*createProc) _ANSI_ARGS_((struct Tcl_HashTable *tablePtr,
char *key, int *newPtr));
} Tcl_HashTable;
/*
* Structure definition for information used to keep track of searches
* through hash tables:
*/
typedef struct Tcl_HashSearch {
Tcl_HashTable *tablePtr; /* Table being searched. */
int nextIndex; /* Index of next bucket to be
* enumerated after present one. */
Tcl_HashEntry *nextEntryPtr; /* Next entry to be enumerated in the
* the current bucket. */
} Tcl_HashSearch;
/*
* Acceptable key types for hash tables:
*/
#define TCL_STRING_KEYS 0
#define TCL_ONE_WORD_KEYS 1
/*
* Macros for clients to use to access fields of hash entries:
*/
#define Tcl_GetHashValue(h) ((h)->clientData)
#define Tcl_SetHashValue(h, value) ((h)->clientData = (ClientData) (value))
#define Tcl_GetHashKey(tablePtr, h) \
((char *) (((tablePtr)->keyType == TCL_ONE_WORD_KEYS) ? (h)->key.oneWordValue \
: (h)->key.string))
/*
* Macros to use for clients to use to invoke find and create procedures
* for hash tables:
*/
#define Tcl_FindHashEntry(tablePtr, key) \
(*((tablePtr)->findProc))(tablePtr, key)
#define Tcl_CreateHashEntry(tablePtr, key, newPtr) \
(*((tablePtr)->createProc))(tablePtr, key, newPtr)
/*
* Exported procedures:
*/
extern void Tcl_DeleteHashEntry _ANSI_ARGS_((
Tcl_HashEntry *entryPtr));
extern void Tcl_DeleteHashTable _ANSI_ARGS_((
Tcl_HashTable *tablePtr));
extern Tcl_HashEntry * Tcl_FirstHashEntry _ANSI_ARGS_((
Tcl_HashTable *tablePtr,
Tcl_HashSearch *searchPtr));
extern char * Tcl_HashStats _ANSI_ARGS_((Tcl_HashTable *tablePtr));
extern void Tcl_InitHashTable _ANSI_ARGS_((Tcl_HashTable *tablePtr,
int keyType));
extern Tcl_HashEntry * Tcl_NextHashEntry _ANSI_ARGS_((
Tcl_HashSearch *searchPtr));
#endif /* _TCLHASH */