So users can better track their ruleset via git.
Without sorting, the elements can be listed in a different order
every time the set is created, generating unnecessary git changes.
Mergesort is used. Doesn't sort sets with 'flags interval' set on.
Signed-off-by: Elise Lennion <elise.lennion@xxxxxxxxx>
---
include/expression.h | 1 +
src/Makefile.am | 1 +
src/mergesort.c | 100 +++++++++++++++++++++++++++++++++++++++++++++++++++
src/netlink.c | 4 +++
4 files changed, 106 insertions(+)
create mode 100644 src/mergesort.c
diff --git a/include/expression.h b/include/expression.h
index 71e9c43..ec90265 100644
--- a/include/expression.h
+++ b/include/expression.h
@@ -396,6 +396,7 @@ extern struct expr *range_expr_alloc(const struct location *loc,
extern void compound_expr_add(struct expr *compound, struct expr *expr);
extern void compound_expr_remove(struct expr *compound, struct expr *expr);
+extern void list_expr_sort(struct list_head *head);
extern struct expr *concat_expr_alloc(const struct location *loc);
diff --git a/src/Makefile.am b/src/Makefile.am
index 2a69e19..65cb4b4 100644
--- a/src/Makefile.am
+++ b/src/Makefile.am
@@ -53,6 +53,7 @@ nft_SOURCES = main.c \
mnl.c \
iface.c \
services.c \
+ mergesort.c \
scanner.l \
parser_bison.y
diff --git a/src/mergesort.c b/src/mergesort.c
new file mode 100644
index 0000000..a835320
--- /dev/null
+++ b/src/mergesort.c
@@ -0,0 +1,100 @@
+/*
+ * Copyright (c) 2017 Elise Lennion <elise.lennion@xxxxxxxxx>
+ *
+ * This program is free software; you can redistribute it and/or modify
+ * it under the terms of the GNU General Public License version 2 as
+ * published by the Free Software Foundation.
+ */
+
+#include <stdint.h>
+#include <expression.h>
+#include <gmputil.h>
+#include <list.h>
+
+static int expr_msort_cmp(const struct expr *e1, const struct expr *e2);
+
+static int concat_expr_msort_cmp(const struct expr *e1, const struct expr *e2)
+{
+ struct list_head *l = (&e2->expressions)->next;
+ const struct expr *i1, *i2;
+ int ret;
+
+ list_for_each_entry(i1, &e1->expressions, list) {
+ i2 = list_entry(l, typeof(struct expr), list);
+
+ ret = expr_msort_cmp(i1, i2);
+ if (ret)
+ return ret;
+
+ l = l->next;
+ }
+
+ return false;
+}
+
+static int expr_msort_cmp(const struct expr *e1, const struct expr *e2)
+{
+ switch (e1->ops->type) {
+ case EXPR_SET_ELEM:
+ return expr_msort_cmp(e1->key, e2->key);
+ case EXPR_VALUE:
+ return mpz_cmp(e1->value, e2->value);
+ case EXPR_CONCAT:
+ return concat_expr_msort_cmp(e1, e2);
+ case EXPR_MAPPING:
+ return expr_msort_cmp(e1->left, e2->left);
+ default:
+ BUG("Unknown expression %s\n", e1->ops->name);
+ }
+}
+
+static void list_splice_sorted(struct list_head *list, struct list_head *head)
+{
+ struct list_head *h = head->next;
+ struct list_head *l = list->next;
+
+ while (l != list) {
+ if (h == head ||
+ expr_msort_cmp(list_entry(l, typeof(struct expr), list),
+ list_entry(h, typeof(struct expr), list)) < 0) {
+ l = l->next;
+ list_add_tail(l->prev, h);
+ continue;
+ }
+
+ h = h->next;
+ }
+}
+
+static void list_cut_middle(struct list_head *list, struct list_head *head)
+{
+ struct list_head *s = head->next;
+ struct list_head *e = head->prev;
+
+ while (e != s) {
+ e = e->prev;
+
+ if (e != s)
+ s = s->next;
+ }
+
+ __list_cut_position(list, head, s);
+}
+
+void list_expr_sort(struct list_head *head)
+{
+ struct list_head *list;
+ LIST_HEAD(temp);
+
+ list = &temp;
+
+ if (list_empty(head) || list_is_singular(head))
+ return;
+
+ list_cut_middle(list, head);
+
+ list_expr_sort(head);
+ list_expr_sort(list);
+
+ list_splice_sorted(list, head);
+}
diff --git a/src/netlink.c b/src/netlink.c
index 5f478ff..4135f25 100644
--- a/src/netlink.c
+++ b/src/netlink.c
@@ -1666,6 +1666,10 @@ int netlink_get_setelems(struct netlink_ctx *ctx, const struct handle *h,
ctx->set = set;
set->init = set_expr_alloc(loc);
nftnl_set_elem_foreach(nls, list_setelem_cb, ctx);
+
+ if (!(set->flags & NFT_SET_INTERVAL))
+ list_expr_sort(&ctx->set->init->expressions);
+
nftnl_set_free(nls);
ctx->set = NULL;
--
2.7.4
--
To unsubscribe from this list: send the line "unsubscribe netfilter-devel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at http://vger.kernel.org/majordomo-info.html
