Branch data 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 : 6009615 : lookup (htab, hval, val)
48 : : NAME *htab;
49 : : HASHTYPE hval;
50 : : TYPE val __attribute__ ((unused));
51 : : {
52 : : /* First hash function: simply take the modul but prevent zero. */
53 : 6009615 : size_t idx = 1 + hval % htab->size;
54 : :
55 [ + + ]: 6009615 : if (htab->table[idx].hashval != 0)
56 : : {
57 : : HASHTYPE hash;
58 : :
59 [ + + ]: 2974543 : if (htab->table[idx].hashval == hval
60 [ # # ]: 0 : && COMPARE (htab->table[idx].data, val) == 0)
61 : : return idx;
62 : :
63 : : /* Second hash function as suggested in [Knuth]. */
64 : 77991 : hash = 1 + hval % (htab->size - 2);
65 : :
66 : : do
67 : : {
68 [ + + ]: 335711 : if (idx <= hash)
69 : 167523 : idx = htab->size + idx - hash;
70 : : else
71 : 168188 : idx -= hash;
72 : :
73 : : /* If entry is found use it. */
74 [ + + ]: 335711 : if (htab->table[idx].hashval == hval
75 [ # # ]: 0 : && COMPARE (htab->table[idx].data, val) == 0)
76 : : return idx;
77 : : }
78 [ + + ]: 6267335 : while (htab->table[idx].hashval);
79 : : }
80 : : return idx;
81 : : }
82 : :
83 : :
84 : : static void
85 : 1764596 : insert_entry_2 (NAME *htab, HASHTYPE hval, size_t idx, TYPE data)
86 : : {
87 : : #ifdef ITERATE
88 [ + - ]: 249237 : if (htab->table[idx].hashval == 0)
89 : : {
90 : : # ifdef REVERSE
91 : 249237 : htab->table[idx].next = htab->first;
92 : 249237 : htab->first = &htab->table[idx];
93 : : # else
94 : : /* Add the new value to the list. */
95 : : if (htab->first == NULL)
96 : : htab->first = htab->table[idx].next = &htab->table[idx];
97 : : else
98 : : {
99 : : htab->table[idx].next = htab->first->next;
100 : : htab->first = htab->first->next = &htab->table[idx];
101 : : }
102 : : # endif
103 : : }
104 : : #endif
105 : :
106 : 1764596 : htab->table[idx].hashval = hval;
107 : 1764596 : htab->table[idx].data = data;
108 : :
109 : 1764596 : ++htab->filled;
110 [ + + ]: 1764596 : if (100 * htab->filled > 90 * htab->size)
111 : : {
112 : : /* Table is filled more than 90%. Resize the table. */
113 : : #ifdef ITERATE
114 : : __typeof__ (htab->first) first;
115 : : # ifndef REVERSE
116 : : __typeof__ (htab->first) runp;
117 : : # endif
118 : : #else
119 : 15573 : size_t old_size = htab->size;
120 : : #endif
121 : : #define _TABLE(name) \
122 : : name##_ent *table = htab->table
123 : : #define TABLE(name) _TABLE (name)
124 : 15593 : TABLE(NAME);
125 : :
126 : 15593 : htab->size = next_prime (htab->size * 2);
127 : 15593 : htab->filled = 0;
128 : : #ifdef ITERATE
129 : 20 : first = htab->first;
130 : 20 : htab->first = NULL;
131 : : #endif
132 : 15593 : htab->table = calloc ((1 + htab->size), sizeof (htab->table[0]));
133 [ + - ]: 15593 : if (htab->table == NULL)
134 : : {
135 : : /* We cannot enlarge the table. Live with what we got. This
136 : : might lead to an infinite loop at some point, though. */
137 : 0 : htab->table = table;
138 : 1764596 : return;
139 : : }
140 : :
141 : : /* Add the old entries to the new table. When iteration is
142 : : supported we maintain the order. */
143 : : #ifdef ITERATE
144 : : # ifdef REVERSE
145 [ + + ]: 161252 : while (first != NULL)
146 : : {
147 : 161232 : insert_entry_2 (htab, first->hashval,
148 : : lookup (htab, first->hashval, first->data),
149 : : first->data);
150 : :
151 : 161232 : first = first->next;
152 : : }
153 : : # else
154 : : assert (first != NULL);
155 : : runp = first = first->next;
156 : : do
157 : : insert_entry_2 (htab, runp->hashval,
158 : : lookup (htab, runp->hashval, runp->data), runp->data);
159 : : while ((runp = runp->next) != first);
160 : : # endif
161 : : #else
162 [ + + ]: 733572 : for (idx = 1; idx <= old_size; ++idx)
163 [ + + ]: 717999 : if (table[idx].hashval != 0)
164 : 648135 : insert_entry_2 (htab, table[idx].hashval,
165 : : lookup (htab, table[idx].hashval, table[idx].data),
166 : : table[idx].data);
167 : : #endif
168 : :
169 : 15593 : free (table);
170 : : }
171 : : }
172 : :
173 : :
174 : : int
175 : : #define INIT(name) _INIT (name)
176 : : #define _INIT(name) \
177 : : name##_init
178 : 24627 : INIT(NAME) (htab, init_size)
179 : : NAME *htab;
180 : : size_t init_size;
181 : : {
182 : : /* We need the size to be a prime. */
183 : 24627 : init_size = next_prime (init_size);
184 : :
185 : : /* Initialize the data structure. */
186 : 24627 : htab->size = init_size;
187 : 24627 : htab->filled = 0;
188 : : #ifdef ITERATE
189 : 9 : htab->first = NULL;
190 : : #endif
191 : 24627 : htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0]));
192 [ + - ]: 24627 : if (htab->table == NULL)
193 : : return -1;
194 : :
195 : 24627 : return 0;
196 : : }
197 : :
198 : :
199 : : int
200 : : #define FREE(name) _FREE (name)
201 : : #define _FREE(name) \
202 : : name##_free
203 : 24524 : FREE(NAME) (htab)
204 : : NAME *htab;
205 : : {
206 : 24524 : free (htab->table);
207 : 24524 : return 0;
208 : : }
209 : :
210 : :
211 : : int
212 : : #define INSERT(name) _INSERT (name)
213 : : #define _INSERT(name) \
214 : : name##_insert
215 : 955229 : INSERT(NAME) (htab, hval, data)
216 : : NAME *htab;
217 : : HASHTYPE hval;
218 : : TYPE data;
219 : : {
220 : : size_t idx;
221 : :
222 : : /* Make the hash value nonzero. */
223 [ + - ]: 955229 : hval = hval ?: 1;
224 : :
225 : 955229 : idx = lookup (htab, hval, data);
226 : :
227 [ + - ]: 955229 : if (htab->table[idx].hashval != 0)
228 : : /* We don't want to overwrite the old value. */
229 : : return -1;
230 : :
231 : : /* An empty bucket has been found. */
232 : 955229 : insert_entry_2 (htab, hval, idx, data);
233 : 955229 : return 0;
234 : : }
235 : :
236 : :
237 : : #ifdef OVERWRITE
238 : : int
239 : : #define INSERT(name) _INSERT (name)
240 : : #define _INSERT(name) \
241 : : name##_overwrite
242 : : INSERT(NAME) (htab, hval, data)
243 : : NAME *htab;
244 : : HASHTYPE hval;
245 : : TYPE data;
246 : : {
247 : : size_t idx;
248 : :
249 : : /* Make the hash value nonzero. */
250 : : hval = hval ?: 1;
251 : :
252 : : idx = lookup (htab, hval, data);
253 : :
254 : : /* The correct bucket has been found. */
255 : : insert_entry_2 (htab, hval, idx, data);
256 : : return 0;
257 : : }
258 : : #endif
259 : :
260 : :
261 : : TYPE
262 : : #define FIND(name) _FIND (name)
263 : : #define _FIND(name) \
264 : : name##_find
265 : 4245019 : FIND(NAME) (htab, hval, val)
266 : : NAME *htab;
267 : : HASHTYPE hval;
268 : : TYPE val;
269 : : {
270 : : size_t idx;
271 : :
272 : : /* Make the hash value nonzero. */
273 [ + - ]: 4245019 : hval = hval ?: 1;
274 : :
275 : 4245019 : idx = lookup (htab, hval, val);
276 : :
277 [ + + ]: 4245019 : if (htab->table[idx].hashval == 0)
278 : : return NULL;
279 : :
280 : 4245019 : return htab->table[idx].data;
281 : : }
282 : :
283 : :
284 : : #ifdef ITERATE
285 : : # define ITERATEFCT(name) _ITERATEFCT (name)
286 : : # define _ITERATEFCT(name) \
287 : : name##_iterate
288 : : TYPE
289 : 176024 : ITERATEFCT(NAME) (htab, ptr)
290 : : NAME *htab;
291 : : void **ptr;
292 : : {
293 : 176024 : void *p = *ptr;
294 : :
295 : : # define TYPENAME(name) _TYPENAME (name)
296 : : # define _TYPENAME(name) name##_ent
297 : :
298 : : # ifdef REVERSE
299 [ + + ]: 176024 : if (p == NULL)
300 : 14 : p = htab->first;
301 : : else
302 : 176010 : p = ((TYPENAME(NAME) *) p)->next;
303 : :
304 [ + + ]: 176024 : if (p == NULL)
305 : : {
306 : 14 : *ptr = NULL;
307 : 14 : return NULL;
308 : : }
309 : : # else
310 : : if (p == NULL)
311 : : {
312 : : if (htab->first == NULL)
313 : : return NULL;
314 : : p = htab->first->next;
315 : : }
316 : : else
317 : : {
318 : : if (p == htab->first)
319 : : return NULL;
320 : :
321 : : p = ((TYPENAME(NAME) *) p)->next;
322 : : }
323 : : # endif
324 : :
325 : : /* Prepare the next element. If possible this will pull the data
326 : : into the cache, for reading. */
327 : 176010 : __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2);
328 : :
329 : 176024 : return ((TYPENAME(NAME) *) (*ptr = p))->data;
330 : : }
331 : : #endif
|
