Linux红黑树(一)——数据结构

超、凢脫俗 2022-09-19 00:18 167阅读 0赞

### 摘要 ###

兹博文探讨四个重点：1、简单介绍红黑树；2、红黑树节点数据结构；3、红黑树节点中父节点指针域和自身节点颜色有机结合；4、定义红黑树和操作树节点父节点指针和节点颜色的接口，包括一系列宏和两个函数。

注：所有代码源自kernel 3.10

### 前言 ###

援引<Documentation/rbtree.txt>中的一部分，并做简单的翻译(个别地方不太好)，姑且作为红黑树博文的开篇。

What are red-black trees, and what are they for?
    ------------------------------------------------
    什么是红黑树？并且他们用于什么？
    
    Red-black trees are a type of self-balancing binary search tree, used for
    storing sortable key/value data pairs.  This differs from radix trees (which
    are used to efficiently store sparse arrays and thus use long integer indexes
    to insert/access/delete nodes) and hash tables (which are not kept sorted to
    be easily traversed in order, and must be tuned for a specific size and
    hash function where rbtrees scale gracefully storing arbitrary keys).
    
    红黑树是一种自平衡二叉搜索树，用于存储可排序的键/数值数据。它不同于基数树
    （用来有效地存储稀疏数组，因此使用长整数索来插入/存取/删除节点）和哈希表
    （它不用进行排序就可以很容易地按序遍历，但必须设定具体大小和散列函数，而红黑树优
    雅的扩展存储任意键）
    
    Red-black trees are similar to AVL trees, but provide faster real-time bounded
    worst case performance for insertion and deletion (at most two rotations and
    three rotations, respectively, to balance the tree), with slightly slower
    (but still O(log n)) lookup time.
    
    红黑树类似于AVL树，但对于插入（至多两次旋转）和删除（至多三次旋转来重新平衡红黑树）
    提供最坏情况下实时复杂度的更快的性能，和稍慢的查询时间（依旧是O(log n)）
    
    To quote Linux Weekly News:
    
        There are a number of red-black trees in use in the kernel.
        The deadline and CFQ I/O schedulers employ rbtrees to
        track requests; the packet CD/DVD driver does the same.
        The high-resolution timer code uses an rbtree to organize outstanding
        timer requests.  The ext3 filesystem tracks directory entries in a
        red-black tree.  Virtual memory areas (VMAs) are tracked with red-black
        trees, as are epoll file descriptors, cryptographic keys, and network
        packets in the "hierarchical token bucket" scheduler.
    
    援引Linux Weekly News:
    	deadline和CFQ(Completely Fair Queueing)两种I/O调度,运用rbtree跟踪请求;
    CD/DVD块数据驱动器也是如此。高分辨率定时器代码中使用rbtree出色的组织定时器的请求。
    Ext3文件系统使用rbtree跟踪目录项。虚拟存储区（VMA）的跟踪，以及epoll的文件描述符，
    加密密钥，“分层令牌桶”调度网络数据包也均有rbtree的使用。

### 1、红黑树节点数据结构 ###

<linux/rbtree.h>
    
    struct rb_node {
           unsignedlong  __rb_parent_color; //下面详细解析这个变量
           structrb_node *rb_right;//右孩子指针域
           structrb_node *rb_left;//左孩子指针域
    } __attribute__((aligned(sizeof(long))));

——sizeof(long)返回long类型的字节数n；aligned(n)——指明结构体n字节对齐；\_\_attribute\_\_是GCC编译器的扩展，属性约束！这句话的含义：struct rb\_node按照4字节(long)对齐!对于\_\_attribute\_\_和aligned详细说明和用法可以查阅[gcc在线用户手册][gcc]

structrb\_node结构体4字节对齐，那么它在内存中的基地址base一定是的4的倍数（base % 4 == 0）；由于指针在32位系统之上占用4B，则32bit基地址base的低两位一定为0（否则“base % 4 == 0”不成立，不再是4B对齐）。

红黑树节点必须保存四个值：

（1）自身的颜色(color，红黑树的必须)

（2）父节点指针（使得红黑树向上走查找父节点的时间复杂度是O(1)）

（3）左孩子节点指针（使得红黑树向左走查找左孩子的时间复杂度是O(1)）

（4）右孩子节点指针（使得红黑树向右走查找右孩子的时间复杂度是O(1)）

<linux/augmented.h>
    #define	RB_RED		0
    #define	RB_BLACK	1

