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
46static size_t
47lookup (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
82static void
83insert_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
172int
173#define INIT(name) _INIT (name)
174#define _INIT(name) \
175  name##_init
176INIT(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
195int
196#define FREE(name) _FREE (name)
197#define _FREE(name) \
198  name##_free
199FREE(NAME) (NAME *htab)
200{
201  free (htab->table);
202  return 0;
203}
204
205
206int
207#define INSERT(name) _INSERT (name)
208#define _INSERT(name) \
209  name##_insert
210INSERT(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
230int
231#define INSERT(name) _INSERT (name)
232#define _INSERT(name) \
233  name##_overwrite
234INSERT(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
250TYPE
251#define FIND(name) _FIND (name)
252#define _FIND(name) \
253  name##_find
254FIND(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
274TYPE
275ITERATEFCT(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