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

[Jan Kara]

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 ;)

> +/**
> + * 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'.

> + * @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.

> + */
> +void range_tree_add(struct range_tree_root *root,
> +					struct range_tree_node *node)
> +{
> +	struct rb_node **p = &root->head.rb_node;
> +	struct rb_node *parent = NULL;
> +	struct range_tree_node *ptr;
> +
> +	WARN_ON_ONCE(!RB_EMPTY_NODE(&node->rb));
> +
> +	while (*p) {
> +		parent = *p;
> +		ptr = rb_entry(parent, struct range_tree_node, rb);
> +		if (node->start < ptr->start)
> +			p = &(*p)->rb_left;
> +		else
> +			p = &(*p)->rb_right;
> +	}
> +	rb_link_node(&node->rb, parent, p);
> +	rb_insert_color(&node->rb, &root->head);
> +
  ^^ Spurious empty line.

> +}
> +

								Honza
-- 
Jan Kara <jack@xxxxxxx>
SUSE Labs, CR
--
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/