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