lkml.org 
[lkml]   [2012]   [Apr]   [7]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
From
Date
SubjectRe: [PATCH 1/2] [RFC] Range tree implementation
On Sat, Apr 7, 2012 at 2:08 AM, John Stultz <john.stultz@linaro.org> wrote:
> After Andrew suggested something like his mumbletree idea
> to better store a list of ranges, I worked on a few different
> approaches, and this is what I've finally managed to get working.
>
> I suspect range-tree isn't a totally accurate name, but I
> couldn't quite make out the difference between range trees
> and interval trees, so I just picked one to call it. Do
> let me know if you have a better name.
>
> The idea of storing ranges in a tree is nice, but has a number
> of complications. When adding a range, its possible that a
> large range will consume and merge a number of smaller ranges.
> When removing a range, its possible you may end up splitting an
> existing range, causing one range to become two. 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.
>
> So, this is a much simplified and more list_head like
> implementation. You can add a node to a tree, or remove a node
> to a tree, but the generic implementation doesn't do the
> merging or splitting for you. But it does provide helpers to
> find overlapping and adjacent ranges.
>
> Andrew also really wanted this range-tree implementation to be
> resuable so we don't duplicate the file locking logic. I'm not
> totally convinced that the requirements between the volatile
> ranges and file locking are really equivelent, but this reduced
> impelementation may make it possible.
>
> Do let me know what you think or if you have other ideas for
> better ways to do the same.

Hi John,

I have implemented an interval lookup tree using the augmented
features of the in-kernel rbtree for the KVM tools project. We
currently use it for several things as a framework code such as MMIO
memory mapping.

From what I see in the patch, you haven't fully implemented the
interval structure (it needs to keep track of additional parameters
when building it, and the search is a bit different and is based on
those parameters).

I could send that code as a patch against the kernel tree if something
like that is actually required for the kernel at this point.

Thanks.


\
 
 \ /
  Last update: 2012-04-07 19:39    [W:1.047 / U:0.080 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site