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 file changed