hash.c

早期freebsd实现

/* hash.c - hash table lookup strings -
   Copyright (C) 1987 Free Software Foundation, Inc.

This file is part of GAS, the GNU Assembler.

GAS is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 1, or (at your option)
any later version.

GAS is distributed in the hope that it will be useful,
but WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
GNU General Public License for more details.

You should have received a copy of the GNU General Public License
along with GAS; see the file COPYING.  If not, write to
the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */

/*
 * BUGS, GRIPES, APOLOGIA etc.
 *
 * A typical user doesn't need ALL this: I intend to make a library out
 * of it one day - Dean Elsner.
 * Also, I want to change the definition of a symbol to (address,length)
 * so I can put arbitrary binary in the names stored. [see hsh.c for that]
 *
 * This slime is common coupled inside the module. Com-coupling (and other
 * vandalism) was done to speed running time. The interfaces at the
 * module's edges are adequately clean.
 *
 * There is no way to (a) run a test script through this heap and (b)
 * compare results with previous scripts, to see if we have broken any
 * code. Use GNU (f)utilities to do this. A few commands assist test.
 * The testing is awkward: it tries to be both batch & interactive.
 * For now, interactive rules!
 */

/*
 *  The idea is to implement a symbol table. A test jig is here.
 *  Symbols are arbitrary strings; they can't contain '\0'.
 *	[See hsh.c for a more general symbol flavour.]
 *  Each symbol is associated with a char*, which can point to anything
 *  you want, allowing an arbitrary property list for each symbol.
 *
 *  The basic operations are:
 *
 *    new                     creates symbol table, returns handle
 *    find (symbol)           returns char*
 *    insert (symbol,char*)   error if symbol already in table
 *    delete (symbol)         returns char* if symbol was in table
 *    apply                   so you can delete all symbols before die()
 *    die                     destroy symbol table (free up memory)
 *
 *  Supplementary functions include:
 *
 *    say                     how big? what % full?
 *    replace (symbol,newval) report previous value
 *    jam (symbol,value)      assert symbol:=value
 *
 *  You, the caller, have control over errors: this just reports them.
 *
 *  This package requires malloc(), free().
 *  Malloc(size) returns NULL or address of char[size].
 *  Free(address) frees same.
 */

/*
 *  The code and its structures are re-enterent.
 *  Before you do anything else, you must call hash_new() which will
 *  return the address of a hash-table-control-block (or NULL if there
 *  is not enough memory). You then use this address as a handle of the
 *  symbol table by passing it to all the other hash_...() functions.
 *  The only approved way to recover the memory used by the symbol table
 *  is to call hash_die() with the handle of the symbol table.
 *
 *  Before you call hash_die() you normally delete anything pointed to
 *  by individual symbols. After hash_die() you can't use that symbol
 *  table again.
 *
 *  The char* you associate with a symbol may not be NULL (0) because
 *  NULL is returned whenever a symbol is not in the table. Any other
 *  value is OK, except DELETED, #defined below.
 *
 *  When you supply a symbol string for insertion, YOU MUST PRESERVE THE
 *  STRING until that symbol is deleted from the table. The reason is that
 *  only the address you supply, NOT the symbol string itself, is stored
 *  in the symbol table.
 *
 *  You may delete and add symbols arbitrarily.
 *  Any or all symbols may have the same 'value' (char *). In fact, these
 *  routines don't do anything with your symbol values.
 *
 *  You have no right to know where the symbol:char* mapping is stored,
 *  because it moves around in memory; also because we may change how it
 *  works and we don't want to break your code do we? However the handle
 *  (address of struct hash_control) is never changed in
 *  the life of the symbol table.
 *
 *  What you CAN find out about a symbol table is:
 *    how many slots are in the hash table?
 *    how many slots are filled with symbols?
 *    (total hashes,collisions) for (reads,writes) (*)
 *  All of the above values vary in time.
 *  (*) some of these numbers will not be meaningful if we change the
 *  internals.
 */

