1 /* Copyright (C) 2000-2010 Red Hat, Inc.
2 This file is part of elfutils.
3 Written by Ulrich Drepper <drepper@redhat.com>, 2000.
5 This file is free software; you can redistribute it and/or modify
6 it under the terms of either
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
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
18 or both in parallel, as here.
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.
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/>. */
33 /* Before including this file the following macros must be defined:
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
39 The following macros if present select features:
41 ITERATE iterating over the table entries is possible
42 REVERSE iterate in reverse order of insert
47 lookup (htab, hval, val)
50 TYPE val __attribute__ ((unused));
52 /* First hash function: simply take the modul but prevent zero. Small values
53 can skip the division, which helps performance when this is common. */
54 size_t idx = 1 + (hval < htab->size ? hval : hval % htab->size);
56 if (htab->table[idx].hashval != 0)
60 if (htab->table[idx].hashval == hval
61 && COMPARE (htab->table[idx].data, val) == 0)
64 /* Second hash function as suggested in [Knuth]. */
65 hash = 1 + hval % (htab->size - 2);
70 idx = htab->size + idx - hash;
74 /* If entry is found use it. */
75 if (htab->table[idx].hashval == hval
76 && COMPARE (htab->table[idx].data, val) == 0)
79 while (htab->table[idx].hashval);
86 insert_entry_2 (NAME *htab, HASHTYPE hval, size_t idx, TYPE data)
89 if (htab->table[idx].hashval == 0)
92 htab->table[idx].next = htab->first;
93 htab->first = &htab->table[idx];
95 /* Add the new value to the list. */
96 if (htab->first == NULL)
97 htab->first = htab->table[idx].next = &htab->table[idx];
100 htab->table[idx].next = htab->first->next;
101 htab->first = htab->first->next = &htab->table[idx];
107 htab->table[idx].hashval = hval;
108 htab->table[idx].data = data;
111 if (100 * htab->filled > 90 * htab->size)
113 /* Table is filled more than 90%. Resize the table. */
115 __typeof__ (htab->first) first;
117 __typeof__ (htab->first) runp;
120 size_t old_size = htab->size;
122 #define _TABLE(name) \
123 name##_ent *table = htab->table
124 #define TABLE(name) _TABLE (name)
127 htab->size = next_prime (htab->size * 2);
133 htab->table = calloc ((1 + htab->size), sizeof (htab->table[0]));
134 if (htab->table == NULL)
136 /* We cannot enlarge the table. Live with what we got. This
137 might lead to an infinite loop at some point, though. */
142 /* Add the old entries to the new table. When iteration is
143 supported we maintain the order. */
146 while (first != NULL)
148 insert_entry_2 (htab, first->hashval,
149 lookup (htab, first->hashval, first->data),
155 assert (first != NULL);
156 runp = first = first->next;
158 insert_entry_2 (htab, runp->hashval,
159 lookup (htab, runp->hashval, runp->data), runp->data);
160 while ((runp = runp->next) != first);
163 for (idx = 1; idx <= old_size; ++idx)
164 if (table[idx].hashval != 0)
165 insert_entry_2 (htab, table[idx].hashval,
166 lookup (htab, table[idx].hashval, table[idx].data),
176 #define INIT(name) _INIT (name)
177 #define _INIT(name) \
179 INIT(NAME) (htab, init_size)
183 /* We need the size to be a prime. */
184 init_size = next_prime (init_size);
186 /* Initialize the data structure. */
187 htab->size = init_size;
192 htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0]));
193 if (htab->table == NULL)
201 #define FREE(name) _FREE (name)
202 #define _FREE(name) \
213 #define INSERT(name) _INSERT (name)
214 #define _INSERT(name) \
216 INSERT(NAME) (htab, hval, data)
223 /* Make the hash value nonzero. */
226 idx = lookup (htab, hval, data);
228 if (htab->table[idx].hashval != 0)
229 /* We don't want to overwrite the old value. */
232 /* An empty bucket has been found. */
233 insert_entry_2 (htab, hval, idx, data);
240 #define INSERT(name) _INSERT (name)
241 #define _INSERT(name) \
243 INSERT(NAME) (htab, hval, data)
250 /* Make the hash value nonzero. */
253 idx = lookup (htab, hval, data);
255 /* The correct bucket has been found. */
256 insert_entry_2 (htab, hval, idx, data);
263 #define FIND(name) _FIND (name)
264 #define _FIND(name) \
266 FIND(NAME) (htab, hval, val)
273 /* Make the hash value nonzero. */
276 idx = lookup (htab, hval, val);
278 if (htab->table[idx].hashval == 0)
281 return htab->table[idx].data;
286 # define ITERATEFCT(name) _ITERATEFCT (name)
287 # define _ITERATEFCT(name) \
290 ITERATEFCT(NAME) (htab, ptr)
296 # define TYPENAME(name) _TYPENAME (name)
297 # define _TYPENAME(name) name##_ent
303 p = ((TYPENAME(NAME) *) p)->next;
313 if (htab->first == NULL)
315 p = htab->first->next;
319 if (p == htab->first)
322 p = ((TYPENAME(NAME) *) p)->next;
326 /* Prepare the next element. If possible this will pull the data
327 into the cache, for reading. */
328 __builtin_prefetch (((TYPENAME(NAME) *) p)->next, 0, 2);
330 return ((TYPENAME(NAME) *) (*ptr = p))->data;