X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=bfd%2Fhash.c;h=5246145491ad54b015134bcc4bc4ea4ed605e177;hb=660df28acfa1b58c978d65d9cb26d37023f791ce;hp=9766eaf0cf233cf57e434ca79fccd96d3651122e;hpb=dc810e3900d47ab2eea86d50231ff2e70b596847;p=deliverable%2Fbinutils-gdb.git diff --git a/bfd/hash.c b/bfd/hash.c index 9766eaf0cf..5246145491 100644 --- a/bfd/hash.c +++ b/bfd/hash.c @@ -1,28 +1,29 @@ /* hash.c -- hash table routines for BFD - Copyright 1993, 1994, 1995, 1997, 1999, 2001 - Free Software Foundation, Inc. + Copyright (C) 1993-2019 Free Software Foundation, Inc. Written by Steve Chamberlain -This file is part of BFD, the Binary File Descriptor library. + This file is part of BFD, the Binary File Descriptor library. -This program 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 of the License, or -(at your option) any later version. + This program 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 3 of the License, or + (at your option) any later version. -This program is distributed in the hope that it will be useful, -but WITHOUT ANY WARRANTY; without even the implied warranty of -MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the -GNU General Public License for more details. + This program is distributed in the hope that it will be useful, + but WITHOUT ANY WARRANTY; without even the implied warranty of + MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the + GNU General Public License for more details. -You should have received a copy of the GNU General Public License -along with this program; if not, write to the Free Software -Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */ + You should have received a copy of the GNU General Public License + along with this program; if not, write to the Free Software + Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, + MA 02110-1301, USA. */ -#include "bfd.h" #include "sysdep.h" +#include "bfd.h" #include "libbfd.h" #include "objalloc.h" +#include "libiberty.h" /* SECTION @@ -67,7 +68,7 @@ SUBSECTION <> (if you know approximately how many entries you will need, the function <>, which takes a @var{size} argument, may be used). - <> returns <> if some sort of + <> returns <> if some sort of error occurs. @findex bfd_hash_newfunc @@ -87,6 +88,10 @@ SUBSECTION been allocated for a hash table. This will not free up the <> itself, which you must provide. +@findex bfd_hash_set_default_size + Use <> to set the default size of + hash table to use. + INODE Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables SUBSECTION @@ -96,24 +101,24 @@ SUBSECTION The function <> is used both to look up a string in the hash table and to create a new entry. - If the @var{create} argument is <>, <> + If the @var{create} argument is <>, <> will look up a string. If the string is found, it will returns a pointer to a <>. If the string is not found in the table <> will return <>. You should not modify any of the fields in the returns <>. - If the @var{create} argument is <>, the string will be + If the @var{create} argument is <>, the string will be entered into the hash table if it is not already there. Either way a pointer to a <> will be returned, either to the existing structure or to a newly created one. In this case, a <> return means that an error occurred. - If the @var{create} argument is <>, and a new entry is + If the @var{create} argument is <>, and a new entry is created, the @var{copy} argument is used to decide whether to copy the string onto the hash table objalloc or not. If - @var{copy} is passed as <>, you must be careful not to + @var{copy} is passed as <>, you must be careful not to deallocate or modify the string as long as the hash table exists. @@ -133,7 +138,7 @@ SUBSECTION generic pointer passed to <>. The function must return a <> value, which indicates whether to continue traversing the hash table. If the function returns - <>, <> will stop the traversal and + <>, <> will stop the traversal and return immediately. INODE @@ -225,26 +230,24 @@ SUBSUBSECTION EXAMPLE .struct bfd_hash_entry * -.@var{function_name} (entry, table, string) -. struct bfd_hash_entry *entry; -. struct bfd_hash_table *table; -. const char *string; +.@var{function_name} (struct bfd_hash_entry *entry, +. struct bfd_hash_table *table, +. const char *string) .{ . struct @var{entry_type} *ret = (@var{entry_type} *) entry; . . {* Allocate the structure if it has not already been allocated by a . derived class. *} -. if (ret == (@var{entry_type} *) NULL) +. if (ret == NULL) . { -. ret = ((@var{entry_type} *) -. bfd_hash_allocate (table, sizeof (@var{entry_type}))); -. if (ret == (@var{entry_type} *) NULL) -. return NULL; +. ret = bfd_hash_allocate (table, sizeof (* ret)); +. if (ret == NULL) +. return NULL; . } . . {* Call the allocation method of the base class. *} . ret = ((@var{entry_type} *) -. @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string)); +. @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string)); . . {* Initialize the local fields here. *} . @@ -295,79 +298,144 @@ SUBSUBSECTION */ /* The default number of entries to use when creating a hash table. */ -#define DEFAULT_SIZE (4051) +#define DEFAULT_SIZE 4051 + +/* The following function returns a nearest prime number which is + greater than N, and near a power of two. Copied from libiberty. + Returns zero for ridiculously large N to signify an error. */ + +static unsigned long +higher_prime_number (unsigned long n) +{ + /* These are primes that are near, but slightly smaller than, a + power of two. */ + static const unsigned long primes[] = + { + (unsigned long) 31, + (unsigned long) 61, + (unsigned long) 127, + (unsigned long) 251, + (unsigned long) 509, + (unsigned long) 1021, + (unsigned long) 2039, + (unsigned long) 4093, + (unsigned long) 8191, + (unsigned long) 16381, + (unsigned long) 32749, + (unsigned long) 65521, + (unsigned long) 131071, + (unsigned long) 262139, + (unsigned long) 524287, + (unsigned long) 1048573, + (unsigned long) 2097143, + (unsigned long) 4194301, + (unsigned long) 8388593, + (unsigned long) 16777213, + (unsigned long) 33554393, + (unsigned long) 67108859, + (unsigned long) 134217689, + (unsigned long) 268435399, + (unsigned long) 536870909, + (unsigned long) 1073741789, + (unsigned long) 2147483647, + /* 4294967291L */ + ((unsigned long) 2147483647) + ((unsigned long) 2147483644), + }; + + const unsigned long *low = &primes[0]; + const unsigned long *high = &primes[sizeof (primes) / sizeof (primes[0])]; + + while (low != high) + { + const unsigned long *mid = low + (high - low) / 2; + if (n >= *mid) + low = mid + 1; + else + high = mid; + } + + if (n >= *low) + return 0; + + return *low; +} + +static unsigned long bfd_default_hash_table_size = DEFAULT_SIZE; /* Create a new hash table, given a number of entries. */ -boolean -bfd_hash_table_init_n (table, newfunc, size) - struct bfd_hash_table *table; - struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *, - struct bfd_hash_table *, - const char *)); - unsigned int size; +bfd_boolean +bfd_hash_table_init_n (struct bfd_hash_table *table, + struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, + struct bfd_hash_table *, + const char *), + unsigned int entsize, + unsigned int size) { - unsigned int alloc; + unsigned long alloc; - alloc = size * sizeof (struct bfd_hash_entry *); + alloc = size; + alloc *= sizeof (struct bfd_hash_entry *); + if (alloc / sizeof (struct bfd_hash_entry *) != size) + { + bfd_set_error (bfd_error_no_memory); + return FALSE; + } - table->memory = (PTR) objalloc_create (); + table->memory = (void *) objalloc_create (); if (table->memory == NULL) { bfd_set_error (bfd_error_no_memory); - return false; + return FALSE; } - table->table = ((struct bfd_hash_entry **) - objalloc_alloc ((struct objalloc *) table->memory, alloc)); + table->table = (struct bfd_hash_entry **) + objalloc_alloc ((struct objalloc *) table->memory, alloc); if (table->table == NULL) { + bfd_hash_table_free (table); bfd_set_error (bfd_error_no_memory); - return false; + return FALSE; } - memset ((PTR) table->table, 0, alloc); + memset ((void *) table->table, 0, alloc); table->size = size; + table->entsize = entsize; + table->count = 0; + table->frozen = 0; table->newfunc = newfunc; - return true; + return TRUE; } /* Create a new hash table with the default number of entries. */ -boolean -bfd_hash_table_init (table, newfunc) - struct bfd_hash_table *table; - struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *, - struct bfd_hash_table *, - const char *)); +bfd_boolean +bfd_hash_table_init (struct bfd_hash_table *table, + struct bfd_hash_entry *(*newfunc) (struct bfd_hash_entry *, + struct bfd_hash_table *, + const char *), + unsigned int entsize) { - return bfd_hash_table_init_n (table, newfunc, DEFAULT_SIZE); + return bfd_hash_table_init_n (table, newfunc, entsize, + bfd_default_hash_table_size); } /* Free a hash table. */ void -bfd_hash_table_free (table) - struct bfd_hash_table *table; +bfd_hash_table_free (struct bfd_hash_table *table) { objalloc_free ((struct objalloc *) table->memory); table->memory = NULL; } -/* Look up a string in a hash table. */ - -struct bfd_hash_entry * -bfd_hash_lookup (table, string, create, copy) - struct bfd_hash_table *table; - const char *string; - boolean create; - boolean copy; +static inline unsigned long +bfd_hash_hash (const char *string, unsigned int *lenp) { - register const unsigned char *s; - register unsigned long hash; - register unsigned int c; - struct bfd_hash_entry *hashp; + const unsigned char *s; + unsigned long hash; unsigned int len; - unsigned int index; + unsigned int c; + BFD_ASSERT (string != NULL); hash = 0; len = 0; s = (const unsigned char *) string; @@ -375,14 +443,32 @@ bfd_hash_lookup (table, string, create, copy) { hash += c + (c << 17); hash ^= hash >> 2; - ++len; } + len = (s - (const unsigned char *) string) - 1; hash += len + (len << 17); hash ^= hash >> 2; + if (lenp != NULL) + *lenp = len; + return hash; +} + +/* Look up a string in a hash table. */ + +struct bfd_hash_entry * +bfd_hash_lookup (struct bfd_hash_table *table, + const char *string, + bfd_boolean create, + bfd_boolean copy) +{ + unsigned long hash; + struct bfd_hash_entry *hashp; + unsigned int len; + unsigned int _index; - index = hash % table->size; - for (hashp = table->table[index]; - hashp != (struct bfd_hash_entry *) NULL; + hash = bfd_hash_hash (string, &len); + _index = hash % table->size; + for (hashp = table->table[_index]; + hashp != NULL; hashp = hashp->next) { if (hashp->hash == hash @@ -391,47 +477,129 @@ bfd_hash_lookup (table, string, create, copy) } if (! create) - return (struct bfd_hash_entry *) NULL; + return NULL; - hashp = (*table->newfunc) ((struct bfd_hash_entry *) NULL, table, string); - if (hashp == (struct bfd_hash_entry *) NULL) - return (struct bfd_hash_entry *) NULL; if (copy) { - char *new; + char *new_string; - new = (char *) objalloc_alloc ((struct objalloc *) table->memory, - len + 1); - if (!new) + new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory, + len + 1); + if (!new_string) { bfd_set_error (bfd_error_no_memory); - return (struct bfd_hash_entry *) NULL; + return NULL; } - strcpy (new, string); - string = new; + memcpy (new_string, string, len + 1); + string = new_string; } + + return bfd_hash_insert (table, string, hash); +} + +/* Insert an entry in a hash table. */ + +struct bfd_hash_entry * +bfd_hash_insert (struct bfd_hash_table *table, + const char *string, + unsigned long hash) +{ + struct bfd_hash_entry *hashp; + unsigned int _index; + + hashp = (*table->newfunc) (NULL, table, string); + if (hashp == NULL) + return NULL; hashp->string = string; hashp->hash = hash; - hashp->next = table->table[index]; - table->table[index] = hashp; + _index = hash % table->size; + hashp->next = table->table[_index]; + table->table[_index] = hashp; + table->count++; + + if (!table->frozen && table->count > table->size * 3 / 4) + { + unsigned long newsize = higher_prime_number (table->size); + struct bfd_hash_entry **newtable; + unsigned int hi; + unsigned long alloc = newsize * sizeof (struct bfd_hash_entry *); + + /* If we can't find a higher prime, or we can't possibly alloc + that much memory, don't try to grow the table. */ + if (newsize == 0 || alloc / sizeof (struct bfd_hash_entry *) != newsize) + { + table->frozen = 1; + return hashp; + } + + newtable = ((struct bfd_hash_entry **) + objalloc_alloc ((struct objalloc *) table->memory, alloc)); + if (newtable == NULL) + { + table->frozen = 1; + return hashp; + } + memset (newtable, 0, alloc); + + for (hi = 0; hi < table->size; hi ++) + while (table->table[hi]) + { + struct bfd_hash_entry *chain = table->table[hi]; + struct bfd_hash_entry *chain_end = chain; + + while (chain_end->next && chain_end->next->hash == chain->hash) + chain_end = chain_end->next; + + table->table[hi] = chain_end->next; + _index = chain->hash % newsize; + chain_end->next = newtable[_index]; + newtable[_index] = chain; + } + table->table = newtable; + table->size = newsize; + } return hashp; } +/* Rename an entry in a hash table. */ + +void +bfd_hash_rename (struct bfd_hash_table *table, + const char *string, + struct bfd_hash_entry *ent) +{ + unsigned int _index; + struct bfd_hash_entry **pph; + + _index = ent->hash % table->size; + for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next) + if (*pph == ent) + break; + if (*pph == NULL) + abort (); + + *pph = ent->next; + ent->string = string; + ent->hash = bfd_hash_hash (string, NULL); + _index = ent->hash % table->size; + ent->next = table->table[_index]; + table->table[_index] = ent; +} + /* Replace an entry in a hash table. */ void -bfd_hash_replace (table, old, nw) - struct bfd_hash_table *table; - struct bfd_hash_entry *old; - struct bfd_hash_entry *nw; +bfd_hash_replace (struct bfd_hash_table *table, + struct bfd_hash_entry *old, + struct bfd_hash_entry *nw) { - unsigned int index; + unsigned int _index; struct bfd_hash_entry **pph; - index = old->hash % table->size; - for (pph = &table->table[index]; - (*pph) != (struct bfd_hash_entry *) NULL; + _index = old->hash % table->size; + for (pph = &table->table[_index]; + (*pph) != NULL; pph = &(*pph)->next) { if (*pph == old) @@ -444,29 +612,13 @@ bfd_hash_replace (table, old, nw) abort (); } -/* Base method for creating a new hash table entry. */ - -/*ARGSUSED*/ -struct bfd_hash_entry * -bfd_hash_newfunc (entry, table, string) - struct bfd_hash_entry *entry; - struct bfd_hash_table *table; - const char *string ATTRIBUTE_UNUSED; -{ - if (entry == (struct bfd_hash_entry *) NULL) - entry = ((struct bfd_hash_entry *) - bfd_hash_allocate (table, sizeof (struct bfd_hash_entry))); - return entry; -} - /* Allocate space in a hash table. */ -PTR -bfd_hash_allocate (table, size) - struct bfd_hash_table *table; - unsigned int size; +void * +bfd_hash_allocate (struct bfd_hash_table *table, + unsigned int size) { - PTR ret; + void * ret; ret = objalloc_alloc ((struct objalloc *) table->memory, size); if (ret == NULL && size != 0) @@ -474,26 +626,58 @@ bfd_hash_allocate (table, size) return ret; } +/* Base method for creating a new hash table entry. */ + +struct bfd_hash_entry * +bfd_hash_newfunc (struct bfd_hash_entry *entry, + struct bfd_hash_table *table, + const char *string ATTRIBUTE_UNUSED) +{ + if (entry == NULL) + entry = (struct bfd_hash_entry *) bfd_hash_allocate (table, + sizeof (* entry)); + return entry; +} + /* Traverse a hash table. */ void -bfd_hash_traverse (table, func, info) - struct bfd_hash_table *table; - boolean (*func) PARAMS ((struct bfd_hash_entry *, PTR)); - PTR info; +bfd_hash_traverse (struct bfd_hash_table *table, + bfd_boolean (*func) (struct bfd_hash_entry *, void *), + void * info) { unsigned int i; + table->frozen = 1; for (i = 0; i < table->size; i++) { struct bfd_hash_entry *p; for (p = table->table[i]; p != NULL; p = p->next) - { - if (! (*func) (p, info)) - return; - } + if (! (*func) (p, info)) + goto out; } + out: + table->frozen = 0; +} + +unsigned long +bfd_hash_set_default_size (unsigned long hash_size) +{ + /* Extend this prime list if you want more granularity of hash table size. */ + static const unsigned long hash_size_primes[] = + { + 31, 61, 127, 251, 509, 1021, 2039, 4091, 8191, 16381, 32749, 65537 + }; + unsigned int _index; + + /* Work out best prime number near the hash_size. */ + for (_index = 0; _index < ARRAY_SIZE (hash_size_primes) - 1; ++_index) + if (hash_size <= hash_size_primes[_index]) + break; + + bfd_default_hash_table_size = hash_size_primes[_index]; + return bfd_default_hash_table_size; } /* A few different object file formats (a.out, COFF, ELF) use a string @@ -532,33 +716,29 @@ struct bfd_strtab_hash struct strtab_hash_entry *last; /* Whether to precede strings with a two byte length, as in the XCOFF .debug section. */ - boolean xcoff; + bfd_boolean xcoff; }; -static struct bfd_hash_entry *strtab_hash_newfunc - PARAMS ((struct bfd_hash_entry *, struct bfd_hash_table *, const char *)); - /* Routine to create an entry in a strtab. */ static struct bfd_hash_entry * -strtab_hash_newfunc (entry, table, string) - struct bfd_hash_entry *entry; - struct bfd_hash_table *table; - const char *string; +strtab_hash_newfunc (struct bfd_hash_entry *entry, + struct bfd_hash_table *table, + const char *string) { struct strtab_hash_entry *ret = (struct strtab_hash_entry *) entry; /* Allocate the structure if it has not already been allocated by a subclass. */ - if (ret == (struct strtab_hash_entry *) NULL) - ret = ((struct strtab_hash_entry *) - bfd_hash_allocate (table, sizeof (struct strtab_hash_entry))); - if (ret == (struct strtab_hash_entry *) NULL) + if (ret == NULL) + ret = (struct strtab_hash_entry *) bfd_hash_allocate (table, + sizeof (* ret)); + if (ret == NULL) return NULL; /* Call the allocation method of the superclass. */ - ret = ((struct strtab_hash_entry *) - bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string)); + ret = (struct strtab_hash_entry *) + bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string); if (ret) { @@ -579,16 +759,17 @@ strtab_hash_newfunc (entry, table, string) /* Create a new strtab. */ struct bfd_strtab_hash * -_bfd_stringtab_init () +_bfd_stringtab_init (void) { struct bfd_strtab_hash *table; - bfd_size_type amt = sizeof (struct bfd_strtab_hash); + bfd_size_type amt = sizeof (* table); table = (struct bfd_strtab_hash *) bfd_malloc (amt); if (table == NULL) return NULL; - if (! bfd_hash_table_init (&table->table, strtab_hash_newfunc)) + if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc, + sizeof (struct strtab_hash_entry))) { free (table); return NULL; @@ -597,7 +778,7 @@ _bfd_stringtab_init () table->size = 0; table->first = NULL; table->last = NULL; - table->xcoff = false; + table->xcoff = FALSE; return table; } @@ -607,61 +788,61 @@ _bfd_stringtab_init () string. */ struct bfd_strtab_hash * -_bfd_xcoff_stringtab_init () +_bfd_xcoff_stringtab_init (void) { struct bfd_strtab_hash *ret; ret = _bfd_stringtab_init (); if (ret != NULL) - ret->xcoff = true; + ret->xcoff = TRUE; return ret; } /* Free a strtab. */ void -_bfd_stringtab_free (table) - struct bfd_strtab_hash *table; +_bfd_stringtab_free (struct bfd_strtab_hash *table) { bfd_hash_table_free (&table->table); free (table); } /* Get the index of a string in a strtab, adding it if it is not - already present. If HASH is false, we don't really use the hash - table, and we don't eliminate duplicate strings. */ + already present. If HASH is FALSE, we don't really use the hash + table, and we don't eliminate duplicate strings. If COPY is true + then store a copy of STR if creating a new entry. */ bfd_size_type -_bfd_stringtab_add (tab, str, hash, copy) - struct bfd_strtab_hash *tab; - const char *str; - boolean hash; - boolean copy; +_bfd_stringtab_add (struct bfd_strtab_hash *tab, + const char *str, + bfd_boolean hash, + bfd_boolean copy) { - register struct strtab_hash_entry *entry; + struct strtab_hash_entry *entry; if (hash) { - entry = strtab_hash_lookup (tab, str, true, copy); + entry = strtab_hash_lookup (tab, str, TRUE, copy); if (entry == NULL) return (bfd_size_type) -1; } else { - entry = ((struct strtab_hash_entry *) - bfd_hash_allocate (&tab->table, - sizeof (struct strtab_hash_entry))); + entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table, + sizeof (* entry)); if (entry == NULL) return (bfd_size_type) -1; if (! copy) entry->root.string = str; else { + size_t len = strlen (str) + 1; char *n; - n = (char *) bfd_hash_allocate (&tab->table, strlen (str) + 1); + n = (char *) bfd_hash_allocate (&tab->table, len); if (n == NULL) return (bfd_size_type) -1; + memcpy (n, str, len); entry->root.string = n; } entry->index = (bfd_size_type) -1; @@ -690,8 +871,7 @@ _bfd_stringtab_add (tab, str, hash, copy) /* Get the number of bytes in a strtab. */ bfd_size_type -_bfd_stringtab_size (tab) - struct bfd_strtab_hash *tab; +_bfd_stringtab_size (struct bfd_strtab_hash *tab) { return tab->size; } @@ -699,13 +879,11 @@ _bfd_stringtab_size (tab) /* Write out a strtab. ABFD must already be at the right location in the file. */ -boolean -_bfd_stringtab_emit (abfd, tab) - register bfd *abfd; - struct bfd_strtab_hash *tab; +bfd_boolean +_bfd_stringtab_emit (bfd *abfd, struct bfd_strtab_hash *tab) { - register boolean xcoff; - register struct strtab_hash_entry *entry; + bfd_boolean xcoff; + struct strtab_hash_entry *entry; xcoff = tab->xcoff; @@ -723,13 +901,13 @@ _bfd_stringtab_emit (abfd, tab) /* The output length includes the null byte. */ bfd_put_16 (abfd, (bfd_vma) len, buf); - if (bfd_bwrite ((PTR) buf, (bfd_size_type) 2, abfd) != 2) - return false; + if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2) + return FALSE; } - if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len) - return false; + if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len) + return FALSE; } - return true; + return TRUE; }