1/*	$OpenBSD: hash.c,v 1.2 2017/08/11 14:58:56 jasper 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
24#include "hash.h"
25
26struct _hash_record {
27	uint32_t	hv;
28	struct hash_entry	*p;
29};
30
31struct hash {
32	struct _hash_record 	*t;
33	unsigned int 		size;
34	unsigned int 		total;
35	unsigned int 		deleted;
36};
37
38#define DELETED		((struct hash_entry *)h)
39#define NONE		(h->size)
40
41/* Don't bother changing the hash table if the change is small enough.  */
42#define MINSIZE		(1UL << 4)
43#define MINDELETED	4
44
45static void hash_resize(struct hash *);
46static uint32_t hash_interval(const char *, const char **);
47static unsigned int hash_qlookup(struct hash *, const char *);
48
49
50/* hash_delete only frees the hash structure. Use hash_first/hash_next
51 * to free entries as well.  */
52void
53hash_delete(struct hash *h)
54{
55	free(h->t);
56	h->t = NULL;
57}
58
59static void
60hash_resize(struct hash *h)
61{
62	struct _hash_record *n;
63	size_t ns;
64	unsigned int	j;
65	unsigned int	i, incr;
66
67	if (4 * h->deleted < h->total) {
68		if (h->size >= (UINT_MAX >> 1U))
69			ns = UINT_MAX;
70		else
71			ns = h->size << 1U;
72	} else if (3 * h->deleted > 2 * h->total)
73		ns = h->size >> 1U;
74	else
75		ns = h->size;
76	if (ns < MINSIZE)
77		ns = MINSIZE;
78
79	n = calloc(ns, sizeof(struct _hash_record));
80	if (!n)
81		return;
82
83	for (j = 0; j < h->size; j++) {
84		if (h->t[j].p != NULL && h->t[j].p != DELETED) {
85			i = h->t[j].hv % ns;
86			incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
87			while (n[i].p != NULL) {
88				i += incr;
89				if (i >= ns)
90					i -= ns;
91			}
92			n[i].hv = h->t[j].hv;
93			n[i].p = h->t[j].p;
94		}
95	}
96	free(h->t);
97	h->t = n;
98	h->size = ns;
99	h->total -= h->deleted;
100	h->deleted = 0;
101}
102
103void *
104hash_remove(struct hash *h, unsigned int i)
105{
106	void		*result = (void *)h->t[i].p;
107
108	if (result == NULL || result == DELETED)
109		return NULL;
110
111	h->t[i].p = DELETED;
112	h->deleted++;
113	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
114		hash_resize(h);
115	return result;
116}
117
118void
119hash_insert(struct hash *h, unsigned int i, struct hash_entry *p,
120    const char *key)
121{
122	p->hkey = key;
123
124	if (h->t[i].p == DELETED) {
125		h->deleted--;
126		h->t[i].p = p;
127	} else {
128		h->t[i].p = p;
129		/* Arbitrary resize boundary.  Tweak if not efficient enough. */
130		if (++h->total * 4 > h->size * 3)
131			hash_resize(h);
132	}
133}
134
135void *
136hash_first(struct hash *h, unsigned int *pos)
137{
138	*pos = 0;
139	return hash_next(h, pos);
140}
141
142void *
143hash_next(struct hash *h, unsigned int *pos)
144{
145	for (; *pos < h->size; (*pos)++)
146		if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
147			return (void *)h->t[(*pos)++].p;
148	return NULL;
149}
150
151struct hash *
152hash_init(unsigned int size)
153{
154	struct hash *h;
155
156	h = calloc(1, sizeof(*h));
157	if (h == NULL)
158		return NULL;
159
160	h->size = 1UL << size;
161	if (h->size < MINSIZE)
162		h->size = MINSIZE;
163	/* Copy info so that caller may free it.  */
164	h->total = h->deleted = 0;
165	h->t = calloc(h->size, sizeof(struct _hash_record));
166	if (h->t == NULL) {
167		free(h);
168		return NULL;
169	}
170
171	return h;
172}
173
174static uint32_t
175hash_interval(const char *s, const char **e)
176{
177	uint32_t k;
178
179	if (!*e)
180		*e = s + strlen(s);
181	if (s == *e)
182		k = 0;
183	else
184		k = *s++;
185	while (s != *e)
186		k =  ((k << 2) | (k >> 30)) ^ *s++;
187	return k;
188}
189
190static unsigned int
191hash_qlookup(struct hash *h, const char *start)
192{
193	const char *end = NULL;
194	unsigned int i, incr;
195	unsigned int empty;
196	uint32_t hv;
197
198	hv = hash_interval(start, &end);
199
200	empty = NONE;
201	i = hv % h->size;
202	incr = ((hv % (h->size-2)) & ~1) + 1;
203	while (h->t[i].p != NULL) {
204		if (h->t[i].p == DELETED) {
205			if (empty == NONE)
206				empty = i;
207		} else if (h->t[i].hv == hv &&
208		    strncmp(h->t[i].p->hkey, start, end - start) == 0 &&
209		    (h->t[i].p->hkey)[end-start] == '\0') {
210			if (empty != NONE) {
211				h->t[empty].hv = hv;
212				h->t[empty].p = h->t[i].p;
213				h->t[i].p = DELETED;
214				return empty;
215			} else {
216				return i;
217			}
218		}
219		i += incr;
220		if (i >= h->size)
221			i -= h->size;
222	}
223
224	/* Found an empty position.  */
225	if (empty != NONE)
226		i = empty;
227	h->t[i].hv = hv;
228	return i;
229}
230
231struct hash_entry *
232hash_find(struct hash *h, const char *start, unsigned int *slot)
233{
234	unsigned int i;
235
236	i = hash_qlookup(h, start);
237	if (slot != NULL)
238		*slot = i;
239
240	if (h->t[i].p == DELETED)
241		return NULL;
242
243	return h->t[i].p;
244}
245