gnu/usr.bin/as/hash.c

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