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