红黑树节点的颜色只有两个——红(0)和黑(1)，使用1bit就足够表示！而struct rb\_node结构体基地址低2位“不使用”，那么可以使用最低位来存储节点的颜色，把基地址和颜色值或(|)运算整合成一个变量\_\_rb\_parent\_color，这样就节省了一个存储颜色的变量。

【如果单独定义一个变量来存储颜色值，假设4B无符号整型（即使是shot或者char类型，在4B对齐状态下也是占用4B）那么当树的节点数量增长时，每增长一个树节点，就会多开销4B！并且存储父节点地址的变量低两位又不使用，4个树节点就浪费1B；记住：核心内存有限，每消耗1B，核心就少1B——不损失性能的情况下，能节约就节约！】

### 2、红黑树根 ###

<linux/rbtree.h>
    struct rb_root {
    	struct rb_node *rb_node;
    };

通过此指针是否为空，来判断树是否为空！引入下面接口

#define RB_EMPTY_ROOT(root)  ((root)->rb_node == NULL)

定义一棵红黑树，初始化为空树：

static struct rb\_root mytree = RB\_ROOT;

其中RB\_ROOT在<linux/rbtree.h>中定义

#define RB_ROOT	(struct rb_root) { NULL, }

它将\{NULL,\}强制转换成(struct rb\_root)，初始化树为空！

### 3、操纵成员\_\_rb\_parent\_color的接口 ###

#### 3.1、提取父节点地址 ####

<linux/rbtree.h>
    #define rb_parent(r)   ((struct rb_node *)((r)->__rb_parent_color & ~3))
    
    <linux/rbtree_augmented.h>
    #define __rb_parent(pc)    ((struct rb_node *)(pc & ~3))

32bit

3=0000 0000 0000 0000 0000 0000 0000 0011

~3 =1111 1111 1111 1111 1111 1111 1111 1100

\_\_rb\_parent\_color & ~3=过滤掉低2位（非0变成0），保留第3-32位。由于\_\_rb\_parent\_color是无符号整数，强制转换成struct rb\_node \*类型。

上面两个宏作用一样，不过参数不一样——前者是指向节点的指针r；后者是节点成员unsignedlong  \_\_rb\_parent\_color。此外，”\_\_”前缀也强调内外之分。

<lib/rbtree.c>
    static inline struct rb_node *rb_red_parent(struct rb_node *red)
    {
    	return (struct rb_node *)red->__rb_parent_color;
    }

由于红色节点的成员变量\_\_rb\_parent\_color的低两位为0，因此\_\_rb\_parent\_color的值就是此红色节点的父节点基址。转换下数据类型，直接返回即可！

#### 3.2、提取和判断结点颜色 ####

<linux/rbtree_augmented.h>
    #define __rb_color(pc)     ((pc) & 1)	//struct rb_node成员“pc”值的最低位。
    #define __rb_is_black(pc)  __rb_color(pc)
    //逻辑判断节点是不是黑色；pc值最低位为1，节点是黑色（真）；最低位为0，不是黑色（假）
    #define __rb_is_red(pc)    (!__rb_color(pc))
    ///逻辑判断节点是不是红色；pc值最低位为1，不是红色（假）；最低位为0，是红色（真）
    #define rb_color(rb)       __rb_color((rb)->__rb_parent_color)
    //提取节点颜色；值0红色，值1为黑色；
    #define rb_is_red(rb)      __rb_is_red((rb)->__rb_parent_color)
    //封装成外部接口，接受struct rb_node* 类型rb为参数
    #define rb_is_black(rb)    __rb_is_black((rb)->__rb_parent_color)
     //封装成外部接口，接受struct rb_node* 类型rb为参数

#### 3.3、设置父节点指针 ####

<linux/rbtree_augmented.h>
    static inline void rb_set_parent(struct rb_node *rb, struct rb_node *p)
    {
    	rb->__rb_parent_color = rb_color(rb) | (unsigned long)p;
    }

![20131208165842671][]

由图示可以很容易明白，这个函数可以用来更新节点的父节点指针使得其指向新的父节点。

#### 3.4、设置父节点指针和节点颜色 ####

<linux/rbtree_augmented.h>
    static inline void rb_set_parent_color(struct rb_node *rb, struct rb_node *p, int color)		       
    {
    	rb->__rb_parent_color = (unsigned long)p | color;
    }

![20131208170038937][]

<lib/rbtree.c>
    static inline void rb_set_black(struct rb_node *rb)
    {
    	rb->__rb_parent_color |= RB_BLACK;
    }

![20131208184920906][]

####    3.5、节点的逻辑判断 ####

