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:
...which is precisely the technique used here.