Re: BIN_TREE vs SPLAY_TREE vs linked list

--MimeMultipartBoundary
Content-Type: TEXT/PLAIN; charset=US-ASCII

On Fri, 27 Mar 1998, Duane Wessels wrote:

> 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 agree with both of you. You can't do URL blacklisting without linked
lists. But linked lists aren't fast enough for large blacklists. The
solution is to use linked lists for the things which require them, and
trees for everything else. (Or something like trees - trees are actually
pretty inefficient for blacklisting because of all the overhead traversing
them.)

Unfortunately, this doesn't allow you to remove all but one type of
structure, as Duane wanted to do. In fact, if you want to be able to
handle very large, very powerful blacklisting, you will end up with more
types of ACLs, not less. (My mods are currently using about 10 different
algorithms, each tuned to a particular type of blacklist. Our standard
blacklist is in excess of 400,000 lines including everything from full
subnet blocks down to blocks on certain CGI arguments on certain servers.
I can't imagine being able to do this with only one type of ACL
structure.)

Kevin

------------------------------------------------------------------------------
 Kevin Fink <kevin@fink.com> N2H2, Creators of Bess
 http://www.fink.com/ 1301 Fifth Avenue, Suite 1501
 http://www.n2h2.com/ Seattle, WA 98101
------------------------------------------------------------------------------
 (206) 971-1400 VOICE (206) 971-1460 FAX (206) 680-7666 PAGER
------------------------------------------------------------------------------

--MimeMultipartBoundary--
Received on Tue Jul 29 2003 - 13:15:47 MDT