aboutsummaryrefslogtreecommitdiff
path: root/gas/hash.c
diff options
context:
space:
mode:
Diffstat (limited to 'gas/hash.c')
-rw-r--r--gas/hash.c1028
1 files changed, 1028 insertions, 0 deletions
diff --git a/gas/hash.c b/gas/hash.c
new file mode 100644
index 0000000..dccd660
--- /dev/null
+++ b/gas/hash.c
@@ -0,0 +1,1028 @@
+/* hash.c - hash table lookup strings -
+ Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 1998
+ 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 2, 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, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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. 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>
+
+#ifndef FALSE
+#define FALSE (0)
+#define TRUE (!FALSE)
+#endif /* no FALSE yet */
+
+#include <ctype.h>
+#define min(a, b) ((a) < (b) ? (a) : (b))
+
+#include "as.h"
+
+#define error as_fatal
+
+static char _deleted_[1];
+#define DELETED ((PTR)_deleted_) /* guarenteed unique address */
+#define START_POWER (10) /* power of two: size of new hash table */
+
+/* TRUE if a symbol is in entry @ ptr. */
+#define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED)
+
+enum stat_enum {
+ /* Number of slots in hash table. The wall does not count here.
+ We expect this is always a power of 2. */
+ STAT_SIZE = 0,
+ /* Number of hash_ask calls. */
+ STAT_ACCESS,
+ STAT_ACCESS_w,
+ /* Number of collisions (total). This may exceed STAT_ACCESS if we
+ have lots of collisions/access. */
+ STAT_COLLIDE,
+ STAT_COLLIDE_w,
+ /* Slots used right now. */
+ STAT_USED,
+ /* How many string compares? */
+ STAT_STRCMP,
+ STAT_STRCMP_w,
+ /* Size of statistics block... this must be last. */
+ STATLENGTH
+};
+#define STAT__READ (0) /* reading */
+#define STAT__WRITE (1) /* writing */
+
+/* When we grow a hash table, by what power of two do we increase it? */
+#define GROW_FACTOR 1
+/* When should we grow it? */
+#define FULL_VALUE(N) ((N) / 2)
+
+/* #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
+
+struct hash_entry
+{
+ const char *hash_string; /* points to where the symbol string is */
+ /* NULL means slot is not used */
+ /* DELETED means slot was deleted */
+ PTR hash_value; /* user's datum, associated with symbol */
+ unsigned long h;
+};
+
+struct hash_control {
+ struct hash_entry *hash_where;/* address of hash table */
+ int hash_sizelog; /* Log of ( hash_mask + 1 ) */
+ int hash_mask; /* masks a hash into index into table */
+ int hash_full; /* when hash_stat[STAT_USED] exceeds this, */
+ /* grow table */
+ struct hash_entry *hash_wall; /* point just after last (usable) entry */
+ /* here we have some statistics */
+ int hash_stat[STATLENGTH]; /* lies & statistics */
+};
+
+/*------------------ 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; 0 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
+
+ */
+
+/* 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 char hash_found;
+
+static struct hash_entry *hash_ask PARAMS ((struct hash_control *,
+ const char *, int));
+static int hash_code PARAMS ((struct hash_control *, const char *));
+static const char *hash_grow PARAMS ((struct hash_control *));
+
+/* Create a new hash table. Return NULL if failed; otherwise return handle
+ (address of struct hash). */
+struct hash_control *
+hash_new ()
+{
+ struct hash_control *retval;
+ struct hash_entry *room; /* points to hash table */
+ struct hash_entry *wall;
+ struct hash_entry *entry;
+ int *ip; /* scan stats block of struct hash_control */
+ int *nd; /* limit of stats block */
+
+ room = (struct hash_entry *) xmalloc (sizeof (struct hash_entry)
+ /* +1 for the wall entry */
+ * ((1 << START_POWER) + 1));
+ retval = (struct hash_control *) xmalloc (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 = FULL_VALUE (1 << START_POWER);
+ for (entry = room; entry <= wall; entry++)
+ entry->hash_string = NULL;
+ return retval;
+}
+
+/*
+ * 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);
+}
+
+#ifdef TEST
+/*
+ * 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.
+ */
+static void
+hash_say (handle, buffer, bufsiz)
+ struct hash_control *handle;
+ int buffer[ /*bufsiz*/ ];
+ int bufsiz;
+{
+ int *nd; /* limit of statistics block */
+ 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;
+ }
+ }
+}
+#endif
+
+/*
+ * 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.
+ *
+ */
+PTR /* NULL if string not in table, else */
+/* returns value of deleted symbol */
+hash_delete (handle, string)
+ struct hash_control *handle;
+ const char *string;
+{
+ PTR retval;
+ struct hash_entry *entry;
+
+ entry = hash_ask (handle, string, STAT__WRITE);
+ if (hash_found)
+ {
+ retval = entry->hash_value;
+ entry->hash_string = DELETED;
+ handle->hash_stat[STAT_USED] -= 1;
+#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.
+ */
+PTR
+hash_replace (handle, string, value)
+ struct hash_control *handle;
+ const char *string;
+ PTR value;
+{
+ struct hash_entry *entry;
+ 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, 0 means OK.
+ * It is an 'error' to insert an existing symbol.
+ */
+
+const char * /* return error string */
+hash_insert (handle, string, value)
+ struct hash_control *handle;
+ const char *string;
+ PTR value;
+{
+ struct hash_entry *entry;
+ const char *retval;
+
+ retval = 0;
+ 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) replaced.
+ * An error message string is returned, 0 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.
+ */
+const char *
+hash_jam (handle, string, value)
+ struct hash_control *handle;
+ const char *string;
+ PTR value;
+{
+ const char *retval;
+ struct hash_entry *entry;
+
+ retval = 0;
+ 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 ( )
+ *
+ * Grow a new (bigger) hash table from the old one.
+ * We choose to double the hash table's size.
+ * Return a human-scrutible error string: 0 if OK.
+ * Warning! This uses hash_jam(), which had better not recurse
+ * back here! Hash_jam() conditionally calls us, but we ALWAYS
+ * call hash_jam()!
+ * Internal.
+ */
+static const char *
+hash_grow (handle) /* make a hash table grow */
+ struct hash_control *handle;
+{
+ struct hash_entry *newwall;
+ struct hash_entry *newwhere;
+ struct hash_entry *newtrack;
+ struct hash_entry *oldtrack;
+ struct hash_entry *oldwhere;
+ struct hash_entry *oldwall;
+ int temp;
+ int newsize;
+ const char *string;
+ const char *retval;
+#ifdef SUSPECT
+ int oldused;
+#endif
+
+ /*
+ * capture info about old hash table
+ */
+ oldwhere = handle->hash_where;
+ oldwall = handle->hash_wall;
+#ifdef SUSPECT
+ oldused = handle->hash_stat[STAT_USED];
+#endif
+ /*
+ * attempt to get enough room for a hash table twice as big
+ */
+ temp = handle->hash_stat[STAT_SIZE];
+ newwhere = ((struct hash_entry *)
+ xmalloc ((unsigned long) ((temp << (GROW_FACTOR + 1))
+ /* +1 for wall slot */
+ * sizeof (struct hash_entry))));
+ if (newwhere == NULL)
+ return "no_room";
+
+ /*
+ * have enough room: now we do all the work.
+ * double the size of everything in handle.
+ */
+ handle->hash_mask = ((handle->hash_mask + 1) << GROW_FACTOR) - 1;
+ handle->hash_stat[STAT_SIZE] <<= GROW_FACTOR;
+ newsize = handle->hash_stat[STAT_SIZE];
+ handle->hash_where = newwhere;
+ handle->hash_full <<= GROW_FACTOR;
+ handle->hash_sizelog += GROW_FACTOR;
+ handle->hash_wall = newwall = newwhere + newsize;
+ /* Set all those pesky new slots to vacant. */
+ for (newtrack = newwhere; newtrack <= newwall; newtrack++)
+ newtrack->hash_string = NULL;
+ /* We will do a scan of the old table, the hard way, using the
+ * new control block to re-insert the data into new hash table. */
+ handle->hash_stat[STAT_USED] = 0;
+ for (oldtrack = oldwhere; oldtrack < oldwall; oldtrack++)
+ if (((string = oldtrack->hash_string) != NULL) && string != DELETED)
+ if ((retval = hash_jam (handle, string, oldtrack->hash_value)))
+ return retval;
+
+#ifdef SUSPECT
+ if (handle->hash_stat[STAT_USED] != oldused)
+ return "hash_used";
+#endif
+
+ /* We have a completely faked up control block.
+ Return the old hash table. */
+ free ((char *) oldwhere);
+
+ return 0;
+}
+
+#ifdef TEST
+/*
+ * h a s h _ a p p l y ( )
+ *
+ * Use this to scan each entry in symbol table.
+ * For each symbol, this calls (applys) a nominated function supplying the
+ * symbol's value (and the symbol's name).
+ * The idea is you use this to destroy whatever is associted with
+ * any values in the table BEFORE you destroy the table with hash_die.
+ * Of course, you can use it for other jobs; whenever you need to
+ * visit all extant symbols in the table.
+ *
+ * We choose to have a call-you-back idea for two reasons:
+ * asthetic: it is a neater idea to use apply than an explicit loop
+ * sensible: if we ever had to grow the symbol table (due to insertions)
+ * then we would lose our place in the table when we re-hashed
+ * symbols into the new table in a different order.
+ *
+ * The order symbols are visited depends entirely on the hashing function.
+ * Whenever you insert a (symbol, value) you risk expanding the table. If
+ * you do expand the table, then the hashing function WILL change, so you
+ * MIGHT get a different order of symbols visited. In other words, if you
+ * want the same order of visiting symbols as the last time you used
+ * hash_apply() then you better not have done any hash_insert()s or
+ * hash_jam()s since the last time you used hash_apply().
+ *
+ * In future we may use the value returned by your nominated function.
+ * One idea is to abort the scan if, after applying the function to a
+ * certain node, the function returns a certain code.
+ *
+ * The function you supply should be of the form:
+ * void myfunct(string,value)
+ * char * string; |* the symbol's name *|
+ * char * value; |* the symbol's value *|
+ * {
+ * |* ... *|
+ * }
+ *
+ */
+void
+hash_apply (handle, function)
+ struct hash_control *handle;
+ void (*function) ();
+{
+ struct hash_entry *entry;
+ struct hash_entry *wall;
+
+ wall = handle->hash_wall;
+ for (entry = handle->hash_where; entry < wall; entry++)
+ {
+ if (islive (entry)) /* silly code: tests entry->string twice! */
+ {
+ (*function) (entry->hash_string, entry->hash_value);
+ }
+ }
+}
+#endif
+
+/*
+ * h a s h _ f i n d ( )
+ *
+ * Given symbol string, find value (if any).
+ * Return found value or NULL.
+ */
+PTR
+hash_find (handle, string)
+ struct hash_control *handle;
+ const char *string;
+{
+ struct hash_entry *entry;
+
+ entry = hash_ask (handle, string, STAT__READ);
+ if (hash_found)
+ return entry->hash_value;
+ else
+ return NULL;
+}
+
+/*
+ * h a s h _ a s k ( )
+ *
+ * Searches for given symbol string.
+ * Return the slot where it OUGHT to live. It may be there.
+ * Return hash_found: TRUE only if symbol is in that slot.
+ * Access argument is to help keep statistics in control block.
+ * Internal.
+ */
+static struct hash_entry * /* string slot, may be empty or deleted */
+hash_ask (handle, string, access_type)
+ struct hash_control *handle;
+ const char *string;
+ int access_type;
+{
+ const char *s;
+ struct hash_entry *slot;
+ int collision; /* count collisions */
+ int strcmps;
+ int hcode;
+
+ /* start looking here */
+ hcode = hash_code (handle, string);
+ slot = handle->hash_where + (hcode & handle->hash_mask);
+
+ handle->hash_stat[STAT_ACCESS + access_type] += 1;
+ collision = strcmps = 0;
+ hash_found = FALSE;
+ while (((s = slot->hash_string) != NULL) && s != DELETED)
+ {
+ if (string == s)
+ {
+ hash_found = TRUE;
+ break;
+ }
+ if (slot->h == (unsigned long) hcode)
+ {
+ if (!strcmp (string, s))
+ {
+ hash_found = TRUE;
+ break;
+ }
+ strcmps++;
+ }
+ collision++;
+ slot++;
+ }
+ /*
+ * slot: return:
+ * in use: we found string slot
+ * at empty:
+ * at wall: we fell off: wrap round ????
+ * in table: dig here slot
+ * at DELETED: dig here slot
+ */
+ if (slot == handle->hash_wall)
+ {
+ slot = handle->hash_where;/* now look again */
+ while (((s = slot->hash_string) != NULL) && s != DELETED)
+ {
+ if (string == s)
+ {
+ hash_found = TRUE;
+ break;
+ }
+ if (slot->h == (unsigned long) hcode)
+ {
+ if (!strcmp (string, s))
+ {
+ hash_found = TRUE;
+ break;
+ }
+ strcmps++;
+ }
+ collision++;
+ slot++;
+ }
+ /*
+ * slot: return:
+ * in use: we found it slot
+ * empty: wall: ERROR IMPOSSIBLE !!!!
+ * in table: dig here slot
+ * DELETED:dig here slot
+ */
+ }
+ handle->hash_stat[STAT_COLLIDE + access_type] += collision;
+ handle->hash_stat[STAT_STRCMP + access_type] += strcmps;
+ if (!hash_found)
+ slot->h = hcode;
+ return slot; /* also return hash_found */
+}
+
+/*
+ * h a s h _ c o d e
+ *
+ * Does hashing of symbol string to hash number.
+ * Internal.
+ */
+static int
+hash_code (handle, string)
+ struct hash_control *handle;
+ const char *string;
+{
+#if 1 /* There seems to be some interesting property of this function
+ that prevents the bfd version below from being an adequate
+ substitute. @@ Figure out what this property is! */
+ long h; /* hash code built here */
+ long c; /* each character lands here */
+ int n; /* Amount to shift h by */
+
+ n = (handle->hash_sizelog - 3);
+ h = 0;
+ while ((c = *string++) != 0)
+ {
+ h += c;
+ h = (h << 3) + (h >> n) + c;
+ }
+ return h;
+#else
+ /* from bfd */
+ unsigned long h = 0;
+ unsigned int len = 0;
+ unsigned int c;
+
+ while ((c = *string++) != 0)
+ {
+ h += c + (c << 17);
+ h ^= h >> 2;
+ ++len;
+ }
+ h += len + (len << 17);
+ h ^= h >> 2;
+ return h;
+#endif
+}
+
+void
+hash_print_statistics (file, name, h)
+ FILE *file;
+ const char *name;
+ struct hash_control *h;
+{
+ unsigned long sz, used, pct;
+
+ if (h == 0)
+ return;
+
+ sz = h->hash_stat[STAT_SIZE];
+ used = h->hash_stat[STAT_USED];
+ pct = (used * 100 + sz / 2) / sz;
+
+ fprintf (file, "%s hash statistics:\n\t%lu/%lu slots used (%lu%%)\n",
+ name, used, sz, pct);
+
+#define P(name, off) \
+ fprintf (file, "\t%-16s %6dr + %6dw = %7d\n", name, \
+ h->hash_stat[off+STAT__READ], \
+ h->hash_stat[off+STAT__WRITE], \
+ h->hash_stat[off+STAT__READ] + h->hash_stat[off+STAT__WRITE])
+
+ P ("accesses:", STAT_ACCESS);
+ P ("collisions:", STAT_COLLIDE);
+ P ("string compares:", STAT_STRCMP);
+
+#undef P
+}
+
+/*
+ * Here is a test program to exercise above.
+ */
+#ifdef TEST
+
+#define TABLES (6) /* number of hash tables to maintain */
+/* (at once) in any testing */
+#define STATBUFSIZE (12) /* we can have 12 statistics */
+
+int statbuf[STATBUFSIZE]; /* display statistics here */
+char answer[100]; /* human farts here */
+char *hashtable[TABLES]; /* we test many hash tables at once */
+char *h; /* points to curent hash_control */
+char **pp;
+char *p;
+char *name;
+char *value;
+int size;
+int used;
+char command;
+int number; /* number 0:TABLES-1 of current hashed */
+/* symbol table */
+
+main ()
+{
+ void applicatee ();
+ void destroy ();
+ char *what ();
+ int *ip;
+
+ number = 0;
+ h = 0;
+ printf ("type h <RETURN> for help\n");
+ for (;;)
+ {
+ printf ("hash_test command: ");
+ gets (answer);
+ command = answer[0];
+ if (isupper (command))
+ command = tolower (command); /* ecch! */
+ switch (command)
+ {
+ case '#':
+ printf ("old hash table #=%d.\n", number);
+ whattable ();
+ break;
+ case '?':
+ for (pp = hashtable; pp < hashtable + TABLES; pp++)
+ {
+ printf ("address of hash table #%d control block is %xx\n"
+ ,pp - hashtable, *pp);
+ }
+ break;
+ case 'a':
+ hash_apply (h, applicatee);
+ break;
+ case 'd':
+ hash_apply (h, destroy);
+ hash_die (h);
+ break;
+ case 'f':
+ p = hash_find (h, name = what ("symbol"));
+ printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT");
+ break;
+ case 'h':
+ printf ("# show old, select new default hash table number\n");
+ printf ("? display all hashtable control block addresses\n");
+ printf ("a apply a simple display-er to each symbol in table\n");
+ printf ("d die: destroy hashtable\n");
+ printf ("f find value of nominated symbol\n");
+ printf ("h this help\n");
+ printf ("i insert value into symbol\n");
+ printf ("j jam value into symbol\n");
+ printf ("n new hashtable\n");
+ printf ("r replace a value with another\n");
+ printf ("s say what %% of table is used\n");
+ printf ("q exit this program\n");
+ printf ("x delete a symbol from table, report its value\n");
+ break;
+ case 'i':
+ p = hash_insert (h, name = what ("symbol"), value = what ("value"));
+ if (p)
+ {
+ printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value,
+ p);
+ }
+ break;
+ case 'j':
+ p = hash_jam (h, name = what ("symbol"), value = what ("value"));
+ if (p)
+ {
+ printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p);
+ }
+ break;
+ case 'n':
+ h = hashtable[number] = (char *) hash_new ();
+ break;
+ case 'q':
+ exit (EXIT_SUCCESS);
+ case 'r':
+ p = hash_replace (h, name = what ("symbol"), value = what ("value"));
+ printf ("old value was \"%s\"\n", p ? p : "{}");
+ break;
+ case 's':
+ hash_say (h, statbuf, STATBUFSIZE);
+ for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++)
+ {
+ printf ("%d ", *ip);
+ }
+ printf ("\n");
+ break;
+ case 'x':
+ p = hash_delete (h, name = what ("symbol"));
+ printf ("old value was \"%s\"\n", p ? p : "{}");
+ break;
+ default:
+ printf ("I can't understand command \"%c\"\n", command);
+ break;
+ }
+ }
+}
+
+char *
+what (description)
+ char *description;
+{
+ char *retval;
+ char *malloc ();
+
+ printf (" %s : ", description);
+ gets (answer);
+ /* will one day clean up answer here */
+ retval = malloc (strlen (answer) + 1);
+ if (!retval)
+ {
+ error ("room");
+ }
+ (void) strcpy (retval, answer);
+ return (retval);
+}
+
+void
+destroy (string, value)
+ char *string;
+ char *value;
+{
+ free (string);
+ free (value);
+}
+
+
+void
+applicatee (string, value)
+ char *string;
+ char *value;
+{
+ printf ("%.20s-%.20s\n", string, value);
+}
+
+whattable () /* determine number: what hash table to use */
+ /* also determine h: points to hash_control */
+{
+
+ for (;;)
+ {
+ printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
+ gets (answer);
+ sscanf (answer, "%d", &number);
+ if (number >= 0 && number < TABLES)
+ {
+ h = hashtable[number];
+ if (!h)
+ {
+ printf ("warning: current hash-table-#%d. has no hash-control\n", number);
+ }
+ return;
+ }
+ else
+ {
+ printf ("invalid hash table number: %d\n", number);
+ }
+ }
+}
+
+
+
+#endif /* #ifdef TEST */
+
+/* end of hash.c */