I found that ffz() to find the index of the not-fully-populated child
node to search was efficient enough to provide a precisely K == 2*levels
constant within the O(1) for accesses in all non-failure cases.
Measuring by cachelines it would have been superior to provide a
cacheline-sized node at each level and perform ffz by hand.
On Tue, Dec 10, 2002 at 01:24:33AM -0800, Andrew Morton wrote:
> Such a search would be an extension to or variant of radix_tree_gang_lookup.
> Something like the (old, untested) code below.
> But it's a big job. First thing to do is to write a userspace
> test harness for the radix-tree code. That's something I need to
> do anyway, because radix_tree_gang_lookup fails for offests beyond
> the 8TB mark, and it's such a pita fixing that stuff in-kernel.
Userspace test harnesses are essential for this kind of work. They
were for several of mine.
Bill
-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@vger.kernel.org
More majordomo info at http://vger.kernel.org/majordomo-info.html
Please read the FAQ at http://www.tux.org/lkml/