Re: [PATCH 1/3] Range tree implementation
From: John Stultz
Date: Tue Apr 24 2012 - 15:25:27 EST
On 04/24/2012 12:14 PM, Peter Zijlstra wrote:
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.
Sorry, I'm not sure I'm following you.
My point above was that a generic range-tree implementation that manages
the splitting and coalescing of ranges internally is difficult, due to
memory ownership issues. This makes it hard to have a generic list_head
style structure that you can use in your own structures. Thus in a way
similar to how the rb_tree leaves the insert and search implementation
to the suers, there is a range_tree_node structure, and the splitting
and coalescing logic is left to the range-tree user.
Does your suggestion address the ownership issue differently? Or is it
just a general optimization improvement?
thanks
-john
--
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/