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. */
57 extern 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. */
CONCAT(PREFIX,fshash)75 struct 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. */
CONCAT(PREFIX,fshash)93 CLASS struct CONCAT(PREFIX,fshash) *
94 CONCAT(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
124 CLASS void
CONCAT(PREFIX,fshash_fini)125 CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
126 {
127 free (htab);
128 }
129 #endif
130
131
CONCAT(PREFIX,fshashent)132 static struct CONCAT(PREFIX,fshashent) *
133 CONCAT(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
168 CLASS int
169 __attribute__ ((unused))
CONCAT(PREFIX,fshash_insert)170 CONCAT(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
194 CLASS int
195 __attribute__ ((unused))
CONCAT(PREFIX,fshash_insert_hash)196 CONCAT(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
218 CLASS int
219 __attribute__ ((unused))
CONCAT(PREFIX,fshash_overwrite)220 CONCAT(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
240 CLASS const TYPE *
CONCAT(PREFIX,fshash_find)241 CONCAT(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