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