1 #include "config.h"
2
3 #if HAVE_OHASH
4
5 int dummy;
6
7 #else
8
9 /* $OpenBSD: ohash.c,v 1.1 2014/06/02 18:52:03 deraadt Exp $ */
10
11 /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
12 *
13 * Permission to use, copy, modify, and distribute this software for any
14 * purpose with or without fee is hereby granted, provided that the above
15 * copyright notice and this permission notice appear in all copies.
16 *
17 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
18 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
19 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
20 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
21 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
22 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
23 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
24 */
25
26 #include <sys/types.h>
27
28 #include <stddef.h>
29 #include <stdint.h>
30 #include <stdlib.h>
31 #include <string.h>
32 #include <limits.h>
33 #include "main.h"
34 #include "compat_ohash.h"
35
36 struct _ohash_record {
37 uint32_t hv;
38 const char *p;
39 };
40
41 #define DELETED ((const char *)h)
42 #define NONE (h->size)
43
44 /* Don't bother changing the hash table if the change is small enough. */
45 #define MINSIZE (1UL << 4)
46 #define MINDELETED 4
47
48 static void ohash_resize(struct ohash *);
49
50
51 /* This handles the common case of variable length keys, where the
52 * key is stored at the end of the record.
53 */
54 void *
ohash_create_entry(struct ohash_info * i,const char * start,const char ** end)55 ohash_create_entry(struct ohash_info *i, const char *start, const char **end)
56 {
57 char *p;
58
59 if (!*end)
60 *end = start + strlen(start);
61 p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data);
62 if (p) {
63 memcpy(p+i->key_offset, start, *end-start);
64 p[i->key_offset + (*end - start)] = '\0';
65 }
66 return (void *)p;
67 }
68
69 /* hash_delete only frees the hash structure. Use hash_first/hash_next
70 * to free entries as well. */
71 void
ohash_delete(struct ohash * h)72 ohash_delete(struct ohash *h)
73 {
74 (h->info.free)(h->t, h->info.data);
75 #ifndef NDEBUG
76 h->t = NULL;
77 #endif
78 }
79
80 static void
ohash_resize(struct ohash * h)81 ohash_resize(struct ohash *h)
82 {
83 struct _ohash_record *n;
84 size_t ns;
85 unsigned int j;
86 unsigned int i, incr;
87
88 if (4 * h->deleted < h->total) {
89 if (h->size >= (UINT_MAX >> 1U))
90 ns = UINT_MAX;
91 else
92 ns = h->size << 1U;
93 } else if (3 * h->deleted > 2 * h->total)
94 ns = h->size >> 1U;
95 else
96 ns = h->size;
97 if (ns < MINSIZE)
98 ns = MINSIZE;
99 #ifdef STATS_HASH
100 STAT_HASH_EXPAND++;
101 STAT_HASH_SIZE += ns - h->size;
102 #endif
103
104 n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);
105 if (!n)
106 return;
107
108 for (j = 0; j < h->size; j++) {
109 if (h->t[j].p != NULL && h->t[j].p != DELETED) {
110 i = h->t[j].hv % ns;
111 incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
112 while (n[i].p != NULL) {
113 i += incr;
114 if (i >= ns)
115 i -= ns;
116 }
117 n[i].hv = h->t[j].hv;
118 n[i].p = h->t[j].p;
119 }
120 }
121 (h->info.free)(h->t, h->info.data);
122 h->t = n;
123 h->size = ns;
124 h->total -= h->deleted;
125 h->deleted = 0;
126 }
127
128 void *
ohash_remove(struct ohash * h,unsigned int i)129 ohash_remove(struct ohash *h, unsigned int i)
130 {
131 void *result = __UNCONST(h->t[i].p);
132
133 if (result == NULL || result == DELETED)
134 return NULL;
135
136 #ifdef STATS_HASH
137 STAT_HASH_ENTRIES--;
138 #endif
139 h->t[i].p = DELETED;
140 h->deleted++;
141 if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
142 ohash_resize(h);
143 return result;
144 }
145
146 void *
ohash_find(struct ohash * h,unsigned int i)147 ohash_find(struct ohash *h, unsigned int i)
148 {
149 if (h->t[i].p == DELETED)
150 return NULL;
151 else
152 return __UNCONST(h->t[i].p);
153 }
154
155 void *
ohash_insert(struct ohash * h,unsigned int i,void * p)156 ohash_insert(struct ohash *h, unsigned int i, void *p)
157 {
158 #ifdef STATS_HASH
159 STAT_HASH_ENTRIES++;
160 #endif
161 if (h->t[i].p == DELETED) {
162 h->deleted--;
163 h->t[i].p = p;
164 } else {
165 h->t[i].p = p;
166 /* Arbitrary resize boundary. Tweak if not efficient enough. */
167 if (++h->total * 4 > h->size * 3)
168 ohash_resize(h);
169 }
170 return p;
171 }
172
173 unsigned int
ohash_entries(struct ohash * h)174 ohash_entries(struct ohash *h)
175 {
176 return h->total - h->deleted;
177 }
178
179 void *
ohash_first(struct ohash * h,unsigned int * pos)180 ohash_first(struct ohash *h, unsigned int *pos)
181 {
182 *pos = 0;
183 return ohash_next(h, pos);
184 }
185
186 void *
ohash_next(struct ohash * h,unsigned int * pos)187 ohash_next(struct ohash *h, unsigned int *pos)
188 {
189 for (; *pos < h->size; (*pos)++)
190 if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
191 return __UNCONST(h->t[(*pos)++].p);
192 return NULL;
193 }
194
195 void
ohash_init(struct ohash * h,unsigned int size,struct ohash_info * info)196 ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info)
197 {
198 h->size = 1UL << size;
199 if (h->size < MINSIZE)
200 h->size = MINSIZE;
201 #ifdef STATS_HASH
202 STAT_HASH_CREATION++;
203 STAT_HASH_SIZE += h->size;
204 #endif
205 /* Copy info so that caller may free it. */
206 h->info.key_offset = info->key_offset;
207 h->info.calloc = info->calloc;
208 h->info.free = info->free;
209 h->info.alloc = info->alloc;
210 h->info.data = info->data;
211 h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),
212 h->info.data);
213 h->total = h->deleted = 0;
214 }
215
216 uint32_t
ohash_interval(const char * s,const char ** e)217 ohash_interval(const char *s, const char **e)
218 {
219 uint32_t k;
220
221 if (!*e)
222 *e = s + strlen(s);
223 if (s == *e)
224 k = 0;
225 else
226 k = *s++;
227 while (s != *e)
228 k = ((k << 2) | (k >> 30)) ^ *s++;
229 return k;
230 }
231
232 unsigned int
ohash_lookup_interval(struct ohash * h,const char * start,const char * end,uint32_t hv)233 ohash_lookup_interval(struct ohash *h, const char *start, const char *end,
234 uint32_t hv)
235 {
236 unsigned int i, incr;
237 unsigned int empty;
238
239 #ifdef STATS_HASH
240 STAT_HASH_LOOKUP++;
241 #endif
242 empty = NONE;
243 i = hv % h->size;
244 incr = ((hv % (h->size-2)) & ~1) + 1;
245 while (h->t[i].p != NULL) {
246 #ifdef STATS_HASH
247 STAT_HASH_LENGTH++;
248 #endif
249 if (h->t[i].p == DELETED) {
250 if (empty == NONE)
251 empty = i;
252 } else if (h->t[i].hv == hv &&
253 strncmp(h->t[i].p+h->info.key_offset, start,
254 end - start) == 0 &&
255 (h->t[i].p+h->info.key_offset)[end-start] == '\0') {
256 if (empty != NONE) {
257 h->t[empty].hv = hv;
258 h->t[empty].p = h->t[i].p;
259 h->t[i].p = DELETED;
260 return empty;
261 } else {
262 #ifdef STATS_HASH
263 STAT_HASH_POSITIVE++;
264 #endif
265 return i;
266 }
267 }
268 i += incr;
269 if (i >= h->size)
270 i -= h->size;
271 }
272
273 /* Found an empty position. */
274 if (empty != NONE)
275 i = empty;
276 h->t[i].hv = hv;
277 return i;
278 }
279
280 unsigned int
ohash_lookup_memory(struct ohash * h,const char * k,size_t size,uint32_t hv)281 ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)
282 {
283 unsigned int i, incr;
284 unsigned int empty;
285
286 #ifdef STATS_HASH
287 STAT_HASH_LOOKUP++;
288 #endif
289 empty = NONE;
290 i = hv % h->size;
291 incr = ((hv % (h->size-2)) & ~1) + 1;
292 while (h->t[i].p != NULL) {
293 #ifdef STATS_HASH
294 STAT_HASH_LENGTH++;
295 #endif
296 if (h->t[i].p == DELETED) {
297 if (empty == NONE)
298 empty = i;
299 } else if (h->t[i].hv == hv &&
300 memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {
301 if (empty != NONE) {
302 h->t[empty].hv = hv;
303 h->t[empty].p = h->t[i].p;
304 h->t[i].p = DELETED;
305 return empty;
306 } else {
307 #ifdef STATS_HASH
308 STAT_HASH_POSITIVE++;
309 #endif
310 } return i;
311 }
312 i += incr;
313 if (i >= h->size)
314 i -= h->size;
315 }
316
317 /* Found an empty position. */
318 if (empty != NONE)
319 i = empty;
320 h->t[i].hv = hv;
321 return i;
322 }
323
324 unsigned int
ohash_qlookup(struct ohash * h,const char * s)325 ohash_qlookup(struct ohash *h, const char *s)
326 {
327 const char *e = NULL;
328 return ohash_qlookupi(h, s, &e);
329 }
330
331 unsigned int
ohash_qlookupi(struct ohash * h,const char * s,const char ** e)332 ohash_qlookupi(struct ohash *h, const char *s, const char **e)
333 {
334 uint32_t hv;
335
336 hv = ohash_interval(s, e);
337 return ohash_lookup_interval(h, s, *e, hv);
338 }
339
340 #endif /*!HAVE_OHASH*/
341