lkml.org 
[lkml]   [2012]   [Apr]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [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



\
 
 \ /
  Last update: 2012-04-24 21:31    [W:0.358 / U:0.012 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site