X-Git-Url: https://git.libre-soc.org/?a=blobdiff_plain;f=gas%2Fhash.c;h=f3c5292e0268278f981cafc14e69d9081195e618;hb=35f7d33dd99346dd368fd7bdbc251001130b86cf;hp=09925f02120612ccef59f7a9a6fb26408cc170f1;hpb=6f2750feaf2827ef8a1a0a5b2f90c1e9a6cabbd1;p=binutils-gdb.git diff --git a/gas/hash.c b/gas/hash.c index 09925f02120..f3c5292e026 100644 --- a/gas/hash.c +++ b/gas/hash.c @@ -1,5 +1,5 @@ /* hash.c -- gas hash table code - Copyright (C) 1987-2016 Free Software Foundation, Inc. + Copyright (C) 1987-2021 Free Software Foundation, Inc. This file is part of GAS, the GNU Assembler. @@ -18,578 +18,38 @@ 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; - -void -set_gas_hash_table_size (unsigned long size) -{ - gas_hash_table_size = bfd_hash_set_default_size (size); -} - -/* Create a hash table. This return a control block. */ - -struct hash_control * -hash_new_sized (unsigned long size) -{ - unsigned long alloc; - struct hash_control *ret; - - 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; -} -struct hash_control * -hash_new (void) -{ - return hash_new_sized (gas_hash_table_size); -} - -/* Delete a hash table, freeing all allocated memory. */ - -void -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. +/* Insert ELEMENT into HTAB. If REPLACE is non-zero existing elements + are overwritten. If ELEMENT already exists, a pointer to the slot + is returned. Otherwise NULL is returned. */ - 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) +void ** +htab_insert (htab_t htab, void *element, int replace) { - 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 - - hash = 0; - for (n = 0; n < len; n++) + void **slot = htab_find_slot (htab, element, INSERT); + if (*slot != NULL) { - c = key[n]; - hash += c + (c << 17); - hash ^= hash >> 2; - } - 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; - - prev = NULL; - for (p = *list; p != NULL; p = p->next) - { -#ifdef HASH_STATISTICS - ++table->hash_compares; -#endif - - if (p->hash == hash) + if (replace) { -#ifdef HASH_STATISTICS - ++table->string_compares; -#endif - - if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0') - { - if (prev != NULL) - { - prev->next = p->next; - p->next = *list; - *list = p; - } - - return p; - } + if (htab->del_f) + (*htab->del_f) (*slot); + *slot = element; } - - prev = p; - } - - return NULL; -} - -/* 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) -{ - struct hash_entry *p; - struct hash_entry **list; - unsigned long hash; - - 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) - { -#ifdef HASH_STATISTICS - ++table->replacements; -#endif - - p->data = val; - } - else - { -#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 slot; } - + *slot = element; return NULL; } -/* 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) -{ - struct hash_entry *p; - void *ret; - - 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; -} - -/* 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) -{ - struct hash_entry *p; - - p = hash_lookup (table, key, strlen (key), NULL, NULL); - if (p == NULL) - return NULL; - - return p->data; -} - -/* 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) -{ - struct hash_entry *p; - - p = hash_lookup (table, key, len, NULL, NULL); - if (p == NULL) - return NULL; - - return p->data; -} - -/* 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) -{ - struct hash_entry *p; - struct hash_entry **list; - - 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; -} - -/* 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)) -{ - unsigned int i; - - for (i = 0; i < table->size; ++i) - { - struct hash_entry *p; - - for (p = table->table[i]; p != NULL; p = p->next) - (*pfn) (p->string, p->data); - } -} - -/* Print hash table statistics on the specified file. NAME is the - name of the hash table, used for printing a header. */ +/* Print statistics about a hash table. */ void -hash_print_statistics (FILE *f ATTRIBUTE_UNUSED, - const char *name ATTRIBUTE_UNUSED, - struct hash_control *table ATTRIBUTE_UNUSED) +htab_print_statistics (FILE *f, const char *name, htab_t 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; - - if (table->table[i] == NULL) - ++empty; - else - { - for (p = table->table[i]; p != NULL; p = p->next) - ++total; - } - } - - fprintf (f, "\t%g average chain length\n", (double) total / table->size); - fprintf (f, "\t%lu empty slots\n", empty); -#endif -} - -#ifdef TEST - -/* 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 () -{ - void applicatee (); - void destroy (); - char *what (); - int *ip; - - number = 0; - h = 0; - printf ("type h for help\n"); - for (;;) - { - printf ("hash_test command: "); - gets (answer); - command = answer[0]; - command = TOLOWER (command); /* Ecch! */ - switch (command) - { - case '#': - printf ("old hash table #=%d.\n", number); - whattable (); - break; - case '?': - for (pp = hashtable; pp < hashtable + TABLES; pp++) - { - printf ("address of hash table #%d control block is %xx\n", - pp - hashtable, *pp); - } - break; - case 'a': - hash_traverse (h, applicatee); - break; - case 'd': - hash_traverse (h, destroy); - hash_die (h); - break; - case 'f': - p = hash_find (h, name = what ("symbol")); - printf ("value of \"%s\" is \"%s\"\n", name, p ? p : "NOT-PRESENT"); - break; - case 'h': - printf ("# show old, select new default hash table number\n"); - printf ("? display all hashtable control block addresses\n"); - printf ("a apply a simple display-er to each symbol in table\n"); - printf ("d die: destroy hashtable\n"); - printf ("f find value of nominated symbol\n"); - printf ("h this help\n"); - printf ("i insert value into symbol\n"); - printf ("j jam value into symbol\n"); - printf ("n new hashtable\n"); - printf ("r replace a value with another\n"); - printf ("s say what %% of table is used\n"); - printf ("q exit this program\n"); - printf ("x delete a symbol from table, report its value\n"); - break; - case 'i': - p = hash_insert (h, name = what ("symbol"), value = what ("value")); - if (p) - { - printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, - p); - } - break; - case 'j': - p = hash_jam (h, name = what ("symbol"), value = what ("value")); - if (p) - { - printf ("symbol=\"%s\" value=\"%s\" error=%s\n", name, value, p); - } - break; - case 'n': - h = hashtable[number] = (char *) hash_new (); - break; - case 'q': - exit (EXIT_SUCCESS); - case 'r': - p = hash_replace (h, name = what ("symbol"), value = what ("value")); - printf ("old value was \"%s\"\n", p ? p : "{}"); - break; - case 's': - hash_say (h, statbuf, STATBUFSIZE); - for (ip = statbuf; ip < statbuf + STATBUFSIZE; ip++) - { - printf ("%d ", *ip); - } - printf ("\n"); - break; - case 'x': - p = hash_delete (h, name = what ("symbol")); - printf ("old value was \"%s\"\n", p ? p : "{}"); - break; - default: - printf ("I can't understand command \"%c\"\n", command); - break; - } - } -} - -char * -what (description) - char *description; -{ - printf (" %s : ", description); - gets (answer); - return xstrdup (answer); -} - -void -destroy (string, value) - char *string; - char *value; -{ - free (string); - free (value); -} - -void -applicatee (string, value) - char *string; - char *value; -{ - printf ("%.20s-%.20s\n", string, value); + fprintf (f, "\t%u searches\n", table->searches); + fprintf (f, "\t%u collisions\n", table->collisions); + fprintf (f, "\t%lu elements\n", (unsigned long) htab_elements (table)); + fprintf (f, "\t%lu table size\n", (unsigned long) htab_size (table)); } - -/* 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); - gets (answer); - sscanf (answer, "%d", &number); - if (number >= 0 && number < TABLES) - { - h = hashtable[number]; - if (!h) - { - printf ("warning: current hash-table-#%d. has no hash-control\n", number); - } - return; - } - else - { - printf ("invalid hash table number: %d\n", number); - } - } -} - -#endif /* TEST */