Return to hash.c CVS log

Up to [Apple XNU] / GNUtools / cctools / as

Annotation of GNUtools/cctools/as/hash.c, revision 1.1

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

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.