From 2f61f093c3149465f2a68764b25c817adbe87fcd Mon Sep 17 00:00:00 2001
From: Patrick McHardy <kaber@trash.net>
Date: Wed, 22 Jan 2014 20:53:12 +0000
Subject: set: add abstract set descriptions

Signed-off-by: Patrick McHardy <kaber@trash.net>
---
 src/Makefile.in |   1 +
 src/rule.c      |   5 ++-
 src/set_desc.c  | 108 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 113 insertions(+), 1 deletion(-)
 create mode 100644 src/set_desc.c

diff --git a/src/Makefile.in b/src/Makefile.in
index 8ac2b460..642f73ef 100644
--- a/src/Makefile.in
+++ b/src/Makefile.in
@@ -18,6 +18,7 @@ nft-obj			+= netlink.o
 nft-obj			+= netlink_linearize.o
 nft-obj			+= netlink_delinearize.o
 nft-obj			+= segtree.o
+nft-obj			+= set_desc.o
 nft-obj			+= rbtree.o
 nft-obj			+= gmputil.o
 nft-obj			+= utils.o
diff --git a/src/rule.c b/src/rule.c
index 18d72d9d..b43ce107 100644
--- a/src/rule.c
+++ b/src/rule.c
@@ -482,14 +482,17 @@ static int do_add_setelems(struct netlink_ctx *ctx, const struct handle *h,
 	return 0;
 }
 
+extern void set_desc_create(struct set *set);
 static int do_add_set(struct netlink_ctx *ctx, const struct handle *h,
 		      struct set *set)
 {
 	if (netlink_add_set(ctx, h, set) < 0)
-		return -1;
+		; //return -1;
 	if (set->init != NULL) {
 		if (set->flags & SET_F_INTERVAL)
 			set_to_intervals(set);
+		set_desc_create(set);
+
 		if (do_add_setelems(ctx, &set->handle, set->init) < 0)
 			return -1;
 	}
diff --git a/src/set_desc.c b/src/set_desc.c
new file mode 100644
index 00000000..76ae5e27
--- /dev/null
+++ b/src/set_desc.c
@@ -0,0 +1,108 @@
+#include <string.h>
+
+#include <expression.h>
+#include <rule.h>
+#include <gmputil.h>
+#include <utils.h>
+#include <rbtree.h>
+
+extern void set_desc_create(struct set *set);
+
+struct cluster {
+	struct rb_node		rb_node;
+	struct list_head	list;
+	mpz_t			val;
+};
+
+static struct cluster *cl_alloc(const mpz_t val)
+{
+	struct cluster *cl;
+
+	cl = xzalloc(sizeof(*cl));
+	mpz_init_set(cl->val, val);
+	return cl;
+}
+
+static struct cluster *cl_lookup(struct rb_root *root, const mpz_t val)
+{
+	struct rb_node *n = root->rb_node;
+	struct cluster *cl;
+	int d;
+
+	while (n != NULL) {
+		cl = rb_entry(n, struct cluster, rb_node);
+
+		d = mpz_cmp(val, cl->val);
+		if (d < 0)
+			n = n->rb_left;
+		else if (d > 0)
+			n = n->rb_right;
+		else
+			return cl;
+	}
+	return NULL;
+}
+
+static void cl_insert(struct rb_root *root, struct cluster *new)
+{
+	struct rb_node **p = &root->rb_node;
+	struct rb_node *parent = NULL;
+	struct cluster *cl;
+	int d;
+
+	while (*p != NULL) {
+		parent = *p;
+		cl = rb_entry(parent, struct cluster, rb_node);
+
+		d = mpz_cmp(new->val, cl->val);
+		if (d < 0)
+			p = &(*p)->rb_left;
+		else if (d > 0)
+			p = &(*p)->rb_right;
+		else
+			break;
+	}
+
+	rb_link_node(&new->rb_node, parent, p);
+	rb_insert_color(&new->rb_node, root);
+}
+
+void set_desc_create(struct set *set)
+{
+	struct cluster *cl, *next;
+	struct expr *i;
+	mpz_t mask, tmp;
+	unsigned int n;
+
+	printf("desc: ");
+	expr_print(set->init); printf("\n");
+
+	mpz_init(tmp);
+	for (n = 1; n < set->init->dtype->size; n++) {
+		struct rb_root root = RB_ROOT;
+		LIST_HEAD(list);
+		unsigned int cnt = 0;
+
+		mpz_init(mask);
+		mpz_prefixmask(mask, set->init->dtype->size, n);
+
+		gmp_printf("mask %u 0x%08Zx: %u\n", n, mask);
+		list_for_each_entry(i, &set->init->expressions, list) {
+			mpz_and(tmp, i->value, mask);
+			cl = cl_lookup(&root, tmp);
+			if (cl == NULL) {
+				gmp_printf("  new 0x%08Zx\n", tmp);
+				cl = cl_alloc(tmp);
+				cl_insert(&root, cl);
+				list_add_tail(&cl->list, &list);
+				cnt++;
+			}
+		}
+
+		list_for_each_entry_safe(cl, next, &list, list)
+			xfree(cl);
+		mpz_clear(mask);
+		printf("  cnt: %u\n", cnt);
+	}
+	printf("\n");
+}
-- 
cgit v1.2.3