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