/*
 *  I N T E R N A L
 *
 *  Hash table is an array of hash_entries; each entry is a pointer to a
 *  a string and a user-supplied value 1 char* wide.
 *
 *  The array always has 2 ** n elements, n>0, n integer.
 *  There is also a 'wall' entry after the array, which is always empty
 *  and acts as a sentinel to stop running off the end of the array.
 *  When the array gets too full, we create a new array twice as large
 *  and re-hash the symbols into the new array, then forget the old array.
 *  (Of course, we copy the values into the new array before we junk the
 *  old array!)
 *
 */

#include <stdio.h>
#define TRUE           (1)
#define FALSE          (0)
#include <ctype.h>
#define min(a, b)	((a) < (b) ? (a) : (b))

#include "hash.h"
char *xmalloc();

#define DELETED     ((char *)1)	/* guarenteed invalid address */
#define START_POWER    (11)	/* power of two: size of new hash table *//* JF was 6 */
/* JF These next two aren't used any more. */
/* #define START_SIZE    (64)	/ * 2 ** START_POWER */
/* #define START_FULL    (32)      / * number of entries before table expands */
#define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED)
				/* above TRUE if a symbol is in entry @ ptr */

#define STAT_SIZE      (0)      /* number of slots in hash table */
				/* the wall does not count here */
				/* we expect this is always a power of 2 */
#define STAT_ACCESS    (1)	/* number of hash_ask()s */
#define STAT__READ     (0)      /* reading */
#define STAT__WRITE    (1)      /* writing */
#define STAT_COLLIDE   (3)	/* number of collisions (total) */
				/* this may exceed STAT_ACCESS if we have */
				/* lots of collisions/access */
#define STAT_USED      (5)	/* slots used right now */
#define STATLENGTH     (6)	/* size of statistics block */
#if STATLENGTH != HASH_STATLENGTH
Panic! Please make #include "stat.h" agree with previous definitions!
#endif

/* #define SUSPECT to do runtime checks */
/* #define TEST to be a test jig for hash...() */

#ifdef TEST			/* TEST: use smaller hash table */
#undef  START_POWER
#define START_POWER (3)
#undef  START_SIZE
#define START_SIZE  (8)
#undef  START_FULL
#define START_FULL  (4)
#endif

/*------------------ plan ---------------------------------- i = internal

struct hash_control * c;
struct hash_entry   * e;                                                    i
int                   b[z];     buffer for statistics
                      z         size of b
char                * s;        symbol string (address) [ key ]
char                * v;        value string (address)  [datum]
boolean               f;        TRUE if we found s in hash table            i
char                * t;        error string; "" means OK
int                   a;        access type [0...n)                         i

c=hash_new       ()             create new hash_control

hash_die         (c)            destroy hash_control (and hash table)
                                table should be empty.
                                doesn't check if table is empty.
                                c has no meaning after this.

hash_say         (c,b,z)        report statistics of hash_control.
                                also report number of available statistics.

v=hash_delete    (c,s)          delete symbol, return old value if any.
    ask()                       NULL means no old value.
    f

v=hash_replace   (c,s,v)        replace old value of s with v.
    ask()                       NULL means no old value: no table change.
    f

t=hash_insert    (c,s,v)        insert (s,v) in c.
    ask()                       return error string.
    f                           it is an error to insert if s is already
                                in table.
                                if any error, c is unchanged.

t=hash_jam       (c,s,v)        assert that new value of s will be v.       i
    ask()                       it may decide to GROW the table.            i
    f                                                                       i
    grow()                                                                  i
t=hash_grow      (c)            grow the hash table.                        i
    jam()                       will invoke JAM.                            i

?=hash_apply     (c,y)          apply y() to every symbol in c.
    y                           evtries visited in 'unspecified' order.

v=hash_find      (c,s)          return value of s, or NULL if s not in c.
    ask()
    f

f,e=hash_ask()   (c,s,a)        return slot where s SHOULD live.            i
    code()                      maintain collision stats in c.              i

.=hash_code      (c,s)          compute hash-code for s,                    i
                                from parameters of c.                       i

*/

