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