X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=gas%2Fhash.c;h=6977ceeb53284c98e986d653f5152be82577547f;hb=6e29ef6d2828415f5ee2d6e1690d13bc40a8d5d4;hp=85c6080625e7a73fcea037f4261f012be050dcfe;hpb=2da5c03714e1f97bb83d05114e97dcf92eb17b64;p=deliverable%2Fbinutils-gdb.git diff --git a/gas/hash.c b/gas/hash.c index 85c6080625..6977ceeb53 100644 --- a/gas/hash.c +++ b/gas/hash.c @@ -1,6 +1,6 @@ /* hash.c -- gas hash table code Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999, - 2000, 2001, 2002, 2003 + 2000, 2001, 2002, 2003, 2005 Free Software Foundation, Inc. This file is part of GAS, the GNU Assembler. @@ -17,8 +17,8 @@ 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 @@ -33,10 +33,6 @@ #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 { @@ -72,21 +68,55 @@ 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 = size; +} + +/* FIXME: This function should be amalgmated with bfd/hash.c:bfd_hash_set_default_size(). */ +static unsigned long +get_gas_hash_table_size (void) +{ + /* Extend this prime list if you want more granularity of hash table size. */ + static const unsigned long hash_size_primes[] = + { + 1021, 4051, 8599, 16699, 65537 + }; + unsigned int index; + + /* Work out the best prime number near the hash_size. + FIXME: This could be a more sophisticated algorithm, + but is it really worth implementing it ? */ + for (index = 0; index < ARRAY_SIZE (hash_size_primes) - 1; ++index) + if (gas_hash_table_size <= hash_size_primes[index]) + break; + + return hash_size_primes[index]; +} + /* Create a hash table. This return a control block. */ struct hash_control * hash_new (void) { - unsigned int size; + unsigned long size; + unsigned long alloc; struct hash_control *ret; - unsigned int alloc; - size = DEFAULT_SIZE; + size = get_gas_hash_table_size (); - ret = (struct hash_control *) xmalloc (sizeof *ret); + ret = xmalloc (sizeof *ret); obstack_begin (&ret->memory, chunksize); alloc = size * sizeof (struct hash_entry *); - ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc); + ret->table = obstack_alloc (&ret->memory, alloc); memset (ret->table, 0, alloc); ret->size = size; @@ -120,19 +150,13 @@ hash_die (struct hash_control *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 (struct hash_control *, - const char *, - struct hash_entry ***, - unsigned long *); - static struct hash_entry * -hash_lookup (struct hash_control *table, const char *key, +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 long hash; + size_t n; + unsigned int c; unsigned int index; struct hash_entry **list; struct hash_entry *p; @@ -143,13 +167,11 @@ hash_lookup (struct hash_control *table, const char *key, #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; @@ -176,7 +198,7 @@ hash_lookup (struct hash_control *table, const char *key, ++table->string_compares; #endif - if (strcmp (p->string, key) == 0) + if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0') { if (prev != NULL) { @@ -207,7 +229,7 @@ hash_insert (struct hash_control *table, const char *key, PTR value) 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"; @@ -237,7 +259,7 @@ hash_jam (struct hash_control *table, const char *key, PTR value) 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 @@ -274,7 +296,7 @@ hash_replace (struct hash_control *table, const char *key, PTR value) struct hash_entry *p; PTR ret; - p = hash_lookup (table, key, NULL, NULL); + p = hash_lookup (table, key, strlen (key), NULL, NULL); if (p == NULL) return NULL; @@ -297,7 +319,22 @@ 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. */ + +PTR +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; @@ -313,7 +350,7 @@ hash_delete (struct hash_control *table, const char *key) 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;