<linux/rbtree.h>
    /* 'empty' nodes are nodes that are known not to be inserted in an rbree */
    注释已经说得够明白了，代码也很明白。原因以后再论。
    #define RB_EMPTY_NODE(node)  \
    	((node)->__rb_parent_color == (unsigned long)(node))
    #define RB_CLEAR_NODE(node)  \
    	((node)->__rb_parent_color = (unsigned long)(node))

### 4、扩展红黑树 ###

针对扩展红黑树的操作，必须提供特定操作的回调函数。核心定义一个扩展红黑树的回调函数数据结构。包括三部分，分别是：繁殖，拷贝，旋转！

struct rb_augment_callbacks {
    	void (*propagate)(struct rb_node *node, struct rb_node *stop);
    	void (*copy)(struct rb_node *old, struct rb_node *new);
    	void (*rotate)(struct rb_node *old, struct rb_node *new);
    };

静态定义扩展红黑树的回调函数可以调用下面宏,它根据用户提供的参数定义对应的回调函数名和函数体！

#define RB_DECLARE_CALLBACKS(rbstatic, rbname, rbstruct, rbfield,	\
    			     rbtype, rbaugmented, rbcompute)		\
    static inline void							\
    rbname ## _propagate(struct rb_node *rb, struct rb_node *stop)		\
    {									\
    	while (rb != stop) {						\
    		rbstruct *node = rb_entry(rb, rbstruct, rbfield);	\
    		rbtype augmented = rbcompute(node);			\
    		if (node->rbaugmented == augmented)			\
    			break;						\
    		node->rbaugmented = augmented;				\
    		rb = rb_parent(&node->rbfield);				\
    	}								\
    }									\
    static inline void							\
    rbname ## _copy(struct rb_node *rb_old, struct rb_node *rb_new)		\
    {									\
    	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
    	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
    	new->rbaugmented = old->rbaugmented;				\
    }									\
    static void								\
    rbname ## _rotate(struct rb_node *rb_old, struct rb_node *rb_new)	\
    {									\
    	rbstruct *old = rb_entry(rb_old, rbstruct, rbfield);		\
    	rbstruct *new = rb_entry(rb_new, rbstruct, rbfield);		\
    	new->rbaugmented = old->rbaugmented;				\
    	old->rbaugmented = rbcompute(old);				\
    }									\
    rbstatic const struct rb_augment_callbacks rbname = {			\
    	rbname ## _propagate, rbname ## _copy, rbname ## _rotate	\
    };

理解宏的最好方式就是用以个实例套进去，推演一遍！下面这个代码是<rbtree.txt>中的实例

static void augment_propagate(struct rb_node *rb, struct rb_node *stop)
    {
    	while (rb != stop) {
    		struct interval_tree_node *node =
    			rb_entry(rb, struct interval_tree_node, rb);
    		unsigned long subtree_last = compute_subtree_last(node);
    		if (node->__subtree_last == subtree_last)
    			break;
    		node->__subtree_last = subtree_last;
    		rb = rb_parent(&node->rb);
    	}
    }
    
    static void augment_copy(struct rb_node *rb_old, struct rb_node *rb_new)
    {
    	struct interval_tree_node *old =
    		rb_entry(rb_old, struct interval_tree_node, rb);
    	struct interval_tree_node *new =
    		rb_entry(rb_new, struct interval_tree_node, rb);
    
    	new->__subtree_last = old->__subtree_last;
    }
    
    static void augment_rotate(struct rb_node *rb_old, struct rb_node *rb_new)
    {
    	struct interval_tree_node *old =
    		rb_entry(rb_old, struct interval_tree_node, rb);
    	struct interval_tree_node *new =
    		rb_entry(rb_new, struct interval_tree_node, rb);
    
    	new->__subtree_last = old->__subtree_last;
    	old->__subtree_last = compute_subtree_last(old);
    }

static const struct rb_augment_callbacks augment_callbacks = {
    	augment_propagate, augment_copy, augment_rotate
    };

对于红黑树的操作，下篇博文给予详细解析！

声明：

>>     知识要传播，劳动要尊重! 受益于开源，回馈于社会! 大家共参与，服务全人类!

>>     本博文由my\_live\_123原创(http://blog.csdn.net/cwcmcw)，转载请注明出处!   ^\_^

[gcc]: http://gcc.gnu.org/onlinedocs/
[20131208165842671]: /images/20220828/6c4aa6924d2b4dfb8e916a00361de97b.png
[20131208170038937]: /images/20220828/849e11bb0bd1435d845e1008ab8f685f.png
[20131208184920906]: /images/20220828/273ee517175449368a8060175c8e016f.png