X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=gas%2Fhash.c;h=cfffede7e2e909648894c2aacafa28318b32b93b;hb=3036c8991964674ca2407c543645d841ad431267;hp=b57ba9ef25b874457eeba82e134e0a7105eb3a9a;hpb=fecd2382e77b89f12c9d630ed4e42e9a54ba6953;p=deliverable%2Fbinutils-gdb.git diff --git a/gas/hash.c b/gas/hash.c index b57ba9ef25..cfffede7e2 100644 --- a/gas/hash.c +++ b/gas/hash.c @@ -1,990 +1,595 @@ -/* hash.c - hash table lookup strings - - Copyright (C) 1987, 1990, 1991 Free Software Foundation, Inc. - -This file is part of GAS, the GNU Assembler. - -GAS is free software; you can redistribute it and/or modify -it under the terms of the GNU General Public License as published by -the Free Software Foundation; either version 1, or (at your option) -any later version. - -GAS is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. - -You should have received a copy of the GNU General Public License -along with GAS; see the file COPYING. If not, write to -the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */ - -/* static const char rcsid[] = "$Id$"; */ - -/* - * BUGS, GRIPES, APOLOGIA etc. - * - * A typical user doesn't need ALL this: I intend to make a library out - * of it one day - Dean Elsner. - * Also, I want to change the definition of a symbol to (address,length) - * so I can put arbitrary binary in the names stored. [see hsh.c for that] - * - * This slime is common coupled inside the module. Com-coupling (and other - * vandalism) was done to speed running time. The interfaces at the - * module's edges are adequately clean. - * - * There is no way to (a) run a test script through this heap and (b) - * compare results with previous scripts, to see if we have broken any - * code. Use GNU (f)utilities to do this. A few commands assist test. - * The testing is awkward: it tries to be both batch & interactive. - * For now, interactive rules! - */ - -/* - * The idea is to implement a symbol table. A test jig is here. - * Symbols are arbitrary strings; they can't contain '\0'. - * [See hsh.c for a more general symbol flavour.] - * Each symbol is associated with a char*, which can point to anything - * you want, allowing an arbitrary property list for each symbol. - * - * The basic operations are: - * - * new creates symbol table, returns handle - * find (symbol) returns char* - * insert (symbol,char*) error if symbol already in table - * delete (symbol) returns char* if symbol was in table - * apply so you can delete all symbols before die() - * die destroy symbol table (free up memory) - * - * Supplementary functions include: - * - * say how big? what % full? - * replace (symbol,newval) report previous value - * jam (symbol,value) assert symbol:=value - * - * You, the caller, have control over errors: this just reports them. - * - * This package requires malloc(), free(). - * Malloc(size) returns NULL or address of char[size]. - * Free(address) frees same. - */ - -/* - * The code and its structures are re-enterent. - * Before you do anything else, you must call hash_new() which will - * return the address of a hash-table-control-block (or NULL if there - * is not enough memory). You then use this address as a handle of the - * symbol table by passing it to all the other hash_...() functions. - * The only approved way to recover the memory used by the symbol table - * is to call hash_die() with the handle of the symbol table. - * - * Before you call hash_die() you normally delete anything pointed to - * by individual symbols. After hash_die() you can't use that symbol - * table again. - * - * The char* you associate with a symbol may not be NULL (0) because - * NULL is returned whenever a symbol is not in the table. Any other - * value is OK, except DELETED, #defined below. - * - * When you supply a symbol string for insertion, YOU MUST PRESERVE THE - * STRING until that symbol is deleted from the table. The reason is that - * only the address you supply, NOT the symbol string itself, is stored - * in the symbol table. - * - * You may delete and add symbols arbitrarily. - * Any or all symbols may have the same 'value' (char *). In fact, these - * routines don't do anything with your symbol values. - * - * You have no right to know where the symbol:char* mapping is stored, - * because it moves around in memory; also because we may change how it - * works and we don't want to break your code do we? However the handle - * (address of struct hash_control) is never changed in - * the life of the symbol table. - * - * What you CAN find out about a symbol table is: - * how many slots are in the hash table? - * how many slots are filled with symbols? - * (total hashes,collisions) for (reads,writes) (*) - * All of the above values vary in time. - * (*) some of these numbers will not be meaningful if we change the - * internals. - */ - -/* - * I N T E R N A L - * - * Hash table is an array of hash_entries; each entry is a pointer to a - * a string and a user-supplied value 1 char* wide. - * - * The array always has 2 ** n elements, n>0, n integer. - * There is also a 'wall' entry after the array, which is always empty - * and acts as a sentinel to stop running off the end of the array. - * When the array gets too full, we create a new array twice as large - * and re-hash the symbols into the new array, then forget the old array. - * (Of course, we copy the values into the new array before we junk the - * old array!) - * - */ - -#include - -#ifndef FALSE -#define FALSE (0) -#define TRUE (!FALSE) -#endif /* no FALSE yet */ - -#include -#define min(a, b) ((a) < (b) ? (a) : (b)) +/* hash.c -- gas hash table code + Copyright (C) 1987-2019 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 3, 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, 51 Franklin Street - Fifth Floor, Boston, MA + 02110-1301, 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 + assembler. 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 "safe-ctype.h" +#include "obstack.h" + +/* 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. */ + void *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 */ +}; + +/* The default number of entries to use when creating a hash table. + Note this value can be reduced to 4051 by using the command line + switch --reduce-memory-overheads, or set to other values by using + the --hash-size= switch. */ + +static unsigned long gas_hash_table_size = 65537; -#define error as_fatal - -#define DELETED ((char *)1) /* guarenteed invalid address */ -#define START_POWER (11) /* power of two: size of new hash table *//* JF was 6 */ -/* JF These next two aren't used any more. */ -/* #define START_SIZE (64) / * 2 ** START_POWER */ -/* #define START_FULL (32) / * number of entries before table expands */ -#define islive(ptr) (ptr->hash_string && ptr->hash_string!=DELETED) - /* above TRUE if a symbol is in entry @ ptr */ - -#define STAT_SIZE (0) /* number of slots in hash table */ - /* the wall does not count here */ - /* we expect this is always a power of 2 */ -#define STAT_ACCESS (1) /* number of hash_ask()s */ -#define STAT__READ (0) /* reading */ -#define STAT__WRITE (1) /* writing */ -#define STAT_COLLIDE (3) /* number of collisions (total) */ - /* this may exceed STAT_ACCESS if we have */ - /* lots of collisions/access */ -#define STAT_USED (5) /* slots used right now */ -#define STATLENGTH (6) /* size of statistics block */ -#if STATLENGTH != HASH_STATLENGTH -Panic! Please make #include "stat.h" agree with previous definitions! -#endif +void +set_gas_hash_table_size (unsigned long size) +{ + gas_hash_table_size = bfd_hash_set_default_size (size); +} -/* #define SUSPECT to do runtime checks */ -/* #define TEST to be a test jig for hash...() */ +/* 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 - -/*------------------ plan ---------------------------------- i = internal - -struct hash_control * c; -struct hash_entry * e; i -int b[z]; buffer for statistics - z size of b -char * s; symbol string (address) [ key ] -char * v; value string (address) [datum] -boolean f; TRUE if we found s in hash table i -char * t; error string; "" means OK -int a; access type [0...n) i - -c=hash_new () create new hash_control - -hash_die (c) destroy hash_control (and hash table) - table should be empty. - doesn't check if table is empty. - c has no meaning after this. - -hash_say (c,b,z) report statistics of hash_control. - also report number of available statistics. - -v=hash_delete (c,s) delete symbol, return old value if any. - ask() NULL means no old value. - f - -v=hash_replace (c,s,v) replace old value of s with v. - ask() NULL means no old value: no table change. - f - -t=hash_insert (c,s,v) insert (s,v) in c. - ask() return error string. - f it is an error to insert if s is already - in table. - if any error, c is unchanged. - -t=hash_jam (c,s,v) assert that new value of s will be v. i - ask() it may decide to GROW the table. i - f i - grow() i -t=hash_grow (c) grow the hash table. i - jam() will invoke JAM. i - -?=hash_apply (c,y) apply y() to every symbol in c. - y evtries visited in 'unspecified' order. - -v=hash_find (c,s) return value of s, or NULL if s not in c. - ask() - f - -f,e=hash_ask() (c,s,a) return slot where s SHOULD live. i - code() maintain collision stats in c. i - -.=hash_code (c,s) compute hash-code for s, i - from parameters of c. i - -*/ - -static char hash_found; /* returned by hash_ask() to stop extra */ - /* testing. hash_ask() wants to return both */ - /* a slot and a status. This is the status. */ - /* TRUE: found symbol */ - /* FALSE: absent: empty or deleted slot */ - /* Also returned by hash_jam(). */ - /* TRUE: we replaced a value */ - /* FALSE: we inserted a value */ - -static struct hash_entry * hash_ask(); -static int hash_code (); -static char * hash_grow(); - -/* - * h a s h _ n e w ( ) - * - */ struct hash_control * -hash_new() /* create a new hash table */ - /* return NULL if failed */ - /* return handle (address of struct hash) */ +hash_new_sized (unsigned long size) { - register struct hash_control * retval; - register struct hash_entry * room; /* points to hash table */ - register struct hash_entry * wall; - register struct hash_entry * entry; - register int * ip; /* scan stats block of struct hash_control */ - register int * nd; /* limit of stats block */ - - if (( room = (struct hash_entry *) malloc( sizeof(struct - hash_entry)*((1<hash_stat + STATLENGTH; - for (ip=retval->hash_stat; ipmemory, 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 - retval -> hash_stat[STAT_SIZE] = 1< hash_mask = (1< hash_sizelog = START_POWER; - /* works for 1's compl ok */ - retval -> hash_where = room; - retval -> hash_wall = - wall = room + (1< hash_full = (1<hash_string = NULL; - } - } - } - else - { - retval = NULL; /* no room for table: fake a failure */ - } - return(retval); /* return NULL or set-up structs */ + 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. - */ -void -hash_die(handle) - struct hash_control * handle; +struct hash_control * +hash_new (void) { - free((char *)handle->hash_where); - free((char *)handle); + return hash_new_sized (gas_hash_table_size); } - -/* - * 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. - */ + +/* Delete a hash table, freeing all allocated memory. */ + void -hash_say(handle,buffer,bufsiz) - register struct hash_control * handle; - register int buffer[/*bufsiz*/]; - register int bufsiz; +hash_die (struct hash_control *table) +{ + obstack_free (&table->memory, 0); + free (table); +} + +/* 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 (struct hash_control *table, const char *key, size_t len, + struct hash_entry ***plist, unsigned long *phash) { - register int * nd; /* limit of statistics block */ - register int * ip; /* scan statistics */ + unsigned long hash; + size_t n; + unsigned int c; + unsigned int hindex; + 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; + for (n = 0; n < len; n++) { - *buffer++ = STATLENGTH; - for (; ip> 2; } -} - -/* - * h a s h _ d e l e t e ( ) - * - * Try to delete a symbol from the table. - * If it was there, return its value (and adjust STAT_USED). - * Otherwise, return NULL. - * Anyway, the symbol is not present after this function. - * - */ -char * /* NULL if string not in table, else */ - /* returns value of deleted symbol */ -hash_delete(handle,string) - register struct hash_control * handle; - register char * string; -{ - register char * retval; /* NULL if string not in table */ - register struct hash_entry * entry; /* NULL or entry of this symbol */ + hash += len + (len << 17); + hash ^= hash >> 2; + + if (phash != NULL) + *phash = hash; + + hindex = hash % table->size; + list = table->table + hindex; + + if (plist != NULL) + *plist = list; - entry = hash_ask(handle,string,STAT__WRITE); - if (hash_found) + prev = NULL; + for (p = *list; p != NULL; p = p->next) { - retval = entry -> hash_value; - entry -> hash_string = DELETED; /* mark as deleted */ - handle -> hash_stat[STAT_USED] -= 1; /* slots-in-use count */ -#ifdef SUSPECT - if (handle->hash_stat[STAT_USED]<0) +#ifdef HASH_STATISTICS + ++table->hash_compares; +#endif + + if (p->hash == hash) + { +#ifdef HASH_STATISTICS + ++table->string_compares; +#endif + + if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0') { - error("hash_delete"); + if (prev != NULL) + { + prev->next = p->next; + p->next = *list; + *list = p; + } + + return p; } -#endif /* def SUSPECT */ - } - else - { - retval = NULL; + } + + prev = p; } - return(retval); + + return NULL; } - -/* - * h a s h _ r e p l a c e ( ) - * - * Try to replace the old value of a symbol with a new value. - * Normally return the old value. - * Return NULL and don't change the table if the symbol is not already - * in the table. - */ -char * -hash_replace(handle,string,value) - register struct hash_control * handle; - register char * string; - register char * value; + +/* 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 (struct hash_control *table, const char *key, void *val) { - register struct hash_entry * entry; - register char * retval; + struct hash_entry *p; + struct hash_entry **list; + unsigned long hash; - entry = hash_ask(handle,string,STAT__WRITE); - if (hash_found) + p = hash_lookup (table, key, strlen (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 = val; + + p->next = *list; + *list = p; + + return NULL; +} + +/* 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 (struct hash_control *table, const char *key, void *val) +{ + struct hash_entry *p; + struct hash_entry **list; + unsigned long hash; + + p = hash_lookup (table, key, strlen (key), &list, &hash); + if (p != NULL) { - retval = entry -> hash_value; - entry -> hash_value = value; +#ifdef HASH_STATISTICS + ++table->replacements; +#endif + + p->data = val; } else { - retval = NULL; +#ifdef HASH_STATISTICS + ++table->insertions; +#endif + + p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); + p->string = key; + p->hash = hash; + p->data = val; + + p->next = *list; + *list = 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, "" means OK. - * It is an 'error' to insert an existing symbol. - */ - -char * /* return error string */ -hash_insert(handle,string,value) - register struct hash_control * handle; - register char * string; - register char * value; + +/* 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. */ + +void * +hash_replace (struct hash_control *table, const char *key, void *value) { - register struct hash_entry * entry; - register char * retval; + struct hash_entry *p; + void *ret; - retval = ""; - if (handle->hash_stat[STAT_USED] > handle->hash_full) - { - retval = hash_grow(handle); - } - if ( ! * retval) - { - entry = hash_ask(handle,string,STAT__WRITE); - if (hash_found) - { - retval = "exists"; - } - else - { - entry -> hash_value = value; - entry -> hash_string = string; - handle-> hash_stat[STAT_USED] += 1; - } - } - return(retval); + p = hash_lookup (table, key, strlen (key), NULL, NULL); + if (p == NULL) + return NULL; + +#ifdef HASH_STATISTICS + ++table->replacements; +#endif + + ret = p->data; + + p->data = value; + + return ret; } - -/* - * h a s h _ j a m ( ) - * - * Regardless of what was in the symbol table before, after hash_jam() - * the named symbol has the given value. The symbol is either inserted or - * (its value is) relpaced. - * An error message string is returned, "" means OK. - * - * WARNING: this may decide to grow the hashed symbol table. - * To do this, we call hash_grow(), WHICH WILL recursively CALL US. - * - * We report status internally: hash_found is TRUE if we replaced, but - * false if we inserted. - */ -char * -hash_jam(handle,string,value) - register struct hash_control * handle; - register char * string; - register char * value; + +/* Find an entry in a hash table, returning its value. Returns NULL + if the entry is not found. */ + +void * +hash_find (struct hash_control *table, const char *key) { - register char * retval; - register struct hash_entry * entry; + struct hash_entry *p; - retval = ""; - if (handle->hash_stat[STAT_USED] > handle->hash_full) - { - retval = hash_grow(handle); - } - if (! * retval) - { - entry = hash_ask(handle,string,STAT__WRITE); - if ( ! hash_found) - { - entry -> hash_string = string; - handle->hash_stat[STAT_USED] += 1; - } - entry -> hash_value = value; - } - return(retval); + p = hash_lookup (table, key, strlen (key), NULL, NULL); + if (p == NULL) + return NULL; + + return p->data; } -/* - * 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: "" 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 char * -hash_grow(handle) /* make a hash table grow */ - struct hash_control * handle; +/* As hash_find, but KEY is of length LEN and is not guaranteed to be + NUL-terminated. */ + +void * +hash_find_n (struct hash_control *table, const char *key, size_t len) { - register struct hash_entry * newwall; - register struct hash_entry * newwhere; - struct hash_entry * newtrack; - register struct hash_entry * oldtrack; - register struct hash_entry * oldwhere; - register struct hash_entry * oldwall; - register int temp; - int newsize; - char * string; - char * retval; -#ifdef SUSPECT - int oldused; -#endif + struct hash_entry *p; - /* - * 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((long)((temp+temp+1)*sizeof(struct hash_entry)))) != NULL) - /* +1 for wall slot */ - { - retval = ""; /* 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"; - } -#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 "". - */ - } - } - else - { - retval = "no room"; - } - return(retval); + p = hash_lookup (table, key, len, NULL, NULL); + if (p == NULL) + return NULL; + + return p->data; } - -/* - * 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)(); + +/* Delete an entry from a hash table. This returns the value stored + for that entry, or NULL if there is no such entry. */ + +void * +hash_delete (struct hash_control *table, const char *key, int freeme) { - register struct hash_entry * entry; - register struct hash_entry * wall; + struct hash_entry *p; + struct hash_entry **list; - 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, strlen (key), &list, NULL); + if (p == NULL) + return NULL; + + if (p != *list) + abort (); + +#ifdef HASH_STATISTICS + ++table->deletions; +#endif + + *list = p->next; + + if (freeme) + obstack_free (&table->memory, p); + + return p->data; } - -/* - * h a s h _ f i n d ( ) - * - * Given symbol string, find value (if any). - * Return found value or NULL. - */ -char * -hash_find(handle,string) /* return char* or NULL */ - struct hash_control * handle; - char * string; + +/* Traverse a hash table. Call the function on every entry in the + hash table. */ + +void +hash_traverse (struct hash_control *table, + void (*pfn) (const char *key, void *value)) { - register struct hash_entry * entry; - register char * retval; + unsigned int i; - entry = hash_ask(handle,string,STAT__READ); - if (hash_found) - { - retval = entry->hash_value; - } - else + for (i = 0; i < table->size; ++i) { - retval = NULL; + struct hash_entry *p; + + for (p = table->table[i]; p != NULL; p = p->next) + (*pfn) (p->string, p->data); } - return(retval); } - -/* - * 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; - char * string; - int access; /* access type */ + +/* Print hash table statistics on the specified file. NAME is the + name of the hash table, used for printing a header. */ + +void +hash_print_statistics (FILE *f ATTRIBUTE_UNUSED, + const char *name ATTRIBUTE_UNUSED, + struct hash_control *table ATTRIBUTE_UNUSED) { - register char *string1; /* JF avoid strcmp calls */ - register char * s; - register int c; - register struct hash_entry * slot; - register int collision; /* count collisions */ - - slot = handle->hash_where + hash_code(handle,string); /* start looking here */ - handle->hash_stat[STAT_ACCESS+access] += 1; - collision = 0; - hash_found = FALSE; - while ( ((s = slot->hash_string) != NULL) && s!=DELETED ) - { - for(string1=string;;) { - if((c= *s++) == 0) { - if(!*string1) - hash_found = TRUE; - break; - } - if(*string1++!=c) - break; - } - 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) +#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) { - slot = handle->hash_where; /* now look again */ - while( ((s = slot->hash_string) != NULL) && s!=DELETED ) + struct hash_entry *p; + + if (table->table[i] == NULL) + ++empty; + else { - for(string1=string;*s;string1++,s++) { - if(*string1!=*s) - break; - } - if(*s==*string1) { - hash_found = TRUE; - break; - } - collision++; - slot++; + for (p = table->table[i]; p != NULL; p = p->next) + ++total; } - /* - * slot: return: - * in use: we found it slot - * empty: wall: ERROR IMPOSSIBLE !!!! - * in table: dig here slot - * DELETED:dig here slot - */ } -/* fprintf(stderr,"hash_ask(%s)->%d(%d)\n",string,hash_code(handle,string),collision); */ - handle -> hash_stat[STAT_COLLIDE+access] += collision; - 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; - register char * string; -{ - register long h; /* hash code built here */ - register long c; /* each character lands here */ - register 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 & handle->hash_mask); + 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 -#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() +/* 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) + +/* Display statistics here. */ +int statbuf[STATBUFSIZE]; + +/* Human farts here. */ +char answer[100]; + +/* We test many hash tables at once. */ +char *hashtable[TABLES]; + +/* Points to current hash_control. */ +char *h; +char **pp; +char *p; +char *name; +char *value; +int size; +int used; +char command; + +/* Number 0:TABLES-1 of current hashed symbol table. */ +int number; + +int +main () { - char (*applicatee()); - char * hash_find(); - char * destroy(); - char * what(); - struct hash_control * hash_new(); - char * hash_replace(); - int * ip; + void applicatee (); + void destroy (); + char *what (); + int *ip; number = 0; h = 0; - printf("type h for help\n"); - for(;;) + printf ("type h for help\n"); + for (;;) { - printf("hash_test command: "); - gets(answer); + printf ("hash_test command: "); + gets (answer); command = answer[0]; - if (isupper(command)) command = tolower(command); /* ecch! */ + command = TOLOWER (command); /* Ecch! */ switch (command) { case '#': - printf("old hash table #=%d.\n",number); - whattable(); + printf ("old hash table #=%d.\n", number); + whattable (); break; case '?': - for (pp=hashtable; pp=0 && number= 0 && number < TABLES) { h = hashtable[number]; if (!h) { - printf("warning: current hash-table-#%d. has no hash-control\n",number); + printf ("warning: current hash-table-#%d. has no hash-control\n", number); } return; } else { - printf("invalid hash table number: %d\n",number); + printf ("invalid hash table number: %d\n", number); } } } - - -#endif /* #ifdef TEST */ - -/* end: hash.c */ +#endif /* TEST */