Re: BIN_TREE vs SPLAY_TREE vs linked list

Arjan de Vet writes:

>You're testing the case here that you have to find whether an item is in a
>list/tree and with my LRU patch for the linked list method the results are
>quite similar.
>
>The reason I introduced BTREE (and at the same time somebody else SPLAY) was
>for large blocking lists where you have to find that an item is *not* in the
>list/tree; in case of LINKED LIST you have to traverse the whole list and
>the tree algorithms should work much better here. So the test above doesn't
>give a good comparison.
>
>A good test would be to make a blocking list (dstdomain type) for e.g.
>1000-5000 sites and do the test run again.
>
>>My first preference would be to keep the linked-list approach because
>>it is much simpler to implement and maintain, but I am also open to
>>keeping SPLAY instead.
>
>I'm afraid linked lists cannot handle big blocking lists.

Unless I am missing something, I don't see how you can do
URL blacklisting in Squid with anything but linked lists.

In Squid, all URL ACL matching is done with regular expressions,
not strcmp(). Don't the tree structures require fucntions which
return -1, 0, or +1? Regular expression matching returns 0 (match)
or 1 (no match).

>I assume you used a stand-alone version of acl.c with some modifications. If
>you publish the necessary information/patches I can do some test runs with
>other ACLs this weekend.

My code is at
    http://squid.nlanr.net/Squid/Devel/ACL-testing/

Duane W.
Received on Tue Jul 29 2003 - 13:15:47 MDT