hash.texi revision 1.1.1.3
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 209The creation routine for the linker hash table, which is in 210@code{linker.c}, looks just like this example. 211@var{function_name} is @code{_bfd_link_hash_newfunc}. 212@var{entry_type} is @code{struct bfd_link_hash_entry}. 213@var{base_newfunc} is @code{bfd_hash_newfunc}, the creation 214routine for a basic hash table. 215 216@code{_bfd_link_hash_newfunc} also initializes the local fields 217in a linker hash table entry: @code{type}, @code{written} and 218@code{next}. 219 220@node Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type 221@subsubsection Write other derived routines 222You will want to write other routines for your new hash table, 223as well. 224 225You will want an initialization routine which calls the 226initialization routine of the hash table you are deriving from 227and initializes any other local fields. For the linker hash 228table, this is @code{_bfd_link_hash_table_init} in @code{linker.c}. 229 230You will want a lookup routine which calls the lookup routine 231of the hash table you are deriving from and casts the result. 232The linker hash table uses @code{bfd_link_hash_lookup} in 233@code{linker.c} (this actually takes an additional argument which 234it uses to decide how to return the looked up value). 235 236You may want a traversal routine. This should just call the 237traversal routine of the hash table you are deriving from with 238appropriate casts. The linker hash table uses 239@code{bfd_link_hash_traverse} in @code{linker.c}. 240 241These routines may simply be defined as macros. For example, 242the a.out backend linker hash table, which is derived from the 243linker hash table, uses macros for the lookup and traversal 244routines. These are @code{aout_link_hash_lookup} and 245@code{aout_link_hash_traverse} in aoutx.h. 246 247@findex bfd_hash_table_init_n 248@subsubsection @code{bfd_hash_table_init_n} 249@deftypefn {Function} bool bfd_hash_table_init_n (struct bfd_hash_table *, struct bfd_hash_entry *(* {*newfunc*}) (struct bfd_hash_entry *, struct bfd_hash_table *, const char *), unsigned int {*entsize*}, unsigned int {*size*}); 250Create a new hash table, given a number of entries. 251 252@end deftypefn 253@findex bfd_hash_table_init 254@subsubsection @code{bfd_hash_table_init} 255@deftypefn {Function} bool bfd_hash_table_init (struct bfd_hash_table *, struct bfd_hash_entry *(* {*newfunc*}) (struct bfd_hash_entry *, struct bfd_hash_table *, const char *), unsigned int {*entsize*}); 256Create a new hash table with the default number of entries. 257 258@end deftypefn 259@findex bfd_hash_table_free 260@subsubsection @code{bfd_hash_table_free} 261@deftypefn {Function} void bfd_hash_table_free (struct bfd_hash_table *); 262Free a hash table. 263 264@end deftypefn 265@findex bfd_hash_lookup 266@subsubsection @code{bfd_hash_lookup} 267@deftypefn {Function} struct bfd_hash_entry *bfd_hash_lookup (struct bfd_hash_table *, const char *, bool {*create*}, bool {*copy*}); 268Look up a string in a hash table. 269 270@end deftypefn 271@findex bfd_hash_insert 272@subsubsection @code{bfd_hash_insert} 273@deftypefn {Function} struct bfd_hash_entry *bfd_hash_insert (struct bfd_hash_table *, const char *, unsigned long {*hash*}); 274Insert an entry in a hash table. 275 276@end deftypefn 277@findex bfd_hash_rename 278@subsubsection @code{bfd_hash_rename} 279@deftypefn {Function} void bfd_hash_rename (struct bfd_hash_table *, const char *, struct bfd_hash_entry *); 280Rename an entry in a hash table. 281 282@end deftypefn 283@findex bfd_hash_replace 284@subsubsection @code{bfd_hash_replace} 285@deftypefn {Function} void bfd_hash_replace (struct bfd_hash_table *, struct bfd_hash_entry * {*old*}, struct bfd_hash_entry * {*new*}); 286Replace an entry in a hash table. 287 288@end deftypefn 289@findex bfd_hash_allocate 290@subsubsection @code{bfd_hash_allocate} 291@deftypefn {Function} void *bfd_hash_allocate (struct bfd_hash_table *, unsigned int {*size*}); 292Allocate space in a hash table. 293 294@end deftypefn 295@findex bfd_hash_newfunc 296@subsubsection @code{bfd_hash_newfunc} 297@deftypefn {Function} struct bfd_hash_entry *bfd_hash_newfunc (struct bfd_hash_entry *, struct bfd_hash_table *, const char *); 298Base method for creating a new hash table entry. 299 300@end deftypefn 301@findex bfd_hash_traverse 302@subsubsection @code{bfd_hash_traverse} 303@deftypefn {Function} void bfd_hash_traverse (struct bfd_hash_table *, bool (*) (struct bfd_hash_entry *, void *), void *); 304Traverse a hash table. 305 306@end deftypefn 307@findex bfd_hash_set_default_size 308@subsubsection @code{bfd_hash_set_default_size} 309@deftypefn {Function} unsigned int bfd_hash_set_default_size (unsigned int); 310Set hash table default size. 311 312@end deftypefn 313@findex _bfd_stringtab_init 314@subsubsection @code{_bfd_stringtab_init} 315@deftypefn {Function} struct bfd_strtab_hash *_bfd_stringtab_init (void); 316Create a new strtab. 317 318@end deftypefn 319@findex _bfd_xcoff_stringtab_init 320@subsubsection @code{_bfd_xcoff_stringtab_init} 321@deftypefn {Function} struct bfd_strtab_hash *_bfd_xcoff_stringtab_init (bool {*isxcoff64*}); 322Create a new strtab in which the strings are output in the format 323used in the XCOFF .debug section: a two byte length precedes each 324string. 325 326@end deftypefn 327@findex _bfd_stringtab_free 328@subsubsection @code{_bfd_stringtab_free} 329@deftypefn {Function} void _bfd_stringtab_free (struct bfd_strtab_hash *); 330Free a strtab. 331 332@end deftypefn 333@findex _bfd_stringtab_add 334@subsubsection @code{_bfd_stringtab_add} 335@deftypefn {Function} bfd_size_type _bfd_stringtab_add (struct bfd_strtab_hash *, const char *, bool {*hash*}, bool {*copy*}); 336Get the index of a string in a strtab, adding it if it is not 337already present. If HASH is FALSE, we don't really use the hash 338table, and we don't eliminate duplicate strings. If COPY is true 339then store a copy of STR if creating a new entry. 340 341@end deftypefn 342@findex _bfd_stringtab_size 343@subsubsection @code{_bfd_stringtab_size} 344@deftypefn {Function} bfd_size_type _bfd_stringtab_size (struct bfd_strtab_hash *); 345Get the number of bytes in a strtab. 346 347@end deftypefn 348@findex _bfd_stringtab_emit 349@subsubsection @code{_bfd_stringtab_emit} 350@deftypefn {Function} bool _bfd_stringtab_emit (bfd *, struct bfd_strtab_hash *); 351Write out a strtab. ABFD must already be at the right location in 352the file. 353 354@end deftypefn 355