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