gas/hash.c

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