Re: Splay Tree - IP access checkiing

G'day Andreas!

Andreas Jung wrote:
>
> the Changelog of Squid 1.1.6 mentions Splay tree for fast IP access
checking.
> What does it mean exactly ?

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.

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/

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

Any feedback would be greatly appreciated.

Later
Ed

-- 
Ed Knowles aka Jasper				   Phone : +61 2 9385 4962
E-mail: ed@fatboy.geog.unsw.edu.au	           Fax   : +61 2 9313 7878
            What I lack in morals I make up for in principles.