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
25struct _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
37static 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 */
43void *
44ohash_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.  */
60void
61ohash_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
69static void
70ohash_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
117void *
118ohash_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
135void *
136ohash_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
144void *
145ohash_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
162unsigned int
163ohash_entries(struct ohash *h)
164{
165	return h->total - h->deleted;
166}
167
168void *
169ohash_first(struct ohash *h, unsigned int *pos)
170{
171	*pos = 0;
172	return ohash_next(h, pos);
173}
174
175void *
176ohash_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
184void
185ohash_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
205uint32_t
206ohash_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
221unsigned int
222ohash_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
269unsigned int
270ohash_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
313unsigned int
314ohash_qlookup(struct ohash *h, const char *s)
315{
316	const char *e = NULL;
317	return ohash_qlookupi(h, s, &e);
318}
319
320unsigned int
321ohash_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