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