How does RBTree's color trick work?

Question

In wikipedia : Red-black_tree

Tracking the color of each node requires only 1 bit of information per node because there >are only two colors. The tree does not contain any other data specific to its being a red–>black tree so its memory footprint is almost identical to classic (uncolored) binary search >tree. In many cases the additional bit of information can be stored at no additional memory >cost.

And I found an implement of rbtree in C:

#ifdef UINTPTR_MAX

static inline enum rb_color get_color(const struct rbtree_node *node)
{
    return node->parent & 1;
}

static inline void set_color(enum rb_color color, struct rbtree_node *node)
{
    node->parent = (node->parent & ~1UL) | color;
}

static inline struct rbtree_node *get_parent(const struct rbtree_node *node)
{ 
    return (struct rbtree_node *)(node->parent & ~1UL);
}

static inline void set_parent(struct rbtree_node *parent, struct rbtree_node *node)
{
    node->parent = (uintptr_t)parent | (node->parent & 1);
}

#else
...
#endif

My question is how this color trick works?Thx.

Answer 1

It's using a(n incredibly sketchy) trick of altering the pointer to the parent to store a single bit, which indicates the color. The least significant bit in that pointer contains the color:

static inline enum rb_color get_color(const struct rbtree_node *node)
{
    return node->parent & 1;
}

If the low bit is 0 then the color is, say, red, and if the low bit is 1 then the color is black. (Realize that it's irrelevant whether red is 0 and black is 1, or vice versa).

---

@Daniel Fischer commented with a link that warrants being brought out of the comments:

http://en.wikipedia.org/wiki/Pointer_tagging

...which is precisely the technique used here.