Re: [PATCH 1/3] Range tree implementation

[Peter Zijlstra]

On Tue, 2012-04-24 at 10:49 -0700, John Stultz wrote:
> This makes it
> very difficult to provide generic list_head like behavior, as
> the parent structures would need to be duplicated and removed,
> and that has lots of memory ownership issues. 

You can in fact modify the rb-tree to have O(1) iteration by using the
empty leaf pointers to keep pointers to next/prev nodes.

Its a bit of a bother since you'd need to wrap ->rb_left and ->rb_right
in functions.. but now that we have coccinelle that shouldn't actually
be too hard.


--
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/