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

From: Rajesh Venkatasubramanian
Date: Mon Nov 15 2004 - 20:51:47 EST

On Mon, 15 Nov 2004, Werner Almesberger wrote:

> Rajesh Venkatasubramanian wrote:
> > 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;
> > };
> Okay. Any reason why you've put "start, end" before "prio_tree_node" ?
> The other way around would seem to make things a lot easier.

I don't have any reason. I am okay with either.

> > 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.
> Yes, they're a bit confusing :-) It would actually be nice if you
> could write a little paper describing this particular type of radix
> priority search tree, since it differs quite a bit from the original.
> Also, the original paper is comparably difficult to obtain if you
> don't have a university library at hand. Better documentation of how
> prio_tree works might also encourage new uses of it.

I have already started doing that. Please check
Documentation/prio_tree.txt in 2.6.10-rc2. The document can be
improved a lot, but for now it tries to explain the differences
from the original paper. Yes. I got a copy of the original paper
from my university library, there are no digital copies available.

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