tech-kern archive

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index][Old Index]

Re: radix tree implementation for quota ?

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 Laight:

Home | Main Index | Thread Index | Old Index