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 /* The default number of entries to use when creating a hash table. */
365 /* Create a new hash table, given a number of entries. */
368 bfd_hash_table_init_n (struct bfd_hash_table *table,
385 table->memory = (void *) objalloc_create ();
386 if (table->memory == NULL)
391 table->table = (struct bfd_hash_entry **)
392 objalloc_alloc ((struct objalloc *) table->memory, alloc);
393 if (table->table == NULL)
395 bfd_hash_table_free (table);
399 memset ((void *) table->table, 0, alloc);
400 table->size = size;
401 table->entsize = entsize;
402 table->count = 0;
403 table->frozen = 0;
404 table->newfunc = newfunc;
408 /* Create a new hash table with the default number of entries. */
411 bfd_hash_table_init (struct bfd_hash_table *table,
417 return bfd_hash_table_init_n (table, newfunc, entsize,
421 /* Free a hash table. */
424 bfd_hash_table_free (struct bfd_hash_table *table)
426 objalloc_free ((struct objalloc *) table->memory);
427 table->memory = NULL;
454 /* Look up a string in a hash table. */
457 bfd_hash_lookup (struct bfd_hash_table *table,
468 _index = hash % table->size;
469 for (hashp = table->table[_index];
485 new_string = (char *) objalloc_alloc ((struct objalloc *) table->memory,
496 table, string, hash);
499 /* Insert an entry in a hash table. */
502 bfd_hash_insert (struct bfd_hash_table *table,
509 hashp = (*table->newfunc) (NULL, table, string);
514 _index = hash % table->size;
515 hashp->next = table->table[_index];
516 table->table[_index] = hashp;
517 table->count++;
519 if (!table->frozen && table->count > table->size * 3 / 4)
521 unsigned long newsize = higher_prime_number (table->size);
527 that much memory, don't try to grow the table. */
530 table->frozen = 1;
535 objalloc_alloc ((struct objalloc *) table->memory, alloc));
538 table->frozen = 1;
543 for (hi = 0; hi < table->size; hi ++)
544 while (table->table[hi])
546 struct bfd_hash_entry *chain = table->table[hi];
552 table->table[hi] = chain_end->next;
557 table->table = newtable;
558 table->size = newsize;
564 /* Rename an entry in a hash table. */
567 bfd_hash_rename (struct bfd_hash_table *table,
574 _index = ent->hash % table->size;
575 for (pph = &table->table[_index]; *pph != NULL; pph = &(*pph)->next)
584 _index = ent->hash % table->size;
585 ent->next = table->table[_index];
586 table->table[_index] = ent;
589 /* Replace an entry in a hash table. */
592 bfd_hash_replace (struct bfd_hash_table *table,
599 _index = old->hash % table->size;
600 for (pph = &table->table[_index];
614 /* Allocate space in a hash table. */
617 bfd_hash_allocate (struct bfd_hash_table *table,
622 ret = objalloc_alloc ((struct objalloc *) table->memory, size);
628 /* Base method for creating a new hash table entry. */
632 struct bfd_hash_table *table,
636 entry = (struct bfd_hash_entry *) bfd_hash_allocate (table,
641 /* Traverse a hash table. */
644 bfd_hash_traverse (struct bfd_hash_table *table,
650 table->frozen = 1;
651 for (i = 0; i < table->size; i++)
655 for (p = table->table[i]; p != NULL; p = p->next)
660 table->frozen = 0;
667 /* Extend this prime list if you want more granularity of hash table size. */
685 table. These functions support adding strings to a string table,
686 returning the byte offset, and writing out the table.
692 to construct the entire symbol table at once, we could get by
694 string table reductions?) */
696 /* An entry in the strtab hash table. */
701 /* Index in string table. */
707 /* The strtab hash table. */
711 struct bfd_hash_table table;
727 struct bfd_hash_table *table,
735 ret = (struct strtab_hash_entry *) bfd_hash_allocate (table,
742 bfd_hash_newfunc ((struct bfd_hash_entry *) ret, table, string);
758 bfd_hash_lookup (&(t)->table, (string), (create), (copy)))
765 struct bfd_strtab_hash *table;
766 bfd_size_type amt = sizeof (* table);
768 table = (struct bfd_strtab_hash *) bfd_malloc (amt);
769 if (table == NULL)
772 if (!bfd_hash_table_init (&table->table, strtab_hash_newfunc,
775 free (table);
779 table->size = 0;
780 table->first = NULL;
781 table->last = NULL;
782 table->xcoff = FALSE;
784 return table;
805 _bfd_stringtab_free (struct bfd_strtab_hash *table)
807 bfd_hash_table_free (&table->table);
808 free (table);
813 table, and we don't eliminate duplicate strings. If COPY is true
832 entry = (struct strtab_hash_entry *) bfd_hash_allocate (&tab->table,
843 n = (char *) bfd_hash_allocate (&tab->table, len);
