/[dtapublic]/projs/trunk/shared_source/tcl_base/tclhash.c
ViewVC logotype

Contents of /projs/trunk/shared_source/tcl_base/tclhash.c

Parent Directory Parent Directory | Revision Log Revision Log


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

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25