svn commit: r202149 - user/luigi/ipfw3-head/sys/netinet/ipfw

[Luigi Rizzo]

Author: luigi
Date: Tue Jan 12 10:13:09 2010
New Revision: 202149
URL: http://svn.freebsd.org/changeset/base/202149

Log:
  add removal code, fix some bugs

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 10:06:32 2010	(r202148)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.c	Tue Jan 12 10:13:09 2010	(r202149)
@@ -292,9 +292,15 @@ heap_free(struct dn_heap *h)
 }
 
 /*
- * hash table
-*/
+ * hash table support.
+ */
 
+/*
+ * Initialize, allocating bucket pointers inline.
+ * Recycle previous record if possible.
+ * If the 'new' function is not supplied, we assume that the
+ * key passed to ht_find is the same object to be stored in.
+ */
 struct dn_ht *
 dn_ht_init(struct dn_ht *ht, int buckets, int ofs,
         int (*h)(void *, uintptr_t arg),
@@ -336,19 +342,19 @@ dn_ht_init(struct dn_ht *ht, int buckets
 
 /* lookup and optionally create element */
 void *
-dn_ht_find(struct dn_ht *ht, void *obj, int create)
+dn_ht_find(struct dn_ht *ht, void *key, int create)
 {
 	int i;
 	void *p;
 
-	i = (ht->buckets == 1) ? 0 : ht->hash(obj, ht->arg) % ht->buckets;
+	i = (ht->buckets == 1) ? 0 : ht->hash(key, 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))
+		if (ht->match(p, key, ht->arg))
 			break;
 	}
 	if (p == NULL && create) {
-		p = ht->new(obj, ht->arg);
+		p = ht->new ? ht->new(key, ht->arg) : key;
 		if (p) {
 			ht->entries++;
 			*(void **)((char *)p + ht->ofs) = ht->ht[i];
@@ -381,6 +387,29 @@ dn_ht_scan(struct dn_ht *ht, int (*fn)(v
 	return found;
 }
 
+/*
+ * remove obj from the table, using key to find the slot.
+ * Returns obj if found, NULL if not found
+ */
+void *
+dn_ht_remove(struct dn_ht *ht, void *obj, void *key)
+{
+	int i;
+	void **pp, *p;
+
+	i = (ht->buckets == 1) ? 0 : ht->hash(obj, ht->arg) % ht->buckets;
+	// log(1, "find %p in bucket %d\n", obj, i);
+	for (pp = &ht->ht[i]; (p = *pp); pp = (void **)((char *)p + ht->ofs)) {
+		if (p != obj)
+			continue;
+		/* link in the next element */
+		*pp = *(void **)((char *)p + ht->ofs);
+		*(void **)((char *)p + ht->ofs) = NULL;
+		ht->entries--;
+		return obj;
+	}
+	return NULL;	/* failed */
+}
 
 #ifndef _KERNEL
 /*
@@ -393,10 +422,23 @@ struct x {
 	char buf[0];
 };
 
-int hfn(void *_x, uintptr_t arg)
+int hfn1(void *_x, uintptr_t arg)
 {
-	char *p = _x;
-	return p[0];
+	return *(char *)_x;
+}
+int matchfn1(void *_x, void *_obj, uintptr_t arg)
+{
+	return (strcmp(((struct x *)_x)->buf, _obj) == 0);
+}
+
+int hfn2(void *_x, uintptr_t arg)
+{
+	return ((struct x *)_x)->buf[0];
+}
+int matchfn2(void *_x, void *_obj, uintptr_t arg)
+{
+	return (strcmp(((struct x *)_x)->buf,
+			((struct x *)_obj)->buf) == 0);
 }
 
 void *newfn(void *_x, uintptr_t arg)
@@ -409,12 +451,6 @@ void *newfn(void *_x, uintptr_t arg)
 	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",
@@ -433,17 +469,28 @@ static void
 test_hash()
 {
 	char **p;
-	struct dn_ht *h = dn_ht_init(NULL, 10, 0, hfn, matchfn, newfn,
-		0);
+	struct dn_ht *h;
+	void *x = NULL;
+
+	/* first, find and allocate */
+	h = dn_ht_init(NULL, 10, 0, hfn1, matchfn1, newfn, 0);
 
 	for (p = strings; *p; p++) {
 		dn_ht_find(h, *p, 1);
 	}
 	dn_ht_scan(h, doprint, 0);
+	printf("/* second -- find without allocate */\n");
+	h = dn_ht_init(NULL, 10, 0, hfn2, matchfn2, NULL, 0);
 	for (p = strings; *p; p++) {
-//		dn_ht_scan(h, doprint, HEAP_SCAN_DEL);
-		dn_ht_find(h, *p, 1);
+		void **y = newfn(*p, 0);
+		if (x == NULL)
+			x = y;
+		dn_ht_find(h, y, 1);
 	}
+	dn_ht_scan(h, doprint, 0);
+	printf("remove %p gives %p\n", x, dn_ht_remove(h, x, x));
+	printf("remove %p gives %p\n", x, dn_ht_remove(h, x, x));
+	dn_ht_scan(h, doprint, 0);
 }
 
 int

Modified: user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h
==============================================================================
--- user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h	Tue Jan 12 10:06:32 2010	(r202148)
+++ user/luigi/ipfw3-head/sys/netinet/ipfw/dn_heap.h	Tue Jan 12 10:13:09 2010	(r202149)
@@ -98,11 +98,12 @@ struct dn_ht {
 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),
+        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);
+void *dn_ht_find(struct dn_ht *, void *key, int create);
+void *dn_ht_remove(struct dn_ht *, void *obj, void *key);
 
 enum {
         DN_HT_SCAN_DEL = 1,