1/* Fixed size hash table with internal linking.
2   Copyright (C) 2000, 2001, 2002, 2004, 2005 Red Hat, Inc.
3   This file is part of elfutils.
4   Written by Ulrich Drepper <drepper@redhat.com>, 2000.
5
6   This file is free software; you can redistribute it and/or modify
7   it under the terms of either
8
9     * the GNU Lesser General Public License as published by the Free
10       Software Foundation; either version 3 of the License, or (at
11       your option) any later version
12
13   or
14
15     * the GNU General Public License as published by the Free
16       Software Foundation; either version 2 of the License, or (at
17       your option) any later version
18
19   or both in parallel, as here.
20
21   elfutils is distributed in the hope that it will be useful, but
22   WITHOUT ANY WARRANTY; without even the implied warranty of
23   MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
24   General Public License for more details.
25
26   You should have received copies of the GNU General Public License and
27   the GNU Lesser General Public License along with this program.  If
28   not, see <http://www.gnu.org/licenses/>.  */
29
30#include <errno.h>
31#include <stdlib.h>
32#include <string.h>
33#include <sys/cdefs.h>
34#include <sys/param.h>
35
36#include <system.h>
37
38#define CONCAT(t1,t2) __CONCAT (t1,t2)
39
40/* Before including this file the following macros must be defined:
41
42   TYPE           data type of the hash table entries
43   HASHFCT        name of the hashing function to use
44   HASHTYPE       type used for the hashing value
45   COMPARE        comparison function taking two pointers to TYPE objects
46   CLASS          can be defined to `static' to avoid exporting the functions
47   PREFIX         prefix to be used for function and data type names
48   STORE_POINTER  if defined the table stores a pointer and not an element
49                  of type TYPE
50   INSERT_HASH    if defined alternate insert function which takes a hash
51                  value is defined
52   NO_FINI_FCT    if defined the fini function is not defined
53*/
54
55
56/* Defined separately.  */
57extern size_t next_prime (size_t seed);
58
59
60/* Set default values.  */
61#ifndef HASHTYPE
62# define HASHTYPE size_t
63#endif
64
65#ifndef CLASS
66# define CLASS
67#endif
68
69#ifndef PREFIX
70# define PREFIX
71#endif
72
73
74/* The data structure.  */
75struct CONCAT(PREFIX,fshash)
76{
77  size_t nslots;
78  struct CONCAT(PREFIX,fshashent)
79  {
80    HASHTYPE hval;
81#ifdef STORE_POINTER
82# define ENTRYP(el) (el).entry
83    TYPE *entry;
84#else
85# define ENTRYP(el) &(el).entry
86    TYPE entry;
87#endif
88  } table[0];
89};
90
91
92/* Constructor for the hashing table.  */
93CLASS struct CONCAT(PREFIX,fshash) *
94CONCAT(PREFIX,fshash_init) (size_t nelems)
95{
96  struct CONCAT(PREFIX,fshash) *result;
97  /* We choose a size for the hashing table 150% over the number of
98     entries.  This will guarantee short medium search lengths.  */
99  const size_t max_size_t = ~((size_t) 0);
100
101  if (nelems >= (max_size_t / 3) * 2)
102    {
103      errno = EINVAL;
104      return NULL;
105    }
106
107  /* Adjust the size to be used for the hashing table.  */
108  nelems = next_prime (MAX ((nelems * 3) / 2, 10));
109
110  /* Allocate the data structure for the result.  */
111  result = (struct CONCAT(PREFIX,fshash) *)
112    xcalloc (sizeof (struct CONCAT(PREFIX,fshash))
113	     + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1);
114  if (result == NULL)
115    return NULL;
116
117  result->nslots = nelems;
118
119  return result;
120}
121
122
123#ifndef NO_FINI_FCT
124CLASS void
125CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
126{
127  free (htab);
128}
129#endif
130
131
132static struct CONCAT(PREFIX,fshashent) *
133CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab,
134			      HASHTYPE hval, TYPE *data)
135{
136  size_t idx = 1 + hval % htab->nslots;
137
138  if (htab->table[idx].hval != 0)
139    {
140      HASHTYPE hash;
141
142      /* See whether this is the same entry.  */
143      if (htab->table[idx].hval == hval
144	  && COMPARE (data, ENTRYP (htab->table[idx])) == 0)
145	return &htab->table[idx];
146
147      /* Second hash function as suggested in [Knuth].  */
148      hash = 1 + hval % (htab->nslots - 2);
149
150      do
151	{
152	  if (idx <= hash)
153	    idx = htab->nslots + idx - hash;
154	  else
155	    idx -= hash;
156
157	  if (htab->table[idx].hval == hval
158	      && COMPARE (data, ENTRYP(htab->table[idx])) == 0)
159	    return &htab->table[idx];
160	}
161      while (htab->table[idx].hval != 0);
162    }
163
164  return &htab->table[idx];
165}
166
167
168CLASS int
169__attribute__ ((unused))
170CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab,
171			      const char *str,
172			      size_t len __attribute__ ((unused)), TYPE *data)
173{
174  HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
175  struct CONCAT(PREFIX,fshashent) *slot;
176
177  slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
178 if (slot->hval != 0)
179    /* We don't want to overwrite the old value.  */
180    return -1;
181
182  slot->hval = hval;
183#ifdef STORE_POINTER
184  slot->entry = data;
185#else
186  slot->entry = *data;
187#endif
188
189  return 0;
190}
191
192
193#ifdef INSERT_HASH
194CLASS int
195__attribute__ ((unused))
196CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab,
197				   HASHTYPE hval, TYPE *data)
198{
199  struct CONCAT(PREFIX,fshashent) *slot;
200
201  slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
202  if (slot->hval != 0)
203    /* We don't want to overwrite the old value.  */
204    return -1;
205
206  slot->hval = hval;
207#ifdef STORE_POINTER
208  slot->entry = data;
209#else
210  slot->entry = *data;
211#endif
212
213  return 0;
214}
215#endif
216
217
218CLASS int
219__attribute__ ((unused))
220CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab,
221				 const char *str,
222				 size_t len __attribute__ ((unused)),
223				 TYPE *data)
224{
225  HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
226  struct CONCAT(PREFIX,fshashent) *slot;
227
228  slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
229  slot->hval = hval;
230#ifdef STORE_POINTER
231  slot->entry = data;
232#else
233  slot->entry = *data;
234#endif
235
236  return 0;
237}
238
239
240CLASS const TYPE *
241CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab,
242			    const char *str,
243			    size_t len __attribute__ ((unused)), TYPE *data)
244{
245  HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
246  struct CONCAT(PREFIX,fshashent) *slot;
247
248  slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab,
249				       hval, data);
250  if (slot->hval == 0)
251    /* Not found.  */
252    return NULL;
253
254  return ENTRYP(*slot);
255}
256
257
258/* Unset the macros we expect.  */
259#undef TYPE
260#undef HASHFCT
261#undef HASHTYPE
262#undef COMPARE
263#undef CLASS
264#undef PREFIX
265#undef INSERT_HASH
266#undef STORE_POINTER
267#undef NO_FINI_FCT
268