OpenCores
URL https://opencores.org/ocsvn/openrisc/openrisc/trunk

Subversion Repositories openrisc

[/] [openrisc/] [trunk/] [gnu-old/] [gdb-7.1/] [bfd/] [doc/] [hash.texi] - Blame information for rev 853

Go to most recent revision | Details | Compare with Previous | View Log

Line No. Rev Author Line
1 227 jeremybenn
@section Hash Tables
2
@cindex Hash tables
3
BFD provides a simple set of hash table functions.  Routines
4
are provided to initialize a hash table, to free a hash table,
5
to look up a string in a hash table and optionally create an
6
entry for it, and to traverse a hash table.  There is
7
currently no routine to delete an string from a hash table.
8
 
9
The basic hash table does not permit any data to be stored
10
with a string.  However, a hash table is designed to present a
11
base class from which other types of hash tables may be
12
derived.  These derived types may store additional information
13
with the string.  Hash tables were implemented in this way,
14
rather than simply providing a data pointer in a hash table
15
entry, because they were designed for use by the linker back
16
ends.  The linker may create thousands of hash table entries,
17
and the overhead of allocating private data and storing and
18
following pointers becomes noticeable.
19
 
20
The basic hash table code is in @code{hash.c}.
21
 
22
@menu
23
* Creating and Freeing a Hash Table::
24
* Looking Up or Entering a String::
25
* Traversing a Hash Table::
26
* Deriving a New Hash Table Type::
27
@end menu
28
 
29
@node Creating and Freeing a Hash Table, Looking Up or Entering a String, Hash Tables, Hash Tables
30
@subsection Creating and freeing a hash table
31
@findex bfd_hash_table_init
32
@findex bfd_hash_table_init_n
33
To create a hash table, create an instance of a @code{struct
34
bfd_hash_table} (defined in @code{bfd.h}) and call
35
@code{bfd_hash_table_init} (if you know approximately how many
36
entries you will need, the function @code{bfd_hash_table_init_n},
37
which takes a @var{size} argument, may be used).
38
@code{bfd_hash_table_init} returns @code{FALSE} if some sort of
39
error occurs.
40
 
41
@findex bfd_hash_newfunc
42
The function @code{bfd_hash_table_init} take as an argument a
43
function to use to create new entries.  For a basic hash
44
table, use the function @code{bfd_hash_newfunc}.  @xref{Deriving
45
a New Hash Table Type}, for why you would want to use a
46
different value for this argument.
47
 
48
@findex bfd_hash_allocate
49
@code{bfd_hash_table_init} will create an objalloc which will be
50
used to allocate new entries.  You may allocate memory on this
51
objalloc using @code{bfd_hash_allocate}.
52
 
53
@findex bfd_hash_table_free
54
Use @code{bfd_hash_table_free} to free up all the memory that has
55
been allocated for a hash table.  This will not free up the
56
@code{struct bfd_hash_table} itself, which you must provide.
57
 
58
@findex bfd_hash_set_default_size
59
Use @code{bfd_hash_set_default_size} to set the default size of
60
hash table to use.
61
 
62
@node Looking Up or Entering a String, Traversing a Hash Table, Creating and Freeing a Hash Table, Hash Tables
63
@subsection Looking up or entering a string
64
@findex bfd_hash_lookup
65
The function @code{bfd_hash_lookup} is used both to look up a
66
string in the hash table and to create a new entry.
67
 
68
If the @var{create} argument is @code{FALSE}, @code{bfd_hash_lookup}
69
will look up a string.  If the string is found, it will
70
returns a pointer to a @code{struct bfd_hash_entry}.  If the
71
string is not found in the table @code{bfd_hash_lookup} will
72
return @code{NULL}.  You should not modify any of the fields in
73
the returns @code{struct bfd_hash_entry}.
74
 
75
If the @var{create} argument is @code{TRUE}, the string will be
76
entered into the hash table if it is not already there.
77
Either way a pointer to a @code{struct bfd_hash_entry} will be
78
returned, either to the existing structure or to a newly
79
created one.  In this case, a @code{NULL} return means that an
80
error occurred.
81
 
82
If the @var{create} argument is @code{TRUE}, and a new entry is
83
created, the @var{copy} argument is used to decide whether to
84
copy the string onto the hash table objalloc or not.  If
85
@var{copy} is passed as @code{FALSE}, you must be careful not to
86
deallocate or modify the string as long as the hash table
87
exists.
88
 
89
@node Traversing a Hash Table, Deriving a New Hash Table Type, Looking Up or Entering a String, Hash Tables
90
@subsection Traversing a hash table
91
@findex bfd_hash_traverse
92
The function @code{bfd_hash_traverse} may be used to traverse a
93
hash table, calling a function on each element.  The traversal
94
is done in a random order.
95
 
96
@code{bfd_hash_traverse} takes as arguments a function and a
97
generic @code{void *} pointer.  The function is called with a
98
hash table entry (a @code{struct bfd_hash_entry *}) and the
99
generic pointer passed to @code{bfd_hash_traverse}.  The function
100
must return a @code{boolean} value, which indicates whether to
101
continue traversing the hash table.  If the function returns
102
@code{FALSE}, @code{bfd_hash_traverse} will stop the traversal and
103
return immediately.
104
 
105
@node Deriving a New Hash Table Type, , Traversing a Hash Table, Hash Tables
106
@subsection Deriving a new hash table type
107
Many uses of hash tables want to store additional information
108
which each entry in the hash table.  Some also find it
109
convenient to store additional information with the hash table
110
itself.  This may be done using a derived hash table.
111
 
112
Since C is not an object oriented language, creating a derived
113
hash table requires sticking together some boilerplate
114
routines with a few differences specific to the type of hash
115
table you want to create.
116
 
