Add ohash_* functions to libc.

Ok'd deraadt@, millert@

1 files changed, 84 insertions, 0 deletions

diff --git a/lib/libc/ohash/ohash_lookup_interval.c b/lib/libc/ohash/ohash_lookup_interval.c
new file mode 100644
index 00000000000..0eaf9643005
--- /dev/null
+++ b/lib/libc/ohash/ohash_lookup_interval.c
@@ -0,0 +1,84 @@
+/* $OpenBSD: ohash_lookup_interval.c,v 1.1 2001/03/02 13:27:07 espie Exp $ */
+/* ex:ts=8 sw=4: 
+ */
+
+/*
+ * Copyright (c) 1999 Marc Espie.
+ *
+ * Code written for the OpenBSD project.
+ *
+ * Redistribution and use in source and binary forms, with or without
+ * modification, are permitted provided that the following conditions
+ * are met:
+ * 1. Redistributions of source code must retain the above copyright
+ *    notice, this list of conditions and the following disclaimer.
+ * 2. Redistributions in binary form must reproduce the above copyright
+ *    notice, this list of conditions and the following disclaimer in the
+ *    documentation and/or other materials provided with the distribution.
+ *
+ * THIS SOFTWARE IS PROVIDED BY THE OPENBSD PROJECT AND CONTRIBUTORS
+ * ``AS IS'' AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
+ * LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
+ * A PARTICULAR PURPOSE ARE DISCLAIMED.  IN NO EVENT SHALL THE OPENBSD
+ * PROJECT OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
+ * SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
+ * LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
+ * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
+ * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
+ * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
+ * OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
+ */
+
+#include "ohash_int.h"
+	
+unsigned int
+ohash_lookup_interval(h, start, end, hv)
+	struct ohash 	*h;
+	const char 	*start;
+	const char 	*end;
+	u_int32_t	hv;
+{
+	unsigned int 	i, incr;
+	unsigned int	empty;
+	
+#ifdef STATS_HASH
+	STAT_HASH_LOOKUP++;
+#endif
+	empty = NONE;
+	i = hv % h->size;
+	incr = ((hv % (h->size-2)) & ~1) + 1;
+	while (h->t[i].p != NULL) {
+#ifdef STATS_HASH
+		STAT_HASH_LENGTH++;
+#endif
+		if (h->t[i].p == DELETED) {
+			if (empty == NONE)
+				empty = i;
+		} else if (h->t[i].hv == hv && 
+		    strncmp(h->t[i].p+h->info.key_offset, start, 
+		    	end - start) == 0 &&
+		    (h->t[i].p+h->info.key_offset)[end-start] == '\0') {
+		    	if (empty != NONE) {
+				h->t[empty].hv = hv;
+				h->t[empty].p = h->t[i].p;
+				h->t[i].p = DELETED;
+				return empty;
+			} else {
+#ifdef STATS_HASH
+				STAT_HASH_POSITIVE++;
+#endif
+				return i;
+			}
+		}
+		i += incr;
+		if (i >= h->size) 
+			i -= h->size;
+	}
+
+	/* Found an empty position.  */
+	if (empty != NONE) 
+		i = empty;
+	h->t[i].hv = hv;
+	return i;
+}
+