-/* hash.c - hash table lookup strings -
- Copyright (C) 1987, 1990, 1991, 1992 Free Software Foundation, Inc.
+/* hash.c -- gas hash table code
+ Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
+ 2000
+ Free Software Foundation, Inc.
This file is part of GAS, the GNU Assembler.
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!
- */
-\f
-/*
- * 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.
- */
-\f
-/*
- * 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. */
-\f
-/*
- * 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))
+ 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. */
+
+/* This version of the hash table code is a wholescale replacement of
+ the old hash table code, which was fairly bad. This is based on
+ the hash table code in BFD, but optimized slightly for the
+ asssembler. The assembler does not need to derive structures that
+ are stored in the hash table. Instead, it always stores a pointer.
+ The assembler uses the hash table mostly to store symbols, and we
+ don't need to confuse the symbol structure with a hash table
+ structure. */
#include "as.h"
+#include "obstack.h"
-#define error as_fatal
-
-#define DELETED ((PTR)1) /* guarenteed invalid address */
-#define START_POWER (11) /* 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)
-
-/* Number of slots in hash table. The wall does not count here.
- We expect this is always a power of 2. */
-#define STAT_SIZE (0)
-#define STAT_ACCESS (1) /* number of hash_ask()s */
-#define STAT__READ (0) /* reading */
-#define STAT__WRITE (1) /* writing */
-/* Number of collisions (total). This may exceed STAT_ACCESS if we
- have lots of collisions/access. */
-#define STAT_COLLIDE (3)
-#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
+/* The default number of entries to use when creating a hash table. */
-/* #define SUSPECT to do runtime checks */
-/* #define TEST to be a test jig for hash...() */
+#define DEFAULT_SIZE (4051)
+
+/* An entry in a hash table. */
+
+struct hash_entry {
+ /* Next entry for this hash code. */
+ struct hash_entry *next;
+ /* String being hashed. */
+ const char *string;
+ /* Hash code. This is the full hash code, not the index into the
+ table. */
+ unsigned long hash;
+ /* Pointer being stored in the hash table. */
+ PTR data;
+};
+
+/* A hash table. */
+
+struct hash_control {
+ /* The hash array. */
+ struct hash_entry **table;
+ /* The number of slots in the hash table. */
+ unsigned int size;
+ /* An obstack for this hash table. */
+ struct obstack memory;
+
+#ifdef HASH_STATISTICS
+ /* Statistics. */
+ unsigned long lookups;
+ unsigned long hash_compares;
+ unsigned long string_compares;
+ unsigned long insertions;
+ unsigned long replacements;
+ unsigned long deletions;
+#endif /* HASH_STATISTICS */
+};
+
+/* Create a hash table. This return a control block. */
-#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
-\f
-/*------------------ 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
-
- */
-\f
-/* 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 *));
-\f
-/* 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 = (1 << START_POWER) / 2;
- for (entry = room; entry <= wall; entry++)
- entry->hash_string = NULL;
- return retval;
+ unsigned int size;
+ struct hash_control *ret;
+ unsigned int alloc;
+
+ size = DEFAULT_SIZE;
+
+ ret = (struct hash_control *) xmalloc (sizeof *ret);
+ obstack_begin (&ret->memory, chunksize);
+ alloc = size * sizeof (struct hash_entry *);
+ ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
+ memset (ret->table, 0, alloc);
+ ret->size = size;
+
+#ifdef HASH_STATISTICS
+ ret->lookups = 0;
+ ret->hash_compares = 0;
+ ret->string_compares = 0;
+ ret->insertions = 0;
+ ret->replacements = 0;
+ ret->deletions = 0;
+#endif
+
+ return ret;
}
-/*
- * 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.
- */
+/* Delete a hash table, freeing all allocated memory. */
+
void
-hash_die (handle)
- struct hash_control *handle;
+hash_die (table)
+ struct hash_control *table;
{
- free ((char *) handle->hash_where);
- free ((char *) handle);
+ obstack_free (&table->memory, 0);
+ free (table);
}
-\f
-/*
- * 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)
- 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;
- }
- }
-}
-\f
-/*
- * 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;
+/* Look up a string in a hash table. This returns a pointer to the
+ hash_entry, or NULL if the string is not in the table. If PLIST is
+ not NULL, this sets *PLIST to point to the start of the list which
+ would hold this hash entry. If PHASH is not NULL, this sets *PHASH
+ to the hash code for KEY.
+
+ Each time we look up a string, we move it to the start of the list
+ for its hash code, to take advantage of referential locality. */
+
+static struct hash_entry *hash_lookup PARAMS ((struct hash_control *,
+ const char *,
+ struct hash_entry ***,
+ unsigned long *));
+
+static struct hash_entry *
+hash_lookup (table, key, plist, phash)
+ struct hash_control *table;
+ const char *key;
+ struct hash_entry ***plist;
+ unsigned long *phash;
{
- PTR retval;
- struct hash_entry *entry;
+ register unsigned long hash;
+ unsigned int len;
+ register const unsigned char *s;
+ register unsigned int c;
+ unsigned int index;
+ struct hash_entry **list;
+ struct hash_entry *p;
+ struct hash_entry *prev;
+
+#ifdef HASH_STATISTICS
+ ++table->lookups;
+#endif
- entry = hash_ask (handle, string, STAT__WRITE);
- if (hash_found)
+ hash = 0;
+ len = 0;
+ s = (const unsigned char *) key;
+ while ((c = *s++) != '\0')
{
- 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;
+ hash += c + (c << 17);
+ hash ^= hash >> 2;
+ ++len;
}
- return (retval);
-}
-\f
-/*
- * 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;
+ hash += len + (len << 17);
+ hash ^= hash >> 2;
- entry = hash_ask (handle, string, STAT__WRITE);
- if (hash_found)
- {
- retval = entry->hash_value;
- entry->hash_value = value;
- }
- else
- {
- retval = NULL;
- }
- ;
- return retval;
-}
-\f
-/*
- * 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;
+ if (phash != NULL)
+ *phash = hash;
- retval = 0;
- if (handle->hash_stat[STAT_USED] > handle->hash_full)
- {
- retval = hash_grow (handle);
- }
- if (!retval)
+ index = hash % table->size;
+ list = table->table + index;
+
+ if (plist != NULL)
+ *plist = list;
+
+ prev = NULL;
+ for (p = *list; p != NULL; p = p->next)
{
- entry = hash_ask (handle, string, STAT__WRITE);
- if (hash_found)
- {
- retval = "exists";
- }
- else
+#ifdef HASH_STATISTICS
+ ++table->hash_compares;
+#endif
+
+ if (p->hash == hash)
{
- entry->hash_value = value;
- entry->hash_string = string;
- handle->hash_stat[STAT_USED] += 1;
+#ifdef HASH_STATISTICS
+ ++table->string_compares;
+#endif
+
+ if (strcmp (p->string, key) == 0)
+ {
+ if (prev != NULL)
+ {
+ prev->next = p->next;
+ p->next = *list;
+ *list = p;
+ }
+
+ return p;
+ }
}
+
+ prev = p;
}
- return retval;
+
+ return NULL;
}
-\f
-/*
- * 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, 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.
- */
+
+/* Insert an entry into a hash table. This returns NULL on success.
+ On error, it returns a printable string indicating the error. It
+ is considered to be an error if the entry already exists in the
+ hash table. */
+
const char *
-hash_jam (handle, string, value)
- struct hash_control *handle;
- const char *string;
+hash_insert (table, key, value)
+ struct hash_control *table;
+ const char *key;
PTR value;
{
- const char *retval;
- struct hash_entry *entry;
+ struct hash_entry *p;
+ struct hash_entry **list;
+ unsigned long hash;
- 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;
+ p = hash_lookup (table, key, &list, &hash);
+ if (p != NULL)
+ return "exists";
+
+#ifdef HASH_STATISTICS
+ ++table->insertions;
+#endif
+
+ p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
+ p->string = key;
+ p->hash = hash;
+ p->data = value;
+
+ p->next = *list;
+ *list = p;
+
+ return NULL;
}
-/*
- * 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;
+/* Insert or replace an entry in a hash table. This returns NULL on
+ success. On error, it returns a printable string indicating the
+ error. If an entry already exists, its value is replaced. */
+
+const char *
+hash_jam (table, key, value)
+ struct hash_control *table;
+ const char *key;
+ PTR value;
{
- 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
+ struct hash_entry *p;
+ struct hash_entry **list;
+ unsigned long hash;
- /*
- * 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];
- if ((newwhere = ((struct hash_entry *)
- xmalloc ((unsigned long) ((temp + temp + 1)
- * sizeof (struct hash_entry)))))
- != NULL)
- /* +1 for wall slot */
+ p = hash_lookup (table, key, &list, &hash);
+ if (p != NULL)
{
- retval = 0; /* assume success until proven otherwise */
- /*
- * have enough room: now we do all the work.
- * double the size of everything in handle,
- * note: hash_mask frob works for 1's & for 2's complement machines
- */
- handle->hash_mask = handle->hash_mask + handle->hash_mask + 1;
- handle->hash_stat[STAT_SIZE] <<= 1;
- newsize = handle->hash_stat[STAT_SIZE];
- handle->hash_where = newwhere;
- handle->hash_full <<= 1;
- handle->hash_sizelog += 1;
- handle->hash_stat[STAT_USED] = 0;
- 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; /* inserts will bump it up to correct */
- for (oldtrack = oldwhere; oldtrack < oldwall; oldtrack++)
- if (((string = oldtrack->hash_string) != NULL) && string != DELETED)
- if ((retval = hash_jam (handle, string, oldtrack->hash_value)))
- break;
-
-#ifdef SUSPECT
- if (!retval && handle->hash_stat[STAT_USED] != oldused)
- {
- retval = "hash_used";
- }
+#ifdef HASH_STATISTICS
+ ++table->replacements;
#endif
- if (!retval)
- {
- /*
- * we have a completely faked up control block.
- * return the old hash table.
- */
- free ((char *) oldwhere);
- /*
- * Here with success. retval is already 0.
- */
- }
+
+ p->data = value;
}
else
{
- retval = "no room";
+#ifdef HASH_STATISTICS
+ ++table->insertions;
+#endif
+
+ p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p));
+ p->string = key;
+ p->hash = hash;
+ p->data = value;
+
+ p->next = *list;
+ *list = p;
}
- return retval;
+
+ return NULL;
}
-\f
-/*
- * 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.
- * To be safe, please make your functions of type char *. If you always
- * return NULL, then the scan will complete, visiting every symbol in
- * the table exactly once. ALL OTHER RETURNED VALUES have no meaning yet!
- * Caveat Actor!
- *
- * The function you supply should be of the form:
- * char * myfunct(string,value)
- * char * string; |* the symbol's name *|
- * char * value; |* the symbol's value *|
- * {
- * |* ... *|
- * return(NULL);
- * }
- *
- * The returned value of hash_apply() is (char*)NULL. In future it may return
- * other values. NULL means "completed scan OK". Other values have no meaning
- * yet. (The function has no graceful failures.)
- */
-char *
-hash_apply (handle, function)
- struct hash_control *handle;
- char *(*function) ();
+
+/* Replace an existing entry in a hash table. This returns the old
+ value stored for the entry. If the entry is not found in the hash
+ table, this does nothing and returns NULL. */
+
+PTR
+hash_replace (table, key, value)
+ struct hash_control *table;
+ const char *key;
+ PTR value;
{
- struct hash_entry *entry;
- struct hash_entry *wall;
+ struct hash_entry *p;
+ PTR ret;
- 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);
- }
- }
- return (NULL);
+ p = hash_lookup (table, key, NULL, NULL);
+ if (p == NULL)
+ return NULL;
+
+#ifdef HASH_STATISTICS
+ ++table->replacements;
+#endif
+
+ ret = p->data;
+
+ p->data = value;
+
+ return ret;
}
-\f
-/*
- * h a s h _ f i n d ( )
- *
- * Given symbol string, find value (if any).
- * Return found value or NULL.
- */
+
+/* Find an entry in a hash table, returning its value. Returns NULL
+ if the entry is not found. */
+
PTR
-hash_find (handle, string)
- struct hash_control *handle;
- const char *string;
+hash_find (table, key)
+ struct hash_control *table;
+ const char *key;
{
- struct hash_entry *entry;
+ struct hash_entry *p;
- entry = hash_ask (handle, string, STAT__READ);
- if (hash_found)
- return entry->hash_value;
- else
+ p = hash_lookup (table, key, NULL, NULL);
+ if (p == NULL)
return NULL;
+
+ return p->data;
}
-\f
-/*
- * 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)
- struct hash_control *handle;
- const char *string;
- int access; /* access type */
+
+/* Delete an entry from a hash table. This returns the value stored
+ for that entry, or NULL if there is no such entry. */
+
+PTR
+hash_delete (table, key)
+ struct hash_control *table;
+ const char *key;
{
- const char *s;
- struct hash_entry *slot;
- int collision; /* count collisions */
+ struct hash_entry *p;
+ struct hash_entry **list;
- /* start looking here */
- slot = handle->hash_where + hash_code (handle, string);
+ p = hash_lookup (table, key, &list, NULL);
+ if (p == NULL)
+ return NULL;
- handle->hash_stat[STAT_ACCESS + access] += 1;
- collision = 0;
- hash_found = FALSE;
- while (((s = slot->hash_string) != NULL) && s != DELETED)
- {
- if (string == s || !strcmp (string, s))
- hash_found = TRUE;
- if (hash_found)
- break;
- 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 || !strcmp (string, s))
- hash_found = TRUE;
- 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] += collision;
- return (slot); /* also return hash_found */
+ if (p != *list)
+ abort ();
+
+#ifdef HASH_STATISTICS
+ ++table->deletions;
+#endif
+
+ *list = p->next;
+
+ /* Note that we never reclaim the memory for this entry. If gas
+ ever starts deleting hash table entries in a big way, this will
+ have to change. */
+
+ return p->data;
}
-\f
-/*
- * 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;
+
+/* Traverse a hash table. Call the function on every entry in the
+ hash table. */
+
+void
+hash_traverse (table, pfn)
+ struct hash_control *table;
+ void (*pfn) PARAMS ((const char *key, PTR value));
{
-#if 0
- long h; /* hash code built here */
- long c; /* each character lands here */
- int n; /* Amount to shift h by */
+ unsigned int i;
- n = (handle->hash_sizelog - 3);
- h = 0;
- while ((c = *string++) != 0)
+ for (i = 0; i < table->size; ++i)
{
- h += c;
- h = (h << 3) + (h >> n) + c;
+ struct hash_entry *p;
+
+ for (p = table->table[i]; p != NULL; p = p->next)
+ (*pfn) (p->string, p->data);
}
- return (h & handle->hash_mask);
-#else
- unsigned long h = 0;
- unsigned int len = 0;
- unsigned int c;
+}
+
+/* Print hash table statistics on the specified file. NAME is the
+ name of the hash table, used for printing a header. */
- while ((c = *string++) != 0)
+void
+hash_print_statistics (f, name, table)
+ FILE *f ATTRIBUTE_UNUSED;
+ const char *name ATTRIBUTE_UNUSED;
+ struct hash_control *table ATTRIBUTE_UNUSED;
+{
+#ifdef HASH_STATISTICS
+ unsigned int i;
+ unsigned long total;
+ unsigned long empty;
+
+ fprintf (f, "%s hash statistics:\n", name);
+ fprintf (f, "\t%lu lookups\n", table->lookups);
+ fprintf (f, "\t%lu hash comparisons\n", table->hash_compares);
+ fprintf (f, "\t%lu string comparisons\n", table->string_compares);
+ fprintf (f, "\t%lu insertions\n", table->insertions);
+ fprintf (f, "\t%lu replacements\n", table->replacements);
+ fprintf (f, "\t%lu deletions\n", table->deletions);
+
+ total = 0;
+ empty = 0;
+ for (i = 0; i < table->size; ++i)
{
- h += c + (c << 17);
- h ^= h >> 2;
- ++len;
+ struct hash_entry *p;
+
+ if (table->table[i] == NULL)
+ ++empty;
+ else
+ {
+ for (p = table->table[i]; p != NULL; p = p->next)
+ ++total;
+ }
}
- h += len + (len << 17);
- h ^= h >> 2;
- return h & handle->hash_mask;
+
+ fprintf (f, "\t%g average chain length\n", (double) total / table->size);
+ fprintf (f, "\t%lu empty slots\n", empty);
#endif
}
\f
-/*
- * 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 */
+/* This test program is left over from the old hash table code. */
+
+/* Number of hash tables to maintain (at once) in any testing. */
+#define TABLES (6)
+
+/* We can have 12 statistics. */
+#define STATBUFSIZE (12)
-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 */
+/* Display statistics here. */
+int statbuf[STATBUFSIZE];
+
+/* Human farts here. */
+char answer[100];
+
+/* We test many hash tables at once. */
+char *hashtable[TABLES];
+
+/* Points to curent hash_control. */
+char *h;
char **pp;
char *p;
char *name;
int size;
int used;
char command;
-int number; /* number 0:TABLES-1 of current hashed */
-/* symbol table */
+/* Number 0:TABLES-1 of current hashed symbol table. */
+int number;
+
+int
main ()
{
- char (*applicatee ());
- char *destroy ();
+ void applicatee ();
+ void destroy ();
char *what ();
int *ip;
gets (answer);
command = answer[0];
if (isupper (command))
- command = tolower (command); /* ecch! */
+ command = tolower (command); /* Ecch! */
switch (command)
{
case '#':
case '?':
for (pp = hashtable; pp < hashtable + TABLES; pp++)
{
- printf ("address of hash table #%d control block is %xx\n"
- ,pp - hashtable, *pp);
+ printf ("address of hash table #%d control block is %xx\n",
+ pp - hashtable, *pp);
}
break;
case 'a':
- hash_apply (h, applicatee);
+ hash_traverse (h, applicatee);
break;
case 'd':
- hash_apply (h, destroy);
+ hash_traverse (h, destroy);
hash_die (h);
break;
case 'f':
printf (" %s : ", description);
gets (answer);
- /* will one day clean up answer here */
+ /* Will one day clean up answer here. */
retval = malloc (strlen (answer) + 1);
if (!retval)
{
return (retval);
}
-char *
+void
destroy (string, value)
char *string;
char *value;
{
free (string);
free (value);
- return (NULL);
}
-
-char *
+void
applicatee (string, value)
char *string;
char *value;
{
printf ("%.20s-%.20s\n", string, value);
- return (NULL);
}
-whattable () /* determine number: what hash table to use */
- /* also determine h: points to hash_control */
-{
+/* Determine number: what hash table to use.
+ Also determine h: points to hash_control. */
+void
+whattable ()
+{
for (;;)
{
printf (" what hash table (%d:%d) ? ", 0, TABLES - 1);
}
}
-
-
-#endif /* #ifdef TEST */
-
-/* end of hash.c */
+#endif /* TEST */
projects / deliverable / binutils-gdb.git / blobdiff