X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=gas%2Fhash.c;h=c484588606611ebf27d26e17ae0605f8d4cc190e;hb=d402189f2faa0aaa9fb8ad4669fdf0059946cd8a;hp=f2e98a69e8b0409288211c309eccabc71c874311;hpb=b041f888acb608ad6d70d30e5a6d19ae23a9b69c;p=deliverable%2Fbinutils-gdb.git diff --git a/gas/hash.c b/gas/hash.c index f2e98a69e8..c484588606 100644 --- a/gas/hash.c +++ b/gas/hash.c @@ -1,12 +1,11 @@ /* hash.c -- gas hash table code - Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 98, 99, 2000 - Free Software Foundation, Inc. + Copyright (C) 1987-2020 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 2, or (at your option) + 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, @@ -16,25 +15,22 @@ 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. */ + 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 - asssembler. The assembler does not need to derive structures that + 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" -/* The default number of entries to use when creating a hash table. */ - -#define DEFAULT_SIZE (4051) - /* An entry in a hash table. */ struct hash_entry { @@ -46,7 +42,7 @@ struct hash_entry { table. */ unsigned long hash; /* Pointer being stored in the hash table. */ - PTR data; + void *data; }; /* A hash table. */ @@ -70,18 +66,28 @@ struct hash_control { #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 () +hash_new_sized (unsigned long size) { - unsigned int size; + unsigned long alloc; struct hash_control *ret; - unsigned int alloc; - - size = DEFAULT_SIZE; - ret = (struct hash_control *) xmalloc (sizeof *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); @@ -100,11 +106,16 @@ hash_new () 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 (table) - struct hash_control *table; +hash_die (struct hash_control *table) { obstack_free (&table->memory, 0); free (table); @@ -119,23 +130,14 @@ hash_die (table) 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; +hash_lookup (struct hash_control *table, const char *key, size_t len, + struct hash_entry ***plist, unsigned long *phash) { - register unsigned long hash; - unsigned int len; - register const unsigned char *s; - register unsigned int c; - unsigned int index; + unsigned long hash; + size_t n; + unsigned int c; + unsigned int hindex; struct hash_entry **list; struct hash_entry *p; struct hash_entry *prev; @@ -145,13 +147,11 @@ hash_lookup (table, key, plist, phash) #endif hash = 0; - len = 0; - s = (const unsigned char *) key; - while ((c = *s++) != '\0') + for (n = 0; n < len; n++) { + c = key[n]; hash += c + (c << 17); hash ^= hash >> 2; - ++len; } hash += len + (len << 17); hash ^= hash >> 2; @@ -159,8 +159,8 @@ hash_lookup (table, key, plist, phash) if (phash != NULL) *phash = hash; - index = hash % table->size; - list = table->table + index; + hindex = hash % table->size; + list = table->table + hindex; if (plist != NULL) *plist = list; @@ -178,7 +178,7 @@ hash_lookup (table, key, plist, phash) ++table->string_compares; #endif - if (strcmp (p->string, key) == 0) + if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0') { if (prev != NULL) { @@ -203,16 +203,13 @@ hash_lookup (table, key, plist, phash) hash table. */ const char * -hash_insert (table, key, value) - struct hash_control *table; - const char *key; - PTR value; +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, &list, &hash); + p = hash_lookup (table, key, strlen (key), &list, &hash); if (p != NULL) return "exists"; @@ -223,7 +220,7 @@ hash_insert (table, key, value) p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); p->string = key; p->hash = hash; - p->data = value; + p->data = val; p->next = *list; *list = p; @@ -236,23 +233,20 @@ hash_insert (table, key, value) error. If an entry already exists, its value is replaced. */ const char * -hash_jam (table, key, value) - struct hash_control *table; - const char *key; - PTR value; +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, &list, &hash); + p = hash_lookup (table, key, strlen (key), &list, &hash); if (p != NULL) { #ifdef HASH_STATISTICS ++table->replacements; #endif - p->data = value; + p->data = val; } else { @@ -263,7 +257,7 @@ hash_jam (table, key, value) p = (struct hash_entry *) obstack_alloc (&table->memory, sizeof (*p)); p->string = key; p->hash = hash; - p->data = value; + p->data = val; p->next = *list; *list = p; @@ -276,16 +270,13 @@ hash_jam (table, key, value) 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; +void * +hash_replace (struct hash_control *table, const char *key, void *value) { struct hash_entry *p; - PTR ret; + void *ret; - p = hash_lookup (table, key, NULL, NULL); + p = hash_lookup (table, key, strlen (key), NULL, NULL); if (p == NULL) return NULL; @@ -303,14 +294,27 @@ hash_replace (table, key, value) /* Find an entry in a hash table, returning its value. Returns NULL if the entry is not found. */ -PTR -hash_find (table, key) - struct hash_control *table; - const char *key; +void * +hash_find (struct hash_control *table, const char *key) { struct hash_entry *p; - p = hash_lookup (table, key, NULL, NULL); + 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; @@ -320,15 +324,13 @@ hash_find (table, key) /* 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; +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, &list, NULL); + p = hash_lookup (table, key, strlen (key), &list, NULL); if (p == NULL) return NULL; @@ -341,9 +343,8 @@ hash_delete (table, key) *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. */ + if (freeme) + obstack_free (&table->memory, p); return p->data; } @@ -352,9 +353,8 @@ hash_delete (table, key) hash table. */ void -hash_traverse (table, pfn) - struct hash_control *table; - void (*pfn) PARAMS ((const char *key, PTR value)); +hash_traverse (struct hash_control *table, + void (*pfn) (const char *key, void *value)) { unsigned int i; @@ -371,10 +371,9 @@ hash_traverse (table, pfn) name of the hash table, used for printing a header. */ void -hash_print_statistics (f, name, table) - FILE *f ATTRIBUTE_UNUSED; - const char *name ATTRIBUTE_UNUSED; - struct hash_control *table ATTRIBUTE_UNUSED; +hash_print_statistics (FILE *f ATTRIBUTE_UNUSED, + const char *name ATTRIBUTE_UNUSED, + struct hash_control *table ATTRIBUTE_UNUSED) { #ifdef HASH_STATISTICS unsigned int i; @@ -428,7 +427,7 @@ char answer[100]; /* We test many hash tables at once. */ char *hashtable[TABLES]; -/* Points to curent hash_control. */ +/* Points to current hash_control. */ char *h; char **pp; char *p; @@ -457,8 +456,7 @@ main () printf ("hash_test command: "); gets (answer); command = answer[0]; - if (isupper (command)) - command = tolower (command); /* Ecch! */ + command = TOLOWER (command); /* Ecch! */ switch (command) { case '#': @@ -545,19 +543,9 @@ char * what (description) char *description; { - char *retval; - char *malloc (); - printf (" %s : ", description); gets (answer); - /* Will one day clean up answer here. */ - retval = malloc (strlen (answer) + 1); - if (!retval) - { - error ("room"); - } - (void) strcpy (retval, answer); - return (retval); + return xstrdup (answer); } void