/* hash.c -- gas hash table code
- Copyright (C) 1987, 90, 91, 92, 93, 94, 95, 96, 98, 1999
+ Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
+ 2000, 2001, 2002, 2003, 2005
Free Software Foundation, Inc.
This file is part of GAS, the GNU Assembler.
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. */
/* A hash table. */
-struct hash_control
-{
+struct hash_control {
/* The hash array. */
struct hash_entry **table;
/* The number of slots in the hash table. */
#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=<NUMBER> 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 ()
+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;
ret->deletions = 0;
#endif
- return ret;
+ return ret;
}
/* 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);
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 long hash;
+ size_t n;
+ unsigned int c;
unsigned int index;
struct hash_entry **list;
struct hash_entry *p;
#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;
++table->string_compares;
#endif
- if (strcmp (p->string, key) == 0)
+ if (strncmp (p->string, key, len) == 0 && p->string[len] == '\0')
{
if (prev != NULL)
{
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, PTR value)
{
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";
++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;
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, PTR value)
{
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->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;
table, this does nothing and returns NULL. */
PTR
-hash_replace (table, key, value)
- struct hash_control *table;
- const char *key;
- PTR value;
+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;
if the entry is not found. */
PTR
-hash_find (table, key)
- struct hash_control *table;
- const char *key;
+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. */
+
+PTR
+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;
for that entry, or NULL if there is no such entry. */
PTR
-hash_delete (table, key)
- struct hash_control *table;
- const char *key;
+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;
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, PTR value))
{
unsigned int i;
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;
/* 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)
-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 */
+/* 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;
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 ()
printf ("hash_test command: ");
gets (answer);
command = answer[0];
- if (isupper (command))
- command = tolower (command); /* ecch! */
+ command = TOLOWER (command); /* Ecch! */
switch (command)
{
case '#':
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':
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
free (value);
}
-
void
applicatee (string, value)
char *string;
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);
}
}
-#endif /* #ifdef TEST */
-
-/* end of hash.c */
+#endif /* TEST */
projects / deliverable / binutils-gdb.git / blobdiff