Родительский указатель в ядре linux RBTree

Question

Мне интересно знать, как поддерживается родительский указатель? Насколько я понимаю, в 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. Все, что я спрашиваю, как работает эта маска для маскировки указателя?

Answer 1

Я не знал, что это было задано ранее.

Red black node's struct alignment in linux kernel

Это точно подробное описание мне было нужно.

Answer 2

Получите мой ответ как предположение, мне слишком лениво проверьте его сейчас :-) На самом деле младший бит не используется, потому что адрес всегда выровнен, так что младший бит ДОЛЖЕН быть 0;

Точно так же они используют самый младший бит в некоторой ситуации на страницах управления ресурсами памяти - они просто используют младший бит в предположении, что он всегда выровнен и он должен быть 0; поэтому установка его как 1 не меняет ситуацию.

Удачи.