/* hash.c -- gas hash table code
- Copyright (C) 1987-2018 Free Software Foundation, Inc.
+ Copyright (C) 1987-2023 Free Software Foundation, Inc.
This file is part of GAS, the GNU Assembler.
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 */
-};
+/* Hash function for a string_tuple. */
-/* 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=<NUMBER> switch. */
-
-static unsigned long gas_hash_table_size = 65537;
-
-void
-set_gas_hash_table_size (unsigned long size)
+hashval_t
+hash_string_tuple (const void *e)
{
- gas_hash_table_size = bfd_hash_set_default_size (size);
+ string_tuple_t *tuple = (string_tuple_t *) e;
+ return htab_hash_string (tuple->key);
}
-/* Create a hash table. This return a control block. */
+/* Equality function for a string_tuple. */
-struct hash_control *
-hash_new_sized (unsigned long size)
+int
+eq_string_tuple (const void *a, const void *b)
{
- unsigned long alloc;
- struct hash_control *ret;
-
- ret = XNEW (struct hash_control);
- 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;
+ const string_tuple_t *ea = (const string_tuple_t *) a;
+ const string_tuple_t *eb = (const string_tuple_t *) b;
-#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;
+ return strcmp (ea->key, eb->key) == 0;
}
-struct hash_control *
-hash_new (void)
-{
- return hash_new_sized (gas_hash_table_size);
-}
+/* 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. */
-/* Delete a hash table, freeing all allocated memory. */
-
-void
-hash_die (struct hash_control *table)
+void **
+htab_insert (htab_t htab, void *element, int replace)
{
- 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)
-{
- 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++)
- {
- 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)
+ void **slot = htab_find_slot (htab, element, INSERT);
+ if (*slot != NULL)
{
-#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 slot;
}
-
+ *slot = element;
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 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
-}
-\f
-#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 <RETURN> 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);
-}
-
-/* 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);
- }
- }
+ 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));
}
-
-#endif /* TEST */
projects / thirdparty / binutils-gdb.git / blobdiff