SplayTrees/Updated patch for long srcdomain and dstdomain ACLs

From: Arjan de Vet <Arjan.deVet@dont-contact.us>
Date: Sun, 9 Feb 1997 21:33:04 +0100 (MET)

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


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:

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

>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.

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

This archive was generated by hypermail pre-2.1.9 : Tue Dec 09 2003 - 16:34:24 MST