1 /* Fixed size hash table with internal linking.
2 Copyright (C) 2000, 2001, 2002, 2004 Red Hat, Inc.
3 Written by Ulrich Drepper <drepper@redhat.com>, 2000.
4
5 This program is free software; you can redistribute it and/or modify
6 it under the terms of the GNU General Public License as published by
7 the Free Software Foundation, version 2.
8
9 This program is distributed in the hope that it will be useful,
10 but WITHOUT ANY WARRANTY; without even the implied warranty of
11 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
12 GNU General Public License for more details.
13
14 You should have received a copy of the GNU General Public License
15 along with this program; if not, write to the Free Software Foundation,
16 Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307, USA. */
17
18 #include <errno.h>
19 #include <stdlib.h>
20 #include <string.h>
21 #include <sys/cdefs.h>
22 #include <sys/param.h>
23
24 #include <system.h>
25
26 #define CONCAT(t1,t2) __CONCAT (t1,t2)
27
28 /* Before including this file the following macros must be defined:
29
30 TYPE data type of the hash table entries
31 HASHFCT name of the hashing function to use
32 HASHTYPE type used for the hashing value
33 COMPARE comparison function taking two pointers to TYPE objects
34 CLASS can be defined to `static' to avoid exporting the functions
35 PREFIX prefix to be used for function and data type names
36 STORE_POINTER if defined the table stores a pointer and not an element
37 of type TYPE
38 INSERT_HASH if defined alternate insert function which takes a hash
39 value is defined
40 NO_FINI_FCT if defined the fini function is not defined
41 */
42
43
44 /* Defined separately. */
45 extern size_t next_prime (size_t seed);
46
47
48 /* Set default values. */
49 #ifndef HASHTYPE
50 # define HASHTYPE size_t
51 #endif
52
53 #ifndef CLASS
54 # define CLASS
55 #endif
56
57 #ifndef PREFIX
58 # define PREFIX
59 #endif
60
61
62 /* The data structure. */
CONCAT(PREFIX,fshash)63 struct CONCAT(PREFIX,fshash)
64 {
65 size_t nslots;
66 struct CONCAT(PREFIX,fshashent)
67 {
68 HASHTYPE hval;
69 #ifdef STORE_POINTER
70 # define ENTRYP(el) (el).entry
71 TYPE *entry;
72 #else
73 # define ENTRYP(el) &(el).entry
74 TYPE entry;
75 #endif
76 } table[0];
77 };
78
79
80 /* Constructor for the hashing table. */
CONCAT(PREFIX,fshash)81 CLASS struct CONCAT(PREFIX,fshash) *
82 CONCAT(PREFIX,fshash_init) (size_t nelems)
83 {
84 struct CONCAT(PREFIX,fshash) *result;
85 /* We choose a size for the hashing table 150% over the number of
86 entries. This will guarantee short medium search lengths. */
87 const size_t max_size_t = ~((size_t) 0);
88
89 if (nelems >= (max_size_t / 3) * 2)
90 {
91 errno = EINVAL;
92 return NULL;
93 }
94
95 /* Adjust the size to be used for the hashing table. */
96 nelems = next_prime (MAX ((nelems * 3) / 2, 10));
97
98 /* Allocate the data structure for the result. */
99 result = (struct CONCAT(PREFIX,fshash) *)
100 xcalloc (sizeof (struct CONCAT(PREFIX,fshash))
101 + (nelems + 1) * sizeof (struct CONCAT(PREFIX,fshashent)), 1);
102 if (result == NULL)
103 return NULL;
104
105 result->nslots = nelems;
106
107 return result;
108 }
109
110
111 #ifndef NO_FINI_FCT
112 CLASS void
CONCAT(PREFIX,fshash_fini)113 CONCAT(PREFIX,fshash_fini) (struct CONCAT(PREFIX,fshash) *htab)
114 {
115 free (htab);
116 }
117 #endif
118
119
CONCAT(PREFIX,fshashent)120 static struct CONCAT(PREFIX,fshashent) *
121 CONCAT(PREFIX,fshash_lookup) (struct CONCAT(PREFIX,fshash) *htab,
122 HASHTYPE hval, TYPE *data)
123 {
124 size_t idx = 1 + hval % htab->nslots;
125
126 if (htab->table[idx].hval != 0)
127 {
128 HASHTYPE hash;
129
130 /* See whether this is the same entry. */
131 if (htab->table[idx].hval == hval
132 && COMPARE (data, ENTRYP (htab->table[idx])) == 0)
133 return &htab->table[idx];
134
135 /* Second hash function as suggested in [Knuth]. */
136 hash = 1 + hval % (htab->nslots - 2);
137
138 do
139 {
140 if (idx <= hash)
141 idx = htab->nslots + idx - hash;
142 else
143 idx -= hash;
144
145 if (htab->table[idx].hval == hval
146 && COMPARE (data, ENTRYP(htab->table[idx])) == 0)
147 return &htab->table[idx];
148 }
149 while (htab->table[idx].hval != 0);
150 }
151
152 return &htab->table[idx];
153 }
154
155
156 CLASS int
157 __attribute__ ((unused))
CONCAT(PREFIX,fshash_insert)158 CONCAT(PREFIX,fshash_insert) (struct CONCAT(PREFIX,fshash) *htab,
159 const char *str, size_t len, TYPE *data)
160 {
161 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
162 struct CONCAT(PREFIX,fshashent) *slot;
163
164 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
165 if (slot->hval != 0)
166 /* We don't want to overwrite the old value. */
167 return -1;
168
169 slot->hval = hval;
170 #ifdef STORE_POINTER
171 slot->entry = data;
172 #else
173 slot->entry = *data;
174 #endif
175
176 return 0;
177 }
178
179
180 #ifdef INSERT_HASH
181 CLASS int
182 __attribute__ ((unused))
CONCAT(PREFIX,fshash_insert_hash)183 CONCAT(PREFIX,fshash_insert_hash) (struct CONCAT(PREFIX,fshash) *htab,
184 HASHTYPE hval, TYPE *data)
185 {
186 struct CONCAT(PREFIX,fshashent) *slot;
187
188 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
189 if (slot->hval != 0)
190 /* We don't want to overwrite the old value. */
191 return -1;
192
193 slot->hval = hval;
194 #ifdef STORE_POINTER
195 slot->entry = data;
196 #else
197 slot->entry = *data;
198 #endif
199
200 return 0;
201 }
202 #endif
203
204
205 CLASS int
206 __attribute__ ((unused))
CONCAT(PREFIX,fshash_overwrite)207 CONCAT(PREFIX,fshash_overwrite) (struct CONCAT(PREFIX,fshash) *htab,
208 const char *str, size_t len, TYPE *data)
209 {
210 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
211 struct CONCAT(PREFIX,fshashent) *slot;
212
213 slot = CONCAT(PREFIX,fshash_lookup) (htab, hval, data);
214 slot->hval = hval;
215 #ifdef STORE_POINTER
216 slot->entry = data;
217 #else
218 slot->entry = *data;
219 #endif
220
221 return 0;
222 }
223
224
225 const CLASS TYPE *
CONCAT(PREFIX,fshash_find)226 CONCAT(PREFIX,fshash_find) (const struct CONCAT(PREFIX,fshash) *htab,
227 const char *str, size_t len, TYPE *data)
228 {
229 HASHTYPE hval = HASHFCT (str, len ?: strlen (str));
230 struct CONCAT(PREFIX,fshashent) *slot;
231
232 slot = CONCAT(PREFIX,fshash_lookup) ((struct CONCAT(PREFIX,fshash) *) htab,
233 hval, data);
234 if (slot->hval == 0)
235 /* Not found. */
236 return NULL;
237
238 return ENTRYP(*slot);
239 }
240
241
242 /* Unset the macros we expect. */
243 #undef TYPE
244 #undef HASHFCT
245 #undef HASHTYPE
246 #undef COMPARE
247 #undef CLASS
248 #undef PREFIX
249 #undef INSERT_HASH
250 #undef STORE_POINTER
251 #undef NO_FINI_FCT
252