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