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