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 Red Hat elfutils.
4 Written by Ulrich Drepper <drepper@redhat.com>, 2000.
5
6 Red Hat elfutils is free software; you can redistribute it and/or modify
7 it under the terms of the GNU General Public License as published by the
8 Free Software Foundation; version 2 of the License.
9
10 Red Hat elfutils is distributed in the hope that it will be useful, but
11 WITHOUT ANY WARRANTY; without even the implied warranty of
12 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
13 General Public License for more details.
14
15 You should have received a copy of the GNU General Public License along
16 with Red Hat elfutils; if not, write to the Free Software Foundation,
17 Inc., 51 Franklin Street, Fifth Floor, Boston MA 02110-1301 USA.
18
19 In addition, as a special exception, Red Hat, Inc. gives You the
20 additional right to link the code of Red Hat elfutils with code licensed
21 under any Open Source Initiative certified open source license
22 (http://www.opensource.org/licenses/index.php) which requires the
23 distribution of source code with any binary distribution and to
24 distribute linked combinations of the two. Non-GPL Code permitted under
25 this exception must only link to the code of Red Hat elfutils through
26 those well defined interfaces identified in the file named EXCEPTION
27 found in the source code files (the "Approved Interfaces"). The files
28 of Non-GPL Code may instantiate templates or use macros or inline
29 functions from the Approved Interfaces without causing the resulting
30 work to be covered by the GNU General Public License. Only Red Hat,
31 Inc. may make changes or additions to the list of Approved Interfaces.
32 Red Hat's grant of this exception is conditioned upon your not adding
33 any new exceptions. If you wish to add a new Approved Interface or
34 exception, please contact Red Hat. You must obey the GNU General Public
35 License in all respects for all of the Red Hat elfutils code and other
36 code used in conjunction with Red Hat elfutils except the Non-GPL Code
37 covered by this exception. If you modify this file, you may extend this
38 exception to your version of the file, but you are not obligated to do
39 so. If you do not wish to provide this exception without modification,
40 you must delete this exception statement from your version and license
41 this file solely under the GPL without exception.
42
43 Red Hat elfutils is an included package of the Open Invention Network.
44 An included package of the Open Invention Network is a package for which
45 Open Invention Network licensees cross-license their patents. No patent
46 license is granted, either expressly or impliedly, by designation as an
47 included package. Should you wish to participate in the Open Invention
48 Network licensing program, please visit www.openinventionnetwork.com
49 <http://www.openinventionnetwork.com>. */
50
51 #include <errno.h>
52 #include <stdlib.h>
53 #include <string.h>
54 #include <sys/cdefs.h>
55 #include <sys/param.h>
56
57 #include <system.h>
58
59 #define CONCAT(t1,t2) __CONCAT (t1,t2)
60
61 /* Before including this file the following macros must be defined:
62
63 TYPE data type of the hash table entries
64 HASHFCT name of the hashing function to use
65 HASHTYPE type used for the hashing value
66 COMPARE comparison function taking two pointers to TYPE objects
67 CLASS can be defined to `static' to avoid exporting the functions
68 PREFIX prefix to be used for function and data type names
69 STORE_POINTER if defined the table stores a pointer and not an element
70 of type TYPE
71 INSERT_HASH if defined alternate insert function which takes a hash
72 value is defined
73 NO_FINI_FCT if defined the fini function is not defined
74 */
75
76
77 /* Defined separately. */
78 extern size_t next_prime (size_t seed);
79
80
81 /* Set default values. */
82 #ifndef HASHTYPE
83 # define HASHTYPE size_t
84 #endif
85
86 #ifndef CLASS
87 # define CLASS
88 #endif
89
90 #ifndef PREFIX
91 # define PREFIX
92 #endif
93
94
95 /* The data structure. */
CONCAT(PREFIX,fshash)96 struct CONCAT(PREFIX,fshash)
97 {
98 size_t nslots;
99 struct CONCAT(PREFIX,fshashent)
100 {
101 HASHTYPE hval;
102 #ifdef STORE_POINTER
103 # define ENTRYP(el) (el).entry
104 TYPE *entry;
105 #else
106 # define ENTRYP(el) &(el).entry
107 TYPE entry;
108 #endif
109 } table[0];
110 };
111
112
113 /* Constructor for the hashing table. */
CONCAT(PREFIX,fshash)114 CLASS struct CONCAT(PREFIX,fshash) *
115 CONCAT(PREFIX,fshash_init) (size_t nelems)
116 {
117 struct CONCAT(PREFIX,fshash) *result;
118 /* We choose a size for the hashing table 150% over the number of
119 entries. This will guarantee short medium search lengths. */
120 const size_t max_size_t = ~((size_t) 0);
121
122 if (nelems >= (max_size_t / 3) * 2)
123 {
124 errno = EINVAL;
125 return NULL;
126 }
127
128 /* Adjust the size to be used for the hashing table. */
129 nelems = next_prime (MAX ((nelems * 3) / 2, 10));
130
131 /* Allocate the data structure for the result. */
132 result = (struct CONCAT(PREFIX,fshash) *)
133 xcalloc (sizeof (struct CONCAT(PREFIX,fshash))
134 + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1);
135 if (result == NULL)
136 return NULL;
137
138 result->nslots = nelems;
139
140 return result;
141 }
142
143
144 #ifndef NO_FINI_FCT
145 CLASS void
CONCAT(PREFIX,fshash_fini)146 CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
147 {
148 free (htab);
149 }
150 #endif
151
152
CONCAT(PREFIX,fshashent)153 static struct CONCAT(PREFIX,fshashent) *
154 CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab,
155 HASHTYPE hval, TYPE *data)
156 {
157 size_t idx = 1 + hval % htab->nslots;
158
159 if (htab->table[idx].hval != 0)
160 {
161 HASHTYPE hash;
162
163 /* See whether this is the same entry. */
164 if (htab->table[idx].hval == hval
165 && COMPARE (data, ENTRYP (htab->table[idx])) == 0)
166 return &htab->table[idx];
167
168 /* Second hash function as suggested in [Knuth]. */
169 hash = 1 + hval % (htab->nslots - 2);
170
171 do
172 {
173 if (idx <= hash)
174 idx = htab->nslots + idx - hash;
175 else
176 idx -= hash;
177
178 if (htab->table[idx].hval == hval
179 && COMPARE (data, ENTRYP(htab->table[idx])) == 0)
180 return &htab->table[idx];
181 }
182 while (htab->table[idx].hval != 0);
183 }
184
185 return &htab->table[idx];
186 }
187
188
189 CLASS int
190 __attribute__ ((unused))
CONCAT(PREFIX,fshash_insert)191 CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab,
192 const char *str,
193 size_t len __attribute__ ((unused)), TYPE *data)
194 {
195 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
196 struct CONCAT(PREFIX,fshashent) *slot;
197
198 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
199 if (slot->hval != 0)
200 /* We don't want to overwrite the old value. */
201 return -1;
202
203 slot->hval = hval;
204 #ifdef STORE_POINTER
205 slot->entry = data;
206 #else
207 slot->entry = *data;
208 #endif
209
210 return 0;
211 }
212
213
214 #ifdef INSERT_HASH
215 CLASS int
216 __attribute__ ((unused))
CONCAT(PREFIX,fshash_insert_hash)217 CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab,
218 HASHTYPE hval, TYPE *data)
219 {
220 struct CONCAT(PREFIX,fshashent) *slot;
221
222 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
223 if (slot->hval != 0)
224 /* We don't want to overwrite the old value. */
225 return -1;
226
227 slot->hval = hval;
228 #ifdef STORE_POINTER
229 slot->entry = data;
230 #else
231 slot->entry = *data;
232 #endif
233
234 return 0;
235 }
236 #endif
237
238
239 CLASS int
240 __attribute__ ((unused))
CONCAT(PREFIX,fshash_overwrite)241 CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab,
242 const char *str,
243 size_t len __attribute__ ((unused)),
244 TYPE *data)
245 {
246 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
247 struct CONCAT(PREFIX,fshashent) *slot;
248
249 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
250 slot->hval = hval;
251 #ifdef STORE_POINTER
252 slot->entry = data;
253 #else
254 slot->entry = *data;
255 #endif
256
257 return 0;
258 }
259
260
261 CLASS const TYPE *
CONCAT(PREFIX,fshash_find)262 CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab,
263 const char *str,
264 size_t len __attribute__ ((unused)), TYPE *data)
265 {
266 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
267 struct CONCAT(PREFIX,fshashent) *slot;
268
269 slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab,
270 hval, data);
271 if (slot->hval == 0)
272 /* Not found. */
273 return NULL;
274
275 return ENTRYP(*slot);
276 }
277
278
279 /* Unset the macros we expect. */
280 #undef TYPE
281 #undef HASHFCT
282 #undef HASHTYPE
283 #undef COMPARE
284 #undef CLASS
285 #undef PREFIX
286 #undef INSERT_HASH
287 #undef STORE_POINTER
288 #undef NO_FINI_FCT
289