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

Annotation of /projs/trunk/shared_source/c_tcl_base_7_5_w_mods/tclhash.c

Parent Directory Parent Directory | Revision Log Revision Log


Revision 64 - (hide annotations) (download)
Sun Oct 30 04:21:11 2016 UTC (7 years, 8 months ago) by dashley
File MIME type: text/plain
File size: 25930 byte(s)
Adjust line endings to Windows style.
Set properties to expand the "Header" keyword.
Change header and footer.
1 dashley 64 /* $Header$ */
2 dashley 25 /*
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 dashley 64 /* End of tclhash.c */

Properties

Name Value
svn:keywords Header

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25