home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / oleo-1.4 / hash.c < prev    next >
Encoding:
C/C++ Source or Header  |  1993-05-14  |  27.7 KB  |  947 lines
  1. /*
  2.  * hash.c - hash table lookup strings - Copyright (C) 1987, 1992, 1993 Free Software
  3.  * Foundation, Inc.
  4.  *
  5.  * This file is part of GAS, the GNU Assembler.
  6.  *
  7.  * GAS is free software; you can redistribute it and/or modify it under the
  8.  * terms of the GNU General Public License as published by the Free Software
  9.  * Foundation; either version 2, or (at your option) any later version.
  10.  *
  11.  * GAS is distributed in the hope that it will be useful, but WITHOUT ANY
  12.  * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
  13.  * FOR A PARTICULAR PURPOSE.  See the GNU General Public License for more
  14.  * details.
  15.  *
  16.  * You should have received a copy of the GNU General Public License along with
  17.  * GAS; see the file COPYING.  If not, write to the Free Software Foundation,
  18.  * 675 Mass Ave, Cambridge, MA 02139, USA.
  19.  */
  20.  
  21. /*
  22.  * BUGS, GRIPES, APOLOGIA etc.
  23.  *
  24.  * A typical user doesn't need ALL this: I intend to make a library out of it
  25.  * one day - Dean Elsner. Also, I want to change the definition of a symbol
  26.  * to (address,length) so I can put arbitrary binary in the names stored.
  27.  * [see hsh.c for that]
  28.  *
  29.  * This slime is common coupled inside the module. Com-coupling (and other
  30.  * vandalism) was done to speed running time. The interfaces at the module's
  31.  * edges are adequately clean.
  32.  *
  33.  * There is no way to (a) run a test script through this heap and (b) compare
  34.  * results with previous scripts, to see if we have broken any code. Use GNU
  35.  * (f)utilities to do this. A few commands assist test. The testing is
  36.  * awkward: it tries to be both batch & interactive. For now, interactive
  37.  * rules!
  38.  */
  39.  
  40.  
  41. /* The idea is to implement a symbol table. A test jig is here. Symbols are
  42. arbitrary strings; they can't contain '\0'.  Each symbol is associated with a
  43. VOIDSTAR, which can point to anything you want, allowing an arbitrary
  44. property list for each symbol.
  45.  
  46.     The basic operations are:
  47.         new            creates symbol table, returns handle
  48.         find (symbol)        returns VOIDSTAR
  49.         insert(symbol,VOIDSTAR) error if symbol already in table
  50.         delete (symbol)        returns VOIDSTAR if symbol was in table
  51.         apply            so you can delete all symbols before
  52.         die()            destroy symbol table (free up memory)
  53.     Supplementary functions include:
  54.         say how big?
  55.          what % full?
  56.           replace (symbol,newval)    report previous value
  57.          jam (symbol,value)    assert symbol:=value
  58.         
  59. You, the caller, have control over errors: this just reports them.
  60.  
  61. This package requires malloc(), free(). Malloc(size) returns NULL or address
  62. of char[size].  Free(address) frees same.  */
  63.  
  64.  
  65. /*
  66.  * The code and its structures are re-enterent. Before you do anything else,
  67.  * you must call hash_new() which will return the address of a
  68.  * hash-table-control-block (or NULL if there is not enough memory). You then
  69.  * use this address as a handle of the symbol table by passing it to all the
  70.  * other hash_...() functions. The only approved way to recover the memory
  71.  * used by the symbol table is to call hash_die() with the handle of the
  72.  * symbol table.
  73.  *
  74.  * Before you call hash_die() you normally delete anything pointed to by
  75.  * individual symbols. After hash_die() you can't use that symbol table
  76.  * again.
  77.  *
  78.  * The char* you associate with a symbol may not be NULL (0) because NULL is
  79.  * returned whenever a symbol is not in the table. Any other value is OK,
  80.  * except DELETED, #defined below.
  81.  *
  82.  * When you supply a symbol string for insertion, YOU MUST PRESERVE THE STRING
  83.  * until that symbol is deleted from the table. The reason is that only the
  84.  * address you supply, NOT the symbol string itself, is stored in the symbol
  85.  * table.
  86.  *
  87.  * You may delete and add symbols arbitrarily. Any or all symbols may have the
  88.  * same 'value' (char *). In fact, these routines don't do anything with your
  89.  * symbol values.
  90.  *
  91.  * You have no right to know where the symbol:char* mapping is stored, because
  92.  * it moves around in memory; also because we may change how it works and we
  93.  * don't want to break your code do we? However the handle (address of struct
  94.  * hash_control) is never changed in the life of the symbol table.
  95.  *
  96.  * What you CAN find out about a symbol table is: how many slots are in the hash
  97.  * table? how many slots are filled with symbols? (total hashes,collisions)
  98.  * for (reads,writes) (*) All of the above values vary in time. (*) some of
  99.  * these numbers will not be meaningful if we change the internals.
  100.  */
  101.  
  102.  
  103. /*
  104.  * I N T E R N A L
  105.  *
  106.  * Hash table is an array of hash_entries; each entry is a pointer to a a string
  107.  * and a user-supplied value 1 char* wide.
  108.  *
  109.  * The array always has 2 ** n elements, n>0, n integer. There is also a 'wall'
  110.  * entry after the array, which is always empty and acts as a sentinel to
  111.  * stop running off the end of the array. When the array gets too full, we
  112.  * create a new array twice as large and re-hash the symbols into the new
  113.  * array, then forget the old array. (Of course, we copy the values into the
  114.  * new array before we junk the old array!)
  115.  *
  116.  */
  117.  
  118. #include <stdio.h>
  119. #ifndef VOIDSTAR
  120. #define VOIDSTAR void *
  121. #endif
  122. VOIDSTAR malloc ();
  123. void free ();
  124.  
  125. #undef TRUE
  126. #define TRUE           (1)
  127. #undef FALSE
  128. #define FALSE          (0)
  129. #include <ctype.h>
  130. #define min(a, b)    ((a) < (b) ? (a) : (b))
  131.  
  132. #include "sysdef.h"        /* For Oleo, specificly. define bzero etc. */
  133. #include "hash.h"
  134.  
  135. #define DELETED     ((char *)1)    /* guarenteed invalid address */
  136. #define START_POWER    (11)    /* power of two: size of new hash table */    /* JF was 6 */
  137. /* JF These next two aren't used any more. */
  138. /* #define START_SIZE    (64)    / * 2 ** START_POWER */
  139. /* #define START_FULL    (32)      / * number of entries before table expands */
  140. #define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED)
  141. /* above TRUE if a symbol is in entry @ ptr */
  142.  
  143. #define STAT_SIZE      (0)    /* number of slots in hash table */
  144. /* the wall does not count here */
  145. /* we expect this is always a power of 2 */
  146. #define STAT_ACCESS    (1)    /* number of hash_ask()s */
  147. #define STAT__READ     (0)    /* reading */
  148. #define STAT__WRITE    (1)    /* writing */
  149. #define STAT_COLLIDE   (3)    /* number of collisions (total) */
  150. /* this may exceed STAT_ACCESS if we have */
  151. /* lots of collisions/access */
  152. #define STAT_USED      (5)    /* slots used right now */
  153. #define STATLENGTH     (6)    /* size of statistics block */
  154. #if STATLENGTH != HASH_STATLENGTH
  155. Panic ! Please make this agree with previous definitions!
  156. #include "stat.h"
  157. #endif
  158.  
  159. /* #define SUSPECT to do runtime checks */
  160. /* #define TEST_ME to be a test jig for hash...() */
  161.  
  162. #ifdef TEST_ME            /* TEST_ME: use smaller hash table */
  163. #undef  START_POWER
  164. #define START_POWER (3)
  165. #undef  START_SIZE
  166. #define START_SIZE  (8)
  167. #undef  START_FULL
  168. #define START_FULL  (4)
  169. #endif
  170.  
  171.  
  172. /*------------------ plan ---------------------------------- i = internal
  173.  
  174. struct hash_control * c;
  175. struct hash_entry   * e;                                                    i
  176. int                   b[z];     buffer for statistics
  177.                       z         size of b
  178. char                * s;        symbol string (address) [ key ]
  179. char                * v;        value string (address)  [datum]
  180. boolean               f;        TRUE if we found s in hash table            i
  181. char                * t;        error string; NULL means OK
  182. int                   a;        access type [0...n)                         i
  183.  
  184. c=hash_new       ()             create new hash_control
  185.  
  186. hash_die         (c)            destroy hash_control (and hash table)
  187.                                 table should be empty.
  188.                                 doesn't check if table is empty.
  189.                                 c has no meaning after this.
  190.  
  191. hash_say         (c,b,z)        report statistics of hash_control.
  192.                                 also report number of available statistics.
  193.  
  194. v=hash_delete    (c,s)          delete symbol, return old value if any.
  195.     ask()                       NULL means no old value.
  196.     f
  197.  
  198. v=hash_replace   (c,s,v)        replace old value of s with v.
  199.     ask()                       NULL means no old value: no table change.
  200.     f
  201.  
  202. t=hash_insert    (c,s,v)        insert (s,v) in c.
  203.     ask()                       return error string.
  204.     f                           it is an error to insert if s is already
  205.                                 in table.
  206.                                 if any error, c is unchanged.
  207.  
  208. t=hash_jam       (c,s,v)        assert that new value of s will be v.       i
  209.     ask()                       it may decide to GROW the table.            i
  210.     f                                                                       i
  211.     grow()                                                                  i
  212. t=hash_grow      (c)            grow the hash table.                        i
  213.     jam()                       will invoke JAM.                            i
  214.  
  215. ?=hash_apply     (c,y)          apply y() to every symbol in c.
  216.     y                           evtries visited in 'unspecified' order.
  217.  
  218. v=hash_find      (c,s)          return value of s, or NULL if s not in c.
  219.     ask()
  220.     f
  221.  
  222. f,e=hash_ask()   (c,s,a)        return slot where s SHOULD live.            i
  223.     code()                      maintain collision stats in c.              i
  224.  
  225. .=hash_code      (c,s)          compute hash-code for s,                    i
  226.                                 from parameters of c.                       i
  227.  
  228. */
  229.  
  230.  
  231. static char hash_found;        /* returned by hash_ask() to stop
  232.                      * extra */
  233. /* testing. hash_ask() wants to return both */
  234. /* a slot and a status. This is the status. */
  235. /* TRUE: found symbol */
  236. /* FALSE: absent: empty or deleted slot */
  237. /* Also returned by hash_jam(). */
  238. /* TRUE: we replaced a value */
  239. /* FALSE: we inserted a value */
  240.  
  241. static struct hash_entry *hash_ask ();
  242. static int hash_code ();
  243. static char *hash_grow ();
  244.  
  245.  
  246. /*
  247.  * h a s h _ n e w ( )
  248.  *
  249.  */
  250. struct hash_control *
  251. hash_new ()            /* create a new hash table */
  252.      /* return handle (address of struct hash) */
  253. {
  254.   register struct hash_control *retval;
  255.   register struct hash_entry *room;    /* points to hash table */
  256.   register struct hash_entry *wall;
  257.   register struct hash_entry *entry;
  258.  
  259.   /* +1 for the wall entry */
  260.   if ((room = (struct hash_entry *) malloc (sizeof (struct hash_entry) * ((1 << START_POWER) + 1))) == 0)
  261.       return NULL;
  262.   if ((retval = (struct hash_control *) malloc (sizeof (struct hash_control))) == 0)
  263.     {
  264.       free (room);
  265.       return NULL;
  266.     }
  267.   bzero (retval->hash_stat, STATLENGTH * sizeof (int));
  268.  
  269.   retval->hash_stat[STAT_SIZE] = 1 << START_POWER;
  270.   retval->hash_mask = (1 << START_POWER) - 1;
  271.   retval->hash_sizelog = START_POWER;
  272.   /* works for 1's compl ok */
  273.   retval->hash_where = room;
  274.   retval->hash_wall =
  275.     wall = room + (1 << START_POWER);
  276.   retval->hash_full = (1 << START_POWER) / 2;
  277.   for (entry = room; entry <= wall; entry++)
  278.     entry->hash_string = NULL;
  279.   return retval;
  280. }
  281.  
  282. /*
  283.  * h a s h _ d i e ( )
  284.  *
  285.  * Table should be empty, but this is not checked. To empty the table, try
  286.  * hash_apply()ing a symbol deleter. Return to free memory both the hash
  287.  * table and it's control block. 'handle' has no meaning after this function.
  288.  * No errors are recoverable.
  289.  */
  290. void
  291. hash_die (handle)
  292.      struct hash_control *handle;
  293. {
  294.   free ((char *) handle->hash_where);
  295.   free ((char *) handle);
  296. }
  297.  
  298.  
  299. /*
  300.  * h a s h _ s a y ( )
  301.  *
  302.  * Return the size of the statistics table, and as many statistics as we can
  303.  * until either (a) we have run out of statistics or (b) caller has run out
  304.  * of buffer. NOTE: hash_say treats all statistics alike. These numbers may
  305.  * change with time, due to insertions, deletions and expansions of the
  306.  * table. The first "statistic" returned is the length of hash_stat[]. Then
  307.  * contents of hash_stat[] are read out (in ascending order) until your
  308.  * buffer or hash_stat[] is exausted.
  309.  */
  310. void
  311. hash_say (handle, buffer, bufsiz)
  312.      register struct hash_control *handle;
  313.      register int buffer[ /* bufsiz */ ];
  314.      register int bufsiz;
  315. {
  316.   register int *nd;        /* limit of statistics block */
  317.   register int *ip;        /* scan statistics */
  318.  
  319.   ip = handle->hash_stat;
  320.   nd = ip + min (bufsiz - 1, STATLENGTH);
  321.   if (bufsiz > 0)
  322.     {                /* trust nothing! bufsiz<=0 is dangerous */
  323.       *buffer++ = STATLENGTH;
  324.       for (; ip < nd; ip++, buffer++)
  325.     {
  326.       *buffer = *ip;
  327.     }
  328.     }
  329. }
  330.  
  331.  
  332. /*
  333.  * h a s h _ d e l e t e ( )
  334.  *
  335.  * Try to delete a symbol from the table. If it was there, return its value (and
  336.  * adjust STAT_USED). Otherwise, return NULL. Anyway, the symbol is not
  337.  * present after this function.
  338.  *
  339.  */
  340. char *                /* NULL if string not in table, else */
  341. /* returns value of deleted symbol */
  342. hash_delete (handle, string)
  343.      register struct hash_control *handle;
  344.      register char *string;
  345. {
  346.   register char *retval;    /* NULL if string not in table */
  347.   register struct hash_entry *entry;    /* NULL or entry of this
  348.                          * symbol */
  349.  
  350.   entry = hash_ask (handle, string, STAT__WRITE);
  351.   if (hash_found)
  352.     {
  353.       retval = entry->hash_value;
  354.       entry->hash_string = DELETED;    /* mark as deleted */
  355.       handle->hash_stat[STAT_USED] -= 1;    /* slots-in-use count */
  356. #ifdef SUSPECT
  357.       if (handle->hash_stat[STAT_USED] < 0)
  358.     {
  359.       error ("hash_delete");
  360.     }
  361. #endif /* def SUSPECT */
  362.     }
  363.   else
  364.     {
  365.       retval = NULL;
  366.     }
  367.   return (retval);
  368. }
  369.  
  370.  
  371. /*
  372.  * h a s h _ r e p l a c e ( )
  373.  *
  374.  * Try to replace the old value of a symbol with a new value. Normally return
  375.  * the old value. Return NULL and don't change the table if the symbol is not
  376.  * already in the table.
  377.  */
  378. char *
  379. hash_replace (handle, string, value)
  380.      register struct hash_control *handle;
  381.      register char *string;
  382.      register char *value;
  383. {
  384.   register struct hash_entry *entry;
  385.   register char *retval;
  386.  
  387.   entry = hash_ask (handle, string, STAT__WRITE);
  388.   if (hash_found)
  389.     {
  390.       retval = entry->hash_value;
  391.       entry->hash_value = value;
  392.     }
  393.   else
  394.     {
  395.       retval = NULL;
  396.     }
  397.   ;
  398.   return (retval);
  399. }
  400.  
  401.  
  402. /*
  403.  * h a s h _ i n s e r t ( )
  404.  *
  405.  * Insert a (symbol-string, value) into the hash table. Return an error string,
  406.  * NULL means OK. It is an 'error' to insert an existing symbol.
  407.  */
  408.  
  409. char *                /* return error string */
  410. hash_insert (handle, string, value)
  411.      register struct hash_control *handle;
  412.      register char *string;
  413.      register VOIDSTAR value;
  414. {
  415.   register struct hash_entry *entry;
  416.   register char *retval;
  417.  
  418.   retval = NULL;
  419.   if (handle->hash_stat[STAT_USED] > handle->hash_full)
  420.     retval = hash_grow (handle);
  421.   if (!retval)
  422.     {
  423.       entry = hash_ask (handle, string, STAT__WRITE);
  424.       if (hash_found)
  425.     retval = "exists";
  426.       else
  427.     {
  428.       entry->hash_value = value;
  429.       entry->hash_string = string;
  430.       handle->hash_stat[STAT_USED] += 1;
  431.     }
  432.     }
  433.   return (retval);
  434. }
  435.  
  436.  
  437. /*
  438.  * h a s h _ j a m ( )
  439.  *
  440.  * Regardless of what was in the symbol table before, after hash_jam() the named
  441.  * symbol has the given value. The symbol is either inserted or (its value
  442.  * is) relpaced. An error message string is returned, NULL means OK.
  443.  *
  444.  * WARNING: this may decide to grow the hashed symbol table. To do this, we call
  445.  * hash_grow(), WHICH WILL recursively CALL US.
  446.  *
  447.  * We report status internally: hash_found is TRUE if we replaced, but false if
  448.  * we inserted.
  449.  */
  450. char *
  451. hash_jam (handle, string, value)
  452.      register struct hash_control *handle;
  453.      register char *string;
  454.      register char *value;
  455. {
  456.   register char *retval;
  457.   register struct hash_entry *entry;
  458.  
  459.   if (handle->hash_stat[STAT_USED] > handle->hash_full)
  460.     retval = hash_grow (handle);
  461.   else
  462.     retval = NULL;
  463.   if (!retval)
  464.     {
  465.       entry = hash_ask (handle, string, STAT__WRITE);
  466.       if (!hash_found)
  467.     {
  468.       entry->hash_string = string;
  469.       handle->hash_stat[STAT_USED] += 1;
  470.     }
  471.       entry->hash_value = value;
  472.     }
  473.   return (retval);
  474. }
  475.  
  476. /*
  477.  * h a s h _ g r o w ( )
  478.  *
  479.  * Grow a new (bigger) hash table from the old one. We choose to double the hash
  480.  * table's size. Return a human-scrutible error string: NULL if OK. Warning!
  481.  * This uses hash_jam(), which had better not recurse back here! Hash_jam()
  482.  * conditionally calls us, but we ALWAYS call hash_jam()! Internal.
  483.  */
  484. static char *
  485. hash_grow (handle)        /* make a hash table grow */
  486.      struct hash_control *handle;
  487. {
  488.   register struct hash_entry *newwall;
  489.   register struct hash_entry *newwhere;
  490.   struct hash_entry *newtrack;
  491.   register struct hash_entry *oldtrack;
  492.   register struct hash_entry *oldwhere;
  493.   register struct hash_entry *oldwall;
  494.   register int temp;
  495.   int newsize;
  496.   char *string;
  497.   char *retval;
  498. #ifdef SUSPECT
  499.   int oldused;
  500. #endif
  501.  
  502.   /*
  503.      * capture info about old hash table
  504.      */
  505.   oldwhere = handle->hash_where;
  506.   oldwall = handle->hash_wall;
  507. #ifdef SUSPECT
  508.   oldused = handle->hash_stat[STAT_USED];
  509. #endif
  510.   /*
  511.      * attempt to get enough room for a hash table twice as big
  512.      */
  513.   temp = handle->hash_stat[STAT_SIZE];
  514.   /* +1 for wall slot */
  515.   if ((newwhere = (struct hash_entry *) malloc ((long) ((temp + temp + 1) * sizeof (struct hash_entry)))) == 0)
  516.       return "no room";
  517.   retval = 0;            /* assume success until proven otherwise */
  518.   /*
  519.          * have enough room: now we do all the work. double the size
  520.          * of everything in handle, note: hash_mask frob works for
  521.          * 1's & for 2's complement machines
  522.          */
  523.   handle->hash_mask = handle->hash_mask + handle->hash_mask + 1;
  524.   handle->hash_stat[STAT_SIZE] <<= 1;
  525.   newsize = handle->hash_stat[STAT_SIZE];
  526.   handle->hash_where = newwhere;
  527.   handle->hash_full <<= 1;
  528.   handle->hash_sizelog += 1;
  529.   handle->hash_stat[STAT_USED] = 0;
  530.   handle->hash_wall =
  531.     newwall = newwhere + newsize;
  532.   /*
  533.          * set all those pesky new slots to vacant.
  534.          */
  535.   for (newtrack = newwhere; newtrack <= newwall; newtrack++)
  536.     newtrack->hash_string = NULL;
  537.   /*
  538.          * we will do a scan of the old table, the hard way, using
  539.          * the new control block to re-insert the data into new hash
  540.          * table.
  541.          */
  542.   handle->hash_stat[STAT_USED] = 0;    /* inserts will bump it
  543.                              * up to correct */
  544.   for (oldtrack = oldwhere; oldtrack < oldwall; oldtrack++)
  545.     {
  546.       if ((string = oldtrack->hash_string) && string != DELETED)
  547.     {
  548.       if ((retval = hash_jam (handle, string, oldtrack->hash_value)))
  549.         break;
  550.     }
  551.     }
  552. #ifdef SUSPECT
  553.   if (!retval && handle->hash_stat[STAT_USED] != oldused)
  554.     return "hash_used";
  555. #endif
  556.   if (!retval)
  557.     {
  558.       /*
  559.              * we have a completely faked up control block.
  560.              * return the old hash table.
  561.              */
  562.       free ((char *) oldwhere);
  563.       /*
  564.              * Here with success. retval is already NULL.
  565.              */
  566.     }
  567.   return (retval);
  568. }
  569.  
  570.  
  571. /*
  572.  * h a s h _ a p p l y ( )
  573.  *
  574.  * Use this to scan each entry in symbol table. For each symbol, this calls
  575.  * (applys) a nominated function supplying the symbol's value (and the
  576.  * symbol's name). The idea is you use this to destroy whatever is associted
  577.  * with any values in the table BEFORE you destroy the table with hash_die.
  578.  * Of course, you can use it for other jobs; whenever you need to visit all
  579.  * extant symbols in the table.
  580.  *
  581.  * We choose to have a call-you-back idea for two reasons: asthetic: it is a
  582.  * neater idea to use apply than an explicit loop sensible: if we ever had to
  583.  * grow the symbol table (due to insertions) then we would lose our place in
  584.  * the table when we re-hashed symbols into the new table in a different
  585.  * order.
  586.  *
  587.  * The order symbols are visited depends entirely on the hashing function.
  588.  * Whenever you insert a (symbol, value) you risk expanding the table. If you
  589.  * do expand the table, then the hashing function WILL change, so you MIGHT
  590.  * get a different order of symbols visited. In other words, if you want the
  591.  * same order of visiting symbols as the last time you used hash_apply() then
  592.  * you better not have done any hash_insert()s or hash_jam()s since the last
  593.  * time you used hash_apply().
  594.  *
  595.  * In future we may use the value returned by your nominated function. One idea
  596.  * is to abort the scan if, after applying the function to a certain node,
  597.  * the function returns a certain code. To be safe, please make your
  598.  * functions of type char *. If you always return NULL, then the scan will
  599.  * complete, visiting every symbol in the table exactly once. ALL OTHER
  600.  * RETURNED VALUES have no meaning yet! Caveat Actor!
  601.  *
  602.  * The function you supply should be of the form: char * myfunct(string,value)
  603.  * char * string;        |* the symbol's name *| char * value;         |* the
  604.  * symbol's value *| { |* ... *| return(NULL); }
  605.  *
  606.  * The returned value of hash_apply() is (char*)NULL. In future it may return
  607.  * other values. NULL means "completed scan OK". Other values have no meaning
  608.  * yet. (The function has no graceful failures.)
  609.  */
  610. char *
  611. hash_apply (handle, function)
  612.      struct hash_control *handle;
  613.      char *(*function) ();
  614. {
  615.   register struct hash_entry *entry;
  616.   register struct hash_entry *wall;
  617.  
  618.   wall = handle->hash_wall;
  619.   for (entry = handle->hash_where; entry < wall; entry++)
  620.     {
  621.       if (islive (entry))    /* silly code: tests entry->string
  622.                      * twice! */
  623.     (*function) (entry->hash_string, entry->hash_value);
  624.     }
  625.   return (NULL);
  626. }
  627.  
  628.  
  629. /*
  630.  * h a s h _ f i n d ( )
  631.  *
  632.  * Given symbol string, find value (if any). Return found value or NULL.
  633.  */
  634. VOIDSTAR
  635. hash_find (handle, string)    /* return char* or NULL */
  636.      struct hash_control *handle;
  637.      char *string;
  638. {
  639.   register struct hash_entry *entry;
  640.  
  641.   entry = hash_ask (handle, string, STAT__READ);
  642.   return hash_found ? entry->hash_value : NULL;
  643. }
  644.  
  645.  
  646. /*
  647.  * h a s h _ a s k ( )
  648.  *
  649.  * Searches for given symbol string. Return the slot where it OUGHT to live. It
  650.  * may be there. Return hash_found: TRUE only if symbol is in that slot.
  651.  * Access argument is to help keep statistics in control block. Internal.
  652.  */
  653. static struct hash_entry *    /* string slot, may be empty or deleted */
  654. hash_ask (handle, string, access)
  655.      struct hash_control *handle;
  656.      char *string;
  657.      int access;        /* access type */
  658. {
  659.   register char *string1;    /* JF avoid strcmp calls */
  660.   register char *s;
  661.   register int c;
  662.   register struct hash_entry *slot;
  663.   register int collision;    /* count collisions */
  664.  
  665.   slot = handle->hash_where + hash_code (handle, string);    /* start looking here */
  666.   handle->hash_stat[STAT_ACCESS + access] += 1;
  667.   collision = 0;
  668.   hash_found = FALSE;
  669.   while ((s = slot->hash_string) && s != DELETED)
  670.     {
  671.       for (string1 = string;;)
  672.     {
  673.       if (!(c = *s++))
  674.         {
  675.           if (!*string1)
  676.         hash_found = TRUE;
  677.           break;
  678.         }
  679.       if (*string1++ != c)
  680.         break;
  681.     }
  682.       if (hash_found)
  683.     break;
  684.       collision++;
  685.       slot++;
  686.     }
  687.   /*
  688.      * slot:                                                      return:
  689.      * in use:     we found string                           slot at
  690.      * empty: at wall:        we fell off: wrap round   ???? in table:
  691.      * dig here                  slot at DELETED: dig here
  692.      * slot
  693.      */
  694.   if (slot == handle->hash_wall)
  695.     {
  696.       slot = handle->hash_where;/* now look again */
  697.       while ((s = slot->hash_string) && s != DELETED)
  698.     {
  699.       for (string1 = string; *s; string1++, s++)
  700.         {
  701.           if (*string1 != *s)
  702.         break;
  703.         }
  704.       if (*s == *string1)
  705.         {
  706.           hash_found = TRUE;
  707.           break;
  708.         }
  709.       collision++;
  710.       slot++;
  711.     }
  712.       /*
  713.          * slot:
  714.          * return: in use: we found it
  715.          * slot empty:  wall:         ERROR IMPOSSIBLE
  716.          * !!!! in table:     dig here                     slot
  717.          * DELETED:dig here                                   slot
  718.          */
  719.     }
  720.   /*
  721.      * fprintf(stderr,"hash_ask(%s)->%d(%d)\n",string,hash_code(handle,str
  722.      * ing),collision);
  723.      */
  724.   handle->hash_stat[STAT_COLLIDE + access] += collision;
  725.   return (slot);        /* also return hash_found */
  726. }
  727.  
  728.  
  729. /*
  730.  * h a s h _ c o d e
  731.  *
  732.  * Does hashing of symbol string to hash number. Internal.
  733.  */
  734. static int
  735. hash_code (handle, string)
  736.      struct hash_control *handle;
  737.      register char *string;
  738. {
  739.   register long int h;        /* hash code built here */
  740.   register long int c;        /* each character lands here */
  741.   register int n;        /* Amount to shift h by */
  742.  
  743.   n = (handle->hash_sizelog - 3);
  744.   h = 0;
  745.   while (c = *string++)
  746.     {
  747.       h += c;
  748.       h = (h << 3) + (h >> n) + c;
  749.     }
  750.   return (h & handle->hash_mask);
  751. }
  752.  
  753.  
  754. /*
  755.  * Here is a test program to exercise above.
  756.  */
  757. #ifdef TEST_ME
  758.  
  759. #define TABLES (6)        /* number of hash tables to maintain */
  760. /* (at once) in any testing */
  761. #define STATBUFSIZE (12)    /* we can have 12 statistics */
  762.  
  763. int statbuf[STATBUFSIZE];    /* display statistics here */
  764. char answer[100];        /* human farts here */
  765. char *hashtable[TABLES];    /* we test many hash tables at once */
  766. char *h;            /* points to curent hash_control */
  767. char **pp;
  768. char *p;
  769. char *name;
  770. char *value;
  771. int size;
  772. int used;
  773. char command;
  774. int number;            /* number 0:TABLES-1 of current hashed */
  775. /* symbol table */
  776.  
  777. int
  778. main ()
  779. {
  780.   char (*applicatee ());
  781.   VOIDSTAR hash_find ();
  782.   char *destroy ();
  783.   char *what ();
  784.   struct hash_control *hash_new ();
  785.   char *hash_replace ();
  786.   int *ip;
  787.  
  788.   number = 0;
  789.   h = 0;
  790.   printf ("type h <RETURN> for help\n");
  791.   for (;;)
  792.     {
  793.       printf ("hash_test command: ");
  794.       gets (answer);
  795.       command = answer[0];
  796.       if (isupper (command))
  797.     command = tolower (command);    /* ecch! */
  798.       switch (command)
  799.     {
  800.     case '#':
  801.       printf ("old hash table #=%d.\n", number);
  802.       whattable ();
  803.       break;
  804.     case '?':
  805.       for (pp = hashtable; pp < hashtable + TABLES; pp++)
  806.         {
  807.           printf ("address of hash table #%d control block is %xx\n"
  808.               ,pp - hashtable, *pp);
  809.         }
  810.       break;
  811.     case 'a':
  812.       hash_apply (h, applicatee);
  813.       break;
  814.     case 'd':
  815.       hash_apply (h, destroy);
  816.       hash_die (h);
  817.       break;
  818.     case 'f':
  819.       p = hash_find (h, name = what ("symbol"));
  820.       printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
  821.       break;
  822.     case 'h':
  823.       printf ("# show old, select new default hash table number\n");
  824.       printf ("? display all hashtable control block addresses\n");
  825.       printf ("a apply a simple display-er to each symbol in table\n");
  826.       printf ("d die: destroy hashtable\n");
  827.       printf ("f find value of nominated symbol\n");
  828.       printf ("h this help\n");
  829.       printf ("i insert value into symbol\n");
  830.       printf ("j jam value into symbol\n");
  831.       printf ("n new hashtable\n");
  832.       printf ("r replace a value with another\n");
  833.       printf ("s say what %% of table is used\n");
  834.       printf ("q exit this program\n");
  835.       printf ("x delete a symbol from table, report its value\n");
  836.       break;
  837.     case 'i':
  838.       p = hash_insert (h, name = what ("symbol"), value = what ("value"));
  839.       if (*p)
  840.         {
  841.           printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
  842.         }
  843.       break;
  844.     case 'j':
  845.       p = hash_jam (h, name = what ("symbol"), value = what ("value"));
  846.       if (*p)
  847.         {
  848.           printf ("symbol=\"%s\"  value=\"%s\"  error=%s\n", name, value, p);
  849.         }
  850.       break;
  851.     case 'n':
  852.       h = hashtable[number] = (char *) hash_new ();
  853.       break;
  854.     case 'q':
  855.       exit (0);
  856.     case 'r':
  857.       p = hash_replace (h, name = what ("symbol"), value = what ("value"));
  858.       printf ("old value was \"%s\"\n", p ? p : "{}");
  859.       break;
  860.     case 's':
  861.       hash_say (h, statbuf, STATBUFSIZE);
  862.       for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
  863.         {
  864.           printf ("%d ", *ip);
  865.         }
  866.       printf ("\n");
  867.       break;
  868.     case 'x':
  869.       p = hash_delete (h, name = what ("symbol"));
  870.       printf ("old value was \"%s\"\n", p ? p : "{}");
  871.       break;
  872.     default:
  873.       printf ("I can't understand command \"%c\"\n", command);
  874.       break;
  875.     }
  876.     }
  877. }
  878.  
  879. char *
  880. what (description)
  881.      char *description;
  882. {
  883.   char *retval;
  884.  
  885.   printf ("   %s : ", description);
  886.   gets (answer);
  887.   /* will one day clean up answer here */
  888.   retval = malloc (strlen (answer) + 1);
  889.   if (!retval)
  890.     {
  891.       error ("room");
  892.     }
  893.   (void) strcpy (retval, answer);
  894.   return (retval);
  895. }
  896.  
  897. char *
  898. destroy (string, value)
  899.      char *string;
  900.      char *value;
  901. {
  902.   free (string);
  903.   free (value);
  904.   return (NULL);
  905. }
  906.  
  907.  
  908. char *
  909. applicatee (string, value)
  910.      char *string;
  911.      char *value;
  912. {
  913.   printf ("%.20s-%.20s\n", string, value);
  914.   return (NULL);
  915. }
  916.  
  917. void
  918. whattable ()            /* determine number: what hash table to use */
  919. {
  920.  
  921.   for (;;)
  922.     {
  923.       printf ("   what hash table (%d:%d) ?  ", 0, TABLES - 1);
  924.       gets (answer);
  925.       sscanf (answer, "%d", &number);
  926.       if (number >= 0 && number < TABLES)
  927.     {
  928.       h = hashtable[number];
  929.       if (!h)
  930.         {
  931.           printf ("warning: current hash-table-#%d. has no hash-control\n", number);
  932.         }
  933.       return;
  934.     }
  935.       else
  936.     {
  937.       printf ("invalid hash table number: %d\n", number);
  938.     }
  939.     }
  940. }
  941.  
  942.  
  943.  
  944. #endif /* #ifdef TEST_ME */
  945.  
  946. /* end: hash.c */
  947.