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
35 #include <system.h>
36
37 #ifdef __CONCAT
38 #define CONCAT(t1,t2) __CONCAT (t1,t2)
39 #else
40 #define STROF(t2) t2
41 #define CONCAT_EXPANDED(t1,t2) t1 ## t2
42 #define CONCAT(t1,t2) CONCAT_EXPANDED(t1,t2)
43 #endif
44
45 /* Before including this file the following macros must be defined:
46
47 TYPE data type of the hash table entries
48 HASHFCT name of the hashing function to use
49 HASHTYPE type used for the hashing value
50 COMPARE comparison function taking two pointers to TYPE objects
51 CLASS can be defined to `static' to avoid exporting the functions
52 PREFIX prefix to be used for function and data type names
53 STORE_POINTER if defined the table stores a pointer and not an element
54 of type TYPE
55 INSERT_HASH if defined alternate insert function which takes a hash
56 value is defined
57 NO_FINI_FCT if defined the fini function is not defined
58 */
59
60
61 /* Defined separately. */
62 extern size_t next_prime (size_t seed);
63
64
65 /* Set default values. */
66 #ifndef HASHTYPE
67 # define HASHTYPE size_t
68 #endif
69
70 #ifndef CLASS
71 # define CLASS
72 #endif
73
74 #ifndef PREFIX
75 # define PREFIX
76 #endif
77
78
79 /* The data structure. */
CONCAT(PREFIX,fshash)80 struct CONCAT(PREFIX,fshash)
81 {
82 size_t nslots;
83 struct CONCAT(PREFIX,fshashent)
84 {
85 HASHTYPE hval;
86 #ifdef STORE_POINTER
87 # define ENTRYP(el) (el).entry
88 TYPE *entry;
89 #else
90 # define ENTRYP(el) &(el).entry
91 TYPE entry;
92 #endif
93 } table[0];
94 };
95
96
97 /* Constructor for the hashing table. */
CONCAT(PREFIX,fshash)98 CLASS struct CONCAT(PREFIX,fshash) *
99 CONCAT(PREFIX,fshash_init) (size_t nelems)
100 {
101 struct CONCAT(PREFIX,fshash) *result;
102 /* We choose a size for the hashing table 150% over the number of
103 entries. This will guarantee short medium search lengths. */
104 const size_t max_size_t = ~((size_t) 0);
105
106 if (nelems >= (max_size_t / 3) * 2)
107 {
108 errno = EINVAL;
109 return NULL;
110 }
111
112 /* Adjust the size to be used for the hashing table. */
113 nelems = next_prime (MAX ((nelems * 3) / 2, 10));
114
115 /* Allocate the data structure for the result. */
116 result = (struct CONCAT(PREFIX,fshash) *)
117 xcalloc (sizeof (struct CONCAT(PREFIX,fshash))
118 + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1);
119 if (result == NULL)
120 return NULL;
121
122 result->nslots = nelems;
123
124 return result;
125 }
126
127
128 #ifndef NO_FINI_FCT
129 CLASS void
CONCAT(PREFIX,fshash_fini)130 CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
131 {
132 free (htab);
133 }
134 #endif
135
136
CONCAT(PREFIX,fshashent)137 static struct CONCAT(PREFIX,fshashent) *
138 CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab,
139 HASHTYPE hval, TYPE *data)
140 {
141 size_t idx = 1 + hval % htab->nslots;
142
143 if (htab->table[idx].hval != 0)
144 {
145 HASHTYPE hash;
146
147 /* See whether this is the same entry. */
148 if (htab->table[idx].hval == hval
149 && COMPARE (data, ENTRYP (htab->table[idx])) == 0)
150 return &htab->table[idx];
151
152 /* Second hash function as suggested in [Knuth]. */
153 hash = 1 + hval % (htab->nslots - 2);
154
155 do
156 {
157 if (idx <= hash)
158 idx = htab->nslots + idx - hash;
159 else
160 idx -= hash;
161
162 if (htab->table[idx].hval == hval
163 && COMPARE (data, ENTRYP(htab->table[idx])) == 0)
164 return &htab->table[idx];
165 }
166 while (htab->table[idx].hval != 0);
167 }
168
169 return &htab->table[idx];
170 }
171
172
173 CLASS int
174 __attribute__ ((unused))
CONCAT(PREFIX,fshash_insert)175 CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab,
176 const char *str,
177 size_t len __attribute__ ((unused)), TYPE *data)
178 {
179 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
180 struct CONCAT(PREFIX,fshashent) *slot;
181
182 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
183 if (slot->hval != 0)
184 /* We don't want to overwrite the old value. */
185 return -1;
186
187 slot->hval = hval;
188 #ifdef STORE_POINTER
189 slot->entry = data;
190 #else
191 slot->entry = *data;
192 #endif
193
194 return 0;
195 }
196
197
198 #ifdef INSERT_HASH
199 CLASS int
200 __attribute__ ((unused))
CONCAT(PREFIX,fshash_insert_hash)201 CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab,
202 HASHTYPE hval, TYPE *data)
203 {
204 struct CONCAT(PREFIX,fshashent) *slot;
205
206 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
207 if (slot->hval != 0)
208 /* We don't want to overwrite the old value. */
209 return -1;
210
211 slot->hval = hval;
212 #ifdef STORE_POINTER
213 slot->entry = data;
214 #else
215 slot->entry = *data;
216 #endif
217
218 return 0;
219 }
220 #endif
221
222
223 CLASS int
224 __attribute__ ((unused))
CONCAT(PREFIX,fshash_overwrite)225 CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab,
226 const char *str,
227 size_t len __attribute__ ((unused)),
228 TYPE *data)
229 {
230 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
231 struct CONCAT(PREFIX,fshashent) *slot;
232
233 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
234 slot->hval = hval;
235 #ifdef STORE_POINTER
236 slot->entry = data;
237 #else
238 slot->entry = *data;
239 #endif
240
241 return 0;
242 }
243
244
245 CLASS const TYPE *
CONCAT(PREFIX,fshash_find)246 CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab,
247 const char *str,
248 size_t len __attribute__ ((unused)), TYPE *data)
249 {
250 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
251 struct CONCAT(PREFIX,fshashent) *slot;
252
253 slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab,
254 hval, data);
255 if (slot->hval == 0)
256 /* Not found. */
257 return NULL;
258
259 return ENTRYP(*slot);
260 }
261
262
263 /* Unset the macros we expect. */
264 #undef TYPE
265 #undef HASHFCT
266 #undef HASHTYPE
267 #undef COMPARE
268 #undef CLASS
269 #undef PREFIX
270 #undef INSERT_HASH
271 #undef STORE_POINTER
272 #undef NO_FINI_FCT
273