Messages in this thread | | | Date | Thu, 31 May 2012 14:04:23 -0700 | From | John Stultz <> | Subject | Re: [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
| |