hash.c revision 1.1 
1/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
2 *
3 * Permission to use, copy, modify, and distribute this software for any
4 * purpose with or without fee is hereby granted, provided that the above
5 * copyright notice and this permission notice appear in all copies.
6 *
7 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
8 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
9 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
10 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
11 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
12 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
13 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
14 */
15
16#include <stddef.h>
17#include <stdint.h>
18#include <stdlib.h>
19#include <string.h>
20#include <limits.h>
21
22#include "hash.h"
23
24struct _hash_record {
25	uint32_t	hv;
26	struct hash_entry	*p;
27};
28
29struct hash {
30	struct _hash_record 	*t;
31	unsigned int 		size;
32	unsigned int 		total;
33	unsigned int 		deleted;
34};
35
36#define DELETED		((struct hash_entry *)h)
37#define NONE		(h->size)
38
39/* Don't bother changing the hash table if the change is small enough.  */
40#define MINSIZE		(1UL << 4)
41#define MINDELETED	4
42
43static void hash_resize(struct hash *);
44static uint32_t hash_interval(const char *, const char **);
45static unsigned int hash_qlookup(struct hash *, const char *);
46
47
48/* hash_delete only frees the hash structure. Use hash_first/hash_next
49 * to free entries as well.  */
50void
51hash_delete(struct hash *h)
52{
53	free(h->t);
54	h->t = NULL;
55}
56
57static void
58hash_resize(struct hash *h)
59{
60	struct _hash_record *n;
61	size_t ns;
62	unsigned int	j;
63	unsigned int	i, incr;
64
65	if (4 * h->deleted < h->total) {
66		if (h->size >= (UINT_MAX >> 1U))
67			ns = UINT_MAX;
68		else
69			ns = h->size << 1U;
70	} else if (3 * h->deleted > 2 * h->total)
71		ns = h->size >> 1U;
72	else
73		ns = h->size;
74	if (ns < MINSIZE)
75		ns = MINSIZE;
76
77	n = calloc(ns, sizeof(struct _hash_record));
78	if (!n)
79		return;
80
81	for (j = 0; j < h->size; j++) {
82		if (h->t[j].p != NULL && h->t[j].p != DELETED) {
83			i = h->t[j].hv % ns;
84			incr = ((h->t[j].hv % (ns - 2)) & ~1) + 1;
85			while (n[i].p != NULL) {
86				i += incr;
87				if (i >= ns)
88					i -= ns;
89			}
90			n[i].hv = h->t[j].hv;
91			n[i].p = h->t[j].p;
92		}
93	}
94	free(h->t);
95	h->t = n;
96	h->size = ns;
97	h->total -= h->deleted;
98	h->deleted = 0;
99}
100
101void *
102hash_remove(struct hash *h, unsigned int i)
103{
104	void		*result = (void *)h->t[i].p;
105
106	if (result == NULL || result == DELETED)
107		return NULL;
108
109	h->t[i].p = DELETED;
110	h->deleted++;
111	if (h->deleted >= MINDELETED && 4 * h->deleted > h->total)
112		hash_resize(h);
113	return result;
114}
115
116void
117hash_insert(struct hash *h, unsigned int i, struct hash_entry *p,
118    const char *key)
119{
120	p->hkey = key;
121
122	if (h->t[i].p == DELETED) {
123		h->deleted--;
124		h->t[i].p = p;
125	} else {
126		h->t[i].p = p;
127		/* Arbitrary resize boundary.  Tweak if not efficient enough. */
128		if (++h->total * 4 > h->size * 3)
129			hash_resize(h);
130	}
131}
132
133void *
134hash_first(struct hash *h, unsigned int *pos)
135{
136	*pos = 0;
137	return hash_next(h, pos);
138}
139
140void *
141hash_next(struct hash *h, unsigned int *pos)
142{
143	for (; *pos < h->size; (*pos)++)
144		if (h->t[*pos].p != DELETED && h->t[*pos].p != NULL)
145			return (void *)h->t[(*pos)++].p;
146	return NULL;
147}
148
149struct hash *
150hash_init(unsigned int size)
151{
152	struct hash *h;
153
154	h = calloc(1, sizeof(*h));
155	if (h == NULL)
156		return NULL;
157
158	h->size = 1UL << size;
159	if (h->size < MINSIZE)
160		h->size = MINSIZE;
161	/* Copy info so that caller may free it.  */
162	h->total = h->deleted = 0;
163	h->t = calloc(h->size, sizeof(struct _hash_record));
164	if (h->t == NULL) {
165		free(h);
166		return NULL;
167	}
168
169	return h;
170}
171
172static uint32_t
173hash_interval(const char *s, const char **e)
174{
175	uint32_t k;
176
177	if (!*e)
178		*e = s + strlen(s);
179	if (s == *e)
180		k = 0;
181	else
182		k = *s++;
183	while (s != *e)
184		k =  ((k << 2) | (k >> 30)) ^ *s++;
185	return k;
186}
187
188static unsigned int
189hash_qlookup(struct hash *h, const char *start)
190{
191	const char *end = NULL;
192	unsigned int i, incr;
193	unsigned int empty;
194	uint32_t hv;
195
196	hv = hash_interval(start, &end);
197
198	empty = NONE;
199	i = hv % h->size;
200	incr = ((hv % (h->size-2)) & ~1) + 1;
201	while (h->t[i].p != NULL) {
202		if (h->t[i].p == DELETED) {
203			if (empty == NONE)
204				empty = i;
205		} else if (h->t[i].hv == hv &&
206		    strncmp(h->t[i].p->hkey, start, end - start) == 0 &&
207		    (h->t[i].p->hkey)[end-start] == '\0') {
208			if (empty != NONE) {
209				h->t[empty].hv = hv;
210				h->t[empty].p = h->t[i].p;
211				h->t[i].p = DELETED;
212				return empty;
213			} else {
214				return i;
215			}
216		}
217		i += incr;
218		if (i >= h->size)
219			i -= h->size;
220	}
221
222	/* Found an empty position.  */
223	if (empty != NONE)
224		i = empty;
225	h->t[i].hv = hv;
226	return i;
227}
228
229struct hash_entry *
230hash_find(struct hash *h, const char *start, unsigned int *slot)
231{
232	unsigned int i;
233
234	i = hash_qlookup(h, start);
235	if (slot != NULL)
236		*slot = i;
237
238	if (h->t[i].p == DELETED)
239		return NULL;
240
241	return h->t[i].p;
242}
243