RB tree

RB tree

[Alberich de megres]

Hi!

I know this could be a stupid question, but taking a look at rbtree
kernel imprelantacion used in ext3 fs, I understand what lines do, but
i could not see what the use it (i'm not telling it is pointless, only
that i didn't understand why its doing what its doing)

I can see it's zeroing last 2 bits on the rb_parent_color:
#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))

We are getting only last bit:
#define rb_color(r)   ((r)->rb_parent_color & 1)

Setting or clearing the last bit:
#define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
#define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)


And here, comes my trouble:
static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
{
         rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
}
static inline void rb_set_color(struct rb_node *rb, int color)
{
        rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
}
we are aligning the pointer address??


Thanks for the patience!!

Alberich

Re: RB tree

[Wendy Cheng]

I don't have kernel source code handy but iirc ...

Linux RB tree uses the same field (rb_parent_color in your example) to 
store two information: the pointer to the parent node AND the color of 
the node. The purpose (my guess) is to reduce the memory requirement (so 
you only need one word, instead of two, in a 32-bit platform).

This implies if you want the color, you take the last bit. If you want 
to work on parent address, you have to wipe out the last bit. The "~3" 
in the rb_parent() macro is just to make the code more readable (again, 
my guess) since this structure is normally aligned. Check its header 
file (or http://en.wikipedia.org/wiki/Red-black_tree) for details.

Hopefully I interpret your question right.

-- Wendy


Alberich de megres wrote:
> Hi!
>
> I know this could be a stupid question, but taking a look at rbtree
> kernel imprelantacion used in ext3 fs, I understand what lines do, but
> i could not see what the use it (i'm not telling it is pointless, only
> that i didn't understand why its doing what its doing)
>
> I can see it's zeroing last 2 bits on the rb_parent_color:
> #define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
>
> We are getting only last bit:
> #define rb_color(r)   ((r)->rb_parent_color & 1)
>
> Setting or clearing the last bit:
> #define rb_set_red(r)  do { (r)->rb_parent_color &= ~1; } while (0)
> #define rb_set_black(r)  do { (r)->rb_parent_color |= 1; } while (0)
>
>
> And here, comes my trouble:
> static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
> {
>          rb->rb_parent_color = (rb->rb_parent_color & 3) | (unsigned long)p;
> }
> static inline void rb_set_color(struct rb_node *rb, int color)
> {
>         rb->rb_parent_color = (rb->rb_parent_color & ~1) | color;
> }
> we are aligning the pointer address??
>
>
> Thanks for the patience!!
>
> Alberich
> --
> To unsubscribe from this list: send the line "unsubscribe linux-fsdevel" in
> the body of a message to majordomo@vger.kernel.org
> More majordomo info at  http://vger.kernel.org/majordomo-info.html
>