[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: david%l8s.co.uk@localhost
Main Index |
Thread Index |