| @section Hash Tables |
| @cindex Hash tables |
| BFD provides a simple set of hash table functions. Routines |
| are provided to initialize a hash table, to free a hash table, |
| to look up a string in a hash table and optionally create an |
| entry for it, and to traverse a hash table. There is |
| currently no routine to delete an string from a hash table. |
| |
| The basic hash table does not permit any data to be stored |
| with a string. However, a hash table is designed to present a |
| base class from which other types of hash tables may be |
| derived. These derived types may store additional information |
| with the string. Hash tables were implemented in this way, |
| rather than simply providing a data pointer in a hash table |
| entry, because they were designed for use by the linker back |
| ends. The linker may create thousands of hash table entries, |
| and the overhead of allocating private data and storing and |
| following pointers becomes noticeable. |
| |
| The basic hash table code is in @code{hash.c}. |
| |
| @menu |
| * Creating and Freeing a Hash Table:: |
| * Looking Up or Entering a String:: |
| * Traversing a Hash Table:: |
| * Deriving a New Hash Table Type:: |
| @end menu |
| |
| @node Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables |
| @subsection Creating and freeing a hash table |
| @findex bfd_hash_table_init |
| @findex bfd_hash_table_init_n |
| To create a hash table, create an instance of a @code{struct |
| bfd_hash_table} (defined in @code{bfd.h}) and call |
| @code{bfd_hash_table_init} (if you know approximately how many |
| entries you will need, the function @code{bfd_hash_table_init_n}, |
| which takes a @var{size} argument, may be used). |
| @code{bfd_hash_table_init} returns @code{FALSE} if some sort of |
| error occurs. |
| |
| @findex bfd_hash_newfunc |
| The function @code{bfd_hash_table_init} take as an argument a |
| function to use to create new entries. For a basic hash |
| table, use the function @code{bfd_hash_newfunc}. @xref{Deriving |
| a New Hash Table Type}, for why you would want to use a |
| different value for this argument. |
| |
| @findex bfd_hash_allocate |
| @code{bfd_hash_table_init} will create an objalloc which will be |
| used to allocate new entries. You may allocate memory on this |
| objalloc using @code{bfd_hash_allocate}. |
| |
| @findex bfd_hash_table_free |
| Use @code{bfd_hash_table_free} to free up all the memory that has |
| been allocated for a hash table. This will not free up the |
| @code{struct bfd_hash_table} itself, which you must provide. |
| |
| @findex bfd_hash_set_default_size |
| Use @code{bfd_hash_set_default_size} to set the default size of |
| hash table to use. |
| |
| @node Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables |
| @subsection Looking up or entering a string |
| @findex bfd_hash_lookup |
| The function @code{bfd_hash_lookup} is used both to look up a |
| string in the hash table and to create a new entry. |
| |
| If the @var{create} argument is @code{FALSE}, @code{bfd_hash_lookup} |
| will look up a string. If the string is found, it will |
| returns a pointer to a @code{struct bfd_hash_entry}. If the |
| string is not found in the table @code{bfd_hash_lookup} will |
| return @code{NULL}. You should not modify any of the fields in |
| the returns @code{struct bfd_hash_entry}. |
| |
| If the @var{create} argument is @code{TRUE}, the string will be |
| entered into the hash table if it is not already there. |
| Either way a pointer to a @code{struct bfd_hash_entry} will be |
| returned, either to the existing structure or to a newly |
| created one. In this case, a @code{NULL} return means that an |
| error occurred. |
| |
| If the @var{create} argument is @code{TRUE}, 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 @code{FALSE}, you must be careful not to |
| deallocate or modify the string as long as the hash table |
| exists. |
| |
| @node Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables |
| @subsection Traversing a hash table |
| @findex bfd_hash_traverse |
| The function @code{bfd_hash_traverse} may be used to traverse a |
| hash table, calling a function on each element. The traversal |
| is done in a random order. |
| |
| @code{bfd_hash_traverse} takes as arguments a function and a |
| generic @code{void *} pointer. The function is called with a |
| hash table entry (a @code{struct bfd_hash_entry *}) and the |
| generic pointer passed to @code{bfd_hash_traverse}. The function |
| must return a @code{boolean} value, which indicates whether to |
| continue traversing the hash table. If the function returns |
| @code{FALSE}, @code{bfd_hash_traverse} will stop the traversal and |
| return immediately. |
| |
| @node Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables |
| @subsection Deriving a new hash table type |
| Many uses of hash tables want to store additional information |
| which each entry in the hash table. Some also find it |
| convenient to store additional information with the hash table |
| itself. This may be done using a derived hash table. |
| |
| Since C is not an object oriented language, creating a derived |
| hash table requires sticking together some boilerplate |
| routines with a few differences specific to the type of hash |
| table you want to create. |
| |
| An example of a derived hash table is the linker hash table. |
| The structures for this are defined in @code{bfdlink.h}. The |
| functions are in @code{linker.c}. |
| |
| You may also derive a hash table from an already derived hash |
| table. For example, the a.out linker backend code uses a hash |
| table derived from the linker hash table. |
| |
| @menu |
| * Define the Derived Structures:: |
| * Write the Derived Creation Routine:: |
| * Write Other Derived Routines:: |
| @end menu |
| |
| @node Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type |
| @subsubsection Define the derived structures |
| You must define a structure for an entry in the hash table, |
| and a structure for the hash table itself. |
| |
| The first field in the structure for an entry in the hash |
| table must be of the type used for an entry in the hash table |
| you are deriving from. If you are deriving from a basic hash |
| table this is @code{struct bfd_hash_entry}, which is defined in |
| @code{bfd.h}. The first field in the structure for the hash |
| table itself must be of the type of the hash table you are |
| deriving from itself. If you are deriving from a basic hash |
| table, this is @code{struct bfd_hash_table}. |
| |
| For example, the linker hash table defines @code{struct |
| bfd_link_hash_entry} (in @code{bfdlink.h}). The first field, |
| @code{root}, is of type @code{struct bfd_hash_entry}. Similarly, |
| the first field in @code{struct bfd_link_hash_table}, @code{table}, |
| is of type @code{struct bfd_hash_table}. |
| |
| @node Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type |
| @subsubsection Write the derived creation routine |
| You must write a routine which will create and initialize an |
| entry in the hash table. This routine is passed as the |
| function argument to @code{bfd_hash_table_init}. |
| |
| In order to permit other hash tables to be derived from the |
| hash table you are creating, this routine must be written in a |
| standard way. |
| |
| The first argument to the creation routine is a pointer to a |
| hash table entry. This may be @code{NULL}, in which case the |
| routine should allocate the right amount of space. Otherwise |
| the space has already been allocated by a hash table type |
| derived from this one. |
| |
| After allocating space, the creation routine must call the |
| creation routine of the hash table type it is derived from, |
| passing in a pointer to the space it just allocated. This |
| will initialize any fields used by the base hash table. |
| |
| Finally the creation routine must initialize any local fields |
| for the new hash table type. |
| |
| Here is a boilerplate example of a creation routine. |
| @var{function_name} is the name of the routine. |
| @var{entry_type} is the type of an entry in the hash table you |
| are creating. @var{base_newfunc} is the name of the creation |
| routine of the hash table type your hash table is derived |
| from. |
| |
| |
| @example |
| struct bfd_hash_entry * |
| @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 == 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)); |
| |
| /* Initialize the local fields here. */ |
| |
| return (struct bfd_hash_entry *) ret; |
| @} |
| @end example |
| @strong{Description}@* |
| The creation routine for the linker hash table, which is in |
| @code{linker.c}, looks just like this example. |
| @var{function_name} is @code{_bfd_link_hash_newfunc}. |
| @var{entry_type} is @code{struct bfd_link_hash_entry}. |
| @var{base_newfunc} is @code{bfd_hash_newfunc}, the creation |
| routine for a basic hash table. |
| |
| @code{_bfd_link_hash_newfunc} also initializes the local fields |
| in a linker hash table entry: @code{type}, @code{written} and |
| @code{next}. |
| |
| @node Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type |
| @subsubsection Write other derived routines |
| You will want to write other routines for your new hash table, |
| as well. |
| |
| You will want an initialization routine which calls the |
| initialization routine of the hash table you are deriving from |
| and initializes any other local fields. For the linker hash |
| table, this is @code{_bfd_link_hash_table_init} in @code{linker.c}. |
| |
| You will want a lookup routine which calls the lookup routine |
| of the hash table you are deriving from and casts the result. |
| The linker hash table uses @code{bfd_link_hash_lookup} in |
| @code{linker.c} (this actually takes an additional argument which |
| it uses to decide how to return the looked up value). |
| |
| You may want a traversal routine. This should just call the |
| traversal routine of the hash table you are deriving from with |
| appropriate casts. The linker hash table uses |
| @code{bfd_link_hash_traverse} in @code{linker.c}. |
| |
| These routines may simply be defined as macros. For example, |
| the a.out backend linker hash table, which is derived from the |
| linker hash table, uses macros for the lookup and traversal |
| routines. These are @code{aout_link_hash_lookup} and |
| @code{aout_link_hash_traverse} in aoutx.h. |
| |