Re: [PATCH 2/4] [RFC] Range tree implementation

[John Stultz]

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


--
To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at  http://vger.kernel.org/majordomo-info.html
Please read the FAQ at  http://www.tux.org/lkml/