condition for 2.6.16

[Patrick McHardy]

Massimiliano Hofer wrote:
> On Friday 28 April 2006 9:12 am, Patrick McHardy wrote:
> 
> 
>>I'm not really buying that argument, this can all also be done in
>>userspace. But a lot of people seem to consider it useful, so I might
>>reconsider if someone cleans it up so it at least doesn't need to walk
>>the list of conditions for every packet it matches .. but no promises.
> 
> 
> I'll set to work on it. I'll need to change the userspace interface, though.
> The only O(1) way to do it is to store a pointer (or any other id) in the rule 
> itself. I didn't do it in the previous version because I though this was 
> really ugly. I can't find any other match doing a similar thing. Anyway I can 
> do it.

Unfortunately its ugly, but this is a well-known limitation of iptables
itself. Since its the only way to do certain things, I won't complain
if this part is ugly :)

> On the other hand I can make it a guaranteed O(log n) or average O(1) without 
> meddling the rule descriptor and with compatible userspace. What do you 
> prefer?

How would you achieve O(1) average?