Messages in this thread | | | Date | Fri, 21 Apr 2006 11:24:03 -0700 | From | Zach Brown <> | Subject | Re: [PATCH] Shrink rbtree |
| |
> the pointers are always going to be aligned. So let's just use the > lowest bit of the parent pointer instead. This shrinks the rb_node from > 4 machine-words to 3.
We've seen this patch before, haven't we? :) I still like it.
> Another pair of eyes on the 'remove dead code in rb_erase()' bit in > particular would be appreciated.
I'll trade you some eyes for a description beyond the four words obvious, remove, dead, and code.
> struct rb_node > { > - struct rb_node *rb_parent; > - int rb_color; > + unsigned long rb_parent_colour;
How about some kerneldoc comments?
> #define RB_RED 0 > #define RB_BLACK 1
> +#define rb_colour(r) ((r)->rb_parent_colour & 1)
This creates a pretty strong bond between the two.. maybe a RB_COLOUR_MASK and use that and the _RED/_BLACK defines instead of the raw constants?
> +#define rb_is_red(r) (!rb_colour(r)) > +#define rb_is_black(r) rb_colour(r) > +#define rb_set_red(r) do { (r)->rb_parent_colour &= ~1; } while (0) > +#define rb_set_black(r) do { (r)->rb_parent_colour |= 1; } while (0) > + > +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p) > +{
BUG_ON((unsigned long)p & 3);
> + rb->rb_parent_colour = (rb->rb_parent_colour & 3) | (unsigned long)p; > +} > +static inline void rb_set_colour(struct rb_node *rb, int colour) > +{ > + rb->rb_parent_colour = (rb->rb_parent_colour & ~1) | colour; > +} > + > #define RB_ROOT (struct rb_root) { NULL, } > #define rb_entry(ptr, type, member) container_of(ptr, type, member) > > @@ -131,8 +147,7 @@ extern void rb_replace_node(struct rb_no > static inline void rb_link_node(struct rb_node * node, struct rb_node * parent, > struct rb_node ** rb_link) > { > - node->rb_parent = parent; > - node->rb_color = RB_RED; > + node->rb_parent_colour = (unsigned long )parent;
use rb_set_parent(node, parent) and get the assertion.
- z - To unsubscribe from this list: send the line "unsubscribe linux-kernel" in the body of a message to majordomo@vger.kernel.org More majordomo info at http://vger.kernel.org/majordomo-info.html Please read the FAQ at http://www.tux.org/lkml/
| |