__attribute__((aligned(sizeof(long))))
tells the compiler to ensure that the size of struct rb_node
is always going to be at least a multiple of sizeof(long)
. See GCC docs.
That point is somewhat irrelevant though (because the pointers are at least sizeof(long
). And looking at the source, you left out the most important part:
/* The alignment might seem pointless, but allegedly CRIS needs it */
The key to this implementation working, is that struct rb_node
s will always be allocated on addresses that are at least 4-byte aligned. This is guaranteed:
4-byte alignment is guaranteed on 32-bit cpus, 8-byte alignment on 64-bit cpus.
For example, a node pointer might be like 0xF724315C
, which in binary ends in ...1100
.
That means that the last two bits of any pointer to a struct rb_node
will be zero. Because of this, the developers decided to use those two bits for something else (here, the color.)
We see this in the following macro:
#define rb_parent(r) ((struct rb_node *)((r)->__rb_parent_color & ~3))
To get the parent node, one uses that macro which ands off the lower two bits.