Re: [PATCH] Shrink rbtree

[David Woodhouse <dwmw2@infradead.org>]

On Fri, 2006-04-21 at 11:24 -0700, Zach Brown wrote:
> > 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.

Maybe. I thought I'd actually done it once before, but I couldn't
actually find it when I went looking. It should save about 40KiB of RAM
on my Nokia 770, because I should get 145 jffs2_node_frag objects in
each slab page instead of only 127 -- so yes, I like it too :)

> > 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.

Plenty more words in the git commit. They don't make much sense without
the patch right below them, and you can see them in juxtaposition at 
http://git.infradead.org/?p=users/dwmw2/rbtree-2.6.git;a=commitdiff;h=1975e59375756da4ff4e6e7d12f67485e813ace0

> >  #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?

I think it's be better just to drop the RB_RED and RB_BLACK definitions.

> > +static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
> > +{
> 
> 	BUG_ON((unsigned long)p & 3);

Yeah, I suppose we could.
> > @@ -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.

Que?

-- 
dwmw2