SplayTrees/Updated patch for long srcdomain and dstdomain ACLs

In article <9702081735.ZM6708@fatboy.geog.unsw.edu.au> you write:

>> the Changelog of Squid 1.1.6 mentions Splay tree for fast IP access
>> checking.
>
>The structure used to hold the src type acl's has been changed from a linked
>list, that places the last requested acl into the second place of the list,
>into a splay tree.

Was there any reason why you didn't use splay trees for srcdomain and
dstdomain too?

I just updated my balanced binary tree patches for srcdomain and dstdomain
ACLs for Squid 1.1.5, see

        http://www.IAEhv.nl/users/devet/squid/

for the patch and explanation. It should be not to difficult to merge this
patch into Squid 1.1.6.

>A splay tree is a type of balanced tree, but it is self adjusting. The last
>requested acl is placed at the root of the tree. A neat Java demo and further
>explanation can be found at:
>
>http://langevin.usc.edu/~ierardi/classes/SplayTree/

I've been playing with the applets a little bit but a Splay Tree can
become unbalanced fairly easy, in worst case it can become a linked list
again.

>It has been #ifdef out as there appeares to be an, as yet, unsolved bug :(

What kind of bug? I've been working on similar things and putting Squid's
IP lists into binary trees is not trivial I think (see URL above).

I hope we can merge our efforts into one solution for fast ACLs in Squid.

Arjan
Received on Sun Feb 09 1997 - 13:05:46 MST