diff options
Diffstat (limited to 'gas/hash.c')
| -rw-r--r-- | gas/hash.c | 1103 |
1 files changed, 338 insertions, 765 deletions
@@ -1,5 +1,5 @@ -/* hash.c - hash table lookup strings - - Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 1998 +/* hash.c -- gas hash table code + Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 98, 1999 Free Software Foundation, Inc. This file is part of GAS, the GNU Assembler. @@ -15,835 +15,408 @@ 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)) + 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 - -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 */ +/* The default number of entries to use when creating a hash table. */ -/* 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 DEFAULT_SIZE (4051) -/* #define SUSPECT to do runtime checks */ -/* #define TEST to be a test jig for hash...() */ +/* An entry in a hash table. */ -#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; + /* 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; }; -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 */ +/* 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 */ }; - -/*------------------ 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). */ + +/* Create a hash table. This return a control block. */ + 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; + 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); } - -#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; + +/* 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; { - int *nd; /* limit of statistics block */ - int *ip; /* scan statistics */ + 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 - ip = handle->hash_stat; - nd = ip + min (bufsiz - 1, STATLENGTH); - if (bufsiz > 0) /* trust nothing! bufsiz<=0 is dangerous */ + hash = 0; + len = 0; + s = (const unsigned char *) key; + while ((c = *s++) != '\0') { - *buffer++ = STATLENGTH; - for (; ip < nd; ip++, buffer++) - { - *buffer = *ip; - } + hash += c + (c << 17); + hash ^= hash >> 2; + ++len; } -} -#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; + hash += len + (len << 17); + hash ^= hash >> 2; + + if (phash != NULL) + *phash = hash; + + index = hash % table->size; + list = table->table + index; - entry = hash_ask (handle, string, STAT__WRITE); - if (hash_found) + if (plist != NULL) + *plist = list; + + prev = NULL; + for (p = *list; p != NULL; p = p->next) { - retval = entry->hash_value; - entry->hash_string = DELETED; - handle->hash_stat[STAT_USED] -= 1; -#ifdef SUSPECT - if (handle->hash_stat[STAT_USED] < 0) +#ifdef HASH_STATISTICS + ++table->hash_compares; +#endif + + if (p->hash == hash) { - error ("hash_delete"); +#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; + } } -#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; + prev = p; } - ; - return retval; + + return NULL; } - -/* - * 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; + +/* 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_insert (table, key, value) + struct hash_control *table; + const char *key; PTR value; { - struct hash_entry *entry; - const char *retval; + 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) - { - retval = "exists"; - } - else - { - entry->hash_value = value; - entry->hash_string = string; - handle->hash_stat[STAT_USED] += 1; - } - } - return retval; + p = hash_lookup (table, key, &list, &hash); + if (p != NULL) + return "exists"; + +#ifdef HASH_STATISTICS + ++table->insertions; +#endif + + p = 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 _ 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. - */ + +/* 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 (handle, string, value) - struct hash_control *handle; - const char *string; +hash_jam (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) + p = hash_lookup (table, key, &list, &hash); + if (p != NULL) { - retval = hash_grow (handle); +#ifdef HASH_STATISTICS + ++table->replacements; +#endif + + p->data = value; } - if (!retval) + else { - entry = hash_ask (handle, string, STAT__WRITE); - if (!hash_found) - { - entry->hash_string = string; - handle->hash_stat[STAT_USED] += 1; - } - entry->hash_value = value; +#ifdef HASH_STATISTICS + ++table->insertions; +#endif + + p = obstack_alloc (&table->memory, sizeof *p); + p->string = key; + p->hash = hash; + p->data = value; + + p->next = *list; + *list = p; } - return retval; + + 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; +/* 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 *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; + PTR ret; - /* - * 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"; + p = hash_lookup (table, key, NULL, NULL); + if (p == NULL) + return NULL; + +#ifdef HASH_STATISTICS + ++table->replacements; #endif - /* We have a completely faked up control block. - Return the old hash table. */ - free ((char *) oldwhere); + ret = p->data; - 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; + p->data = value; - 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 ret; } -#endif - -/* - * 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; } - -/* - * 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; + +/* 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; { -#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; + struct hash_entry *p; + struct hash_entry **list; + + p = hash_lookup (table, key, &list, NULL); + if (p == NULL) + return NULL; + + 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; } - + +/* Traverse a hash table. Call the function on every entry in the + hash table. */ + void -hash_print_statistics (file, name, h) - FILE *file; - const char *name; - struct hash_control *h; +hash_traverse (table, pfn) + struct hash_control *table; + void (*pfn) PARAMS ((const char *key, PTR value)); { - unsigned long sz, used, pct; + unsigned int i; - if (h == 0) - return; + for (i = 0; i < table->size; ++i) + { + struct hash_entry *p; - sz = h->hash_stat[STAT_SIZE]; - used = h->hash_stat[STAT_USED]; - pct = (used * 100 + sz / 2) / sz; + for (p = table->table[i]; p != NULL; p = p->next) + (*pfn) (p->string, p->data); + } +} - fprintf (file, "%s hash statistics:\n\t%lu/%lu slots used (%lu%%)\n", - name, used, sz, pct); +/* Print hash table statistics on the specified file. NAME is the + name of the hash table, used for printing a header. */ -#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]) +void +hash_print_statistics (f, name, table) + FILE *f; + const char *name; + struct hash_control *table; +{ +#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) + { + struct hash_entry *p; - P ("accesses:", STAT_ACCESS); - P ("collisions:", STAT_COLLIDE); - P ("string compares:", STAT_STRCMP); + if (table->table[i] == NULL) + ++empty; + else + { + for (p = table->table[i]; p != NULL; p = p->next) + ++total; + } + } -#undef P + fprintf (f, "\t%g average chain length\n", (double) total / table->size); + fprintf (f, "\t%lu empty slots\n", empty); +#endif } -/* - * Here is a test program to exercise above. - */ #ifdef TEST +/* This test program is left over from the old hash table code. */ + #define TABLES (6) /* number of hash tables to maintain */ -/* (at once) in any testing */ + /* (at once) in any testing */ #define STATBUFSIZE (12) /* we can have 12 statistics */ int statbuf[STATBUFSIZE]; /* display statistics here */ @@ -858,8 +431,9 @@ int size; int used; char command; int number; /* number 0:TABLES-1 of current hashed */ -/* symbol table */ + /* symbol table */ +int main () { void applicatee (); @@ -891,10 +465,10 @@ main () } 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': @@ -996,8 +570,9 @@ applicatee (string, value) printf ("%.20s-%.20s\n", string, value); } +void whattable () /* determine number: what hash table to use */ - /* also determine h: points to hash_control */ + /* also determine h: points to hash_control */ { for (;;) @@ -1021,8 +596,6 @@ whattable () /* determine number: what hash table to use */ } } - - #endif /* #ifdef TEST */ /* end of hash.c */ |