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 They have all the nice characteristics of Patricia trees, but are quite a bit simpler to construct and maintain. 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
