hash.texi revision 1.6
1@section Hash Tables 2@cindex Hash tables 3BFD provides a simple set of hash table functions. Routines 4are provided to initialize a hash table, to free a hash table, 5to look up a string in a hash table and optionally create an 6entry for it, and to traverse a hash table. There is 7currently no routine to delete an string from a hash table. 8 9The basic hash table does not permit any data to be stored 10with a string. However, a hash table is designed to present a 11base class from which other types of hash tables may be 12derived. These derived types may store additional information 13with the string. Hash tables were implemented in this way, 14rather than simply providing a data pointer in a hash table 15entry, because they were designed for use by the linker back 16ends. The linker may create thousands of hash table entries, 17and the overhead of allocating private data and storing and 18following pointers becomes noticeable. 19 20The basic hash table code is in @code{hash.c}. 21 22@menu 23* Creating and Freeing a Hash Table:: 24* Looking Up or Entering a String:: 25* Traversing a Hash Table:: 26* Deriving a New Hash Table Type:: 27@end menu 28 29@node Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables 30@subsection Creating and freeing a hash table 31@findex bfd_hash_table_init 32@findex bfd_hash_table_init_n 33To create a hash table, create an instance of a @code{struct 34bfd_hash_table} (defined in @code{bfd.h}) and call 35@code{bfd_hash_table_init} (if you know approximately how many 36entries you will need, the function @code{bfd_hash_table_init_n}, 37which takes a @var{size} argument, may be used). 38@code{bfd_hash_table_init} returns @code{FALSE} if some sort of 39error occurs. 40 41@findex bfd_hash_newfunc 42The function @code{bfd_hash_table_init} take as an argument a 43function to use to create new entries. For a basic hash 44table, use the function @code{bfd_hash_newfunc}. @xref{Deriving 45a New Hash Table Type}, for why you would want to use a 46different value for this argument. 47 48@findex bfd_hash_allocate 49@code{bfd_hash_table_init} will create an objalloc which will be 50used to allocate new entries. You may allocate memory on this 51objalloc using @code{bfd_hash_allocate}. 52 53@findex bfd_hash_table_free 54Use @code{bfd_hash_table_free} to free up all the memory that has 55been allocated for a hash table. This will not free up the 56@code{struct bfd_hash_table} itself, which you must provide. 57 58@findex bfd_hash_set_default_size 59Use @code{bfd_hash_set_default_size} to set the default size of 60hash table to use. 61 62@node Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables 63@subsection Looking up or entering a string 64@findex bfd_hash_lookup 65The function @code{bfd_hash_lookup} is used both to look up a 66string in the hash table and to create a new entry. 67 68If the @var{create} argument is @code{FALSE}, @code{bfd_hash_lookup} 69will look up a string. If the string is found, it will 70returns a pointer to a @code{struct bfd_hash_entry}. If the 71string is not found in the table @code{bfd_hash_lookup} will 72return @code{NULL}. You should not modify any of the fields in 73the returns @code{struct bfd_hash_entry}. 74 75If the @var{create} argument is @code{TRUE}, the string will be 76entered into the hash table if it is not already there. 77Either way a pointer to a @code{struct bfd_hash_entry} will be 78returned, either to the existing structure or to a newly 79created one. In this case, a @code{NULL} return means that an 80error occurred. 81 82If the @var{create} argument is @code{TRUE}, and a new entry is 83created, the @var{copy} argument is used to decide whether to 84copy the string onto the hash table objalloc or not. If 85@var{copy} is passed as @code{FALSE}, you must be careful not to 86deallocate or modify the string as long as the hash table 87exists. 88 89@node Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables 90@subsection Traversing a hash table 91@findex bfd_hash_traverse 92The function @code{bfd_hash_traverse} may be used to traverse a 93hash table, calling a function on each element. The traversal 94is done in a random order. 95 96@code{bfd_hash_traverse} takes as arguments a function and a 97generic @code{void *} pointer. The function is called with a 98hash table entry (a @code{struct bfd_hash_entry *}) and the 99generic pointer passed to @code{bfd_hash_traverse}. The function 100must return a @code{boolean} value, which indicates whether to 101continue traversing the hash table. If the function returns 102@code{FALSE}, @code{bfd_hash_traverse} will stop the traversal and 103return immediately. 104 105@node Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables 106@subsection Deriving a new hash table type 107Many uses of hash tables want to store additional information 108which each entry in the hash table. Some also find it 109convenient to store additional information with the hash table 110itself. This may be done using a derived hash table. 111 112Since C is not an object oriented language, creating a derived 113hash table requires sticking together some boilerplate 114routines with a few differences specific to the type of hash 115table you want to create. 116 117An example of a derived hash table is the linker hash table. 118The structures for this are defined in @code{bfdlink.h}. The 119functions are in @code{linker.c}. 120 121You may also derive a hash table from an already derived hash 122table. For example, the a.out linker backend code uses a hash 123table derived from the linker hash table. 124 125@menu 126* Define the Derived Structures:: 127* Write the Derived Creation Routine:: 128* Write Other Derived Routines:: 129@end menu 130 131@node Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type 132@subsubsection Define the derived structures 133You must define a structure for an entry in the hash table, 134and a structure for the hash table itself. 135 136The first field in the structure for an entry in the hash 137table must be of the type used for an entry in the hash table 138you are deriving from. If you are deriving from a basic hash 139table this is @code{struct bfd_hash_entry}, which is defined in 140@code{bfd.h}. The first field in the structure for the hash 141table itself must be of the type of the hash table you are 142deriving from itself. If you are deriving from a basic hash 143table, this is @code{struct bfd_hash_table}. 144 145For example, the linker hash table defines @code{struct 146bfd_link_hash_entry} (in @code{bfdlink.h}). The first field, 147@code{root}, is of type @code{struct bfd_hash_entry}. Similarly, 148the first field in @code{struct bfd_link_hash_table}, @code{table}, 149is of type @code{struct bfd_hash_table}. 150 151@node Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type 152@subsubsection Write the derived creation routine 153You must write a routine which will create and initialize an 154entry in the hash table. This routine is passed as the 155function argument to @code{bfd_hash_table_init}. 156 157In order to permit other hash tables to be derived from the 158hash table you are creating, this routine must be written in a 159standard way. 160 161The first argument to the creation routine is a pointer to a 162hash table entry. This may be @code{NULL}, in which case the 163routine should allocate the right amount of space. Otherwise 164the space has already been allocated by a hash table type 165derived from this one. 166 167After allocating space, the creation routine must call the 168creation routine of the hash table type it is derived from, 169passing in a pointer to the space it just allocated. This 170will initialize any fields used by the base hash table. 171 172Finally the creation routine must initialize any local fields 173for the new hash table type. 174 175Here is a boilerplate example of a creation routine. 176@var{function_name} is the name of the routine. 177@var{entry_type} is the type of an entry in the hash table you 178are creating. @var{base_newfunc} is the name of the creation 179routine of the hash table type your hash table is derived 180from. 181 182 183@example 184struct bfd_hash_entry * 185@var{function_name} (struct bfd_hash_entry *entry, 186 struct bfd_hash_table *table, 187 const char *string) 188@{ 189 struct @var{entry_type} *ret = (@var{entry_type} *) entry; 190 191 /* Allocate the structure if it has not already been allocated by a 192 derived class. */ 193 if (ret == NULL) 194 @{ 195 ret = bfd_hash_allocate (table, sizeof (* ret)); 196 if (ret == NULL) 197 return NULL; 198 @} 199 200 /* Call the allocation method of the base class. */ 201 ret = ((@var{entry_type} *) 202 @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string)); 203 204 /* Initialize the local fields here. */ 205 206 return (struct bfd_hash_entry *) ret; 207@} 208@end example 209@strong{Description}@* 210The creation routine for the linker hash table, which is in 211@code{linker.c}, looks just like this example. 212@var{function_name} is @code{_bfd_link_hash_newfunc}. 213@var{entry_type} is @code{struct bfd_link_hash_entry}. 214@var{base_newfunc} is @code{bfd_hash_newfunc}, the creation 215routine for a basic hash table. 216 217@code{_bfd_link_hash_newfunc} also initializes the local fields 218in a linker hash table entry: @code{type}, @code{written} and 219@code{next}. 220 221@node Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type 222@subsubsection Write other derived routines 223You will want to write other routines for your new hash table, 224as well. 225 226You will want an initialization routine which calls the 227initialization routine of the hash table you are deriving from 228and initializes any other local fields. For the linker hash 229table, this is @code{_bfd_link_hash_table_init} in @code{linker.c}. 230 231You will want a lookup routine which calls the lookup routine 232of the hash table you are deriving from and casts the result. 233The linker hash table uses @code{bfd_link_hash_lookup} in 234@code{linker.c} (this actually takes an additional argument which 235it uses to decide how to return the looked up value). 236 237You may want a traversal routine. This should just call the 238traversal routine of the hash table you are deriving from with 239appropriate casts. The linker hash table uses 240@code{bfd_link_hash_traverse} in @code{linker.c}. 241 242These routines may simply be defined as macros. For example, 243the a.out backend linker hash table, which is derived from the 244linker hash table, uses macros for the lookup and traversal 245routines. These are @code{aout_link_hash_lookup} and 246@code{aout_link_hash_traverse} in aoutx.h. 247 248