1/* $OpenBSD: ohash_lookup_memory.c,v 1.3 2006/01/16 15:52:25 espie Exp $ */
2/* ex:ts=8 sw=4:
3 */
4
5/* Copyright (c) 1999, 2004 Marc Espie <espie@openbsd.org>
6 *
7 * Permission to use, copy, modify, and distribute this software for any
8 * purpose with or without fee is hereby granted, provided that the above
9 * copyright notice and this permission notice appear in all copies.
10 *
11 * THE SOFTWARE IS PROVIDED "AS IS" AND THE AUTHOR DISCLAIMS ALL WARRANTIES
12 * WITH REGARD TO THIS SOFTWARE INCLUDING ALL IMPLIED WARRANTIES OF
13 * MERCHANTABILITY AND FITNESS. IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR
14 * ANY SPECIAL, DIRECT, INDIRECT, OR CONSEQUENTIAL DAMAGES OR ANY DAMAGES
15 * WHATSOEVER RESULTING FROM LOSS OF USE, DATA OR PROFITS, WHETHER IN AN
16 * ACTION OF CONTRACT, NEGLIGENCE OR OTHER TORTIOUS ACTION, ARISING OUT OF
17 * OR IN CONNECTION WITH THE USE OR PERFORMANCE OF THIS SOFTWARE.
18 */
19#include <sys/cdefs.h>
20__FBSDID("$FreeBSD$");
21
22#include "ohash_int.h"
23
24unsigned int
25ohash_lookup_memory(struct ohash *h, const char *k, size_t size, uint32_t hv)
26{
27	unsigned int	i, incr;
28	unsigned int	empty;
29
30#ifdef STATS_HASH
31	STAT_HASH_LOOKUP++;
32#endif
33	empty = NONE;
34	i = hv % h->size;
35	incr = ((hv % (h->size-2)) & ~1) + 1;
36	while (h->t[i].p != NULL) {
37#ifdef STATS_HASH
38		STAT_HASH_LENGTH++;
39#endif
40		if (h->t[i].p == DELETED) {
41			if (empty == NONE)
42				empty = i;
43		} else if (h->t[i].hv == hv &&
44		    memcmp(h->t[i].p+h->info.key_offset, k, size) == 0) {
45		    	if (empty != NONE) {
46				h->t[empty].hv = hv;
47				h->t[empty].p = h->t[i].p;
48				h->t[i].p = DELETED;
49				return empty;
50			} else {
51#ifdef STATS_HASH
52				STAT_HASH_POSITIVE++;
53#endif
54			}	return i;
55		}
56		i += incr;
57		if (i >= h->size)
58			i -= h->size;
59	}
60
61	/* Found an empty position.  */
62	if (empty != NONE)
63		i = empty;
64	h->t[i].hv = hv;
65	return i;
66}
67