1 /* hash.c -- hash table routines for BFD
2 Copyright 1993 Free Software Foundation, Inc.
3 Written by Steve Chamberlain <sac@cygnus.com>
5 This file is part of GLD, the Gnu Linker.
7 GLD is free software; you can redistribute it and/or modify
8 it under the terms of the GNU General Public License as published by
9 the Free Software Foundation; either version 2, or (at your option)
12 GLD is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
15 GNU General Public License for more details.
17 You should have received a copy of the GNU General Public License
18 along with GLD; see the file COPYING. If not, write to
19 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
31 BFD provides a simple set of hash table functions. Routines
32 are provided to initialize a hash table, to free a hash table,
33 to look up a string in a hash table and optionally create an
34 entry for it, and to traverse a hash table. There is
35 currently no routine to delete an string from a hash table.
37 The basic hash table does not permit any data to be stored
38 with a string. However, a hash table is designed to present a
39 base class from which other types of hash tables may be
40 derived. These derived types may store additional information
41 with the string. Hash tables were implemented in this way,
42 rather than simply providing a data pointer in a hash table
43 entry, because they were designed for use by the linker back
44 ends. The linker may create thousands of hash table entries,
45 and the overhead of allocating private data and storing and
46 following pointers becomes noticeable.
48 The basic hash table code is in <<hash.c>>.
51 @* Creating and Freeing a Hash Table::
52 @* Looking Up or Entering a String::
53 @* Traversing a Hash Table::
54 @* Deriving a New Hash Table Type::
58 Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables
60 Creating and freeing a hash table
62 @findex bfd_hash_table_init
63 @findex bfd_hash_table_init_n
64 To create a hash table, create an instance of a <<struct
65 bfd_hash_table>> (defined in <<bfd.h>>) and call
66 <<bfd_hash_table_init>> (if you know approximately how many
67 entries you will need, the function <<bfd_hash_table_init_n>>,
68 which takes a @var{size} argument, may be used).
69 <<bfd_hash_table_init>> returns <<false>> if some sort of
72 @findex bfd_hash_newfunc
73 The function <<bfd_hash_table_init>> take as an argument a
74 function to use to create new entries. For a basic hash
75 table, use the function <<bfd_hash_newfunc>>. @xref{Deriving
76 a New Hash Table Type} for why you would want to use a
77 different value for this argument.
79 @findex bfd_hash_allocate
80 <<bfd_hash_table_init>> will create an obstack which will be
81 used to allocate new entries. You may allocate memory on this
82 obstack using <<bfd_hash_allocate>>.
84 @findex bfd_hash_table_free
85 Use <<bfd_hash_table_free>> to free up all the memory that has
86 been allocated for a hash table. This will not free up the
87 <<struct bfd_hash_table>> itself, which you must provide.
90 Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables
92 Looking up or entering a string
94 @findex bfd_hash_lookup
95 The function <<bfd_hash_lookup>> is used both to look up a
96 string in the hash table and to create a new entry.
98 If the @var{create} argument is <<false>>, <<bfd_hash_lookup>>
99 will look up a string. If the string is found, it will
100 returns a pointer to a <<struct bfd_hash_entry>>. If the
101 string is not found in the table <<bfd_hash_lookup>> will
102 return <<NULL>>. You should not modify any of the fields in
103 the returns <<struct bfd_hash_entry>>.
105 If the @var{create} argument is <<true>>, the string will be
106 entered into the hash table if it is not already there.
107 Either way a pointer to a <<struct bfd_hash_entry>> will be
108 returned, either to the existing structure or to a newly
109 created one. In this case, a <<NULL>> return means that an
112 If the @var{create} argument is <<true>>, and a new entry is
113 created, the @var{copy} argument is used to decide whether to
114 copy the string onto the hash table obstack or not. If
115 @var{copy} is passed as <<false>>, you must be careful not to
116 deallocate or modify the string as long as the hash table
120 Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables
122 Traversing a hash table
124 @findex bfd_hash_traverse
125 The function <<bfd_hash_traverse>> may be used to traverse a
126 hash table, calling a function on each element. The traversal
127 is done in a random order.
129 <<bfd_hash_traverse>> takes as arguments a function and a
130 generic <<void *>> pointer. The function is called with a
131 hash table entry (a <<struct bfd_hash_entry *>>) and the
132 generic pointer passed to <<bfd_hash_traverse>>. The function
133 must return a <<boolean>> value, which indicates whether to
134 continue traversing the hash table. If the function returns
135 <<false>>, <<bfd_hash_traverse>> will stop the traversal and
139 Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables
141 Deriving a new hash table type
143 Many uses of hash tables want to store additional information
144 which each entry in the hash table. Some also find it
145 convenient to store additional information with the hash table
146 itself. This may be done using a derived hash table.
148 Since C is not an object oriented language, creating a derived
149 hash table requires sticking together some boilerplate
150 routines with a few differences specific to the type of hash
151 table you want to create.
153 An example of a derived hash table is the linker hash table.
154 The structures for this are defined in <<bfdlink.h>>. The
155 functions are in <<linker.c>>.
157 You may also derive a hash table from an already derived hash
158 table. For example, the a.out linker backend code uses a hash
159 table derived from the linker hash table.
162 @* Define the Derived Structures::
163 @* Write the Derived Creation Routine::
164 @* Write Other Derived Routines::
168 Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type
170 Define the derived structures
172 You must define a structure for an entry in the hash table,
173 and a structure for the hash table itself.
175 The first field in the structure for an entry in the hash
176 table must be of the type used for an entry in the hash table
177 you are deriving from. If you are deriving from a basic hash
178 table this is <<struct bfd_hash_entry>>, which is defined in
179 <<bfd.h>>. The first field in the structure for the hash
180 table itself must be of the type of the hash table you are
181 deriving from itself. If you are deriving from a basic hash
182 table, this is <<struct bfd_hash_table>>.
184 For example, the linker hash table defines <<struct
185 bfd_link_hash_entry>> (in <<bfdlink.h>>). The first field,
186 <<root>>, is of type <<struct bfd_hash_entry>>. Similarly,
187 the first field in <<struct bfd_link_hash_table>>, <<table>>,
188 is of type <<struct bfd_hash_table>>.
191 Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type
193 Write the derived creation routine
195 You must write a routine which will create and initialize an
196 entry in the hash table. This routine is passed as the
197 function argument to <<bfd_hash_table_init>>.
199 In order to permit other hash tables to be derived from the
200 hash table you are creating, this routine must be written in a
203 The first argument to the creation routine is a pointer to a
204 hash table entry. This may be <<NULL>>, in which case the
205 routine should allocate the right amount of space. Otherwise
206 the space has already been allocated by a hash table type
207 derived from this one.
209 After allocating space, the creation routine must call the
210 creation routine of the hash table type it is derived from,
211 passing in a pointer to the space it just allocated. This
212 will initialize any fields used by the base hash table.
214 Finally the creation routine must initialize any local fields
215 for the new hash table type.
217 Here is a boilerplate example of a creation routine.
218 @var{function_name} is the name of the routine.
219 @var{entry_type} is the type of an entry in the hash table you
220 are creating. @var{base_newfunc} is the name of the creation
221 routine of the hash table type your hash table is derived
226 .struct bfd_hash_entry *
227 .@var{function_name} (entry, table, string)
228 . struct bfd_hash_entry *entry;
229 . struct bfd_hash_table *table;
230 . const char *string;
232 . struct @var{entry_type} *ret = (@var{entry_type} *) entry;
234 . {* Allocate the structure if it has not already been allocated by a
236 . if (ret == (@var{entry_type} *) NULL)
237 . ret = ((@var{entry_type} *)
238 . bfd_hash_allocate (table, sizeof (@var{entry_type})));
240 . {* Call the allocation method of the base class. *}
241 . ret = ((@var{entry_type} *)
242 . @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string));
244 . {* Initialize the local fields here. *}
246 . return (struct bfd_hash_entry *) ret;
250 The creation routine for the linker hash table, which is in
251 <<linker.c>>, looks just like this example.
252 @var{function_name} is <<_bfd_link_hash_newfunc>>.
253 @var{entry_type} is <<struct bfd_link_hash_entry>>.
254 @var{base_newfunc} is <<bfd_hash_newfunc>>, the creation
255 routine for a basic hash table.
257 <<_bfd_link_hash_newfunc>> also initializes the local fields
258 in a linker hash table entry: <<type>>, <<written>> and
262 Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type
264 Write other derived routines
266 You will want to write other routines for your new hash table,
269 You will want an initialization routine which calls the
270 initialization routine of the hash table you are deriving from
271 and initializes any other local fields. For the linker hash
272 table, this is <<_bfd_link_hash_table_init>> in <<linker.c>>.
274 You will want a lookup routine which calls the lookup routine
275 of the hash table you are deriving from and casts the result.
276 The linker hash table uses <<bfd_link_hash_lookup>> in
277 <<linker.c>> (this actually takes an additional argument which
278 it uses to decide how to return the looked up value).
280 You may want a traversal routine. This should just call the
281 traversal routine of the hash table you are deriving from with
282 appropriate casts. The linker hash table uses
283 <<bfd_link_hash_traverse>> in <<linker.c>>.
285 These routines may simply be defined as macros. For example,
286 the a.out backend linker hash table, which is derived from the
287 linker hash table, uses macros for the lookup and traversal
288 routines. These are <<aout_link_hash_lookup>> and
289 <<aout_link_hash_traverse>> in aoutx.h.
292 /* Obstack allocation and deallocation routines. */
293 #define obstack_chunk_alloc bfd_xmalloc_by_size_t
294 #define obstack_chunk_free free
296 /* The default number of entries to use when creating a hash table. */
297 #define DEFAULT_SIZE (4051)
299 /* Create a new hash table, given a number of entries. */
302 bfd_hash_table_init_n (table
, newfunc
, size
)
303 struct bfd_hash_table
*table
;
304 struct bfd_hash_entry
*(*newfunc
) PARAMS ((struct bfd_hash_entry
*,
305 struct bfd_hash_table
*,
311 alloc
= size
* sizeof (struct bfd_hash_entry
*);
312 obstack_begin (&table
->memory
, alloc
);
313 table
->table
= ((struct bfd_hash_entry
**)
314 obstack_alloc (&table
->memory
, alloc
));
315 memset ((PTR
) table
->table
, 0, alloc
);
317 table
->newfunc
= newfunc
;
321 /* Create a new hash table with the default number of entries. */
324 bfd_hash_table_init (table
, newfunc
)
325 struct bfd_hash_table
*table
;
326 struct bfd_hash_entry
*(*newfunc
) PARAMS ((struct bfd_hash_entry
*,
327 struct bfd_hash_table
*,
330 return bfd_hash_table_init_n (table
, newfunc
, DEFAULT_SIZE
);
333 /* Free a hash table. */
336 bfd_hash_table_free (table
)
337 struct bfd_hash_table
*table
;
339 obstack_free (&table
->memory
, (PTR
) NULL
);
342 /* Look up a string in a hash table. */
344 struct bfd_hash_entry
*
345 bfd_hash_lookup (table
, string
, create
, copy
)
346 struct bfd_hash_table
*table
;
351 register const unsigned char *s
;
352 register unsigned long hash
;
353 register unsigned int c
;
354 struct bfd_hash_entry
*hashp
;
360 s
= (const unsigned char *) string
;
361 while ((c
= *s
++) != '\0')
363 hash
+= c
+ (c
<< 17);
367 hash
+= len
+ (len
<< 17);
370 index
= hash
% table
->size
;
371 for (hashp
= table
->table
[index
];
372 hashp
!= (struct bfd_hash_entry
*) NULL
;
375 if (hashp
->hash
== hash
376 && strcmp (hashp
->string
, string
) == 0)
381 return (struct bfd_hash_entry
*) NULL
;
383 hashp
= (*table
->newfunc
) ((struct bfd_hash_entry
*) NULL
, table
, string
);
384 if (hashp
== (struct bfd_hash_entry
*) NULL
)
385 return (struct bfd_hash_entry
*) NULL
;
390 new = (char *) obstack_alloc (&table
->memory
, len
+ 1);
391 strcpy (new, string
);
394 hashp
->string
= string
;
396 hashp
->next
= table
->table
[index
];
397 table
->table
[index
] = hashp
;
402 /* Base method for creating a new hash table entry. */
405 struct bfd_hash_entry
*
406 bfd_hash_newfunc (entry
, table
, string
)
407 struct bfd_hash_entry
*entry
;
408 struct bfd_hash_table
*table
;
411 if (entry
== (struct bfd_hash_entry
*) NULL
)
412 entry
= ((struct bfd_hash_entry
*)
413 bfd_hash_allocate (table
, sizeof (struct bfd_hash_entry
)));
417 /* Allocate space in a hash table. */
420 bfd_hash_allocate (table
, size
)
421 struct bfd_hash_table
*table
;
424 return obstack_alloc (&table
->memory
, size
);
427 /* Traverse a hash table. */
430 bfd_hash_traverse (table
, func
, info
)
431 struct bfd_hash_table
*table
;
432 boolean (*func
) PARAMS ((struct bfd_hash_entry
*, PTR
));
437 for (i
= 0; i
< table
->size
; i
++)
439 struct bfd_hash_entry
*p
;
441 for (p
= table
->table
[i
]; p
!= NULL
; p
= p
->next
)
443 if (! (*func
) (p
, info
))
This page took 0.03713 seconds and 4 git commands to generate.