Skip site navigation (1)Skip section navigation (2) 
Date:      Tue, 12 Jan 2010 09:06:36 +0000 (UTC)
From:      Luigi Rizzo <luigi@FreeBSD.org>
To:        src-committers@freebsd.org, svn-src-user@freebsd.org
Subject:   svn commit: r202145 - user/luigi/ipfw3-head/sys/netinet/ipfw
Message-ID:  <201001120906.o0C96ade036886@svn.freebsd.org>
next in thread | raw e-mail | index | archive | help 
Author: luigi
Date: Tue Jan 12 09:06:36 2010
New Revision: 202145
URL: http://svn.freebsd.org/changeset/base/202145

Log:
  add support for hash tables

Modified:
  user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c
  user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h

Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c	Tue Jan 12 07:55:02 2010	(r202144)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c	Tue Jan 12 09:06:36 2010	(r202145)
@@ -291,16 +291,170 @@ heap_free(struct dn_heap *h)
 	bzero(h, sizeof(*h) );
 }
 
+/*
+ * hash table
+*/
+
+struct dn_ht *
+dn_ht_init(struct dn_ht *ht, int buckets, int ofs,
+        int (*h)(void *, uintptr_t arg),
+        int (*match)(void *, void *, uintptr_t arg),
+	void *(*new)(void *, uintptr_t arg), uintptr_t arg)
+{
+	int l;
+
+	if (h == NULL)
+		return NULL;
+	if (buckets < 1 || buckets > 65536)
+		return NULL;
+	if (ht) {	/* see if we can reuse */
+		if (buckets <= ht->buckets) {
+			ht->buckets = buckets;
+		} else {
+			/* free pointers if not allocated inline */
+			if (ht->ht != (void *)(ht + 1))
+				free(ht->ht, M_DN_HEAP);
+			free(ht, M_DN_HEAP);
+			ht = NULL;
+		}
+	}
+	if (ht == NULL) {
+		l = sizeof(*ht) + buckets * sizeof(void **);
+		ht = malloc(l, M_DN_HEAP, M_NOWAIT);
+	}
+	if (ht) {
+		ht->ht = (void **)(ht + 1);
+		ht->buckets = buckets;
+		ht->ofs = ofs;
+		ht->hash = h;
+		ht->match = match;
+		ht->new = new;
+		ht->arg = arg;
+	}
+	return ht;
+}
+
+/* lookup and optionally create element */
+void *
+dn_ht_find(struct dn_ht *ht, void *obj, int create)
+{
+	int i;
+	void *p;
+
+	i = (ht->buckets == 1) ? 0 : ht->hash(obj, ht->arg) % ht->buckets;
+	// log(1, "find %p in bucket %d\n", obj, i);
+	for (p = ht->ht[i]; p; p = *(void **)((char *)p + ht->ofs)) {
+		if (ht->match(p, obj, ht->arg))
+			break;
+	}
+	if (p == NULL && create) {
+		p = ht->new(obj, ht->arg);
+		if (p) {
+			ht->entries++;
+			*(void **)((char *)p + ht->ofs) = ht->ht[i];
+			ht->ht[i] = p;
+		}
+	}
+	return p;
+}
+
+int
+dn_ht_scan(struct dn_ht *ht, int (*fn)(void *, uintptr_t), uintptr_t arg)
+{
+	int i, ret, found = 0;
+	void *p, **prev;
+
+	for (i = 0; i < ht->buckets; i++) {
+		prev = &ht->ht[i];
+		while ( (p = *prev) != NULL) {
+			ret = fn(p, arg);
+			if (ret & HEAP_SCAN_DEL) {
+				found++;
+				ht->entries--;
+				*prev = *(void **)((char *)p + ht->ofs);
+			}
+			if (ret & HEAP_SCAN_END)
+				return found;
+			prev = (void **)((char *)p + ht->ofs);
+		}
+	}
+	return found;
+}
+
+
 #ifndef _KERNEL
 /*
- * testing code for the heap
+ * testing code for the heap and hash table
  */
+#include <string.h>
+
+struct x {
+	struct x *ht_link;
+	char buf[0];
+};
+
+int hfn(void *_x, uintptr_t arg)
+{
+	char *p = _x;
+	return p[0];
+}
+
+void *newfn(void *_x, uintptr_t arg)
+{
+	char *s = _x;
+	struct x *p = malloc(sizeof(*p) + 1 + strlen(s),
+		M_DN_HEAP, 0);
+	if (p)
+		strcpy(p->buf, s);
+	return p;
+}
+
+int matchfn(void *_x, void *_obj, uintptr_t arg)
+{
+	struct x *x = _x;
+	return (strcmp(x->buf, _obj) == 0);
+}
+
+char *strings[] = {
+	"undici", "unico", "doppio", "devoto",
+	"uno", "due", "tre", "quattro", "cinque", "sei",
+	"uno", "due", "tre", "quattro", "cinque", "sei",
+	NULL,
+};
+
+int doprint(void *_x, uintptr_t arg)
+{
+	struct x *x = _x;
+	printf("found element <%s>\n", x->buf);
+	return arg;
+}
+
+static void
+test_hash()
+{
+	char **p;
+	struct dn_ht *h = dn_ht_init(NULL, 10, 0, hfn, matchfn, newfn,
+		0);
+
+	for (p = strings; *p; p++) {
+		dn_ht_find(h, *p, 1);
+	}
+	dn_ht_scan(h, doprint, 0);
+	for (p = strings; *p; p++) {
+//		dn_ht_scan(h, doprint, HEAP_SCAN_DEL);
+		dn_ht_find(h, *p, 1);
+	}
+}
+
 int
 main(int argc, char *argv[])
 {
 	struct dn_heap h;
 	int i, n, n2, n3;
 
+	test_hash();
+	return 0;
+
 	/* n = elements, n2 = cycles */
 	n = (argc > 1) ? atoi(argv[1]) : 0;
 	if (n <= 0 || n > 1000000)

Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h	Tue Jan 12 07:55:02 2010	(r202144)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h	Tue Jan 12 09:06:36 2010	(r202145)
@@ -83,4 +83,31 @@ enum {
  */
 int heap_scan(struct dn_heap *, int (*)(void *, uintptr_t), uintptr_t);
 
+/*--- generic hash table support ---*/
+struct dn_ht {
+        int buckets;            /* how many buckets */
+        int entries;            /* how many entries */
+        int ofs;	        /* offset of link field */
+        uintptr_t arg;          /* arg to hash function */
+        int (*hash)(void *, uintptr_t arg);
+        int (*match)(void *, void *, uintptr_t arg);
+        void *(*new)(void *, uintptr_t arg);    /* object create function */
+        void **ht;              /* bucket heads */
+};
+
+struct dn_ht *dn_ht_init(struct dn_ht *, int buckets, int ofs, 
+        int (*h)(void *, uintptr_t arg),
+        int (*match)(void *, void *, uintptr_t arg),
+	void *(*new)(void *, uintptr_t arg),
+	uintptr_t arg);
+
+/* lookup and optionally create element */
+void *dn_ht_find(struct dn_ht *, void *obj, int create);
+
+enum {
+        DN_HT_SCAN_DEL = 1,
+        DN_HT_SCAN_END = 2,
+}; 
+int dn_ht_scan(struct dn_ht *, int (*)(void *, uintptr_t), uintptr_t);
+
 #endif /* _IP_DN_HEAP_H */

Want to link to this message? Use this URL: <https://mail-archive.FreeBSD.org/cgi/mid.cgi?201001120906.o0C96ade036886>