Search backwards when inserting/deleting in/from the top half of the rules in a chain.

before:

insert 50k rules without any previous rules
real    0m1.314s
user    0m1.184s
sys     0m0.123s

insert 50k with one already existing rule
real    2m38.052s
user    2m37.296s
sys     0m0.353s

insert 50k rules in the middle of 20k already existing rules
real    2m43.831s
user    2m43.005s
sys     0m0.414s

delete rule #70000 10k times with 100k rules
real    1m37.990s
user    1m37.247s
sys     0m0.500s


after:

insert 50k without any previous rules
real    0m1.315s
user    0m1.184s
sys     0m0.125s

insert 50k with one already existing rule
real    0m1.313s
user    0m1.189s
sys     0m0.119s

insert 50k rules in the middle of 20k already existing rules
real    0m8.550s
user    0m8.327s
sys     0m0.197s

delete rule #70000 10k times with 100k rules
real    0m35.566s
user    0m35.062s
sys     0m0.416s

1 files changed, 24 insertions, 12 deletions

diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
index 2ddbc5d..0085a06 100644
--- a/libiptc/libiptc.c
+++ b/libiptc/libiptc.c
@@ -295,6 +295,21 @@ static struct rule_head *iptcc_get_rule_num(struct chain_head *c,
 	return NULL;
 }
 
+/* Get a specific rule within a chain backwards */
+static struct rule_head *iptcc_get_rule_num_reverse(struct chain_head *c,
+					    unsigned int rulenum)
+{
+	struct rule_head *r;
+	unsigned int num = 0;
+
+	list_for_each_entry_reverse(r, &c->rules, list) {
+		num++;
+		if (num == rulenum)
+			return r;
+	}
+	return NULL;
+}
+
 /* Returns chain head if found, otherwise NULL. */
 static struct chain_head *
 iptcc_find_chain_by_offset(TC_HANDLE_T handle, unsigned int offset)
@@ -1267,13 +1282,11 @@ TC_INSERT_ENTRY(const IPT_CHAINLABEL chain,
 	   prev points to. */
 	if (rulenum == c->num_rules) {
 		prev = &c->rules;
-	} else {
+	} else if (rulenum + 1 <= c->num_rules/2) {
 		r = iptcc_get_rule_num(c, rulenum + 1);
-		if (!r) {
-			/* Shouldn't happen */
-			errno = ENOENT;
-			return 0;
-		}
+		prev = &r->list;
+	} else {
+		r = iptcc_get_rule_num_reverse(c, c->num_rules - rulenum);
 		prev = &r->list;
 	}
 
@@ -1504,17 +1517,16 @@ TC_DELETE_NUM_ENTRY(const IPT_CHAINLABEL chain,
 		return 0;
 	}
 
-	if (c->num_rules == 0) {
+	if (rulenum >= c->num_rules) {
 		errno = E2BIG;
 		return 0;
 	}
 
 	/* Take advantage of the double linked list if possible. */
-	if (rulenum == c->num_rules - 1)
-		r = list_entry(c->rules.prev, struct rule_head, list);
-	else if (!(r = iptcc_get_rule_num(c, rulenum + 1))) {
-		errno = E2BIG;
-		return 0;
+	if (rulenum + 1 <= c->num_rules/2) {
+		r = iptcc_get_rule_num(c, rulenum + 1);
+	} else {
+		r = iptcc_get_rule_num_reverse(c, c->num_rules - rulenum);
 	}
 
 	/* If we are about to delete the rule that is the current