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