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