X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=bfd%2Fhash.c;h=fc3177331b57de3b29a7b40411b650e726f011f5;hb=a541e3cedd262e3e67cc17145be7fa7cbe035b1d;hp=8ea4375d5c70172be3d513351fdd4785c6c4ac78;hpb=e98fe4f7b54cbdf29aef9287bbb1bea8801dd05a;p=deliverable%2Fbinutils-gdb.git diff --git a/bfd/hash.c b/bfd/hash.c index 8ea4375d5c..fc3177331b 100644 --- a/bfd/hash.c +++ b/bfd/hash.c @@ -1,27 +1,29 @@ /* hash.c -- hash table routines for BFD - Copyright (C) 1993, 94 Free Software Foundation, Inc. + Copyright 1993, 1994, 1995, 1997, 1999, 2001, 2002, 2003, 2004, 2005 + 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 2 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 "libbfd.h" -#include "obstack.h" +#include "objalloc.h" +#include "libiberty.h" /* SECTION @@ -66,26 +68,30 @@ 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 The function <> take as an argument a function to use to create new entries. For a basic hash table, use the function <>. @xref{Deriving - a New Hash Table Type} for why you would want to use a + a New Hash Table Type}, for why you would want to use a different value for this argument. @findex bfd_hash_allocate - <> will create an obstack which will be + <> will create an objalloc which will be used to allocate new entries. You may allocate memory on this - obstack using <>. + objalloc using <>. @findex bfd_hash_table_free Use <> to free up all the memory that has 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 @@ -95,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 obstack or not. If - @var{copy} is passed as <>, you must be careful not to + copy the string onto the hash table objalloc or not. If + @var{copy} is passed as <>, you must be careful not to deallocate or modify the string as long as the hash table exists. @@ -132,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 @@ -224,20 +230,18 @@ 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) +. ret = bfd_hash_allocate (table, sizeof (* ret)); +. if (ret == NULL) . return NULL; . } . @@ -268,7 +272,7 @@ SUBSUBSECTION Write other derived routines You will want to write other routines for your new hash table, - as well. + as well. You will want an initialization routine which calls the initialization routine of the hash table you are deriving from @@ -293,81 +297,76 @@ SUBSUBSECTION <> in aoutx.h. */ -/* Obstack allocation and deallocation routines. */ -#define obstack_chunk_alloc malloc -#define obstack_chunk_free free - /* The default number of entries to use when creating a hash table. */ -#define DEFAULT_SIZE (4051) +#define DEFAULT_SIZE 4051 +static size_t 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 size) { unsigned int alloc; alloc = size * sizeof (struct bfd_hash_entry *); - if (!obstack_begin (&table->memory, alloc)) + + 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 **) - obstack_alloc (&table->memory, alloc)); - if (!table->table) + table->table = objalloc_alloc ((struct objalloc *) table->memory, alloc); + if (table->table == NULL) { 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->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 *)) { - return bfd_hash_table_init_n (table, newfunc, DEFAULT_SIZE); + return bfd_hash_table_init_n (table, newfunc, 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) { - obstack_free (&table->memory, (PTR) NULL); + objalloc_free (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; +bfd_hash_lookup (struct bfd_hash_table *table, + const char *string, + bfd_boolean create, + bfd_boolean copy) { - register const unsigned char *s; - register unsigned long hash; - register unsigned int c; + const unsigned char *s; + unsigned long hash; + unsigned int c; struct bfd_hash_entry *hashp; unsigned int len; unsigned int index; - + hash = 0; len = 0; s = (const unsigned char *) string; @@ -375,14 +374,14 @@ 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; index = hash % table->size; for (hashp = table->table[index]; - hashp != (struct bfd_hash_entry *) NULL; + hashp != NULL; hashp = hashp->next) { if (hashp->hash == hash @@ -391,22 +390,22 @@ 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; + hashp = (*table->newfunc) (NULL, table, string); + if (hashp == NULL) + return NULL; if (copy) { char *new; - new = (char *) obstack_alloc (&table->memory, len + 1); + new = objalloc_alloc ((struct objalloc *) table->memory, len + 1); if (!new) { bfd_set_error (bfd_error_no_memory); - return (struct bfd_hash_entry *) NULL; + return NULL; } - strcpy (new, string); + memcpy (new, string, len + 1); string = new; } hashp->string = string; @@ -420,17 +419,16 @@ bfd_hash_lookup (table, string, create, copy) /* 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; struct bfd_hash_entry **pph; index = old->hash % table->size; for (pph = &table->table[index]; - (*pph) != (struct bfd_hash_entry *) NULL; + (*pph) != NULL; pph = &(*pph)->next) { if (*pph == old) @@ -443,43 +441,38 @@ 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; -{ - 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 = obstack_alloc (&table->memory, size); + ret = objalloc_alloc ((struct objalloc *) table->memory, size); if (ret == NULL && size != 0) bfd_set_error (bfd_error_no_memory); 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 = 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; @@ -488,13 +481,29 @@ bfd_hash_traverse (table, func, info) struct bfd_hash_entry *p; for (p = table->table[i]; p != NULL; p = p->next) - { - if (! (*func) (p, info)) - return; - } + if (! (*func) (p, info)) + return; } } +void +bfd_hash_set_default_size (bfd_size_type hash_size) +{ + /* Extend this prime list if you want more granularity of hash table size. */ + static const bfd_size_type hash_size_primes[] = + { + 1021, 4051, 8599, 16699 + }; + size_t 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]; +} + /* A few different object file formats (a.out, COFF, ELF) use a string table. These functions support adding strings to a string table, returning the byte offset, and writing out the table. @@ -531,33 +540,28 @@ 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 = 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) { @@ -578,18 +582,16 @@ 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 (* table); - table = (struct bfd_strtab_hash *) malloc (sizeof (struct bfd_strtab_hash)); + table = bfd_malloc (amt); if (table == NULL) - { - bfd_set_error (bfd_error_no_memory); - return NULL; - } + return NULL; - if (! bfd_hash_table_init (&table->table, strtab_hash_newfunc)) + if (! bfd_hash_table_init (& table->table, strtab_hash_newfunc)) { free (table); return NULL; @@ -598,7 +600,7 @@ _bfd_stringtab_init () table->size = 0; table->first = NULL; table->last = NULL; - table->xcoff = false; + table->xcoff = FALSE; return table; } @@ -608,50 +610,46 @@ _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 + already present. If HASH is FALSE, we don't really use the hash table, and we don't eliminate duplicate strings. */ 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 = bfd_hash_allocate (&tab->table, sizeof (* entry)); if (entry == NULL) return (bfd_size_type) -1; if (! copy) @@ -660,7 +658,7 @@ _bfd_stringtab_add (tab, str, hash, copy) { char *n; - n = (char *) bfd_hash_allocate (&tab->table, strlen (str) + 1); + n = bfd_hash_allocate (&tab->table, strlen (str) + 1); if (n == NULL) return (bfd_size_type) -1; entry->root.string = n; @@ -691,8 +689,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; } @@ -700,20 +697,18 @@ _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; for (entry = tab->first; entry != NULL; entry = entry->next) { - register const char *str; - register size_t len; + const char *str; + size_t len; str = entry->root.string; len = strlen (str) + 1; @@ -723,14 +718,14 @@ _bfd_stringtab_emit (abfd, tab) bfd_byte buf[2]; /* The output length includes the null byte. */ - bfd_put_16 (abfd, len, buf); - if (bfd_write ((PTR) buf, 1, 2, abfd) != 2) - return false; + bfd_put_16 (abfd, (bfd_vma) len, buf); + if (bfd_bwrite ((void *) buf, (bfd_size_type) 2, abfd) != 2) + return FALSE; } - if (bfd_write ((PTR) str, 1, len, abfd) != len) - return false; + if (bfd_bwrite ((void *) str, (bfd_size_type) len, abfd) != len) + return FALSE; } - return true; + return TRUE; }