Line data Source code
1 : /* Copyright (C) 2000-2010 Red Hat, Inc.
2 : This file is part of elfutils.
3 : Written by Ulrich Drepper <drepper@redhat.com>, 2000.
4 :
5 : This file is free software; you can redistribute it and/or modify
6 : it under the terms of either
7 :
8 : * the GNU Lesser General Public License as published by the Free
9 : Software Foundation; either version 3 of the License, or (at
10 : your option) any later version
11 :
12 : or
13 :
14 : * the GNU General Public License as published by the Free
15 : Software Foundation; either version 2 of the License, or (at
16 : your option) any later version
17 :
18 : or both in parallel, as here.
19 :
20 : elfutils is distributed in the hope that it will be useful, but
21 : WITHOUT ANY WARRANTY; without even the implied warranty of
22 : MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
23 : General Public License for more details.
24 :
25 : You should have received copies of the GNU General Public License and
26 : the GNU Lesser General Public License along with this program. If
27 : not, see <http://www.gnu.org/licenses/>. */
28 :
29 : #include <assert.h>
30 : #include <stdlib.h>
31 : #include <system.h>
32 :
33 : /* Before including this file the following macros must be defined:
34 :
35 : NAME name of the hash table structure.
36 : TYPE data type of the hash table entries
37 : COMPARE comparison function taking two pointers to TYPE objects
38 :
39 : The following macros if present select features:
40 :
41 : ITERATE iterating over the table entries is possible
42 : REVERSE iterate in reverse order of insert
43 : */
44 :
45 :
46 : static size_t
47 0 : lookup (NAME *htab, HASHTYPE hval, TYPE val __attribute__ ((unused)))
48 : {
49 : /* First hash function: simply take the modul but prevent zero. Small values
50 : can skip the division, which helps performance when this is common. */
51 0 : size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
52 :
53 0 : if (htab->table[idx].hashval != 0)
54 : {
55 0 : HASHTYPE hash;
56 :
57 0 : if (htab->table[idx].hashval == hval
58 0 : && COMPARE (htab->table[idx].data, val) == 0)
59 0 : return idx;
60 :
61 : /* Second hash function as suggested in [Knuth]. */
62 0 : hash = 1 + hval % (htab->size - 2);
63 :
64 0 : do
65 : {
66 0 : if (idx <= hash)
67 0 : idx = htab->size + idx - hash;
68 : else
69 0 : idx -= hash;
70 :
71 : /* If entry is found use it. */
72 0 : if (htab->table[idx].hashval == hval
73 0 : && COMPARE (htab->table[idx].data, val) == 0)
74 0 : return idx;
75 : }
76 0 : while (htab->table[idx].hashval);
77 : }
78 : return idx;
79 : }
80 :
81 :
82 : static void
83 249237 : insert_entry_2 (NAME *htab, HASHTYPE hval, size_t idx, TYPE data)
84 : {
85 : #ifdef ITERATE
86 249237 : if (htab->table[idx].hashval == 0)
87 : {
88 : # ifdef REVERSE
89 249237 : htab->table[idx].next = htab->first;
90 249237 : htab->first = &htab->table[idx];
91 : # else
92 : /* Add the new value to the list. */
93 : if (htab->first == NULL)
94 : htab->first = htab->table[idx].next = &htab->table[idx];
95 : else
96 : {
97 : htab->table[idx].next = htab->first->next;
98 : htab->first = htab->first->next = &htab->table[idx];
99 : }
100 : # endif
101 : }
102 : #endif
103 :
104 249237 : htab->table[idx].hashval = hval;
105 249237 : htab->table[idx].data = data;
106 :
107 249237 : ++htab->filled;
108 249237 : if (100 * htab->filled > 90 * htab->size)
109 : {
110 : /* Table is filled more than 90%. Resize the table. */
111 : #ifdef ITERATE
112 20 : __typeof__ (htab->first) first;
113 : # ifndef REVERSE
114 : __typeof__ (htab->first) runp;
115 : # endif
116 : #else
117 : size_t old_size = htab->size;
118 : #endif
119 : #define _TABLE(name) \
120 : name##_ent *table = htab->table
121 : #define TABLE(name) _TABLE (name)
122 20 : TABLE(NAME);
123 :
124 20 : htab->size = next_prime (htab->size * 2);
125 20 : htab->filled = 0;
126 : #ifdef ITERATE
127 20 : first = htab->first;
128 20 : htab->first = NULL;
129 : #endif
130 20 : htab->table = calloc ((1 + htab->size), sizeof (htab->table[0]));
131 20 : if (htab->table == NULL)
132 : {
133 : /* We cannot enlarge the table. Live with what we got. This
134 : might lead to an infinite loop at some point, though. */
135 0 : htab->table = table;
136 0 : return;
137 : }
138 :
139 : /* Add the old entries to the new table. When iteration is
140 : supported we maintain the order. */
141 : #ifdef ITERATE
142 : # ifdef REVERSE
143 161252 : while (first != NULL)
144 : {
145 161232 : insert_entry_2 (htab, first->hashval,
146 : lookup (htab, first->hashval, first->data),
147 : first->data);
148 :
149 161232 : first = first->next;
150 : }
151 : # else
152 : assert (first != NULL);
153 : runp = first = first->next;
154 : do
155 : insert_entry_2 (htab, runp->hashval,
156 : lookup (htab, runp->hashval, runp->data), runp->data);
157 : while ((runp = runp->next) != first);
158 : # endif
159 : #else
160 : for (idx = 1; idx <= old_size; ++idx)
161 : if (table[idx].hashval != 0)
162 : insert_entry_2 (htab, table[idx].hashval,
163 : lookup (htab, table[idx].hashval, table[idx].data),
164 : table[idx].data);
165 : #endif
166 :
167 20 : free (table);
168 : }
169 : }
170 :
171 :
172 : int
173 : #define INIT(name) _INIT (name)
174 : #define _INIT(name) \
175 : name##_init
176 9 : INIT(NAME) (NAME *htab, size_t init_size)
177 : {
178 : /* We need the size to be a prime. */
179 9 : init_size = next_prime (init_size);
180 :
181 : /* Initialize the data structure. */
182 9 : htab->size = init_size;
183 9 : htab->filled = 0;
184 : #ifdef ITERATE
185 9 : htab->first = NULL;
186 : #endif
187 9 : htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0]));
188 9 : if (htab->table == NULL)
189 0 : return -1;
190 :
191 : return 0;
192 : }
193 :
194 :
195 : int
196 : #define FREE(name) _FREE (name)
197 : #define _FREE(name) \
198 : name##_free
199 9 : FREE(NAME) (NAME *htab)
200 : {
201 9 : free (htab->table);
202 9 : return 0;
203 : }
204 :
205 :
206 : int
207 : #define INSERT(name) _INSERT (name)
208 : #define _INSERT(name) \
209 : name##_insert
210 88005 : INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
211 : {
212 88005 : size_t idx;
213 :
214 : /* Make the hash value nonzero. */
215 88005 : hval = hval ?: 1;
216 :
217 88005 : idx = lookup (htab, hval, data);
218 :
219 88005 : if (htab->table[idx].hashval != 0)
220 : /* We don't want to overwrite the old value. */
221 : return -1;
222 :
223 : /* An empty bucket has been found. */
224 88005 : insert_entry_2 (htab, hval, idx, data);
225 88005 : return 0;
226 : }
227 :
228 :
229 : #ifdef OVERWRITE
230 : int
231 : #define INSERT(name) _INSERT (name)
232 : #define _INSERT(name) \
233 : name##_overwrite
234 : INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
235 : {
236 : size_t idx;
237 :
238 : /* Make the hash value nonzero. */
239 : hval = hval ?: 1;
240 :
241 : idx = lookup (htab, hval, data);
242 :
243 : /* The correct bucket has been found. */
244 : insert_entry_2 (htab, hval, idx, data);
245 : return 0;
246 : }
247 : #endif
248 :
249 :
250 : TYPE
251 : #define FIND(name) _FIND (name)
252 : #define _FIND(name) \
253 : name##_find
254 0 : FIND(NAME) (NAME *htab, HASHTYPE hval, TYPE val)
255 : {
256 0 : size_t idx;
257 :
258 : /* Make the hash value nonzero. */
259 0 : hval = hval ?: 1;
260 :
261 0 : idx = lookup (htab, hval, val);
262 :
263 0 : if (htab->table[idx].hashval == 0)
264 : return NULL;
265 :
266 0 : return htab->table[idx].data;
267 : }
268 :
269 :
270 : #ifdef ITERATE
271 : # define ITERATEFCT(name) _ITERATEFCT (name)
272 : # define _ITERATEFCT(name) \
273 : name##_iterate
274 : TYPE
275 176024 : ITERATEFCT(NAME) (NAME *htab, void **ptr)
276 : {
277 176024 : void *p = *ptr;
278 :
279 : # define TYPENAME(name) _TYPENAME (name)
280 : # define _TYPENAME(name) name##_ent
281 :
282 : # ifdef REVERSE
283 176024 : if (p == NULL)
284 14 : p = htab->first;
285 : else
286 176010 : p = ((TYPENAME(NAME) *) p)->next;
287 :
288 176024 : if (p == NULL)
289 : {
290 14 : *ptr = NULL;
291 14 : return NULL;
292 : }
293 : # else
294 : if (p == NULL)
295 : {
296 : if (htab->first == NULL)
297 : return NULL;
298 : p = htab->first->next;
299 : }
300 : else
301 : {
302 : if (p == htab->first)
303 : return NULL;
304 :
305 : p = ((TYPENAME(NAME) *) p)->next;
306 : }
307 : # endif
308 :
309 : /* Prepare the next element. If possible this will pull the data
310 : into the cache, for reading. */
311 176010 : __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2);
312 :
313 176010 : return ((TYPENAME(NAME) *) (*ptr = p))->data;
314 : }
315 : #endif
|