static char hash_found;		/* returned by hash_ask() to stop extra */
				/* testing. hash_ask() wants to return both */
				/* a slot and a status. This is the status. */
				/* TRUE: found symbol */
				/* FALSE: absent: empty or deleted slot */
				/* Also returned by hash_jam(). */
				/* TRUE: we replaced a value */
				/* FALSE: we inserted a value */

static struct hash_entry * hash_ask();
static int hash_code ();
static char * hash_grow();

/*
 *             h a s h _ n e w ( )
 *
 */
struct hash_control *
hash_new()			/* create a new hash table */
				/* return NULL if failed */
				/* return handle (address of struct hash) */
{
  register struct hash_control * retval;
  register struct hash_entry *   room;	/* points to hash table */
  register struct hash_entry *   wall;
  register struct hash_entry *   entry;
  char *                malloc();
  register int *                 ip;	/* scan stats block of struct hash_control */
  register int *                 nd;	/* limit of stats block */

  if ( room = (struct hash_entry *) malloc( sizeof(struct hash_entry)*((1<<START_POWER) + 1) ) )
				/* +1 for the wall entry */
    {
      if ( retval = (struct hash_control *) malloc(sizeof(struct hash_control)) )
	{
	  nd = retval->hash_stat + STATLENGTH;
	  for (ip=retval->hash_stat; ip<nd; ip++)
	    {
	      *ip = 0;
	    }

	  retval -> hash_stat[STAT_SIZE]  = 1<<START_POWER;
	  retval -> hash_mask             = (1<<START_POWER) - 1;
	  retval -> hash_sizelog	  = START_POWER;
				/* works for 1's compl ok */
	  retval -> hash_where            = room;
	  retval -> hash_wall             =
	    wall                          = room + (1<<START_POWER);
	  retval -> hash_full             = (1<<START_POWER)/2;
	  for (entry=room; entry<=wall; entry++)
	    {
	      entry->hash_string = NULL;
	    }
	}
    }
  else
    {
      retval = NULL;		/* no room for table: fake a failure */
    }
  return(retval);		/* return NULL or set-up structs */
}

/*
 *           h a s h _ d i e ( )
 *
 * Table should be empty, but this is not checked.
 * To empty the table, try hash_apply()ing a symbol deleter.
 * Return to free memory both the hash table and it's control
 * block.
 * 'handle' has no meaning after this function.
 * No errors are recoverable.
 */
void
hash_die(handle)
     struct hash_control * handle;
{
  free((char *)handle->hash_where);
  free((char *)handle);
}

/*
 *           h a s h _ s a y ( )
 *
 * Return the size of the statistics table, and as many statistics as
 * we can until either (a) we have run out of statistics or (b) caller
 * has run out of buffer.
 * NOTE: hash_say treats all statistics alike.
 * These numbers may change with time, due to insertions, deletions
 * and expansions of the table.
 * The first "statistic" returned is the length of hash_stat[].
 * Then contents of hash_stat[] are read out (in ascending order)
 * until your buffer or hash_stat[] is exausted.
 */
void
hash_say(handle,buffer,bufsiz)
     register struct hash_control * handle;
     register int                   buffer[/*bufsiz*/];
     register int                   bufsiz;
{
  register int * nd;			/* limit of statistics block */
  register int * ip;			/* scan statistics */

  ip = handle -> hash_stat;
  nd = ip + min(bufsiz-1,STATLENGTH);
  if (bufsiz>0)			/* trust nothing! bufsiz<=0 is dangerous */
    {
      *buffer++ = STATLENGTH;
      for (; ip<nd; ip++,buffer++)
	{
	  *buffer = *ip;
	}
    }
}

