Re: [RFC] Generalize prio_tree (1/3)

From: Rajesh Venkatasubramanian
Date: Mon Nov 15 2004 - 19:08:54 EST

On Mon, 15 Nov 2004, Werner Almesberger wrote:
> > If we impose that there can be only 2 types of prio_tree, then
> > we can simply add an if-else condition in the GET_INDEX macro.
> > IMHO, that will not lead to any noticeable performance drop.
> Yes, that sounds better. It would also allow for a later transition

Yeap. That will be my preference. Make a small patch to generalize
prio_tree using the split VMA_PRIO_TREE and GENERIC_PRIO_TREE. A small
patch has a better chance of getting merged too. Giving a strong
reason for the generalization and showing that the VMA_PRIO_TREE
and GENERIC_PRIO_TREE split does not affect performance noticeably,
we can hope to convince Andrew to merge. We can worry about
changing vm_area_struct's layout later.

> Now, if we want to prepare things already now for a later migration,
> it would be nice to call the generic one "struct prio_tree_node",
> since it would eventually become the only node type anyway.
> Perhaps something along these lines:
> struct prio_tree_node {
> struct vma_prio_tree_node prio_tree_node;
> unsigned long r_index, h_index;
> };
> Or would you consider this as premature optimization ?

Yeap. That looks sane. However, if you are planning to produce
a patch, please consider the following names:

struct prio_tree_node {
unsigned long start, end;
struct raw_prio_tree_node prio_tree_node;

I think the r_index and h_index names are only meaningful in
prio_tree.c. My guess is start and end will be more palatable
to users of prio_tree.

Thank you,
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