lkml.org 
[lkml]   [2012]   [May]   [31]   [last100]   RSS Feed
Views: [wrap][no wrap]   [headers]  [forward] 
 
Messages in this thread
/
Date
From
SubjectRe: [PATCH 2/4] [RFC] Range tree implementation
On 05/31/2012 01:48 PM, Jan Kara wrote:
> On Fri 25-05-12 12:17:34, John Stultz wrote:
>> 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.
> Well, interval tree is a data structure for tracking a set of
> possibly overlapping intervals. Range tree is a data structure tracking
> points allowing for fast queries on a set of points contained in a given
> range (gets useful and interesting when dimension> 1). Your data structure
> is neither so it would be good to have a different name. OTOH there are so
> many data structures that it's hard to find a reasonable unused name ;)

Although I'm not sure your interval tree description doesn't match what
I'm trying to provide. Could you clarify why that doesn't match?

>> +/**
>> + * range_tree_next_in_range - Return the next range in a range_tree still
>> + * contained within a specified range.
> 'within' isn't really correct, right? It should rather be 'intersecting'.

That is more clear, thanks for the suggestion!

>
>> + * @root: range_tree root
>> + * @start: range start
>> + * @end: range end
>> + *
>> + */
>> +struct range_tree_node *range_tree_next_in_range(struct range_tree_node *node,
>> + u64 start, u64 end)
>> +{
>> + struct rb_node *next;
>> + struct range_tree_node *candidate;
>> + if (!node)
>> + return NULL;
>> + next = rb_next(&node->rb);
>> + if (!next)
>> + return NULL;
>> +
>> + candidate = container_of(next, struct range_tree_node, rb);
>> +
>> + if ((candidate->start> end) || (candidate->end< start))
>> + return NULL;
>> +
>> + return candidate;
>> +}
>> +
>> +/**
>> + * range_tree_add - Add a node to a range tree
>> + * @root: range tree to be added to
>> + * @node: range_tree_node to be added
>> + *
>> + * Adds a node to the range tree.
> I think you should document here that the added range must not intersect
> with any other range in the tree.

So for my usage in the volatile range code, I don't want intersecting or
overlapping ranges added, but I didn't feel it was necessary to add this
restriction to my rangetree code as well, since someone might want to
store overlapping ranges.

thanks for the review!
-john




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