/*
 *           h a s h _ d e l e t e ( )
 *
 * Try to delete a symbol from the table.
 * If it was there, return its value (and adjust STAT_USED).
 * Otherwise, return NULL.
 * Anyway, the symbol is not present after this function.
 *
 */
char *				/* NULL if string not in table, else */
				/* returns value of deleted symbol */
hash_delete(handle,string)
     register struct hash_control * handle;
     register char *                string;
{
  register char *                   retval; /* NULL if string not in table */
  register struct hash_entry *      entry; /* NULL or entry of this symbol */

  entry = hash_ask(handle,string,STAT__WRITE);
  if (hash_found)
    {
	  retval = entry -> hash_value;
	  entry -> hash_string = DELETED; /* mark as deleted */
	  handle -> hash_stat[STAT_USED] -= 1; /* slots-in-use count */
#ifdef SUSPECT
	  if (handle->hash_stat[STAT_USED]<0)
	    {
	      error("hash_delete");
	    }
#endif /* def SUSPECT */
    }
  else
    {
      retval = NULL;
    }
  return(retval);
}

/*
 *                   h a s h _ r e p l a c e ( )
 *
 * Try to replace the old value of a symbol with a new value.
 * Normally return the old value.
 * Return NULL and don't change the table if the symbol is not already
 * in the table.
 */
char *
hash_replace(handle,string,value)
     register struct hash_control * handle;
     register char *                string;
     register char *                value;
{
  register struct hash_entry *      entry;
  register char *                   retval;

  entry = hash_ask(handle,string,STAT__WRITE);
  if (hash_found)
    {
      retval = entry -> hash_value;
      entry -> hash_value = value;
    }
  else
    {
      retval = NULL;
    }
  ;
  return (retval);
}

/*
 *                   h a s h _ i n s e r t ( )
 *
 * Insert a (symbol-string, value) into the hash table.
 * Return an error string, "" means OK.
 * It is an 'error' to insert an existing symbol.
 */

char *				/* return error string */
hash_insert(handle,string,value)
     register struct hash_control * handle;
     register char *                string;
     register char *                value;
{
  register struct hash_entry * entry;
  register char *              retval;

  retval = "";
  if (handle->hash_stat[STAT_USED] > handle->hash_full)
    {
      retval = hash_grow(handle);
    }
  if ( ! * retval)
    {
      entry = hash_ask(handle,string,STAT__WRITE);
      if (hash_found)
	{
	  retval = "exists";
	}
      else
	{
	  entry -> hash_value  = value;
	  entry -> hash_string = string;
	  handle-> hash_stat[STAT_USED]  += 1;
	}
    }
  return(retval);
}

/*
 *               h a s h _ j a m ( )
 *
 * Regardless of what was in the symbol table before, after hash_jam()
 * the named symbol has the given value. The symbol is either inserted or
 * (its value is) relpaced.
 * An error message string is returned, "" means OK.
 *
 * WARNING: this may decide to grow the hashed symbol table.
 * To do this, we call hash_grow(), WHICH WILL recursively CALL US.
 *
 * We report status internally: hash_found is TRUE if we replaced, but
 * false if we inserted.
 */
char *
hash_jam(handle,string,value)
     register struct hash_control * handle;
     register char *                string;
     register char *                value;
{
  register char *                   retval;
  register struct hash_entry *      entry;

  retval = "";
  if (handle->hash_stat[STAT_USED] > handle->hash_full)
    {
      retval = hash_grow(handle);
    }
  if (! * retval)
    {
      entry = hash_ask(handle,string,STAT__WRITE);
      if ( ! hash_found)
	{
	  entry -> hash_string = string;
	  handle->hash_stat[STAT_USED] += 1;
	}
      entry -> hash_value = value;
    }
  return(retval);
}

/*
 *               h a s h _ g r o w ( )