Re: [RFC] Generalized prio_tree, revisited

From: Rajesh Venkatasubramanian
Date: Thu Dec 16 2004 - 10:16:26 EST

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,

+static void get_index(const struct prio_tree_root *root,

Should be "inline" ?

To unsubscribe from this list: send the line "unsubscribe linux-kernel" in
the body of a message to majordomo@xxxxxxxxxxxxxxx
More majordomo info at
Please read the FAQ at