Branch data 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 : 1 : 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 : 1 : CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
131 : : {
132 : 1 : free (htab);
133 : 0 : }
134 : : #endif
135 : :
136 : :
137 : : static struct CONCAT(PREFIX,fshashent) *
138 : 858 : CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab,
139 : : HASHTYPE hval, TYPE *data)
140 : : {
141 : 858 : size_t idx = 1 + hval % htab->nslots;
142 : :
143 [ + + ]: 858 : if (htab->table[idx].hval != 0)
144 : : {
145 : 454 : HASHTYPE hash;
146 : :
147 : : /* See whether this is the same entry. */
148 [ + + ]: 454 : if (htab->table[idx].hval == hval
149 [ + + ]: 361 : && COMPARE (data, ENTRYP (htab->table[idx])) == 0)
150 : 359 : return &htab->table[idx];
151 : :
152 : : /* Second hash function as suggested in [Knuth]. */
153 : 95 : hash = 1 + hval % (htab->nslots - 2);
154 : :
155 : 135 : do
156 : : {
157 [ + + ]: 135 : if (idx <= hash)
158 : 73 : idx = htab->nslots + idx - hash;
159 : : else
160 : 62 : idx -= hash;
161 : :
162 [ + + ]: 135 : if (htab->table[idx].hval == hval
163 [ + - ]: 4 : && COMPARE (data, ENTRYP(htab->table[idx])) == 0)
164 : 4 : return &htab->table[idx];
165 : : }
166 [ + + ]: 131 : while (htab->table[idx].hval != 0);
167 : : }
168 : :
169 : 495 : 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 : 853 : CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab,
226 : : const char *str,
227 : : size_t len __attribute__ ((unused)),
228 : : TYPE *data)
229 : : {
230 : 853 : HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
231 : 853 : struct CONCAT(PREFIX,fshashent) *slot;
232 : :
233 : 853 : slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
234 : 853 : slot->hval = hval;
235 : : #ifdef STORE_POINTER
236 : : slot->entry = data;
237 : : #else
238 : 853 : slot->entry = *data;
239 : : #endif
240 : :
241 : 853 : 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 : 5 : 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
|
