X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=gas%2Fhash.c;h=52360066468a9b674a3aed92a0d5a3cf6b18559e;hb=514cd3a0f589fa48ca7bc9504c36436c0cbefcb2;hp=29066339c3ac4c5a6aceb198b4acf18d00f15365;hpb=54d22525bbb6adc042a0005dfeb8a567db25865b;p=deliverable%2Fbinutils-gdb.git diff --git a/gas/hash.c b/gas/hash.c index 29066339c3..5236006646 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, 1999 - Free Software Foundation, Inc. + Copyright (C) 1987-2018 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,29 +15,25 @@ 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 -{ +struct hash_entry { /* Next entry for this hash code. */ struct hash_entry *next; /* String being hashed. */ @@ -47,13 +42,12 @@ struct hash_entry table. */ unsigned long hash; /* Pointer being stored in the hash table. */ - PTR data; + void *data; }; /* A hash table. */ -struct hash_control -{ +struct hash_control { /* The hash array. */ struct hash_entry **table; /* The number of slots in the hash table. */ @@ -72,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); @@ -99,14 +103,19 @@ hash_new () ret->deletions = 0; #endif - return ret; + 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); @@ -121,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; @@ -147,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; @@ -161,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; @@ -180,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) { @@ -205,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"; @@ -222,10 +217,10 @@ hash_insert (table, key, value) ++table->insertions; #endif - p = obstack_alloc (&table->memory, sizeof *p); + 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; @@ -238,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 { @@ -262,10 +254,10 @@ hash_jam (table, key, value) ++table->insertions; #endif - p = obstack_alloc (&table->memory, sizeof *p); + 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; @@ -278,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; @@ -305,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, 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, NULL, NULL); + p = hash_lookup (table, key, len, NULL, NULL); if (p == NULL) return NULL; @@ -322,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; @@ -343,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; } @@ -354,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; @@ -373,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; - const char *name; - struct hash_control *table; +hash_print_statistics (FILE *f ATTRIBUTE_UNUSED, + const char *name ATTRIBUTE_UNUSED, + struct hash_control *table ATTRIBUTE_UNUSED) { #ifdef HASH_STATISTICS unsigned int i; @@ -415,14 +412,23 @@ hash_print_statistics (f, name, table) /* 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 */ -#define STATBUFSIZE (12) /* we can have 12 statistics */ +/* 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]; -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 */ +/* 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; @@ -430,8 +436,9 @@ char *value; int size; int used; char command; -int number; /* number 0:TABLES-1 of current hashed */ - /* symbol table */ + +/* Number 0:TABLES-1 of current hashed symbol table. */ +int number; int main () @@ -449,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 '#': @@ -460,8 +466,8 @@ main () case '?': for (pp = hashtable; pp < hashtable + TABLES; pp++) { - printf ("address of hash table #%d control block is %xx\n" - ,pp - hashtable, *pp); + printf ("address of hash table #%d control block is %xx\n", + pp - hashtable, *pp); } break; case 'a': @@ -537,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 @@ -561,7 +557,6 @@ destroy (string, value) free (value); } - void applicatee (string, value) char *string; @@ -570,11 +565,12 @@ applicatee (string, value) printf ("%.20s-%.20s\n", string, value); } +/* Determine number: what hash table to use. + Also determine h: points to hash_control. */ + void -whattable () /* determine number: what hash table to use */ - /* also determine h: points to hash_control */ +whattable () { - for (;;) { printf (" what hash table (%d:%d) ? ", 0, TABLES - 1); @@ -596,6 +592,4 @@ whattable () /* determine number: what hash table to use */ } } -#endif /* #ifdef TEST */ - -/* end of hash.c */ +#endif /* TEST */