Re: [squid-users] Squid Future (was Re: [squid-users] Squid-2, Squid-3, roadmap)

On Mon, 2008-03-24 at 11:25 +0100, Henrik Nordstrom wrote:
> On Sun, 2008-03-23 at 18:29 +0900, Adrian Chadd wrote:
>
> > The real solution is a tree for offset lookups, and a linear walk of order
> > O(1) for subsequent sequential accesses.
>
> Walking a tree is usually a cheap operation, unless the tree is wrongly
> designed. You just need to remember the current tree node to enable
> linear walk from there.
>
> But it's true splay trees is not the appropriate lookup structure for
> this. To much runtime churn with the tree rebalancing itself..

I believe this to be the case, however as the code only uses the tree
interface, it should be easy to substitute in a different tree ADT here.

-Rob

-- 
GPG key available at: <http://www.robertcollins.net/keys.txt>.