[PATCH] Avoiding overlapping entries in splay trees

In article <199905161719.TAA88471@adv.iae.nl> I wrote:

>In article <373B1CE7.67A27A20@hem.passagen.se> Henrik wrote:
>
>>nontrivial as how to do the checks depends on the ACL type and order of
>>entries, but it is certainly doable.
>
>Indeed. I've implemented a possible solution and am now testing it. I
>still need to do a lot of code cleanups and tests before I can publish
>it as a patch for 2.2.STABLE2.

A first version of the patch is now available from:

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

It would be nice if people would test it and/or review the code (maybe
there are smarter ways to achieve the same results). If you see
'WARNING: This may break Splay tree searching' during startup and/or
experience strange access denied problems this patch may be useful for
you.

I've done some testing with my own access lists (3900 entries) and the
results of Squid with this patch were exactly the same as the old linked
list code whereas Squid without this patch would deny entries in the
access list because of overlaps.

Here's the explanation of how it works which I mailed before:

>The solution has been implemented in a generic way. For each problematic
>data type you need to have a function which can determine whether for a
>given A and B, A is a 'subset' of B or B is a 'subset' of A. Based on
>this a splay tree can be made without overlapping entries.
>
>splay_insert gets two extra parameters (a subset function and a free
>function), splay_splay gets one extra parameter (a subset function
>only). By using NULL as subset function one gets the original behavior.
>
>The only remaining overlapping entries which can give problems are
>things like:
>
> 172.16.1.1-172.16.1.10 and 172.16.1.4-172.16.1.14
>
>It could be that during the building of the splay tree one can change
>these records into
>
> 172.16.1.1-172.16.1.10 and 172.16.1.11-172.16.1.14
>
>as soon as the overlap is detected but I'm not sure yet whether this has
>side effects later on. And it's quite ugly to do this of course.

Arjan
Received on Mon May 24 1999 - 12:54:17 MDT