Replace O(n) with O(1) when TC_INSERT_ENTRY() inserts an entry at the end.

Do the same with TC_DELETE_NUM_ENTRY() when deleting the last rule.

My rule management script does both of these things in certain situations.
Created a file with 50.000 rules which my script converted into
iptables-restore format but inserting each rule with an index instead of
appending like the iptables-save output does. That took a while without this
optimization.  Same thing when deleting the 45.000 last rules in that chain,
the script outputs deletes by number starting from the bottom.

Inserting or deleting (by number) in the middle of the chain is still O(n)
where n is the rulenumber where the insert/delete is taking place.

1 files changed, 23 insertions, 8 deletions

diff --git a/libiptc/libiptc.c b/libiptc/libiptc.c
index 71fe90b..2ddbc5d 100644
--- a/libiptc/libiptc.c
+++ b/libiptc/libiptc.c
@@ -1,4 +1,4 @@
-/* Library which manipulates firewall rules.  Version $Revision: 1.57 $ */
+/* Library which manipulates firewall rules.  Version $Revision: 1.56 $ */
 
 /* Architecture of firewall rules is as follows:
  *
@@ -1262,13 +1262,20 @@ TC_INSERT_ENTRY(const IPT_CHAINLABEL chain,
 		return 0;
 	}
 
-	/* Try to get the rule we want to insert after.
-	   In case of no rules, insert after chain head. */
-	r = iptcc_get_rule_num(c, rulenum + 1);
-	if (r)
-		prev = &r->list;
-	else
+	/* If we are inserting at the end just take advantage of the
+	   double linked list, insert will happen before the entry
+	   prev points to. */
+	if (rulenum == c->num_rules) {
 		prev = &c->rules;
+	} else {
+		r = iptcc_get_rule_num(c, rulenum + 1);
+		if (!r) {
+			/* Shouldn't happen */
+			errno = ENOENT;
+			return 0;
+		}
+		prev = &r->list;
+	}
 
 	if (!(r = iptcc_alloc_rule(c, e->next_offset))) {
 		errno = ENOMEM;
@@ -1497,7 +1504,15 @@ TC_DELETE_NUM_ENTRY(const IPT_CHAINLABEL chain,
 		return 0;
 	}
 
-	if (!(r = iptcc_get_rule_num(c, rulenum + 1))) {
+	if (c->num_rules == 0) {
+		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;
 	}