lkml.org 
[lkml]   [2012]   [Apr]   [24]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
    /
    SubjectRe: [PATCH 1/3] Range tree implementation
    From
    Date
    On Tue, 2012-04-24 at 12:25 -0700, John Stultz wrote:
    > 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?

    Oh, I thought you also wanted a list_head to aid in the traversal
    required to find adjacent ranges etc..

    Brain completely failed to grasp what you were trying to say, sorry for
    the noise.


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