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