summaryrefslogtreecommitdiffstats
path: root/libiptc
diff options
context:
space:
mode:
authorgandalf <gandalf>2004-09-23 19:25:06 +0000
committergandalf <gandalf>2004-09-23 19:25:06 +0000
commit6b3b18690cfb393c121a2574c371e4cc9e7c5764 (patch)
treebcc4161e8c6019995903931a9fe1efa7439bb478 /libiptc
parented53a70872a626a35ab9e8d00a3628ded6d076ac (diff)
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.
Diffstat (limited to 'libiptc')
-rw-r--r--libiptc/libiptc.c31
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;
}