X-Git-Url: http://drtracing.org/?a=blobdiff_plain;f=bfd%2Fhash.c;h=2b06b922ce3efff387eb065183646fcbfd0772bd;hb=01b9137461f11882a03589e8c40fd718b0c09a09;hp=8ea4375d5c70172be3d513351fdd4785c6c4ac78;hpb=e98fe4f7b54cbdf29aef9287bbb1bea8801dd05a;p=deliverable%2Fbinutils-gdb.git diff --git a/bfd/hash.c b/bfd/hash.c index 8ea4375d5c..2b06b922ce 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 + 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., 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 @@ -268,7 +274,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,16 +299,13 @@ 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_boolean bfd_hash_table_init_n (table, newfunc, size) struct bfd_hash_table *table; struct bfd_hash_entry *(*newfunc) PARAMS ((struct bfd_hash_entry *, @@ -313,34 +316,36 @@ bfd_hash_table_init_n (table, newfunc, size) unsigned int alloc; alloc = size * sizeof (struct bfd_hash_entry *); - if (!obstack_begin (&table->memory, alloc)) + + table->memory = (PTR) 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) + 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); table->size = size; table->newfunc = newfunc; - return true; + return TRUE; } /* Create a new hash table with the default number of entries. */ -boolean +bfd_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 *)); { - 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. */ @@ -349,7 +354,8 @@ void bfd_hash_table_free (table) struct bfd_hash_table *table; { - obstack_free (&table->memory, (PTR) NULL); + objalloc_free ((struct objalloc *) table->memory); + table->memory = NULL; } /* Look up a string in a hash table. */ @@ -358,8 +364,8 @@ struct bfd_hash_entry * bfd_hash_lookup (table, string, create, copy) struct bfd_hash_table *table; const char *string; - boolean create; - boolean copy; + bfd_boolean create; + bfd_boolean copy; { register const unsigned char *s; register unsigned long hash; @@ -367,7 +373,7 @@ bfd_hash_lookup (table, string, create, copy) struct bfd_hash_entry *hashp; unsigned int len; unsigned int index; - + hash = 0; len = 0; s = (const unsigned char *) string; @@ -375,8 +381,8 @@ 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; @@ -400,13 +406,14 @@ bfd_hash_lookup (table, string, create, copy) { char *new; - new = (char *) obstack_alloc (&table->memory, len + 1); + new = (char *) objalloc_alloc ((struct objalloc *) table->memory, + len + 1); if (!new) { bfd_set_error (bfd_error_no_memory); return (struct bfd_hash_entry *) NULL; } - strcpy (new, string); + memcpy (new, string, len + 1); string = new; } hashp->string = string; @@ -445,12 +452,11 @@ bfd_hash_replace (table, old, nw) /* 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; + const char *string ATTRIBUTE_UNUSED; { if (entry == (struct bfd_hash_entry *) NULL) entry = ((struct bfd_hash_entry *) @@ -467,7 +473,7 @@ bfd_hash_allocate (table, size) { PTR 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; @@ -478,7 +484,7 @@ bfd_hash_allocate (table, size) void bfd_hash_traverse (table, func, info) struct bfd_hash_table *table; - boolean (*func) PARAMS ((struct bfd_hash_entry *, PTR)); + bfd_boolean (*func) PARAMS ((struct bfd_hash_entry *, PTR)); PTR info; { unsigned int i; @@ -495,6 +501,24 @@ bfd_hash_traverse (table, func, info) } } +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,7 +555,7 @@ 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 @@ -581,13 +605,11 @@ struct bfd_strtab_hash * _bfd_stringtab_init () { struct bfd_strtab_hash *table; + bfd_size_type amt = sizeof (struct bfd_strtab_hash); - table = (struct bfd_strtab_hash *) malloc (sizeof (struct bfd_strtab_hash)); + table = (struct bfd_strtab_hash *) 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)) { @@ -598,7 +620,7 @@ _bfd_stringtab_init () table->size = 0; table->first = NULL; table->last = NULL; - table->xcoff = false; + table->xcoff = FALSE; return table; } @@ -614,7 +636,7 @@ _bfd_xcoff_stringtab_init () ret = _bfd_stringtab_init (); if (ret != NULL) - ret->xcoff = true; + ret->xcoff = TRUE; return ret; } @@ -629,21 +651,21 @@ _bfd_stringtab_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_boolean hash; + bfd_boolean copy; { register 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; } @@ -700,20 +722,20 @@ _bfd_stringtab_size (tab) /* Write out a strtab. ABFD must already be at the right location in the file. */ -boolean +bfd_boolean _bfd_stringtab_emit (abfd, tab) register bfd *abfd; struct bfd_strtab_hash *tab; { - register boolean xcoff; + register bfd_boolean xcoff; register 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 +745,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 ((PTR) buf, (bfd_size_type) 2, abfd) != 2) + return FALSE; } - if (bfd_write ((PTR) str, 1, len, abfd) != len) - return false; + if (bfd_bwrite ((PTR) str, (bfd_size_type) len, abfd) != len) + return FALSE; } - return true; + return TRUE; }