Re: radix tree implementation for quota ?

[David Laight <david%l8s.co.uk@localhost>]

On Sun, Nov 28, 2010 at 09:47:02PM +0000, David Holland wrote:
> 
> (Also, why a radix tree? Radix trees are generally not very efficient.
> If you're going to, though, you might want to reuse the direct,
> indirect, double indirect, etc. method FFS uses for block mapping.)

One lookup scheme I've used which works well with a small number
of items, or random ones provided they dont share low bits, is to
use the low 'n' bits to index an array, each slot contains either
a pointer to an item, or to an array indexed by the next 'n' bits.
(+ the match value or similar).
Lookup just loops until the item is found, the wrong item is found,
or you hit a NULL pointer.

(Might be something like DH that thinking of).

        David

-- 
David Laight: david%l8s.co.uk@localhost