Parent pointer in linux kernel RBTree

Question

I am interested in knowing how is parent pointer maintained ? As far as I understand there's a single variable unsigned long in linux rbtree which stores the address of the parent pointer and the color node ? I am unable to understand how this is possible without the parent pointer getting modified even if its 1 bit color field.

A sample usage as in rbtree.h

struct rb_node
{ 
        unsigned long  rb_parent_color;
#define RB_RED          0
#define RB_BLACK        1
        struct rb_node *rb_right;
        struct rb_node *rb_left;
} __attribute__((aligned(sizeof(long))));

static void __rb_rotate_left(struct rb_node *node, struct rb_root *root)
{
        struct rb_node *right = node->rb_right;
        struct rb_node *parent = rb_parent(node);
        ...
        ...
        ...
}



The macros are defined as 
#define rb_parent(r)   ((struct rb_node *)((r)->rb_parent_color & ~3))
#define rb_color(r)   ((r)->rb_parent_color & 1)

I am unable to understand both the macros, which is related to my earlier question. rb_parent_color is long which holds the address of the parent pointer and color of node (evident from the rb_color macro. All I am asking is how this pointer masking logic works ?

Answer 1

I was not aware that this was asked earlier.

Red black node's struct alignment in linux kernel

This is exactly the detailed description I needed.

Answer 2

Get my answer as assumption, I am too lazy to check it now :-) Actually the lowest bit is unused because the address always aligned so the lowest bit MUST be 0;

The same manner they use the lowest bit in some situation in memory pages managent - they just use lowest bit in assumption that it always aligned and it must be 0; so setting it as 1 does't change things.

Good luck.