X-Git-Url: http://git.efficios.com/?a=blobdiff_plain;f=bfd%2Fhash.c;h=5246145491ad54b015134bcc4bc4ea4ed605e177;hb=036003a671233c43e35b3004f91e4cbd61255cf3;hp=2b67dc5eb020c5a9493e0c0c97790caaa52c091a;hpb=3db64b009284dda3a1ce10a91beb1297475e60a7;p=deliverable%2Fbinutils-gdb.git diff --git a/bfd/hash.c b/bfd/hash.c index 2b67dc5eb0..5246145491 100644 --- a/bfd/hash.c +++ b/bfd/hash.c @@ -1,13 +1,12 @@ /* hash.c -- hash table routines for BFD - Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005, - 2006, 2007 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 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 + 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, @@ -17,7 +16,8 @@ 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. */ + Foundation, Inc., 51 Franklin Street - Fifth Floor, Boston, + MA 02110-1301, USA. */ #include "sysdep.h" #include "bfd.h" @@ -231,8 +231,8 @@ EXAMPLE .struct bfd_hash_entry * .@var{function_name} (struct bfd_hash_entry *entry, -. struct bfd_hash_table *table, -. const char *string) +. struct bfd_hash_table *table, +. const char *string) .{ . struct @var{entry_type} *ret = (@var{entry_type} *) entry; . @@ -242,12 +242,12 @@ EXAMPLE . { . ret = bfd_hash_allocate (table, sizeof (* ret)); . if (ret == NULL) -. return 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. *} . @@ -309,28 +309,37 @@ 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) 127, - (unsigned long) 2039, - (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, + 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), + ((unsigned long) 2147483647) + ((unsigned long) 2147483644), }; const unsigned long *low = &primes[0]; @@ -351,7 +360,7 @@ higher_prime_number (unsigned long n) return *low; } -static size_t bfd_default_hash_table_size = DEFAULT_SIZE; +static unsigned long bfd_default_hash_table_size = DEFAULT_SIZE; /* Create a new hash table, given a number of entries. */ @@ -363,9 +372,15 @@ bfd_hash_table_init_n (struct bfd_hash_table *table, 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 = (void *) objalloc_create (); if (table->memory == NULL) @@ -373,9 +388,11 @@ bfd_hash_table_init_n (struct bfd_hash_table *table, bfd_set_error (bfd_error_no_memory); return FALSE; } - table->table = 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; } @@ -406,25 +423,19 @@ bfd_hash_table_init (struct bfd_hash_table *table, void bfd_hash_table_free (struct bfd_hash_table *table) { - objalloc_free (table->memory); + objalloc_free ((struct objalloc *) table->memory); table->memory = NULL; } -/* 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) +static inline unsigned long +bfd_hash_hash (const char *string, unsigned int *lenp) { const unsigned char *s; unsigned long hash; - unsigned int c; - struct bfd_hash_entry *hashp; unsigned int len; - unsigned int index; + unsigned int c; + BFD_ASSERT (string != NULL); hash = 0; len = 0; s = (const unsigned char *) string; @@ -436,9 +447,27 @@ bfd_hash_lookup (struct bfd_hash_table *table, 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]; + hash = bfd_hash_hash (string, &len); + _index = hash % table->size; + for (hashp = table->table[_index]; hashp != NULL; hashp = hashp->next) { @@ -450,26 +479,42 @@ bfd_hash_lookup (struct bfd_hash_table *table, if (! create) return NULL; - hashp = (*table->newfunc) (NULL, table, string); - if (hashp == NULL) - return NULL; if (copy) { - char *new; + char *new_string; - new = 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 NULL; } - memcpy (new, string, len + 1); - 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) @@ -489,22 +534,26 @@ bfd_hash_lookup (struct bfd_hash_table *table, newtable = ((struct bfd_hash_entry **) objalloc_alloc ((struct objalloc *) table->memory, alloc)); - memset ((PTR) newtable, 0, 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; - int index; 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; + _index = chain->hash % newsize; + chain_end->next = newtable[_index]; + newtable[_index] = chain; } table->table = newtable; table->size = newsize; @@ -513,6 +562,31 @@ bfd_hash_lookup (struct bfd_hash_table *table, 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 @@ -520,11 +594,11 @@ 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]; + _index = old->hash % table->size; + for (pph = &table->table[_index]; (*pph) != NULL; pph = &(*pph)->next) { @@ -560,7 +634,8 @@ bfd_hash_newfunc (struct bfd_hash_entry *entry, const char *string ATTRIBUTE_UNUSED) { if (entry == NULL) - entry = bfd_hash_allocate (table, sizeof (* entry)); + entry = (struct bfd_hash_entry *) bfd_hash_allocate (table, + sizeof (* entry)); return entry; } @@ -586,22 +661,23 @@ bfd_hash_traverse (struct bfd_hash_table *table, table->frozen = 0; } -void -bfd_hash_set_default_size (bfd_size_type hash_size) +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 bfd_size_type hash_size_primes[] = + static const unsigned long hash_size_primes[] = { - 251, 509, 1021, 2039, 4051, 8599, 16699, 32749 + 31, 61, 127, 251, 509, 1021, 2039, 4091, 8191, 16381, 32749, 65537 }; - size_t index; + 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]) + 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]; + 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 @@ -655,7 +731,8 @@ strtab_hash_newfunc (struct bfd_hash_entry *entry, /* Allocate the structure if it has not already been allocated by a subclass. */ if (ret == NULL) - ret = bfd_hash_allocate (table, sizeof (* ret)); + ret = (struct strtab_hash_entry *) bfd_hash_allocate (table, + sizeof (* ret)); if (ret == NULL) return NULL; @@ -687,7 +764,7 @@ _bfd_stringtab_init (void) struct bfd_strtab_hash *table; bfd_size_type amt = sizeof (* table); - table = bfd_malloc (amt); + table = (struct bfd_strtab_hash *) bfd_malloc (amt); if (table == NULL) return NULL; @@ -732,7 +809,8 @@ _bfd_stringtab_free (struct bfd_strtab_hash *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. */ + 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 (struct bfd_strtab_hash *tab, @@ -750,18 +828,21 @@ _bfd_stringtab_add (struct bfd_strtab_hash *tab, } else { - entry = bfd_hash_allocate (&tab->table, sizeof (* 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 = 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;