Lines Matching full:hash
0 /* hash.c -- hash table routines for BFD
30 Hash Tables
32 @cindex Hash tables
33 BFD provides a simple set of hash table functions. Routines
34 are provided to initialize a hash table, to free a hash table,
35 to look up a string in a hash table and optionally create an
36 entry for it, and to traverse a hash table. There is
37 currently no routine to delete an string from a hash table.
39 The basic hash table does not permit any data to be stored
40 with a string. However, a hash table is designed to present a
41 base class from which other types of hash tables may be
43 with the string. Hash tables were implemented in this way,
44 rather than simply providing a data pointer in a hash table
46 ends. The linker may create thousands of hash table entries,
50 The basic hash table code is in <<hash.c>>.
53 @* Creating and Freeing a Hash Table::
55 @* Traversing a Hash Table::
56 @* Deriving a New Hash Table Type::
60 Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables
62 Creating and freeing a hash table
66 To create a hash table, create an instance of a <<struct
76 function to use to create new entries. For a basic hash
78 a New Hash Table Type}, for why you would want to use a
88 been allocated for a hash table. This will not free up the
93 hash table to use.
96 Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables
102 string in the hash table and to create a new entry.
112 entered into the hash table if it is not already there.
120 copy the string onto the hash table objalloc or not. If
122 deallocate or modify the string as long as the hash table
126 Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables
128 Traversing a hash table
132 hash table, calling a function on each element. The traversal
137 hash table entry (a <<struct bfd_hash_entry *>>) and the
140 continue traversing the hash table. If the function returns
145 Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables
147 Deriving a new hash table type
149 Many uses of hash tables want to store additional information
150 which each entry in the hash table. Some also find it
151 convenient to store additional information with the hash table
152 itself. This may be done using a derived hash table.
155 hash table requires sticking together some boilerplate
156 routines with a few differences specific to the type of hash
159 An example of a derived hash table is the linker hash table.
163 You may also derive a hash table from an already derived hash
164 table. For example, the a.out linker backend code uses a hash
165 table derived from the linker hash table.
174 Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type
178 You must define a structure for an entry in the hash table,
179 and a structure for the hash table itself.
181 The first field in the structure for an entry in the hash
182 table must be of the type used for an entry in the hash table
183 you are deriving from. If you are deriving from a basic hash
185 <<bfd.h>>. The first field in the structure for the hash
186 table itself must be of the type of the hash table you are
187 deriving from itself. If you are deriving from a basic hash
190 For example, the linker hash table defines <<struct
197 Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type
202 entry in the hash table. This routine is passed as the
205 In order to permit other hash tables to be derived from the
206 hash table you are creating, this routine must be written in a
210 hash table entry. This may be <<NULL>>, in which case the
212 the space has already been allocated by a hash table type
216 creation routine of the hash table type it is derived from,
218 will initialize any fields used by the base hash table.
221 for the new hash table type.
225 @var{entry_type} is the type of an entry in the hash table you
227 routine of the hash table type your hash table is derived
258 The creation routine for the linker hash table, which is in
263 routine for a basic hash table.
266 in a linker hash table entry: <<type>>, <<written>> and
270 Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type
274 You will want to write other routines for your new hash table,
278 initialization routine of the hash table you are deriving from
279 and initializes any other local fields. For the linker hash
283 of the hash table you are deriving from and casts the result.
284 The linker hash table uses <<bfd_link_hash_lookup>> in
289 traversal routine of the hash table you are deriving from with
290 appropriate casts. The linker hash table uses
294 the a.out backend linker hash table, which is derived from the
295 linker hash table, uses macros for the lookup and traversal
300 /* The default number of entries to use when creating a hash table. */
365 /* Create a new hash table, given a number of entries. */
408 /* Create a new hash table with the default number of entries. */
421 /* Free a hash table. */
434 unsigned long hash;
438 hash = 0;
443 hash += c + (c << 17);
444 hash ^= hash >> 2;
447 hash += len + (len << 17);
448 hash ^= hash >> 2;
451 return hash;
454 /* Look up a string in a hash table. */
462 unsigned long hash;
467 hash = bfd_hash_hash (string, &len);
468 _index = hash % table->size;
473 if (hashp->hash == hash
496 hash);
499 /* Insert an entry in a hash table. */
504 unsigned long hash)
513 hashp->hash = hash;
514 _index = hash % table->size;
549 while (chain_end->next && chain_end->next->hash == chain->hash)
553 _index = chain->hash % newsize;
564 /* Rename an entry in a hash table. */
574 _index = ent->hash % table->size;
583 ent->hash = bfd_hash_hash (string, NULL);
584 _index = ent->hash % table->size;
589 /* Replace an entry in a hash table. */
599 _index = old->hash % table->size;
614 /* Allocate space in a hash table. */
628 /* Base method for creating a new hash table entry. */
641 /* Traverse a hash table. */
667 /* Extend this prime list if you want more granularity of hash table size. */
696 /* An entry in the strtab hash table. */
707 /* The strtab hash table. */
812 already present. If HASH is FALSE, we don't really use the hash
819 bfd_boolean hash,
824 if (hash)
