求解红黑树

haoqing1120

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))));

这个结构体中的#define占内存吗？还有就是，这个是按long对齐的，一般也就是4对齐，那怎么利用rb_parent_color来保存的父节点的颜色的？谢谢了，本人菜鸟一个

haoqing1120

自己顶下，求大神指导啊

myguyan

搜索本版，我记得是用地址的后两位来表示的

Godbach

回复 1# haoqing1120

宏定义是不占用结构体的内存的。这个用法之前讨论过，其中一个作用就是就近方便

Godbach

回复 1# haoqing1120
地址按照 long 对其之后，其最后两个 bit 肯定为 0，与其闲着不用，比如用来存储颜色，而实际上也只是用了一个 bit

haoqing1120

回复 5# Godbach


    谢谢你的答案，我想问的是，既然是按sizeof（long）对齐的，这个结构体也就是12字节了，最后两个bit指的是哪两个bit呢？为什么是0呢？谢谢斑竹的耐心回答

haoqing1120

求解释这句话“既然是sizeof(long)大小的对齐，那么在IA-32上，任何rb_node结构体的地址的低两位肯定都是零，与其空着不用，还不如用它们表示颜色，反正颜色就两种，其实只要一位就够了（估计此处也是照顾16位的机器）。”

xparmenides

struct rb_node
{
        unsigned long  rb_parent_color;
#define        RB_RED                0
...
haoqing1120 发表于 2011-10-31 16:04

所有rb_node变量的地址都是4字节对齐，所以rb_node变量地址的低两位都为0。父节点指针当然指向rb_node型变量，所以父节点指针的低两位也一定为0。所以可以利用这两位来保存颜色，事实上颜色只用一位即可。

amarant

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))));

这个结构体中的#define占内存吗？
#define 是预处理，搞清楚概念

还有就是，这个是按long对齐的，一般也就是4对齐，那怎么利用rb_parent_color来保存的父节点的颜色的？
因为在寻址指针的时候总是会用rb_parent_color & ~3   低两位都给屏蔽了，所以无论低两位值是什么不影响。这样做是为了节省内存，毕竟一个节点就有一个该结构，如果增加一个color结构，那么对整个系统会多消耗很多内存。
楼上说的很清楚了，呵呵

haoqing1120

回复 9# amarant


    谢谢斑竹，原来是&~3把低两位屏蔽了，我就是这个地方没想通，现在明白了