Messages in this thread | | | Date | Tue, 24 Apr 2012 12:25:17 -0700 | From | John Stultz <> | Subject | Re: [PATCH 1/3] Range tree implementation |
| |
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
| |