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