Red-black Trees (rbtree) in Linux January 18, 2007 Rob Landley ============================= red-black树是什么样的树,为什么需要red-black树? ------------------------------------------------ red-black tree(RB树)是一种平衡二叉树,它主要用于存储或者说索引可排序的键 值对数据。RB树(红黑树)与radix树和hash表都不同。radix树是一种比较适合用于 存储稀疏的数据集而且将用一个大整数进行插入,删除,查找的操作基础。而hash表 并不是以某种排序顺序进行存储,而且必须指定大小和hash函数。 RB树与AVL树很相似,但是比AVL树有更好的插入和删除最坏情况的时间复杂度,以及 O(log n)的最坏查找时间复杂度。 引用: 在Linux中有很多地方用到了RD树。anticipatory, deadline, 和CFQ I/O调度都使用 的是RB树进行请求跟踪,还有CD/DVD驱动的包管理也是如此。 高精度计时器(high-resolution timer)使用RB树组织定时请求。 EXT3文件系统也使用RB树来管理目录。 虚拟存储管理系统也是有RB树进行VMAs(Virtual Memory Areas)的管理。 当然还有文件描述符,密码钥匙,“等级令牌桶”调度的网络数据包都是用RB数据进 行组织和管理的。 相关资料: Linux Weekly News article on red-black trees http://lwn.net/Articles/184495/ Wikipedia entry on red-black trees http://en.wikipedia.org/wiki/Red-black_tree 可见RB树(红黑树)在Linux内核中的重要性。 Linux内核的RB树实现 --------------------------------------- 在Linux内核源代码中rb树的实现在lib/rbtree.c文件中,可以通过 #include "linux/rbtree.h"进行使用。 在Linux内核中的RB树实现与传统的实现方式有些不同。它对针对内核对速度的需要做 了些优化。每一个rb_node节点是嵌入在用RB树进行组织的数据结构中,而不是用 rb_node指针进行数据结构的组织。 创建一棵RB树 --------------------- 在RB树里的数据节点包含了一个rb_node数据结构节点。如下: struct mytype { struct rb_node node; char *keystring; }; 可以通过container_of宏取得包含了rb_node的数据结构。也可以通过 rb_entry(node,type,member)取得。 其实是#define rb_entry(node,type,member) container_of(node,type,member) 这里顺便说一下如何通过container_of取得包含rb_node的数据结构指针: 在Linux内核代码里有这样的宏定义: #define container_of(ptr, type, member) ({\ const typeof( ((type *)0)->member ) *__mptr = (ptr);\ (type *)( (char *)__mptr - offsetof(type,member) );}) #define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER) 那么对于struct mytype,如何通过其成员node来取得走首地址呢: 我们肯定已经知道node的地址,假设为pnode; struct mytype* x = rb_entry(pnode, struct mytype, node); 意思是,取得pnode所被包含的数据结构对象的首地址,pnode是指向struct mytype的 成员node的指针。 宏替换完后就是这个样子: ({ const typeof( ((struct mytype *)0)->node ) *__mptr = (pnode); (struct mytype *)((char *)__mptr-((size_t)&((struct mytype*)0)->node)); }) typeof取得struct mytype中node成员的类型,用这个类型定义一个新的指针,把 pnode的值赋给它,在这里起到了类型检查的作用。 offsetof(type,member)是取得member在type对象中相对于此对象首地址的偏移量。 那么用__mptr减去这个偏移量就得到了type对象的起始地址。也就得到了把rb_node 作为嵌入的管理数据结构的对象起始地址。 x = y - offset ---------- rb_node; while (node) { struct mytype *data = container_of(node, struct mytype, node); int result; result = strcmp(string, data->keystring); if (result rb_left; else if (result > 0) node = node->rb_right; else return data; } return NULL; } 向RB树中插入一个数据 -------------------- 在插入一个数据之前先要查找到适合插入的位置,然后将节点加入到树中并将树调整 到平衡状态。 int my_insert(struct rb_root *root, struct mytype *data) { struct rb_node **new = &(root->rb_node), *parent = NULL; /* Figure out where to put new node */ while (*new) { struct mytype *this = container_of(*new, struct mytype, node); int result = strcmp(data->keystring, this->keystring); parent = *new; if (result rb_left); else if (result > 0) new = &((*new)->rb_right); else return FALSE; } /* Add new node and rebalance tree. */ rb_link_node(data->node, parent, new); rb_insert_color(data->node, root); return TRUE; } 删除一个数据节点 ---------------- struct mytype *data = mysearch(mytree, "walrus"); if (data) { rb_erase(data->node, mytree); myfree(data); } 可以通过调用 void rb_replace_node(struct rb_node *old, struct rb_node *new, struct rb_root *tree); 来替换一个节点,但是替换完成后并不会对RB树做任何调整,所以如果新节点的值与 被替换的值有所不同时,可能会出现问题。 |
|小黑屋|最新主题|手机版|微赢网络技术论坛 ( 苏ICP备08020429号 )
GMT+8, 2024-9-30 05:39 , Processed in 0.080851 second(s), 12 queries , Gzip On, MemCache On.
Powered by Discuz! X3.5
© 2001-2023 Discuz! Team.