Line data Source code
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. */
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. */
98 : CLASS struct CONCAT(PREFIX,fshash) *
99 1 : 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 1 : const size_t max_size_t = ~((size_t) 0);
105 :
106 1 : if (nelems >= (max_size_t / 3) * 2)
107 : {
108 0 : errno = EINVAL;
109 0 : return NULL;
110 : }
111 :
112 : /* Adjust the size to be used for the hashing table. */
113 1 : nelems = next_prime (MAX ((nelems * 3) / 2, 10));
114 :
115 : /* Allocate the data structure for the result. */
116 1 : result = (struct CONCAT(PREFIX,fshash) *)
117 1 : xcalloc (sizeof (struct CONCAT(PREFIX,fshash))
118 : + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1);
119 1 : if (result == NULL)
120 : return NULL;
121 :
122 1 : result->nslots = nelems;
123 :
124 1 : return result;
125 : }
126 :
127 :
128 : #ifndef NO_FINI_FCT
129 : CLASS void
130 : CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
131 : {
132 1 : free (htab);
133 : }
134 : #endif
135 :
136 :
137 : static struct CONCAT(PREFIX,fshashent) *
138 539 : CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab,
139 : HASHTYPE hval, TYPE *data)
140 : {
141 539 : size_t idx = 1 + hval % htab->nslots;
142 :
143 539 : if (htab->table[idx].hval != 0)
144 : {
145 : HASHTYPE hash;
146 :
147 : /* See whether this is the same entry. */
148 171 : if (htab->table[idx].hval == hval
149 16 : && COMPARE (data, ENTRYP (htab->table[idx])) == 0)
150 14 : return &htab->table[idx];
151 :
152 : /* Second hash function as suggested in [Knuth]. */
153 157 : hash = 1 + hval % (htab->nslots - 2);
154 :
155 : do
156 : {
157 290 : if (idx <= hash)
158 141 : idx = htab->nslots + idx - hash;
159 : else
160 149 : idx -= hash;
161 :
162 290 : if (htab->table[idx].hval == hval
163 4 : && COMPARE (data, ENTRYP(htab->table[idx])) == 0)
164 4 : return &htab->table[idx];
165 : }
166 286 : while (htab->table[idx].hval != 0);
167 : }
168 :
169 521 : return &htab->table[idx];
170 : }
171 :
172 :
173 : CLASS int
174 : __attribute__ ((unused))
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))
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))
225 534 : CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab,
226 : const char *str,
227 : size_t len __attribute__ ((unused)),
228 : TYPE *data)
229 : {
230 534 : HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
231 : struct CONCAT(PREFIX,fshashent) *slot;
232 :
233 534 : slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
234 534 : slot->hval = hval;
235 : #ifdef STORE_POINTER
236 : slot->entry = data;
237 : #else
238 534 : slot->entry = *data;
239 : #endif
240 :
241 534 : return 0;
242 : }
243 :
244 :
245 : CLASS const TYPE *
246 5 : CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab,
247 : const char *str,
248 : size_t len __attribute__ ((unused)), TYPE *data)
249 : {
250 5 : HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
251 : struct CONCAT(PREFIX,fshashent) *slot;
252 :
253 5 : slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab,
254 : hval, data);
255 5 : if (slot->hval == 0)
256 : /* Not found. */
257 : return NULL;
258 :
259 4 : 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
|
