怎样使用linux内核的红黑树接口

bullity

本人想直接使用内核的红黑树而不做修改，但不知道怎样具体使用，好像有个什么rb_entry什么的，请哪位知道的说下具体怎么使用，？？？

Godbach

我给你找找我前一段转过的一篇帖子啊。

Godbach

linux内核中的红黑树：
http://linux.chinaunix.net/bbs/viewthread.php?tid=1055772

其实，多看看使用红黑树的内核代码应该会有很大帮助。

scutan

Godbach 版写的那个文章不错, 还有就是看内核源码目录下的Document, 也讲了如何使用的.

Godbach

原帖由 scutan 于 2009-2-25 16:24 发表
Godbach 版写的那个文章不错, 还有就是看内核源码目录下的Document, 也讲了如何使用的.

惭愧啊。那篇文章是我转载的。
看来是标题没写清楚。

wsnhyjj

红黑树的每一个rb_node节点是嵌入在用红黑树进行组织的数据结构中，而不是用rb_node指针进行数据结构的组织。
rb_entry这个宏就是用来获取包含了rb_node的数据结构的指针的。

#define rb_entry(node,type,member) container_of(node,type,member)

#define container_of(ptr, type, member) ({\
    const typeof( ((type *)0)->member ) *__mptr = (ptr);\
    (type *)( (char *)__mptr - offsetof(type,member) );})

比如 struct vma_area_struct{
                      ....
                    struct rb_node vm_rb;
                      .....
      }

struct vm_area_struct *vma;
      我们现在知道了 vma->vm_rb的地址(假设为addr, struct rb_node*类型的)，就可以用rb_entry宏来获取vma的值了， 形式如下：
      rb_entry(addr, struct vm_area_struct, vm_rb)。

     自己看下相关内核代码就知道了。

wsnhyjj

红黑树的内核文档中介绍了如何使用的。

Godbach

原帖由 wsnhyjj 于 2009-2-25 18:13 发表
红黑树的内核文档中介绍了如何使用的。

对。内核中对应的文档也介绍了如何使用。