Re: [RFC] Generalized prio_tree, revisited

From: Con Kolivas
Date: Thu Dec 16 2004 - 04:04:53 EST

Werner Almesberger wrote:
did you have a chance to look at the prio_tree generalization ?

I've attached the patch I posted a month ago (plus the trivial
"const" change). It's for 2.6.9, but also applies to 2.6.10-rc2,
which I've been using for a good while now.

The patch splits the radix priority search trees into two types:
the "raw" one with implicit keys, as it's currently used, and a
new, generalized one with explicit keys, which should be used by
new code.

struct prio_tree_root {
struct prio_tree_node *prio_tree_node;
- unsigned int index_bits;
+ unsigned short index_bits;
+ unsigned short raw;
+ /*
+ * 0: nodes are of type struct prio_tree_node
+ * 1: nodes are of type raw_prio_tree_node
+ */

- INIT_PRIO_TREE_ROOT(&inode->i_data.i_mmap);
+ INIT_PRIO_TREE_ROOT(&inode->i_data.i_mmap, 1);

While not being able to comment on the actual patch I think having a 1 or 0 for different types is not clear. Naming them different struct names would seem to me much more readable.


Attachment: signature.asc
Description: OpenPGP digital signature