/* hash.c -- gas hash table code
- Copyright 1987, 1990, 1991, 1992, 1993, 1994, 1995, 1996, 1998, 1999,
- 2000, 2001, 2002, 2003, 2005
- 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,
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
table. */
unsigned long hash;
/* Pointer being stored in the hash table. */
- PTR data;
+ void *data;
};
/* A hash table. */
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];
+ gas_hash_table_size = bfd_hash_set_default_size (size);
}
/* Create a hash table. This return a control block. */
struct hash_control *
-hash_new (void)
+hash_new_sized (unsigned long size)
{
- unsigned long size;
unsigned long alloc;
struct hash_control *ret;
- size = get_gas_hash_table_size ();
-
- ret = xmalloc (sizeof *ret);
+ ret = XNEW (struct hash_control);
obstack_begin (&ret->memory, chunksize);
alloc = size * sizeof (struct hash_entry *);
- ret->table = obstack_alloc (&ret->memory, alloc);
+ ret->table = (struct hash_entry **) obstack_alloc (&ret->memory, alloc);
memset (ret->table, 0, alloc);
ret->size = size;
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
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 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;
#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;
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;
++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 (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";
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;
error. If an entry already exists, its value is replaced. */
const char *
-hash_jam (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
{
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;
value stored for the entry. If the entry is not found in the hash
table, this does nothing and returns NULL. */
-PTR
-hash_replace (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;
/* Find an entry in a hash table, returning its value. Returns NULL
if the entry is not found. */
-PTR
+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;
/* 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 (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;
*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;
}
void
hash_traverse (struct hash_control *table,
- void (*pfn) (const char *key, PTR value))
+ void (*pfn) (const char *key, void *value))
{
unsigned int i;
projects / deliverable / binutils-gdb.git / blobdiff