Мне интересно узнать, как поддерживается родительский указатель? Насколько я понимаю, в linux rbtree есть одна переменная unsigned long, в которой хранится адрес родительского указателя и цветовой узел? Я не могу понять, как это возможно без изменения родительского указателя, даже если его 1-битное поле цвета.
Пример использования, как в 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)
Я не могу понять оба макроса, что связано с моим предыдущим вопросом. rb_parent_color длинный, который содержит адрес родительского указателя и цвет узла (очевидно из макроса rb_color. Все, что я спрашиваю, это как работает эта логика маскировки указателя?