Re: [RFC] Generalized prio_tree, revisited

[Rajesh Venkatasubramanian <vrajesh@umich.edu>]

Werner Almesberger wrote:
> and so on. So it seems to me that we're just at the level of
> abstraction that gives us the most narrow interface and that
> doesn't hide any information we need to implement the other
> cases. And it's just the "engine" that would be used in all
> cases anyway.

Yeah, makes sense. I think we can consider multi_prio_tree_node
later if many future users of prio_tree code need vma->shared.vm_set
like handling.

I am okay with the patch. I haven't tested it myself and I won't
have time to do so for next few days. Below are some small nitpicks.

>  struct prio_tree_node {
>  	struct prio_tree_node	*left;
>  	struct prio_tree_node	*right;
>  	struct prio_tree_node	*parent;
> +	unsigned long		start;
> +	unsigned long		end;
>  };

I wonder whether we should use [start, last] or [first, last] for
index names because "end" normally means last + 1, e.g., vm_end.
In prio_tree we store closed intervals of form [first, last] and
I think the name "last" makes it more explicit. Did I tell you
nitpicking ?

> +
> +struct prio_tree_node *prio_tree_replace(struct prio_tree_root *root, 
> +                struct prio_tree_node *old, struct prio_tree_node *node);

prio_tree_replace should be static in prio_tree.c.

> +struct prio_tree_node *prio_tree_first(struct prio_tree_iter *iter);

Should we go with prio_tree_iter_init and remove prio_tree_first
(similar to vma_prio_tree_next) ? I am not very particular about it,
though.

> +static void get_index(const struct prio_tree_root *root,

Should be "inline" ?

Thanks,
Rajesh