dynamicsizehash.c revision b47e28a743afef4cd02fbe753c1526ed89c472c9 
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 (htab, hval, val)
48     NAME *htab;
49     HASHTYPE hval;
50     TYPE val __attribute__ ((unused));
51{
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);
55
56  if (htab->table[idx].hashval != 0)
57    {
58      HASHTYPE hash;
59
60      if (htab->table[idx].hashval == hval
61	  && COMPARE (htab->table[idx].data, val) == 0)
62	return idx;
63
64      /* Second hash function as suggested in [Knuth].  */
65      hash = 1 + hval % (htab->size - 2);
66
67      do
68	{
69	  if (idx <= hash)
70	    idx = htab->size + idx - hash;
71	  else
72	    idx -= hash;
73
74	  /* If entry is found use it.  */
75	  if (htab->table[idx].hashval == hval
76	      && COMPARE (htab->table[idx].data, val) == 0)
77	    return idx;
78	}
79      while (htab->table[idx].hashval);
80    }
81  return idx;
82}
83
84
85static void
86insert_entry_2 (NAME *htab, HASHTYPE hval, size_t idx, TYPE data)
87{
88#ifdef ITERATE
89  if (htab->table[idx].hashval == 0)
90    {
91# ifdef REVERSE
92      htab->table[idx].next = htab->first;
93      htab->first = &htab->table[idx];
94# else
95      /* Add the new value to the list.  */
96      if (htab->first == NULL)
97	htab->first = htab->table[idx].next = &htab->table[idx];
98      else
99	{
100	  htab->table[idx].next = htab->first->next;
101	  htab->first = htab->first->next = &htab->table[idx];
102	}
103# endif
104    }
105#endif
106
107  htab->table[idx].hashval = hval;
108  htab->table[idx].data = data;
109
110  ++htab->filled;
111  if (100 * htab->filled > 90 * htab->size)
112    {
113      /* Table is filled more than 90%.  Resize the table.  */
114#ifdef ITERATE
115      __typeof__ (htab->first) first;
116# ifndef REVERSE
117      __typeof__ (htab->first) runp;
118# endif
119#else
120      size_t old_size = htab->size;
121#endif
122#define _TABLE(name) \
123      name##_ent *table = htab->table
124#define TABLE(name) _TABLE (name)
125      TABLE(NAME);
126
127      htab->size = next_prime (htab->size * 2);
128      htab->filled = 0;
129#ifdef ITERATE
130      first = htab->first;
131      htab->first = NULL;
132#endif
133      htab->table = calloc ((1 + htab->size), sizeof (htab->table[0]));
134      if (htab->table == NULL)
135	{
136	  /* We cannot enlarge the table.  Live with what we got.  This
137	     might lead to an infinite loop at some point, though.  */
138	  htab->table = table;
139	  return;
140	}
141
142      /* Add the old entries to the new table.  When iteration is
143	 supported we maintain the order.  */
144#ifdef ITERATE
145# ifdef REVERSE
146      while (first != NULL)
147	{
148	  insert_entry_2 (htab, first->hashval,
149			  lookup (htab, first->hashval, first->data),
150			  first->data);
151
152	  first = first->next;
153	}
154# else
155      assert (first != NULL);
156      runp = first = first->next;
157      do
158	insert_entry_2 (htab, runp->hashval,
159			lookup (htab, runp->hashval, runp->data), runp->data);
160      while ((runp = runp->next) != first);
161# endif
162#else
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),
167			  table[idx].data);
168#endif
169
170      free (table);
171    }
172}
173
174
175int
176#define INIT(name) _INIT (name)
177#define _INIT(name) \
178  name##_init
179INIT(NAME) (htab, init_size)
180     NAME *htab;
181     size_t init_size;
182{
183  /* We need the size to be a prime.  */
184  init_size = next_prime (init_size);
185
186  /* Initialize the data structure.  */
187  htab->size = init_size;
188  htab->filled = 0;
189#ifdef ITERATE
190  htab->first = NULL;
191#endif
192  htab->table = (void *) calloc ((init_size + 1), sizeof (htab->table[0]));
193  if (htab->table == NULL)
194    return -1;
195
196  return 0;
197}
198
199
200int
201#define FREE(name) _FREE (name)
202#define _FREE(name) \
203  name##_free
204FREE(NAME) (htab)
205     NAME *htab;
206{
207  free (htab->table);
208  return 0;
209}
210
211
212int
213#define INSERT(name) _INSERT (name)
214#define _INSERT(name) \
215  name##_insert
216INSERT(NAME) (htab, hval, data)
217     NAME *htab;
218     HASHTYPE hval;
219     TYPE data;
220{
221  size_t idx;
222
223  /* Make the hash value nonzero.  */
224  hval = hval ?: 1;
225
226  idx = lookup (htab, hval, data);
227
228  if (htab->table[idx].hashval != 0)
229    /* We don't want to overwrite the old value.  */
230    return -1;
231
232  /* An empty bucket has been found.  */
233  insert_entry_2 (htab, hval, idx, data);
234  return 0;
235}
236
237
238#ifdef OVERWRITE
239int
240#define INSERT(name) _INSERT (name)
241#define _INSERT(name) \
242  name##_overwrite
243INSERT(NAME) (htab, hval, data)
244     NAME *htab;
245     HASHTYPE hval;
246     TYPE data;
247{
248  size_t idx;
249
250  /* Make the hash value nonzero.  */
251  hval = hval ?: 1;
252
253  idx = lookup (htab, hval, data);
254
255  /* The correct bucket has been found.  */
256  insert_entry_2 (htab, hval, idx, data);
257  return 0;
258}
259#endif
260
261
262TYPE
263#define FIND(name) _FIND (name)
264#define _FIND(name) \
265  name##_find
266FIND(NAME) (htab, hval, val)
267     NAME *htab;
268     HASHTYPE hval;
269     TYPE val;
270{
271  size_t idx;
272
273  /* Make the hash value nonzero.  */
274  hval = hval ?: 1;
275
276  idx = lookup (htab, hval, val);
277
278  if (htab->table[idx].hashval == 0)
279    return NULL;
280
281  return htab->table[idx].data;
282}
283
284
285#ifdef ITERATE
286# define ITERATEFCT(name) _ITERATEFCT (name)
287# define _ITERATEFCT(name) \
288  name##_iterate
289TYPE
290ITERATEFCT(NAME) (htab, ptr)
291     NAME *htab;
292     void **ptr;
293{
294  void *p = *ptr;
295
296# define TYPENAME(name) _TYPENAME (name)
297# define _TYPENAME(name) name##_ent
298
299# ifdef REVERSE
300  if (p == NULL)
301    p = htab->first;
302  else
303    p = ((TYPENAME(NAME) *) p)->next;
304
305  if (p == NULL)
306    {
307      *ptr = NULL;
308      return NULL;
309    }
310# else
311  if (p == NULL)
312    {
313      if (htab->first == NULL)
314	return NULL;
315      p = htab->first->next;
316    }
317  else
318    {
319      if (p == htab->first)
320	return NULL;
321
322      p = ((TYPENAME(NAME) *) p)->next;
323    }
324# endif
325
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);
329
330  return ((TYPENAME(NAME) *) (*ptr = p))->data;
331}
332#endif
333