Lines Matching refs:table
1 /* hash.c -- hash table routines for BFD
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
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
77 table, use the function <<bfd_hash_newfunc>>. @xref{Deriving
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.
107 string is not found in the table <<bfd_hash_lookup>> will
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
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
157 table you want to create.
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.
182 table must be of the type used for an entry in the hash table
184 table this is <<struct bfd_hash_entry>>, which is defined in
186 table itself must be of the type of the hash table you are
188 table, this is <<struct bfd_hash_table>>.
190 For example, the linker hash table defines <<struct
193 the first field in <<struct bfd_link_hash_table>>, <<table>>,
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
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
234 . struct bfd_hash_table *table,
243 . ret = bfd_hash_allocate (table, sizeof (* ret));
250 . @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string));
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
280 table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>.
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 .{* An element in the hash table. Most uses will actually use a larger
310 . table. *}
314 .{* A hash table. *}
319 . struct bfd_hash_entry **table;
320 . {* A function used to create new elements in the hash table. The
329 . {* An objalloc for this hash table. This is a struct objalloc *,
332 . {* The number of slots in the hash table. *}
334 . {* The number of entries in the hash table. *}
338 . {* If non-zero, don't grow the hash table. *}
344 /* The default number of entries to use when creating a hash table. */
420 Create a new hash table, given a number of entries.
424 bfd_hash_table_init_n (struct bfd_hash_table *table,
441 table->memory = (void *) objalloc_create ();
442 if (table->memory == NULL)
447 table->table = (struct bfd_hash_entry **)
448 objalloc_alloc ((struct objalloc *) table->memory, alloc);
449 if (table->table == NULL)
451 bfd_hash_table_free (table);
455 memset ((void *) table->table, 0, alloc);
456 table->size = size;
457 table->entsize = entsize;
458 table->count = 0;
459 table->frozen = 0;
460 table->newfunc = newfunc;
476 Create a new hash table with the default number of entries.
480 bfd_hash_table_init (struct bfd_hash_table *table,
486 return bfd_hash_table_init_n (table, newfunc, entsize,
498 Free a hash table.
502 bfd_hash_table_free (struct bfd_hash_table *table)
504 objalloc_free ((struct objalloc *) table->memory);
505 table->memory = NULL;
543 Look up a string in a hash table.
547 bfd_hash_lookup (struct bfd_hash_table *table,
558 _index = hash % table->size;
559 for (hashp = table->table[_index];
575 new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory,
586 return bfd_hash_insert (table, string, hash);
600 Insert an entry in a hash table.
604 bfd_hash_insert (struct bfd_hash_table *table,
611 hashp = (*table->newfunc) (NULL, table, string);
616 _index = hash % table->size;
617 hashp->next = table->table[_index];
618 table->table[_index] = hashp;
619 table->count++;
621 if (!table->frozen && table->count > table->size * 3 / 4)
623 unsigned long newsize = higher_prime_number (table->size);
629 that much memory, don't try to grow the table. */
632 table->frozen = 1;
637 objalloc_alloc ((struct objalloc *) table->memory, alloc));
640 table->frozen = 1;
645 for (hi = 0; hi < table->size; hi ++)
646 while (table->table[hi])
648 struct bfd_hash_entry *chain = table->table[hi];
654 table->table[hi] = chain_end->next;
659 table->table = newtable;
660 table->size = newsize;
676 Rename an entry in a hash table.
680 bfd_hash_rename (struct bfd_hash_table *table,
687 _index = ent->hash % table->size;
688 for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next)
697 _index = ent->hash % table->size;
698 ent->next = table->table[_index];
699 table->table[_index] = ent;
712 Replace an entry in a hash table.
716 bfd_hash_replace (struct bfd_hash_table *table,
723 _index = old->hash % table->size;
724 for (pph = &table->table[_index];
747 Allocate space in a hash table.
751 bfd_hash_allocate (struct bfd_hash_table *table,
756 ret = objalloc_alloc ((struct objalloc *) table->memory, size);
773 Base method for creating a new hash table entry.
778 struct bfd_hash_table *table,
782 entry = (struct bfd_hash_entry *) bfd_hash_allocate (table,
798 Traverse a hash table.
802 bfd_hash_traverse (struct bfd_hash_table *table,
808 table->frozen = 1;
809 for (i = 0; i < table->size; i++)
813 for (p = table->table[i]; p != NULL; p = p->next)
818 table->frozen = 0;
829 Set hash table default size.
836 being allocated for the table of pointers. Note that the number
852 table. These functions support adding strings to a string table,
853 returning the byte offset, and writing out the table.
859 to construct the entire symbol table at once, we could get by
861 string table reductions?) */
863 /* An entry in the strtab hash table. */
868 /* Index in string table. */
874 /* The strtab hash table. */
878 struct bfd_hash_table table;
895 struct bfd_hash_table *table,
903 ret = (struct strtab_hash_entry *) bfd_hash_allocate (table,
910 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
926 bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
942 struct bfd_strtab_hash *table;
943 size_t amt = sizeof (* table);
945 table = (struct bfd_strtab_hash *) bfd_malloc (amt);
946 if (table == NULL)
949 if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
952 free (table);
956 table->size = 0;
957 table->first = NULL;
958 table->last = NULL;
959 table->length_field_size = 0;
961 return table;
1001 _bfd_stringtab_free (struct bfd_strtab_hash *table)
1003 bfd_hash_table_free (&table->table);
1004 free (table);
1019 table, and we don't eliminate duplicate strings. If COPY is true
1039 entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table,
1050 n = (char *) bfd_hash_allocate (&tab->table, len);
Indexes created Fri Apr 10 00:22:58 UTC 2026