9 /* $OpenBSD: ohash.c,v 1.1 2014/06/02 18:52:03 deraadt Exp $ */
11 /* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
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.
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.
26 #include <sys/types.h>
33 #include "compat_ohash.h"
35 struct _ohash_record {
40 #define DELETED ((const char *)h)
41 #define NONE (h->size)
43 /* Don't bother changing the hash table if the change is small enough. */
44 #define MINSIZE (1UL << 4)
47 static void ohash_resize(struct ohash *);
50 /* This handles the common case of variable length keys, where the
51 * key is stored at the end of the record.
54 ohash_create_entry(struct ohash_info *i, const char *start, const char **end)
59 *end = start + strlen(start);
60 p = (i->alloc)(i->key_offset + (*end - start) + 1, i->data);
62 memcpy(p+i->key_offset, start, *end-start);
63 p[i->key_offset + (*end - start)] = '\0';
68 /* hash_delete only frees the hash structure. Use hash_first/hash_next
69 * to free entries as well. */
71 ohash_delete(struct ohash *h)
73 (h->info.free)(h->t, h->info.data);
80 ohash_resize(struct ohash *h)
82 struct _ohash_record *n;
87 if (4 * h->deleted < h->total) {
88 if (h->size >= (UINT_MAX >> 1U))
92 } else if (3 * h->deleted > 2 * h->total)
100 STAT_HASH_SIZE += ns - h->size;
103 n = (h->info.calloc)(ns, sizeof(struct _ohash_record), h->info.data);
107 for (j = 0; j < h->size; j++) {
108 if (h->t[j].p != NULL && h->t[j].p != DELETED) {
110 incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
111 while (n[i].p != NULL) {
116 n[i].hv = h->t[j].hv;
120 (h->info.free)(h->t, h->info.data);
123 h->total -= h->deleted;
128 ohash_remove(struct ohash *h, unsigned int i)
130 void *result = (void *)h->t[i].p;
132 if (result == NULL || result == DELETED)
140 if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
146 ohash_find(struct ohash *h, unsigned int i)
148 if (h->t[i].p == DELETED)
151 return (void *)h->t[i].p;
155 ohash_insert(struct ohash *h, unsigned int i, void *p)
160 if (h->t[i].p == DELETED) {
165 /* Arbitrary resize boundary. Tweak if not efficient enough. */
166 if (++h->total * 4 > h->size * 3)
173 ohash_entries(struct ohash *h)
175 return h->total - h->deleted;
179 ohash_first(struct ohash *h, unsigned int *pos)
182 return ohash_next(h, pos);
186 ohash_next(struct ohash *h, unsigned int *pos)
188 for (; *pos < h->size; (*pos)++)
189 if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
190 return (void *)h->t[(*pos)++].p;
195 ohash_init(struct ohash *h, unsigned int size, struct ohash_info *info)
197 h->size = 1UL << size;
198 if (h->size < MINSIZE)
201 STAT_HASH_CREATION++;
202 STAT_HASH_SIZE += h->size;
204 /* Copy info so that caller may free it. */
205 h->info.key_offset = info->key_offset;
206 h->info.calloc = info->calloc;
207 h->info.free = info->free;
208 h->info.alloc = info->alloc;
209 h->info.data = info->data;
210 h->t = (h->info.calloc)(h->size, sizeof(struct _ohash_record),
212 h->total = h->deleted = 0;
216 ohash_interval(const char *s, const char **e)
227 k = ((k << 2) | (k >> 30)) ^ *s++;
232 ohash_lookup_interval(struct ohash *h, const char *start, const char *end,
235 unsigned int i, incr;
243 incr = ((hv % (h->size-2)) & ~1) + 1;
244 while (h->t[i].p != NULL) {
248 if (h->t[i].p == DELETED) {
251 } else if (h->t[i].hv == hv &&
252 strncmp(h->t[i].p+h->info.key_offset, start,
254 (h->t[i].p+h->info.key_offset)[end-start] == '\0') {
257 h->t[empty].p = h->t[i].p;
262 STAT_HASH_POSITIVE++;
272 /* Found an empty position. */
280 ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)
282 unsigned int i, incr;
290 incr = ((hv % (h->size-2)) & ~1) + 1;
291 while (h->t[i].p != NULL) {
295 if (h->t[i].p == DELETED) {
298 } else if (h->t[i].hv == hv &&
299 memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {
302 h->t[empty].p = h->t[i].p;
307 STAT_HASH_POSITIVE++;
316 /* Found an empty position. */
324 ohash_qlookup(struct ohash *h, const char *s)
326 const char *e = NULL;
327 return ohash_qlookupi(h, s, &e);
331 ohash_qlookupi(struct ohash *h, const char *s, const char **e)
335 hv = ohash_interval(s, e);
336 return ohash_lookup_interval(h, s, *e, hv);
339 #endif /*!HAVE_OHASH*/