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