117
An example of a derived hash table is the linker hash table.
118
The structures for this are defined in @code{bfdlink.h}.  The
119
functions are in @code{linker.c}.
120
 
121
You may also derive a hash table from an already derived hash
122
table.  For example, the a.out linker backend code uses a hash
123
table derived from the linker hash table.
124
 
125
@menu
126
* Define the Derived Structures::
127
* Write the Derived Creation Routine::
128
* Write Other Derived Routines::
129
@end menu
130
 
131
@node Define the Derived Structures, Write the Derived Creation Routine, Deriving a New Hash Table Type, Deriving a New Hash Table Type
132
@subsubsection Define the derived structures
133
You must define a structure for an entry in the hash table,
134
and a structure for the hash table itself.
135
 
136
The first field in the structure for an entry in the hash
137
table must be of the type used for an entry in the hash table
138
you are deriving from.  If you are deriving from a basic hash
139
table this is @code{struct bfd_hash_entry}, which is defined in
140
@code{bfd.h}.  The first field in the structure for the hash
141
table itself must be of the type of the hash table you are
142
deriving from itself.  If you are deriving from a basic hash
143
table, this is @code{struct bfd_hash_table}.
144
 
145
For example, the linker hash table defines @code{struct
146
bfd_link_hash_entry} (in @code{bfdlink.h}).  The first field,
147
@code{root}, is of type @code{struct bfd_hash_entry}.  Similarly,
148
the first field in @code{struct bfd_link_hash_table}, @code{table},
149
is of type @code{struct bfd_hash_table}.
150
 
151
@node Write the Derived Creation Routine, Write Other Derived Routines, Define the Derived Structures, Deriving a New Hash Table Type
152
@subsubsection Write the derived creation routine
153
You must write a routine which will create and initialize an
154
entry in the hash table.  This routine is passed as the
155
function argument to @code{bfd_hash_table_init}.
156
 
157
In order to permit other hash tables to be derived from the
158
hash table you are creating, this routine must be written in a
159
standard way.
160
 
161
The first argument to the creation routine is a pointer to a
162
hash table entry.  This may be @code{NULL}, in which case the
163
routine should allocate the right amount of space.  Otherwise
164
the space has already been allocated by a hash table type
165
derived from this one.
166
 
167
After allocating space, the creation routine must call the
168
creation routine of the hash table type it is derived from,
169
passing in a pointer to the space it just allocated.  This
170
will initialize any fields used by the base hash table.
171
 
172
Finally the creation routine must initialize any local fields
173
for the new hash table type.
174
 
175
Here is a boilerplate example of a creation routine.
176
@var{function_name} is the name of the routine.
177
@var{entry_type} is the type of an entry in the hash table you
178
are creating.  @var{base_newfunc} is the name of the creation
179
routine of the hash table type your hash table is derived
180
from.
181
 
182
 
183
@example
184
struct bfd_hash_entry *
185
@var{function_name} (struct bfd_hash_entry *entry,
186
                     struct bfd_hash_table *table,
187
                     const char *string)
188
@{
189
  struct @var{entry_type} *ret = (@var{entry_type} *) entry;
190
 
191
 /* Allocate the structure if it has not already been allocated by a
192
    derived class.  */
193
  if (ret == NULL)
194
    @{
195
      ret = bfd_hash_allocate (table, sizeof (* ret));
196
      if (ret == NULL)
197
        return NULL;
198
    @}
199
 
200
 /* Call the allocation method of the base class.  */
201
  ret = ((@var{entry_type} *)
202
        @var{base_newfunc} ((struct bfd_hash_entry *) ret, table, string));
203
 
204
 /* Initialize the local fields here.  */
205
 
206
  return (struct bfd_hash_entry *) ret;
207
@}
208
@end example
209
@strong{Description}@*
210
The creation routine for the linker hash table, which is in
211
@code{linker.c}, looks just like this example.
212
@var{function_name} is @code{_bfd_link_hash_newfunc}.
213
@var{entry_type} is @code{struct bfd_link_hash_entry}.
214
@var{base_newfunc} is @code{bfd_hash_newfunc}, the creation
215
routine for a basic hash table.
216
 
217
@code{_bfd_link_hash_newfunc} also initializes the local fields
218
in a linker hash table entry: @code{type}, @code{written} and
219
@code{next}.
220
 
221
@node Write Other Derived Routines, , Write the Derived Creation Routine, Deriving a New Hash Table Type
222
@subsubsection Write other derived routines
223
You will want to write other routines for your new hash table,
224
as well.
225
 
226
You will want an initialization routine which calls the
227
initialization routine of the hash table you are deriving from
228
and initializes any other local fields.  For the linker hash
229
table, this is @code{_bfd_link_hash_table_init} in @code{linker.c}.
230
 
231
You will want a lookup routine which calls the lookup routine
232
of the hash table you are deriving from and casts the result.
233
The linker hash table uses @code{bfd_link_hash_lookup} in
234
@code{linker.c} (this actually takes an additional argument which
235
it uses to decide how to return the looked up value).
236
 
237
You may want a traversal routine.  This should just call the
238
traversal routine of the hash table you are deriving from with
239
appropriate casts.  The linker hash table uses
240
@code{bfd_link_hash_traverse} in @code{linker.c}.
241
 
242
These routines may simply be defined as macros.  For example,
243
the a.out backend linker hash table, which is derived from the
244
linker hash table, uses macros for the lookup and traversal
245
routines.  These are @code{aout_link_hash_lookup} and
246
@code{aout_link_hash_traverse} in aoutx.h.
247
 

powered by: WebSVN 2.1.0

© copyright 1999-2024 OpenCores.org, equivalent to Oliscience, all rights reserved. OpenCores®, registered trademark.