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

Diff of /projs/dtats/trunk/shared_source/c_tcl_base_7_5_w_mods/tclhash.c

Parent Directory Parent Directory | Revision Log Revision Log | View Patch Patch

revision 70 by dashley, Sun Oct 30 04:21:11 2016 UTC revision 71 by dashley, Sat Nov 5 11:07:06 2016 UTC
# Line 1  Line 1 
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 */

Legend:
Removed from v.70  
changed lines
  Added in v.71

dashley@gmail.com
ViewVC Help
Powered by ViewVC 1.1.25