Miles Sabin wrote:
Daniel Hartmeier wrote,
On Fri, Dec 20, 2002 at 12:25:57PM -0500, Michael Shalayeff wrote:
if i'm not mistaken n is the address length there...
so, regardless of the number of addresses in the set it's still
a constant for each address family...
Oh, my bad, so it's O(1) like a hash table, I'll have to read about
patricia some more, I see. :)
I think Ryan thought about adding hashed address pools for source and
destination addresses in filter rules, looks like this is about the
same thing, then.
Just a suggestion ...
Take a peek at ternary trees for this kind of thing,
http://www.ddj.com/documents/s=921/ddj9804a/9804a.htm
http://citeseer.nj.nec.com/bentley97fast.html
Thanks for the suggestion,
I will take a look.
They have all the nice characteristics of Patricia trees, but are quite
a bit simpler to construct and maintain.
While it is true that maintaining Patricia tree is a pain, that's not an
issue here since the code for doing that is already used in the kernel
for the routing tables. I've not reinvented the wheel here :)
Cedric
One of the big advantages of both Patricia and Ternary trees over
hashing is that they support searches for a prefix match (ie. matching
a.b.c.d against a.b.c.0/24) very straightforwardly.
Cheers,
Miles
