Re: [RFC][PATCH 1/3] radix priority search tree - objrmap complexityfix

[Rik van Riel]

On Sun, 21 Mar 2004, Rajesh Venkatasubramanian wrote:

> > what about the cost of a tree rebalance, is that O(log(N)) like with the
> > rbtrees?
> 
> Currently the tree is not balanced, so the tree can be totally skewed
> in some corner cases. However, the maximum height of the tree can be
> only 2 * BITS_PER_LONG.

Fair enough for a radix tree.  Andrea, remember that page
tables don't need to be balanced either, for obvious reasons ;)

> Moreover, I have added an optimization to increase the maximum height
> of the tree on demand. The tree height is controlled by keeping track
> of the maximum file offset mapped. If the number of bits required to
> represent the maximum file offset is B, then the height of the tree
> can be only 2 * B.

Nice touch.  That should really help keep the cost of the
prio_tree down in the common case.

Your stuff is so much nicer than the kb-trees I was thinking
about a year or two ago ... ;)


-- 
"Debugging is twice as hard as writing the code in the first place.
Therefore, if you write the code as cleverly as possible, you are,
by definition, not smart enough to debug it." - Brian W. Kernighan

-
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/