summaryrefslogtreecommitdiffstats
path: root/libiptc/libiptc.c
diff options
context:
space:
mode:
author/C=DE/ST=Berlin/L=Berlin/O=Netfilter Project/OU=Development/CN=gandalf/emailAddress=gandalf@netfilter.org </C=DE/ST=Berlin/L=Berlin/O=Netfilter Project/OU=Development/CN=gandalf/emailAddress=gandalf@netfilter.org>2004-10-24 22:27:31 +0000
committer/C=DE/ST=Berlin/L=Berlin/O=Netfilter Project/OU=Development/CN=gandalf/emailAddress=gandalf@netfilter.org </C=DE/ST=Berlin/L=Berlin/O=Netfilter Project/OU=Development/CN=gandalf/emailAddress=gandalf@netfilter.org>2004-10-24 22:27:31 +0000
commit7ee92163bebc52c15953cd94e5afee7f3fb7a1d6 (patch)
tree1eed598e5eb56894fa80795aac0ec59658d40bb1 /libiptc/libiptc.c
parent9d76e33d8bef8dd18da1e4be1d8e128d4da53eea (diff)
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
Diffstat (limited to 'libiptc/libiptc.c')
-rw-r--r--libiptc/libiptc.c36
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