+#include "objalloc.h"
+#include "libiberty.h"
+
+/*
+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 <<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
+
+INODE
+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 <<struct
+ bfd_hash_table>> (defined in <<bfd.h>>) and call
+ <<bfd_hash_table_init>> (if you know approximately how many
+ entries you will need, the function <<bfd_hash_table_init_n>>,
+ which takes a @var{size} argument, may be used).
+ <<bfd_hash_table_init>> returns <<FALSE>> if some sort of
+ error occurs.
+
+@findex bfd_hash_newfunc
+ The function <<bfd_hash_table_init>> take as an argument a
+ function to use to create new entries. For a basic hash
+ table, use the function <<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
+ <<bfd_hash_table_init>> will create an objalloc which will be
+ used to allocate new entries. You may allocate memory on this
+ objalloc using <<bfd_hash_allocate>>.
+
+@findex bfd_hash_table_free
+ Use <<bfd_hash_table_free>> to free up all the memory that has
+ been allocated for a hash table. This will not free up the
+ <<struct bfd_hash_table>> itself, which you must provide.
+
+@findex bfd_hash_set_default_size
+ Use <<bfd_hash_set_default_size>> 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
+ Looking up or entering a string
+
+@findex bfd_hash_lookup
+ The function <<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 <<FALSE>>, <<bfd_hash_lookup>>
+ will look up a string. If the string is found, it will
+ returns a pointer to a <<struct bfd_hash_entry>>. If the
+ string is not found in the table <<bfd_hash_lookup>> will
+ return <<NULL>>. You should not modify any of the fields in
+ the returns <<struct bfd_hash_entry>>.
+
+ If the @var{create} argument is <<TRUE>>, the string will be
+ entered into the hash table if it is not already there.
+ Either way a pointer to a <<struct bfd_hash_entry>> will be
+ returned, either to the existing structure or to a newly
+ created one. In this case, a <<NULL>> return means that an
+ error occurred.
+
+ If the @var{create} argument is <<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 <<FALSE>>, you must be careful not to
+ deallocate or modify the string as long as the hash table
+ exists.
+
+INODE
+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 <<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.
+
+ <<bfd_hash_traverse>> takes as arguments a function and a
+ generic <<void *>> pointer. The function is called with a
+ hash table entry (a <<struct bfd_hash_entry *>>) and the
+ generic pointer passed to <<bfd_hash_traverse>>. The function
+ must return a <<boolean>> value, which indicates whether to
+ continue traversing the hash table. If the function returns
+ <<FALSE>>, <<bfd_hash_traverse>> will stop the traversal and
+ return immediately.
+
+INODE
+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 <<bfdlink.h>>. The
+ functions are in <<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