lkml.org 
[lkml]   [2012]   [Mar]   [20]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 1/2] [RFC] Range tree implementation
On 03/20/2012 03:00 AM, Dmitry Adamushko wrote:
> Hi John,
>
> On 16 March 2012 23:51, 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.
> Have you considered using 'prio_tree' (include/linux/prio_tree.h)? If
> we aim at addressing a wide range of possible use-cases (different
> patterns of adding/removing volatile ranges), then, at first glance,
> prio_tree looks like a better approach.
I'll take a closer look at that!

> e.g. for the "consume and merge a number of smaller ranges" scenario
> above, prio_tree gives O(log n) [ O(log n + m) ] behavior iso O(m log
> n) in your case.
Yea, one of the items I was looking at yesterday was to improve the
range insert/remove usage, since I end up starting each lookup from the
root node over and over. I'm thinking of adding a iterate-next type
call so that we don't re-start the lookup each iteration of the loop
once we've found an item.

Thanks again for the great feedback!

-john



\
 
 \ /
  Last update: 2012-03-20 19:09    [W:0.061 / U:4.652 seconds]
©2003-2020 Jasper Spaans|hosted at Digital Ocean and TransIP|Read the blog|Advertise on this site