1 |
/* $Header$ */ |
/* $Header$ */ |
2 |
/* |
/* |
3 |
* tclHash.c -- |
* tclHash.c -- |
4 |
* |
* |
5 |
* Implementation of in-memory hash tables for Tcl and Tcl-based |
* Implementation of in-memory hash tables for Tcl and Tcl-based |
6 |
* applications. |
* applications. |
7 |
* |
* |
8 |
* Copyright (c) 1991-1993 The Regents of the University of California. |
* Copyright (c) 1991-1993 The Regents of the University of California. |
9 |
* Copyright (c) 1994 Sun Microsystems, Inc. |
* Copyright (c) 1994 Sun Microsystems, Inc. |
10 |
* |
* |
11 |
* See the file "license.terms" for information on usage and redistribution |
* See the file "license.terms" for information on usage and redistribution |
12 |
* of this file, and for a DISCLAIMER OF ALL WARRANTIES. |
* of this file, and for a DISCLAIMER OF ALL WARRANTIES. |
13 |
* |
* |
14 |
* RCS: @(#) $Id: tclhash.c,v 1.1.1.1 2001/06/13 04:39:25 dtashley Exp $ |
* RCS: @(#) $Id: tclhash.c,v 1.1.1.1 2001/06/13 04:39:25 dtashley Exp $ |
15 |
*/ |
*/ |
16 |
|
|
17 |
#include "tclInt.h" |
#include "tclInt.h" |
18 |
|
|
19 |
/* |
/* |
20 |
* When there are this many entries per bucket, on average, rebuild |
* When there are this many entries per bucket, on average, rebuild |
21 |
* the hash table to make it larger. |
* the hash table to make it larger. |
22 |
*/ |
*/ |
23 |
|
|
24 |
#define REBUILD_MULTIPLIER 3 |
#define REBUILD_MULTIPLIER 3 |
25 |
|
|
26 |
|
|
27 |
/* |
/* |
28 |
* The following macro takes a preliminary integer hash value and |
* The following macro takes a preliminary integer hash value and |
29 |
* produces an index into a hash tables bucket list. The idea is |
* produces an index into a hash tables bucket list. The idea is |
30 |
* to make it so that preliminary values that are arbitrarily similar |
* to make it so that preliminary values that are arbitrarily similar |
31 |
* will end up in different buckets. The hash function was taken |
* will end up in different buckets. The hash function was taken |
32 |
* from a random-number generator. |
* from a random-number generator. |
33 |
*/ |
*/ |
34 |
|
|
35 |
#define RANDOM_INDEX(tablePtr, i) \ |
#define RANDOM_INDEX(tablePtr, i) \ |
36 |
(((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask) |
(((((long) (i))*1103515245) >> (tablePtr)->downShift) & (tablePtr)->mask) |
37 |
|
|
38 |
/* |
/* |
39 |
* Procedure prototypes for static procedures in this file: |
* Procedure prototypes for static procedures in this file: |
40 |
*/ |
*/ |
41 |
|
|
42 |
static Tcl_HashEntry * ArrayFind _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
static Tcl_HashEntry * ArrayFind _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
43 |
CONST char *key)); |
CONST char *key)); |
44 |
static Tcl_HashEntry * ArrayCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
static Tcl_HashEntry * ArrayCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
45 |
CONST char *key, int *newPtr)); |
CONST char *key, int *newPtr)); |
46 |
static Tcl_HashEntry * BogusFind _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
static Tcl_HashEntry * BogusFind _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
47 |
CONST char *key)); |
CONST char *key)); |
48 |
static Tcl_HashEntry * BogusCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
static Tcl_HashEntry * BogusCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
49 |
CONST char *key, int *newPtr)); |
CONST char *key, int *newPtr)); |
50 |
static unsigned int HashString _ANSI_ARGS_((CONST char *string)); |
static unsigned int HashString _ANSI_ARGS_((CONST char *string)); |
51 |
static void RebuildTable _ANSI_ARGS_((Tcl_HashTable *tablePtr)); |
static void RebuildTable _ANSI_ARGS_((Tcl_HashTable *tablePtr)); |
52 |
static Tcl_HashEntry * StringFind _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
static Tcl_HashEntry * StringFind _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
53 |
CONST char *key)); |
CONST char *key)); |
54 |
static Tcl_HashEntry * StringCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
static Tcl_HashEntry * StringCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
55 |
CONST char *key, int *newPtr)); |
CONST char *key, int *newPtr)); |
56 |
static Tcl_HashEntry * OneWordFind _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
static Tcl_HashEntry * OneWordFind _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
57 |
CONST char *key)); |
CONST char *key)); |
58 |
static Tcl_HashEntry * OneWordCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
static Tcl_HashEntry * OneWordCreate _ANSI_ARGS_((Tcl_HashTable *tablePtr, |
59 |
CONST char *key, int *newPtr)); |
CONST char *key, int *newPtr)); |
60 |
|
|
61 |
/* |
/* |
62 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
63 |
* |
* |
64 |
* Tcl_InitHashTable -- |
* Tcl_InitHashTable -- |
65 |
* |
* |
66 |
* Given storage for a hash table, set up the fields to prepare |
* Given storage for a hash table, set up the fields to prepare |
67 |
* the hash table for use. |
* the hash table for use. |
68 |
* |
* |
69 |
* Results: |
* Results: |
70 |
* None. |
* None. |
71 |
* |
* |
72 |
* Side effects: |
* Side effects: |
73 |
* TablePtr is now ready to be passed to Tcl_FindHashEntry and |
* TablePtr is now ready to be passed to Tcl_FindHashEntry and |
74 |
* Tcl_CreateHashEntry. |
* Tcl_CreateHashEntry. |
75 |
* |
* |
76 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
77 |
*/ |
*/ |
78 |
|
|
79 |
void |
void |
80 |
Tcl_InitHashTable(tablePtr, keyType) |
Tcl_InitHashTable(tablePtr, keyType) |
81 |
register Tcl_HashTable *tablePtr; /* Pointer to table record, which |
register Tcl_HashTable *tablePtr; /* Pointer to table record, which |
82 |
* is supplied by the caller. */ |
* is supplied by the caller. */ |
83 |
int keyType; /* Type of keys to use in table: |
int keyType; /* Type of keys to use in table: |
84 |
* TCL_STRING_KEYS, TCL_ONE_WORD_KEYS, |
* TCL_STRING_KEYS, TCL_ONE_WORD_KEYS, |
85 |
* or an integer >= 2. */ |
* or an integer >= 2. */ |
86 |
{ |
{ |
87 |
#if (TCL_SMALL_HASH_TABLE != 4) |
#if (TCL_SMALL_HASH_TABLE != 4) |
88 |
panic("Tcl_InitHashTable: TCL_SMALL_HASH_TABLE is %d, not 4\n", |
panic("Tcl_InitHashTable: TCL_SMALL_HASH_TABLE is %d, not 4\n", |
89 |
TCL_SMALL_HASH_TABLE); |
TCL_SMALL_HASH_TABLE); |
90 |
#endif |
#endif |
91 |
|
|
92 |
tablePtr->buckets = tablePtr->staticBuckets; |
tablePtr->buckets = tablePtr->staticBuckets; |
93 |
tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] = 0; |
tablePtr->staticBuckets[0] = tablePtr->staticBuckets[1] = 0; |
94 |
tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] = 0; |
tablePtr->staticBuckets[2] = tablePtr->staticBuckets[3] = 0; |
95 |
tablePtr->numBuckets = TCL_SMALL_HASH_TABLE; |
tablePtr->numBuckets = TCL_SMALL_HASH_TABLE; |
96 |
tablePtr->numEntries = 0; |
tablePtr->numEntries = 0; |
97 |
tablePtr->rebuildSize = TCL_SMALL_HASH_TABLE*REBUILD_MULTIPLIER; |
tablePtr->rebuildSize = TCL_SMALL_HASH_TABLE*REBUILD_MULTIPLIER; |
98 |
tablePtr->downShift = 28; |
tablePtr->downShift = 28; |
99 |
tablePtr->mask = 3; |
tablePtr->mask = 3; |
100 |
tablePtr->keyType = keyType; |
tablePtr->keyType = keyType; |
101 |
if (keyType == TCL_STRING_KEYS) { |
if (keyType == TCL_STRING_KEYS) { |
102 |
tablePtr->findProc = StringFind; |
tablePtr->findProc = StringFind; |
103 |
tablePtr->createProc = StringCreate; |
tablePtr->createProc = StringCreate; |
104 |
} else if (keyType == TCL_ONE_WORD_KEYS) { |
} else if (keyType == TCL_ONE_WORD_KEYS) { |
105 |
tablePtr->findProc = OneWordFind; |
tablePtr->findProc = OneWordFind; |
106 |
tablePtr->createProc = OneWordCreate; |
tablePtr->createProc = OneWordCreate; |
107 |
} else { |
} else { |
108 |
tablePtr->findProc = ArrayFind; |
tablePtr->findProc = ArrayFind; |
109 |
tablePtr->createProc = ArrayCreate; |
tablePtr->createProc = ArrayCreate; |
110 |
}; |
}; |
111 |
} |
} |
112 |
|
|
113 |
/* |
/* |
114 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
115 |
* |
* |
116 |
* Tcl_DeleteHashEntry -- |
* Tcl_DeleteHashEntry -- |
117 |
* |
* |
118 |
* Remove a single entry from a hash table. |
* Remove a single entry from a hash table. |
119 |
* |
* |
120 |
* Results: |
* Results: |
121 |
* None. |
* None. |
122 |
* |
* |
123 |
* Side effects: |
* Side effects: |
124 |
* The entry given by entryPtr is deleted from its table and |
* The entry given by entryPtr is deleted from its table and |
125 |
* should never again be used by the caller. It is up to the |
* should never again be used by the caller. It is up to the |
126 |
* caller to free the clientData field of the entry, if that |
* caller to free the clientData field of the entry, if that |
127 |
* is relevant. |
* is relevant. |
128 |
* |
* |
129 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
130 |
*/ |
*/ |
131 |
|
|
132 |
void |
void |
133 |
Tcl_DeleteHashEntry(entryPtr) |
Tcl_DeleteHashEntry(entryPtr) |
134 |
Tcl_HashEntry *entryPtr; |
Tcl_HashEntry *entryPtr; |
135 |
{ |
{ |
136 |
register Tcl_HashEntry *prevPtr; |
register Tcl_HashEntry *prevPtr; |
137 |
|
|
138 |
if (*entryPtr->bucketPtr == entryPtr) { |
if (*entryPtr->bucketPtr == entryPtr) { |
139 |
*entryPtr->bucketPtr = entryPtr->nextPtr; |
*entryPtr->bucketPtr = entryPtr->nextPtr; |
140 |
} else { |
} else { |
141 |
for (prevPtr = *entryPtr->bucketPtr; ; prevPtr = prevPtr->nextPtr) { |
for (prevPtr = *entryPtr->bucketPtr; ; prevPtr = prevPtr->nextPtr) { |
142 |
if (prevPtr == NULL) { |
if (prevPtr == NULL) { |
143 |
panic("malformed bucket chain in Tcl_DeleteHashEntry"); |
panic("malformed bucket chain in Tcl_DeleteHashEntry"); |
144 |
} |
} |
145 |
if (prevPtr->nextPtr == entryPtr) { |
if (prevPtr->nextPtr == entryPtr) { |
146 |
prevPtr->nextPtr = entryPtr->nextPtr; |
prevPtr->nextPtr = entryPtr->nextPtr; |
147 |
break; |
break; |
148 |
} |
} |
149 |
} |
} |
150 |
} |
} |
151 |
entryPtr->tablePtr->numEntries--; |
entryPtr->tablePtr->numEntries--; |
152 |
ckfree((char *) entryPtr); |
ckfree((char *) entryPtr); |
153 |
} |
} |
154 |
|
|
155 |
/* |
/* |
156 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
157 |
* |
* |
158 |
* Tcl_DeleteHashTable -- |
* Tcl_DeleteHashTable -- |
159 |
* |
* |
160 |
* Free up everything associated with a hash table except for |
* Free up everything associated with a hash table except for |
161 |
* the record for the table itself. |
* the record for the table itself. |
162 |
* |
* |
163 |
* Results: |
* Results: |
164 |
* None. |
* None. |
165 |
* |
* |
166 |
* Side effects: |
* Side effects: |
167 |
* The hash table is no longer useable. |
* The hash table is no longer useable. |
168 |
* |
* |
169 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
170 |
*/ |
*/ |
171 |
|
|
172 |
void |
void |
173 |
Tcl_DeleteHashTable(tablePtr) |
Tcl_DeleteHashTable(tablePtr) |
174 |
register Tcl_HashTable *tablePtr; /* Table to delete. */ |
register Tcl_HashTable *tablePtr; /* Table to delete. */ |
175 |
{ |
{ |
176 |
register Tcl_HashEntry *hPtr, *nextPtr; |
register Tcl_HashEntry *hPtr, *nextPtr; |
177 |
int i; |
int i; |
178 |
|
|
179 |
/* |
/* |
180 |
* Free up all the entries in the table. |
* Free up all the entries in the table. |
181 |
*/ |
*/ |
182 |
|
|
183 |
for (i = 0; i < tablePtr->numBuckets; i++) { |
for (i = 0; i < tablePtr->numBuckets; i++) { |
184 |
hPtr = tablePtr->buckets[i]; |
hPtr = tablePtr->buckets[i]; |
185 |
while (hPtr != NULL) { |
while (hPtr != NULL) { |
186 |
nextPtr = hPtr->nextPtr; |
nextPtr = hPtr->nextPtr; |
187 |
ckfree((char *) hPtr); |
ckfree((char *) hPtr); |
188 |
hPtr = nextPtr; |
hPtr = nextPtr; |
189 |
} |
} |
190 |
} |
} |
191 |
|
|
192 |
/* |
/* |
193 |
* Free up the bucket array, if it was dynamically allocated. |
* Free up the bucket array, if it was dynamically allocated. |
194 |
*/ |
*/ |
195 |
|
|
196 |
if (tablePtr->buckets != tablePtr->staticBuckets) { |
if (tablePtr->buckets != tablePtr->staticBuckets) { |
197 |
ckfree((char *) tablePtr->buckets); |
ckfree((char *) tablePtr->buckets); |
198 |
} |
} |
199 |
|
|
200 |
/* |
/* |
201 |
* Arrange for panics if the table is used again without |
* Arrange for panics if the table is used again without |
202 |
* re-initialization. |
* re-initialization. |
203 |
*/ |
*/ |
204 |
|
|
205 |
tablePtr->findProc = BogusFind; |
tablePtr->findProc = BogusFind; |
206 |
tablePtr->createProc = BogusCreate; |
tablePtr->createProc = BogusCreate; |
207 |
} |
} |
208 |
|
|
209 |
/* |
/* |
210 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
211 |
* |
* |
212 |
* Tcl_FirstHashEntry -- |
* Tcl_FirstHashEntry -- |
213 |
* |
* |
214 |
* Locate the first entry in a hash table and set up a record |
* Locate the first entry in a hash table and set up a record |
215 |
* that can be used to step through all the remaining entries |
* that can be used to step through all the remaining entries |
216 |
* of the table. |
* of the table. |
217 |
* |
* |
218 |
* Results: |
* Results: |
219 |
* The return value is a pointer to the first entry in tablePtr, |
* The return value is a pointer to the first entry in tablePtr, |
220 |
* or NULL if tablePtr has no entries in it. The memory at |
* or NULL if tablePtr has no entries in it. The memory at |
221 |
* *searchPtr is initialized so that subsequent calls to |
* *searchPtr is initialized so that subsequent calls to |
222 |
* Tcl_NextHashEntry will return all of the entries in the table, |
* Tcl_NextHashEntry will return all of the entries in the table, |
223 |
* one at a time. |
* one at a time. |
224 |
* |
* |
225 |
* Side effects: |
* Side effects: |
226 |
* None. |
* None. |
227 |
* |
* |
228 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
229 |
*/ |
*/ |
230 |
|
|
231 |
Tcl_HashEntry * |
Tcl_HashEntry * |
232 |
Tcl_FirstHashEntry(tablePtr, searchPtr) |
Tcl_FirstHashEntry(tablePtr, searchPtr) |
233 |
Tcl_HashTable *tablePtr; /* Table to search. */ |
Tcl_HashTable *tablePtr; /* Table to search. */ |
234 |
Tcl_HashSearch *searchPtr; /* Place to store information about |
Tcl_HashSearch *searchPtr; /* Place to store information about |
235 |
* progress through the table. */ |
* progress through the table. */ |
236 |
{ |
{ |
237 |
searchPtr->tablePtr = tablePtr; |
searchPtr->tablePtr = tablePtr; |
238 |
searchPtr->nextIndex = 0; |
searchPtr->nextIndex = 0; |
239 |
searchPtr->nextEntryPtr = NULL; |
searchPtr->nextEntryPtr = NULL; |
240 |
return Tcl_NextHashEntry(searchPtr); |
return Tcl_NextHashEntry(searchPtr); |
241 |
} |
} |
242 |
|
|
243 |
/* |
/* |
244 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
245 |
* |
* |
246 |
* Tcl_NextHashEntry -- |
* Tcl_NextHashEntry -- |
247 |
* |
* |
248 |
* Once a hash table enumeration has been initiated by calling |
* Once a hash table enumeration has been initiated by calling |
249 |
* Tcl_FirstHashEntry, this procedure may be called to return |
* Tcl_FirstHashEntry, this procedure may be called to return |
250 |
* successive elements of the table. |
* successive elements of the table. |
251 |
* |
* |
252 |
* Results: |
* Results: |
253 |
* The return value is the next entry in the hash table being |
* The return value is the next entry in the hash table being |
254 |
* enumerated, or NULL if the end of the table is reached. |
* enumerated, or NULL if the end of the table is reached. |
255 |
* |
* |
256 |
* Side effects: |
* Side effects: |
257 |
* None. |
* None. |
258 |
* |
* |
259 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
260 |
*/ |
*/ |
261 |
|
|
262 |
Tcl_HashEntry * |
Tcl_HashEntry * |
263 |
Tcl_NextHashEntry(searchPtr) |
Tcl_NextHashEntry(searchPtr) |
264 |
register Tcl_HashSearch *searchPtr; /* Place to store information about |
register Tcl_HashSearch *searchPtr; /* Place to store information about |
265 |
* progress through the table. Must |
* progress through the table. Must |
266 |
* have been initialized by calling |
* have been initialized by calling |
267 |
* Tcl_FirstHashEntry. */ |
* Tcl_FirstHashEntry. */ |
268 |
{ |
{ |
269 |
Tcl_HashEntry *hPtr; |
Tcl_HashEntry *hPtr; |
270 |
|
|
271 |
while (searchPtr->nextEntryPtr == NULL) { |
while (searchPtr->nextEntryPtr == NULL) { |
272 |
if (searchPtr->nextIndex >= searchPtr->tablePtr->numBuckets) { |
if (searchPtr->nextIndex >= searchPtr->tablePtr->numBuckets) { |
273 |
return NULL; |
return NULL; |
274 |
} |
} |
275 |
searchPtr->nextEntryPtr = |
searchPtr->nextEntryPtr = |
276 |
searchPtr->tablePtr->buckets[searchPtr->nextIndex]; |
searchPtr->tablePtr->buckets[searchPtr->nextIndex]; |
277 |
searchPtr->nextIndex++; |
searchPtr->nextIndex++; |
278 |
} |
} |
279 |
hPtr = searchPtr->nextEntryPtr; |
hPtr = searchPtr->nextEntryPtr; |
280 |
searchPtr->nextEntryPtr = hPtr->nextPtr; |
searchPtr->nextEntryPtr = hPtr->nextPtr; |
281 |
return hPtr; |
return hPtr; |
282 |
} |
} |
283 |
|
|
284 |
/* |
/* |
285 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
286 |
* |
* |
287 |
* Tcl_HashStats -- |
* Tcl_HashStats -- |
288 |
* |
* |
289 |
* Return statistics describing the layout of the hash table |
* Return statistics describing the layout of the hash table |
290 |
* in its hash buckets. |
* in its hash buckets. |
291 |
* |
* |
292 |
* Results: |
* Results: |
293 |
* The return value is a malloc-ed string containing information |
* The return value is a malloc-ed string containing information |
294 |
* about tablePtr. It is the caller's responsibility to free |
* about tablePtr. It is the caller's responsibility to free |
295 |
* this string. |
* this string. |
296 |
* |
* |
297 |
* Side effects: |
* Side effects: |
298 |
* None. |
* None. |
299 |
* |
* |
300 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
301 |
*/ |
*/ |
302 |
|
|
303 |
char * |
char * |
304 |
Tcl_HashStats(tablePtr) |
Tcl_HashStats(tablePtr) |
305 |
Tcl_HashTable *tablePtr; /* Table for which to produce stats. */ |
Tcl_HashTable *tablePtr; /* Table for which to produce stats. */ |
306 |
{ |
{ |
307 |
#define NUM_COUNTERS 10 |
#define NUM_COUNTERS 10 |
308 |
int count[NUM_COUNTERS], overflow, i, j; |
int count[NUM_COUNTERS], overflow, i, j; |
309 |
double average, tmp; |
double average, tmp; |
310 |
register Tcl_HashEntry *hPtr; |
register Tcl_HashEntry *hPtr; |
311 |
char *result, *p; |
char *result, *p; |
312 |
|
|
313 |
/* |
/* |
314 |
* Compute a histogram of bucket usage. |
* Compute a histogram of bucket usage. |
315 |
*/ |
*/ |
316 |
|
|
317 |
for (i = 0; i < NUM_COUNTERS; i++) { |
for (i = 0; i < NUM_COUNTERS; i++) { |
318 |
count[i] = 0; |
count[i] = 0; |
319 |
} |
} |
320 |
overflow = 0; |
overflow = 0; |
321 |
average = 0.0; |
average = 0.0; |
322 |
for (i = 0; i < tablePtr->numBuckets; i++) { |
for (i = 0; i < tablePtr->numBuckets; i++) { |
323 |
j = 0; |
j = 0; |
324 |
for (hPtr = tablePtr->buckets[i]; hPtr != NULL; hPtr = hPtr->nextPtr) { |
for (hPtr = tablePtr->buckets[i]; hPtr != NULL; hPtr = hPtr->nextPtr) { |
325 |
j++; |
j++; |
326 |
} |
} |
327 |
if (j < NUM_COUNTERS) { |
if (j < NUM_COUNTERS) { |
328 |
count[j]++; |
count[j]++; |
329 |
} else { |
} else { |
330 |
overflow++; |
overflow++; |
331 |
} |
} |
332 |
tmp = j; |
tmp = j; |
333 |
average += (tmp+1.0)*(tmp/tablePtr->numEntries)/2.0; |
average += (tmp+1.0)*(tmp/tablePtr->numEntries)/2.0; |
334 |
} |
} |
335 |
|
|
336 |
/* |
/* |
337 |
* Print out the histogram and a few other pieces of information. |
* Print out the histogram and a few other pieces of information. |
338 |
*/ |
*/ |
339 |
|
|
340 |
result = (char *) ckalloc((unsigned) ((NUM_COUNTERS*60) + 300)); |
result = (char *) ckalloc((unsigned) ((NUM_COUNTERS*60) + 300)); |
341 |
sprintf(result, "%d entries in table, %d buckets\n", |
sprintf(result, "%d entries in table, %d buckets\n", |
342 |
tablePtr->numEntries, tablePtr->numBuckets); |
tablePtr->numEntries, tablePtr->numBuckets); |
343 |
p = result + strlen(result); |
p = result + strlen(result); |
344 |
for (i = 0; i < NUM_COUNTERS; i++) { |
for (i = 0; i < NUM_COUNTERS; i++) { |
345 |
sprintf(p, "number of buckets with %d entries: %d\n", |
sprintf(p, "number of buckets with %d entries: %d\n", |
346 |
i, count[i]); |
i, count[i]); |
347 |
p += strlen(p); |
p += strlen(p); |
348 |
} |
} |
349 |
sprintf(p, "number of buckets with %d or more entries: %d\n", |
sprintf(p, "number of buckets with %d or more entries: %d\n", |
350 |
NUM_COUNTERS, overflow); |
NUM_COUNTERS, overflow); |
351 |
p += strlen(p); |
p += strlen(p); |
352 |
sprintf(p, "average search distance for entry: %.1f", average); |
sprintf(p, "average search distance for entry: %.1f", average); |
353 |
return result; |
return result; |
354 |
} |
} |
355 |
|
|
356 |
/* |
/* |
357 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
358 |
* |
* |
359 |
* HashString -- |
* HashString -- |
360 |
* |
* |
361 |
* Compute a one-word summary of a text string, which can be |
* Compute a one-word summary of a text string, which can be |
362 |
* used to generate a hash index. |
* used to generate a hash index. |
363 |
* |
* |
364 |
* Results: |
* Results: |
365 |
* The return value is a one-word summary of the information in |
* The return value is a one-word summary of the information in |
366 |
* string. |
* string. |
367 |
* |
* |
368 |
* Side effects: |
* Side effects: |
369 |
* None. |
* None. |
370 |
* |
* |
371 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
372 |
*/ |
*/ |
373 |
|
|
374 |
static unsigned int |
static unsigned int |
375 |
HashString(string) |
HashString(string) |
376 |
register CONST char *string;/* String from which to compute hash value. */ |
register CONST char *string;/* String from which to compute hash value. */ |
377 |
{ |
{ |
378 |
register unsigned int result; |
register unsigned int result; |
379 |
register int c; |
register int c; |
380 |
|
|
381 |
/* |
/* |
382 |
* I tried a zillion different hash functions and asked many other |
* I tried a zillion different hash functions and asked many other |
383 |
* people for advice. Many people had their own favorite functions, |
* people for advice. Many people had their own favorite functions, |
384 |
* all different, but no-one had much idea why they were good ones. |
* all different, but no-one had much idea why they were good ones. |
385 |
* I chose the one below (multiply by 9 and add new character) |
* I chose the one below (multiply by 9 and add new character) |
386 |
* because of the following reasons: |
* because of the following reasons: |
387 |
* |
* |
388 |
* 1. Multiplying by 10 is perfect for keys that are decimal strings, |
* 1. Multiplying by 10 is perfect for keys that are decimal strings, |
389 |
* and multiplying by 9 is just about as good. |
* and multiplying by 9 is just about as good. |
390 |
* 2. Times-9 is (shift-left-3) plus (old). This means that each |
* 2. Times-9 is (shift-left-3) plus (old). This means that each |
391 |
* character's bits hang around in the low-order bits of the |
* character's bits hang around in the low-order bits of the |
392 |
* hash value for ever, plus they spread fairly rapidly up to |
* hash value for ever, plus they spread fairly rapidly up to |
393 |
* the high-order bits to fill out the hash value. This seems |
* the high-order bits to fill out the hash value. This seems |
394 |
* works well both for decimal and non-decimal strings. |
* works well both for decimal and non-decimal strings. |
395 |
*/ |
*/ |
396 |
|
|
397 |
result = 0; |
result = 0; |
398 |
while (1) { |
while (1) { |
399 |
c = *string; |
c = *string; |
400 |
string++; |
string++; |
401 |
if (c == 0) { |
if (c == 0) { |
402 |
break; |
break; |
403 |
} |
} |
404 |
result += (result<<3) + c; |
result += (result<<3) + c; |
405 |
} |
} |
406 |
return result; |
return result; |
407 |
} |
} |
408 |
|
|
409 |
/* |
/* |
410 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
411 |
* |
* |
412 |
* StringFind -- |
* StringFind -- |
413 |
* |
* |
414 |
* Given a hash table with string keys, and a string key, find |
* Given a hash table with string keys, and a string key, find |
415 |
* the entry with a matching key. |
* the entry with a matching key. |
416 |
* |
* |
417 |
* Results: |
* Results: |
418 |
* The return value is a token for the matching entry in the |
* The return value is a token for the matching entry in the |
419 |
* hash table, or NULL if there was no matching entry. |
* hash table, or NULL if there was no matching entry. |
420 |
* |
* |
421 |
* Side effects: |
* Side effects: |
422 |
* None. |
* None. |
423 |
* |
* |
424 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
425 |
*/ |
*/ |
426 |
|
|
427 |
static Tcl_HashEntry * |
static Tcl_HashEntry * |
428 |
StringFind(tablePtr, key) |
StringFind(tablePtr, key) |
429 |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
430 |
CONST char *key; /* Key to use to find matching entry. */ |
CONST char *key; /* Key to use to find matching entry. */ |
431 |
{ |
{ |
432 |
register Tcl_HashEntry *hPtr; |
register Tcl_HashEntry *hPtr; |
433 |
register CONST char *p1, *p2; |
register CONST char *p1, *p2; |
434 |
int index; |
int index; |
435 |
|
|
436 |
index = HashString(key) & tablePtr->mask; |
index = HashString(key) & tablePtr->mask; |
437 |
|
|
438 |
/* |
/* |
439 |
* Search all of the entries in the appropriate bucket. |
* Search all of the entries in the appropriate bucket. |
440 |
*/ |
*/ |
441 |
|
|
442 |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
443 |
hPtr = hPtr->nextPtr) { |
hPtr = hPtr->nextPtr) { |
444 |
for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) { |
for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) { |
445 |
if (*p1 != *p2) { |
if (*p1 != *p2) { |
446 |
break; |
break; |
447 |
} |
} |
448 |
if (*p1 == '\0') { |
if (*p1 == '\0') { |
449 |
return hPtr; |
return hPtr; |
450 |
} |
} |
451 |
} |
} |
452 |
} |
} |
453 |
return NULL; |
return NULL; |
454 |
} |
} |
455 |
|
|
456 |
/* |
/* |
457 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
458 |
* |
* |
459 |
* StringCreate -- |
* StringCreate -- |
460 |
* |
* |
461 |
* Given a hash table with string keys, and a string key, find |
* Given a hash table with string keys, and a string key, find |
462 |
* the entry with a matching key. If there is no matching entry, |
* the entry with a matching key. If there is no matching entry, |
463 |
* then create a new entry that does match. |
* then create a new entry that does match. |
464 |
* |
* |
465 |
* Results: |
* Results: |
466 |
* The return value is a pointer to the matching entry. If this |
* The return value is a pointer to the matching entry. If this |
467 |
* is a newly-created entry, then *newPtr will be set to a non-zero |
* is a newly-created entry, then *newPtr will be set to a non-zero |
468 |
* value; otherwise *newPtr will be set to 0. If this is a new |
* value; otherwise *newPtr will be set to 0. If this is a new |
469 |
* entry the value stored in the entry will initially be 0. |
* entry the value stored in the entry will initially be 0. |
470 |
* |
* |
471 |
* Side effects: |
* Side effects: |
472 |
* A new entry may be added to the hash table. |
* A new entry may be added to the hash table. |
473 |
* |
* |
474 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
475 |
*/ |
*/ |
476 |
|
|
477 |
static Tcl_HashEntry * |
static Tcl_HashEntry * |
478 |
StringCreate(tablePtr, key, newPtr) |
StringCreate(tablePtr, key, newPtr) |
479 |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
480 |
CONST char *key; /* Key to use to find or create matching |
CONST char *key; /* Key to use to find or create matching |
481 |
* entry. */ |
* entry. */ |
482 |
int *newPtr; /* Store info here telling whether a new |
int *newPtr; /* Store info here telling whether a new |
483 |
* entry was created. */ |
* entry was created. */ |
484 |
{ |
{ |
485 |
register Tcl_HashEntry *hPtr; |
register Tcl_HashEntry *hPtr; |
486 |
register CONST char *p1, *p2; |
register CONST char *p1, *p2; |
487 |
int index; |
int index; |
488 |
|
|
489 |
index = HashString(key) & tablePtr->mask; |
index = HashString(key) & tablePtr->mask; |
490 |
|
|
491 |
/* |
/* |
492 |
* Search all of the entries in this bucket. |
* Search all of the entries in this bucket. |
493 |
*/ |
*/ |
494 |
|
|
495 |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
496 |
hPtr = hPtr->nextPtr) { |
hPtr = hPtr->nextPtr) { |
497 |
for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) { |
for (p1 = key, p2 = hPtr->key.string; ; p1++, p2++) { |
498 |
if (*p1 != *p2) { |
if (*p1 != *p2) { |
499 |
break; |
break; |
500 |
} |
} |
501 |
if (*p1 == '\0') { |
if (*p1 == '\0') { |
502 |
*newPtr = 0; |
*newPtr = 0; |
503 |
return hPtr; |
return hPtr; |
504 |
} |
} |
505 |
} |
} |
506 |
} |
} |
507 |
|
|
508 |
/* |
/* |
509 |
* Entry not found. Add a new one to the bucket. |
* Entry not found. Add a new one to the bucket. |
510 |
*/ |
*/ |
511 |
|
|
512 |
*newPtr = 1; |
*newPtr = 1; |
513 |
hPtr = (Tcl_HashEntry *) ckalloc((unsigned) |
hPtr = (Tcl_HashEntry *) ckalloc((unsigned) |
514 |
(sizeof(Tcl_HashEntry) + strlen(key) - (sizeof(hPtr->key) -1))); |
(sizeof(Tcl_HashEntry) + strlen(key) - (sizeof(hPtr->key) -1))); |
515 |
hPtr->tablePtr = tablePtr; |
hPtr->tablePtr = tablePtr; |
516 |
hPtr->bucketPtr = &(tablePtr->buckets[index]); |
hPtr->bucketPtr = &(tablePtr->buckets[index]); |
517 |
hPtr->nextPtr = *hPtr->bucketPtr; |
hPtr->nextPtr = *hPtr->bucketPtr; |
518 |
hPtr->clientData = 0; |
hPtr->clientData = 0; |
519 |
strcpy(hPtr->key.string, key); |
strcpy(hPtr->key.string, key); |
520 |
*hPtr->bucketPtr = hPtr; |
*hPtr->bucketPtr = hPtr; |
521 |
tablePtr->numEntries++; |
tablePtr->numEntries++; |
522 |
|
|
523 |
/* |
/* |
524 |
* If the table has exceeded a decent size, rebuild it with many |
* If the table has exceeded a decent size, rebuild it with many |
525 |
* more buckets. |
* more buckets. |
526 |
*/ |
*/ |
527 |
|
|
528 |
if (tablePtr->numEntries >= tablePtr->rebuildSize) { |
if (tablePtr->numEntries >= tablePtr->rebuildSize) { |
529 |
RebuildTable(tablePtr); |
RebuildTable(tablePtr); |
530 |
} |
} |
531 |
return hPtr; |
return hPtr; |
532 |
} |
} |
533 |
|
|
534 |
/* |
/* |
535 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
536 |
* |
* |
537 |
* OneWordFind -- |
* OneWordFind -- |
538 |
* |
* |
539 |
* Given a hash table with one-word keys, and a one-word key, find |
* Given a hash table with one-word keys, and a one-word key, find |
540 |
* the entry with a matching key. |
* the entry with a matching key. |
541 |
* |
* |
542 |
* Results: |
* Results: |
543 |
* The return value is a token for the matching entry in the |
* The return value is a token for the matching entry in the |
544 |
* hash table, or NULL if there was no matching entry. |
* hash table, or NULL if there was no matching entry. |
545 |
* |
* |
546 |
* Side effects: |
* Side effects: |
547 |
* None. |
* None. |
548 |
* |
* |
549 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
550 |
*/ |
*/ |
551 |
|
|
552 |
static Tcl_HashEntry * |
static Tcl_HashEntry * |
553 |
OneWordFind(tablePtr, key) |
OneWordFind(tablePtr, key) |
554 |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
555 |
register CONST char *key; /* Key to use to find matching entry. */ |
register CONST char *key; /* Key to use to find matching entry. */ |
556 |
{ |
{ |
557 |
register Tcl_HashEntry *hPtr; |
register Tcl_HashEntry *hPtr; |
558 |
int index; |
int index; |
559 |
|
|
560 |
index = RANDOM_INDEX(tablePtr, key); |
index = RANDOM_INDEX(tablePtr, key); |
561 |
|
|
562 |
/* |
/* |
563 |
* Search all of the entries in the appropriate bucket. |
* Search all of the entries in the appropriate bucket. |
564 |
*/ |
*/ |
565 |
|
|
566 |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
567 |
hPtr = hPtr->nextPtr) { |
hPtr = hPtr->nextPtr) { |
568 |
if (hPtr->key.oneWordValue == key) { |
if (hPtr->key.oneWordValue == key) { |
569 |
return hPtr; |
return hPtr; |
570 |
} |
} |
571 |
} |
} |
572 |
return NULL; |
return NULL; |
573 |
} |
} |
574 |
|
|
575 |
/* |
/* |
576 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
577 |
* |
* |
578 |
* OneWordCreate -- |
* OneWordCreate -- |
579 |
* |
* |
580 |
* Given a hash table with one-word keys, and a one-word key, find |
* Given a hash table with one-word keys, and a one-word key, find |
581 |
* the entry with a matching key. If there is no matching entry, |
* the entry with a matching key. If there is no matching entry, |
582 |
* then create a new entry that does match. |
* then create a new entry that does match. |
583 |
* |
* |
584 |
* Results: |
* Results: |
585 |
* The return value is a pointer to the matching entry. If this |
* The return value is a pointer to the matching entry. If this |
586 |
* is a newly-created entry, then *newPtr will be set to a non-zero |
* is a newly-created entry, then *newPtr will be set to a non-zero |
587 |
* value; otherwise *newPtr will be set to 0. If this is a new |
* value; otherwise *newPtr will be set to 0. If this is a new |
588 |
* entry the value stored in the entry will initially be 0. |
* entry the value stored in the entry will initially be 0. |
589 |
* |
* |
590 |
* Side effects: |
* Side effects: |
591 |
* A new entry may be added to the hash table. |
* A new entry may be added to the hash table. |
592 |
* |
* |
593 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
594 |
*/ |
*/ |
595 |
|
|
596 |
static Tcl_HashEntry * |
static Tcl_HashEntry * |
597 |
OneWordCreate(tablePtr, key, newPtr) |
OneWordCreate(tablePtr, key, newPtr) |
598 |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
599 |
register CONST char *key; /* Key to use to find or create matching |
register CONST char *key; /* Key to use to find or create matching |
600 |
* entry. */ |
* entry. */ |
601 |
int *newPtr; /* Store info here telling whether a new |
int *newPtr; /* Store info here telling whether a new |
602 |
* entry was created. */ |
* entry was created. */ |
603 |
{ |
{ |
604 |
register Tcl_HashEntry *hPtr; |
register Tcl_HashEntry *hPtr; |
605 |
int index; |
int index; |
606 |
|
|
607 |
index = RANDOM_INDEX(tablePtr, key); |
index = RANDOM_INDEX(tablePtr, key); |
608 |
|
|
609 |
/* |
/* |
610 |
* Search all of the entries in this bucket. |
* Search all of the entries in this bucket. |
611 |
*/ |
*/ |
612 |
|
|
613 |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
614 |
hPtr = hPtr->nextPtr) { |
hPtr = hPtr->nextPtr) { |
615 |
if (hPtr->key.oneWordValue == key) { |
if (hPtr->key.oneWordValue == key) { |
616 |
*newPtr = 0; |
*newPtr = 0; |
617 |
return hPtr; |
return hPtr; |
618 |
} |
} |
619 |
} |
} |
620 |
|
|
621 |
/* |
/* |
622 |
* Entry not found. Add a new one to the bucket. |
* Entry not found. Add a new one to the bucket. |
623 |
*/ |
*/ |
624 |
|
|
625 |
*newPtr = 1; |
*newPtr = 1; |
626 |
hPtr = (Tcl_HashEntry *) ckalloc(sizeof(Tcl_HashEntry)); |
hPtr = (Tcl_HashEntry *) ckalloc(sizeof(Tcl_HashEntry)); |
627 |
hPtr->tablePtr = tablePtr; |
hPtr->tablePtr = tablePtr; |
628 |
hPtr->bucketPtr = &(tablePtr->buckets[index]); |
hPtr->bucketPtr = &(tablePtr->buckets[index]); |
629 |
hPtr->nextPtr = *hPtr->bucketPtr; |
hPtr->nextPtr = *hPtr->bucketPtr; |
630 |
hPtr->clientData = 0; |
hPtr->clientData = 0; |
631 |
hPtr->key.oneWordValue = (char *) key; /* CONST XXXX */ |
hPtr->key.oneWordValue = (char *) key; /* CONST XXXX */ |
632 |
*hPtr->bucketPtr = hPtr; |
*hPtr->bucketPtr = hPtr; |
633 |
tablePtr->numEntries++; |
tablePtr->numEntries++; |
634 |
|
|
635 |
/* |
/* |
636 |
* If the table has exceeded a decent size, rebuild it with many |
* If the table has exceeded a decent size, rebuild it with many |
637 |
* more buckets. |
* more buckets. |
638 |
*/ |
*/ |
639 |
|
|
640 |
if (tablePtr->numEntries >= tablePtr->rebuildSize) { |
if (tablePtr->numEntries >= tablePtr->rebuildSize) { |
641 |
RebuildTable(tablePtr); |
RebuildTable(tablePtr); |
642 |
} |
} |
643 |
return hPtr; |
return hPtr; |
644 |
} |
} |
645 |
|
|
646 |
/* |
/* |
647 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
648 |
* |
* |
649 |
* ArrayFind -- |
* ArrayFind -- |
650 |
* |
* |
651 |
* Given a hash table with array-of-int keys, and a key, find |
* Given a hash table with array-of-int keys, and a key, find |
652 |
* the entry with a matching key. |
* the entry with a matching key. |
653 |
* |
* |
654 |
* Results: |
* Results: |
655 |
* The return value is a token for the matching entry in the |
* The return value is a token for the matching entry in the |
656 |
* hash table, or NULL if there was no matching entry. |
* hash table, or NULL if there was no matching entry. |
657 |
* |
* |
658 |
* Side effects: |
* Side effects: |
659 |
* None. |
* None. |
660 |
* |
* |
661 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
662 |
*/ |
*/ |
663 |
|
|
664 |
static Tcl_HashEntry * |
static Tcl_HashEntry * |
665 |
ArrayFind(tablePtr, key) |
ArrayFind(tablePtr, key) |
666 |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
667 |
CONST char *key; /* Key to use to find matching entry. */ |
CONST char *key; /* Key to use to find matching entry. */ |
668 |
{ |
{ |
669 |
register Tcl_HashEntry *hPtr; |
register Tcl_HashEntry *hPtr; |
670 |
int *arrayPtr = (int *) key; |
int *arrayPtr = (int *) key; |
671 |
register int *iPtr1, *iPtr2; |
register int *iPtr1, *iPtr2; |
672 |
int index, count; |
int index, count; |
673 |
|
|
674 |
for (index = 0, count = tablePtr->keyType, iPtr1 = arrayPtr; |
for (index = 0, count = tablePtr->keyType, iPtr1 = arrayPtr; |
675 |
count > 0; count--, iPtr1++) { |
count > 0; count--, iPtr1++) { |
676 |
index += *iPtr1; |
index += *iPtr1; |
677 |
} |
} |
678 |
index = RANDOM_INDEX(tablePtr, index); |
index = RANDOM_INDEX(tablePtr, index); |
679 |
|
|
680 |
/* |
/* |
681 |
* Search all of the entries in the appropriate bucket. |
* Search all of the entries in the appropriate bucket. |
682 |
*/ |
*/ |
683 |
|
|
684 |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
685 |
hPtr = hPtr->nextPtr) { |
hPtr = hPtr->nextPtr) { |
686 |
for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words, |
for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words, |
687 |
count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) { |
count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) { |
688 |
if (count == 0) { |
if (count == 0) { |
689 |
return hPtr; |
return hPtr; |
690 |
} |
} |
691 |
if (*iPtr1 != *iPtr2) { |
if (*iPtr1 != *iPtr2) { |
692 |
break; |
break; |
693 |
} |
} |
694 |
} |
} |
695 |
} |
} |
696 |
return NULL; |
return NULL; |
697 |
} |
} |
698 |
|
|
699 |
/* |
/* |
700 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
701 |
* |
* |
702 |
* ArrayCreate -- |
* ArrayCreate -- |
703 |
* |
* |
704 |
* Given a hash table with one-word keys, and a one-word key, find |
* Given a hash table with one-word keys, and a one-word key, find |
705 |
* the entry with a matching key. If there is no matching entry, |
* the entry with a matching key. If there is no matching entry, |
706 |
* then create a new entry that does match. |
* then create a new entry that does match. |
707 |
* |
* |
708 |
* Results: |
* Results: |
709 |
* The return value is a pointer to the matching entry. If this |
* The return value is a pointer to the matching entry. If this |
710 |
* is a newly-created entry, then *newPtr will be set to a non-zero |
* is a newly-created entry, then *newPtr will be set to a non-zero |
711 |
* value; otherwise *newPtr will be set to 0. If this is a new |
* value; otherwise *newPtr will be set to 0. If this is a new |
712 |
* entry the value stored in the entry will initially be 0. |
* entry the value stored in the entry will initially be 0. |
713 |
* |
* |
714 |
* Side effects: |
* Side effects: |
715 |
* A new entry may be added to the hash table. |
* A new entry may be added to the hash table. |
716 |
* |
* |
717 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
718 |
*/ |
*/ |
719 |
|
|
720 |
static Tcl_HashEntry * |
static Tcl_HashEntry * |
721 |
ArrayCreate(tablePtr, key, newPtr) |
ArrayCreate(tablePtr, key, newPtr) |
722 |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
723 |
register CONST char *key; /* Key to use to find or create matching |
register CONST char *key; /* Key to use to find or create matching |
724 |
* entry. */ |
* entry. */ |
725 |
int *newPtr; /* Store info here telling whether a new |
int *newPtr; /* Store info here telling whether a new |
726 |
* entry was created. */ |
* entry was created. */ |
727 |
{ |
{ |
728 |
register Tcl_HashEntry *hPtr; |
register Tcl_HashEntry *hPtr; |
729 |
int *arrayPtr = (int *) key; |
int *arrayPtr = (int *) key; |
730 |
register int *iPtr1, *iPtr2; |
register int *iPtr1, *iPtr2; |
731 |
int index, count; |
int index, count; |
732 |
|
|
733 |
for (index = 0, count = tablePtr->keyType, iPtr1 = arrayPtr; |
for (index = 0, count = tablePtr->keyType, iPtr1 = arrayPtr; |
734 |
count > 0; count--, iPtr1++) { |
count > 0; count--, iPtr1++) { |
735 |
index += *iPtr1; |
index += *iPtr1; |
736 |
} |
} |
737 |
index = RANDOM_INDEX(tablePtr, index); |
index = RANDOM_INDEX(tablePtr, index); |
738 |
|
|
739 |
/* |
/* |
740 |
* Search all of the entries in the appropriate bucket. |
* Search all of the entries in the appropriate bucket. |
741 |
*/ |
*/ |
742 |
|
|
743 |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
for (hPtr = tablePtr->buckets[index]; hPtr != NULL; |
744 |
hPtr = hPtr->nextPtr) { |
hPtr = hPtr->nextPtr) { |
745 |
for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words, |
for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words, |
746 |
count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) { |
count = tablePtr->keyType; ; count--, iPtr1++, iPtr2++) { |
747 |
if (count == 0) { |
if (count == 0) { |
748 |
*newPtr = 0; |
*newPtr = 0; |
749 |
return hPtr; |
return hPtr; |
750 |
} |
} |
751 |
if (*iPtr1 != *iPtr2) { |
if (*iPtr1 != *iPtr2) { |
752 |
break; |
break; |
753 |
} |
} |
754 |
} |
} |
755 |
} |
} |
756 |
|
|
757 |
/* |
/* |
758 |
* Entry not found. Add a new one to the bucket. |
* Entry not found. Add a new one to the bucket. |
759 |
*/ |
*/ |
760 |
|
|
761 |
*newPtr = 1; |
*newPtr = 1; |
762 |
hPtr = (Tcl_HashEntry *) ckalloc((unsigned) (sizeof(Tcl_HashEntry) |
hPtr = (Tcl_HashEntry *) ckalloc((unsigned) (sizeof(Tcl_HashEntry) |
763 |
+ (tablePtr->keyType*sizeof(int)) - 4)); |
+ (tablePtr->keyType*sizeof(int)) - 4)); |
764 |
hPtr->tablePtr = tablePtr; |
hPtr->tablePtr = tablePtr; |
765 |
hPtr->bucketPtr = &(tablePtr->buckets[index]); |
hPtr->bucketPtr = &(tablePtr->buckets[index]); |
766 |
hPtr->nextPtr = *hPtr->bucketPtr; |
hPtr->nextPtr = *hPtr->bucketPtr; |
767 |
hPtr->clientData = 0; |
hPtr->clientData = 0; |
768 |
for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words, count = tablePtr->keyType; |
for (iPtr1 = arrayPtr, iPtr2 = hPtr->key.words, count = tablePtr->keyType; |
769 |
count > 0; count--, iPtr1++, iPtr2++) { |
count > 0; count--, iPtr1++, iPtr2++) { |
770 |
*iPtr2 = *iPtr1; |
*iPtr2 = *iPtr1; |
771 |
} |
} |
772 |
*hPtr->bucketPtr = hPtr; |
*hPtr->bucketPtr = hPtr; |
773 |
tablePtr->numEntries++; |
tablePtr->numEntries++; |
774 |
|
|
775 |
/* |
/* |
776 |
* If the table has exceeded a decent size, rebuild it with many |
* If the table has exceeded a decent size, rebuild it with many |
777 |
* more buckets. |
* more buckets. |
778 |
*/ |
*/ |
779 |
|
|
780 |
if (tablePtr->numEntries >= tablePtr->rebuildSize) { |
if (tablePtr->numEntries >= tablePtr->rebuildSize) { |
781 |
RebuildTable(tablePtr); |
RebuildTable(tablePtr); |
782 |
} |
} |
783 |
return hPtr; |
return hPtr; |
784 |
} |
} |
785 |
|
|
786 |
/* |
/* |
787 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
788 |
* |
* |
789 |
* BogusFind -- |
* BogusFind -- |
790 |
* |
* |
791 |
* This procedure is invoked when an Tcl_FindHashEntry is called |
* This procedure is invoked when an Tcl_FindHashEntry is called |
792 |
* on a table that has been deleted. |
* on a table that has been deleted. |
793 |
* |
* |
794 |
* Results: |
* Results: |
795 |
* If panic returns (which it shouldn't) this procedure returns |
* If panic returns (which it shouldn't) this procedure returns |
796 |
* NULL. |
* NULL. |
797 |
* |
* |
798 |
* Side effects: |
* Side effects: |
799 |
* Generates a panic. |
* Generates a panic. |
800 |
* |
* |
801 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
802 |
*/ |
*/ |
803 |
|
|
804 |
/* ARGSUSED */ |
/* ARGSUSED */ |
805 |
static Tcl_HashEntry * |
static Tcl_HashEntry * |
806 |
BogusFind(tablePtr, key) |
BogusFind(tablePtr, key) |
807 |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
808 |
CONST char *key; /* Key to use to find matching entry. */ |
CONST char *key; /* Key to use to find matching entry. */ |
809 |
{ |
{ |
810 |
panic("called Tcl_FindHashEntry on deleted table"); |
panic("called Tcl_FindHashEntry on deleted table"); |
811 |
return NULL; |
return NULL; |
812 |
} |
} |
813 |
|
|
814 |
/* |
/* |
815 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
816 |
* |
* |
817 |
* BogusCreate -- |
* BogusCreate -- |
818 |
* |
* |
819 |
* This procedure is invoked when an Tcl_CreateHashEntry is called |
* This procedure is invoked when an Tcl_CreateHashEntry is called |
820 |
* on a table that has been deleted. |
* on a table that has been deleted. |
821 |
* |
* |
822 |
* Results: |
* Results: |
823 |
* If panic returns (which it shouldn't) this procedure returns |
* If panic returns (which it shouldn't) this procedure returns |
824 |
* NULL. |
* NULL. |
825 |
* |
* |
826 |
* Side effects: |
* Side effects: |
827 |
* Generates a panic. |
* Generates a panic. |
828 |
* |
* |
829 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
830 |
*/ |
*/ |
831 |
|
|
832 |
/* ARGSUSED */ |
/* ARGSUSED */ |
833 |
static Tcl_HashEntry * |
static Tcl_HashEntry * |
834 |
BogusCreate(tablePtr, key, newPtr) |
BogusCreate(tablePtr, key, newPtr) |
835 |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
Tcl_HashTable *tablePtr; /* Table in which to lookup entry. */ |
836 |
CONST char *key; /* Key to use to find or create matching |
CONST char *key; /* Key to use to find or create matching |
837 |
* entry. */ |
* entry. */ |
838 |
int *newPtr; /* Store info here telling whether a new |
int *newPtr; /* Store info here telling whether a new |
839 |
* entry was created. */ |
* entry was created. */ |
840 |
{ |
{ |
841 |
panic("called Tcl_CreateHashEntry on deleted table"); |
panic("called Tcl_CreateHashEntry on deleted table"); |
842 |
return NULL; |
return NULL; |
843 |
} |
} |
844 |
|
|
845 |
/* |
/* |
846 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
847 |
* |
* |
848 |
* RebuildTable -- |
* RebuildTable -- |
849 |
* |
* |
850 |
* This procedure is invoked when the ratio of entries to hash |
* This procedure is invoked when the ratio of entries to hash |
851 |
* buckets becomes too large. It creates a new table with a |
* buckets becomes too large. It creates a new table with a |
852 |
* larger bucket array and moves all of the entries into the |
* larger bucket array and moves all of the entries into the |
853 |
* new table. |
* new table. |
854 |
* |
* |
855 |
* Results: |
* Results: |
856 |
* None. |
* None. |
857 |
* |
* |
858 |
* Side effects: |
* Side effects: |
859 |
* Memory gets reallocated and entries get re-hashed to new |
* Memory gets reallocated and entries get re-hashed to new |
860 |
* buckets. |
* buckets. |
861 |
* |
* |
862 |
*---------------------------------------------------------------------- |
*---------------------------------------------------------------------- |
863 |
*/ |
*/ |
864 |
|
|
865 |
static void |
static void |
866 |
RebuildTable(tablePtr) |
RebuildTable(tablePtr) |
867 |
register Tcl_HashTable *tablePtr; /* Table to enlarge. */ |
register Tcl_HashTable *tablePtr; /* Table to enlarge. */ |
868 |
{ |
{ |
869 |
int oldSize, count, index; |
int oldSize, count, index; |
870 |
Tcl_HashEntry **oldBuckets; |
Tcl_HashEntry **oldBuckets; |
871 |
register Tcl_HashEntry **oldChainPtr, **newChainPtr; |
register Tcl_HashEntry **oldChainPtr, **newChainPtr; |
872 |
register Tcl_HashEntry *hPtr; |
register Tcl_HashEntry *hPtr; |
873 |
|
|
874 |
oldSize = tablePtr->numBuckets; |
oldSize = tablePtr->numBuckets; |
875 |
oldBuckets = tablePtr->buckets; |
oldBuckets = tablePtr->buckets; |
876 |
|
|
877 |
/* |
/* |
878 |
* Allocate and initialize the new bucket array, and set up |
* Allocate and initialize the new bucket array, and set up |
879 |
* hashing constants for new array size. |
* hashing constants for new array size. |
880 |
*/ |
*/ |
881 |
|
|
882 |
tablePtr->numBuckets *= 4; |
tablePtr->numBuckets *= 4; |
883 |
tablePtr->buckets = (Tcl_HashEntry **) ckalloc((unsigned) |
tablePtr->buckets = (Tcl_HashEntry **) ckalloc((unsigned) |
884 |
(tablePtr->numBuckets * sizeof(Tcl_HashEntry *))); |
(tablePtr->numBuckets * sizeof(Tcl_HashEntry *))); |
885 |
for (count = tablePtr->numBuckets, newChainPtr = tablePtr->buckets; |
for (count = tablePtr->numBuckets, newChainPtr = tablePtr->buckets; |
886 |
count > 0; count--, newChainPtr++) { |
count > 0; count--, newChainPtr++) { |
887 |
*newChainPtr = NULL; |
*newChainPtr = NULL; |
888 |
} |
} |
889 |
tablePtr->rebuildSize *= 4; |
tablePtr->rebuildSize *= 4; |
890 |
tablePtr->downShift -= 2; |
tablePtr->downShift -= 2; |
891 |
tablePtr->mask = (tablePtr->mask << 2) + 3; |
tablePtr->mask = (tablePtr->mask << 2) + 3; |
892 |
|
|
893 |
/* |
/* |
894 |
* Rehash all of the existing entries into the new bucket array. |
* Rehash all of the existing entries into the new bucket array. |
895 |
*/ |
*/ |
896 |
|
|
897 |
for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) { |
for (oldChainPtr = oldBuckets; oldSize > 0; oldSize--, oldChainPtr++) { |
898 |
for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) { |
for (hPtr = *oldChainPtr; hPtr != NULL; hPtr = *oldChainPtr) { |
899 |
*oldChainPtr = hPtr->nextPtr; |
*oldChainPtr = hPtr->nextPtr; |
900 |
if (tablePtr->keyType == TCL_STRING_KEYS) { |
if (tablePtr->keyType == TCL_STRING_KEYS) { |
901 |
index = HashString(hPtr->key.string) & tablePtr->mask; |
index = HashString(hPtr->key.string) & tablePtr->mask; |
902 |
} else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) { |
} else if (tablePtr->keyType == TCL_ONE_WORD_KEYS) { |
903 |
index = RANDOM_INDEX(tablePtr, hPtr->key.oneWordValue); |
index = RANDOM_INDEX(tablePtr, hPtr->key.oneWordValue); |
904 |
} else { |
} else { |
905 |
register int *iPtr; |
register int *iPtr; |
906 |
int count; |
int count; |
907 |
|
|
908 |
for (index = 0, count = tablePtr->keyType, |
for (index = 0, count = tablePtr->keyType, |
909 |
iPtr = hPtr->key.words; count > 0; count--, iPtr++) { |
iPtr = hPtr->key.words; count > 0; count--, iPtr++) { |
910 |
index += *iPtr; |
index += *iPtr; |
911 |
} |
} |
912 |
index = RANDOM_INDEX(tablePtr, index); |
index = RANDOM_INDEX(tablePtr, index); |
913 |
} |
} |
914 |
hPtr->bucketPtr = &(tablePtr->buckets[index]); |
hPtr->bucketPtr = &(tablePtr->buckets[index]); |
915 |
hPtr->nextPtr = *hPtr->bucketPtr; |
hPtr->nextPtr = *hPtr->bucketPtr; |
916 |
*hPtr->bucketPtr = hPtr; |
*hPtr->bucketPtr = hPtr; |
917 |
} |
} |
918 |
} |
} |
919 |
|
|
920 |
/* |
/* |
921 |
* Free up the old bucket array, if it was dynamically allocated. |
* Free up the old bucket array, if it was dynamically allocated. |
922 |
*/ |
*/ |
923 |
|
|
924 |
if (oldBuckets != tablePtr->staticBuckets) { |
if (oldBuckets != tablePtr->staticBuckets) { |
925 |
ckfree((char *) oldBuckets); |
ckfree((char *) oldBuckets); |
926 |
} |
} |
927 |
} |
} |
928 |
|
|
929 |
/* End of tclhash.c */ |
/* End of tclhash.c */ |