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 : 498474 : 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 [ + + ]: 498474 : size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
52 : :
53 [ + + ]: 498474 : if (htab->table[idx].hashval != 0)
54 : : {
55 : 150070 : HASHTYPE hash;
56 : :
57 [ - + ]: 150070 : if (htab->table[idx].hashval == hval
58 [ # # ]: 0 : && COMPARE (htab->table[idx].data, val) == 0)
59 : : return idx;
60 : :
61 : : /* Second hash function as suggested in [Knuth]. */
62 : 150070 : hash = 1 + hval % (htab->size - 2);
63 : :
64 : 665510 : do
65 : : {
66 [ + + ]: 665510 : if (idx <= hash)
67 : 329134 : idx = htab->size + idx - hash;
68 : : else
69 : 336376 : idx -= hash;
70 : :
71 : : /* If entry is found use it. */
72 [ - + ]: 665510 : if (htab->table[idx].hashval == hval
73 [ # # ]: 0 : && COMPARE (htab->table[idx].data, val) == 0)
74 : : return idx;
75 : : }
76 [ + + ]: 665510 : while (htab->table[idx].hashval);
77 : : }
78 : : return idx;
79 : : }
80 : :
81 : :
82 : : static void
83 : 498474 : insert_entry_2 (NAME *htab, HASHTYPE hval, size_t idx, TYPE data)
84 : : {
85 : : #ifdef ITERATE
86 [ + - ]: 498474 : if (htab->table[idx].hashval == 0)
87 : : {
88 : : # ifdef REVERSE
89 : 498474 : htab->table[idx].next = htab->first;
90 : 498474 : 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 : 498474 : htab->table[idx].hashval = hval;
105 : 498474 : htab->table[idx].data = data;
106 : :
107 : 498474 : ++htab->filled;
108 [ + + ]: 498474 : if (100 * htab->filled > 90 * htab->size)
109 : : {
110 : : /* Table is filled more than 90%. Resize the table. */
111 : : #ifdef ITERATE
112 : 40 : __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 : 40 : TABLE(NAME);
123 : :
124 : 40 : htab->size = next_prime (htab->size * 2);
125 : 40 : htab->filled = 0;
126 : : #ifdef ITERATE
127 : 40 : first = htab->first;
128 : 40 : htab->first = NULL;
129 : : #endif
130 : 40 : htab->table = calloc ((1 + htab->size), sizeof (htab->table[0]));
131 [ - + ]: 40 : 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 [ + + ]: 322504 : while (first != NULL)
144 : : {
145 : 322464 : insert_entry_2 (htab, first->hashval,
146 : : lookup (htab, first->hashval, first->data),
147 : : first->data);
148 : :
149 : 322464 : 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 : 40 : free (table);
168 : : }
169 : : }
170 : :
171 : :
172 : : int
173 : : #define INIT(name) _INIT (name)
174 : : #define _INIT(name) \
175 : : name##_init
176 : 18 : INIT(NAME) (NAME *htab, size_t init_size)
177 : : {
178 : : /* We need the size to be a prime. */
179 : 18 : init_size = next_prime (init_size);
180 : :
181 : : /* Initialize the data structure. */
182 : 18 : htab->size = init_size;
183 : 18 : htab->filled = 0;
184 : : #ifdef ITERATE
185 : 18 : htab->first = NULL;
186 : : #endif
187 : 18 : htab->table = calloc ((init_size + 1), sizeof (htab->table[0]));
188 [ - + ]: 18 : 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 : 18 : FREE(NAME) (NAME *htab)
200 : : {
201 : 18 : free (htab->table);
202 : 18 : return 0;
203 : : }
204 : :
205 : :
206 : : int
207 : : #define INSERT(name) _INSERT (name)
208 : : #define _INSERT(name) \
209 : : name##_insert
210 : 176010 : INSERT(NAME) (NAME *htab, HASHTYPE hval, TYPE data)
211 : : {
212 : 176010 : size_t idx;
213 : :
214 : : /* Make the hash value nonzero. */
215 [ - + ]: 176010 : hval = hval ?: 1;
216 : :
217 : 176010 : idx = lookup (htab, hval, data);
218 : :
219 [ + - ]: 176010 : 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 : 176010 : insert_entry_2 (htab, hval, idx, data);
225 : 176010 : 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 : 352048 : ITERATEFCT(NAME) (NAME *htab, void **ptr)
276 : : {
277 : 352048 : void *p = *ptr;
278 : :
279 : : # define TYPENAME(name) _TYPENAME (name)
280 : : # define _TYPENAME(name) name##_ent
281 : :
282 : : # ifdef REVERSE
283 [ + + ]: 352048 : if (p == NULL)
284 : 28 : p = htab->first;
285 : : else
286 : 352020 : p = ((TYPENAME(NAME) *) p)->next;
287 : :
288 [ + + ]: 352048 : if (p == NULL)
289 : : {
290 : 28 : *ptr = NULL;
291 : 28 : 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 : 352020 : __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2);
312 : :
313 : 352020 : return ((TYPENAME(NAME) *) (*ptr = p))->data;
314 : : }
315 : : #endif
|
