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