Blob


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