Linux红黑树(二)——访问节点

本是古典何须时尚 2022-09-19 00:22 112阅读 0赞

### 核心对红黑树使用两点说明    ###

#### 1、头文件    ####

<Documentation/rbtree.txt>  
Linux's rbtree implementation lives in the file "lib/rbtree.c".  To use it,  
"\#include <linux/rbtree.h>".

#### 2、自我封装    ####

To use rbtrees you'll have to implementyour own insert and search cores. This will avoid us to use callbacks and todrop drammatically performances. I know it's not the cleaner way,  but in C (not in C++) to get performances andgenericity...

【这里中心思想： 在使用rbtree时候，你需要自己实现你的插入和查询的核心代码，即使用核心API，自我封装。这可以避免使用回调函数和性能上的损失。（由于键值不同，调用用户定义的函数，就需要采用回调的形式；显然这里没有使用）】

The Linux rbtree implementation is optimized for speed, and thus has one less layer of indirection (and better cache locality) than more traditional tree implementations.  Instead of using pointers to separate rb\_node and data structures, each instance of struct rb\_node is embedded in the data structure it organizes.  And instead of using a comparison callback function pointer, users are expected to write their own tree search and insert functions which call the provided rbtree functions.  Locking is also left up to the user of the rbtree code.  
  
【在Linux rbtree实现了速度优化，具有比传统树的实现要少一个间接层（和更好的缓存）。每个struct rb\_node实例是嵌入在数据组织成的结构体中，以此代替使用指针来区分rb\_node和数据结构。并且相比采用回调函数的指针形式，用户可以通过调用rbtree提供的函数，写自己的树搜索和插入函数。锁也留给使用rbtree代码的用户自己管理。】

以上两大段，读懂还是读不懂都无关紧要！因为你只需要明白2点即可：1、struct rb\_node实例是嵌入在用户数据结构体当中的，这是和链表一样的通用做法；2、rbtree提供最基础的操作API，不进行封装，用户自己管理操作红黑树的代码

### 1、访问元素（包含数据的结构体）    ###

When dealing with a pointer to the embedded struct rb\_node, the containing data  
structure may be accessed with the standard container\_of() macro.  In addition,  
individual members may be accessed directly via rb\_entry(node, type, member).

<linux/rbtree.h>
    #define	rb_entry(ptr, type, member) container_of(ptr, type, member)

### 2、查找树元素 ###

<Documentation/rbtree.txt>
    Searching for a value in an rbtree
    ----------------------------------
    
    Writing a search function for your tree is fairly straightforward: start at the
    root, compare each value, and follow the left or right branch as necessary.
    
    Example:
    
      struct mytype *my_search(struct rb_root *root, char *string)
      {
      	struct rb_node *node = root->rb_node;
    
      	while (node) {
      		struct mytype *data = container_of(node, struct mytype, node);
    		int result;
    
    		result = strcmp(string, data->keystring);
    
    		if (result < 0)
      			node = node->rb_left;
    		else if (result > 0)
      			node = node->rb_right;
    		else
      			return data;
    	}
    	return NULL;
      }

由于红黑树也是二叉查找树，因此对树元素的查找和二叉查找树的查找算法一致。

1.  若b是空树，则搜索失败，否则转向2
2.  若x等于b的根节点的数据域之值，则查找成功；否则转向3
3.  若x小于b的根节点的数据域之值，则搜索左子树，转向1；否则转向4
4.  查找右子树，转向1

参考 [维基二叉查找树][Link 1]

### 3、树节点的访问 ###

对二叉查找树"中序"遍历可以得到键值有序的序列。内核提供了四个有序访问红黑树节点函数，它们只工作在二叉树情况下，不供其他多叉树使用。一般不需要重新和修改，只有在需要加锁的情况下，才允许这么做。

#### 3.1、获取树的第一个有序节点 ####

树根左子树的最左边的节点

<lib/rbtree.c>
    /*
     * This function returns the first node (in sort order) of the tree.
     */
    struct rb_node *rb_first(const struct rb_root *root)
    {
    	struct rb_node	*n;
    
    	n = root->rb_node;
    	if (!n)//树空
    		return NULL;
    	while (n->rb_left)//树最左端
    		n = n->rb_left;
    	return n;
    }
    EXPORT_SYMBOL(rb_first);

#### 3.2、获取树的最后一个有序节点 ####

树根右子树最右边的节点

<lib/rbtree.c>
    struct rb_node *rb_last(const struct rb_root *root)
    {
    	struct rb_node	*n;
    
    	n = root->rb_node;
    	if (!n)//树空
    		return NULL;
    	while (n->rb_right)//树最右端
    		n = n->rb_right;
    	return n;
    }
    EXPORT_SYMBOL(rb_last);

#### 3.3、获取当前节点的有序后继节点 ####

当前节点的右孩子，或者右子树最左端的节点，或者祖先节点

<lib/rbtree.c>
    struct rb_node *rb_next(const struct rb_node *node)
    {
    	struct rb_node *parent;
    
    	if (RB_EMPTY_NODE(node))
    		return NULL;
    
    	/*
    	 * If we have a right-hand child, go down and then left as far
    	 * as we can.
    	 */
    	if (node->rb_right) {
    		node = node->rb_right; 
    		while (node->rb_left)
    			node=node->rb_left;
    		return (struct rb_node *)node;
    	}
    
    	/*
    	 * No right-hand children. Everything down and left is smaller than us,
    	 * so any 'next' node must be in the general direction of our parent.
    	 * Go up the tree; any time the ancestor is a right-hand child of its
    	 * parent, keep going up. First time it's a left-hand child of its
    	 * parent, said parent is our 'next' node.
    	 */
    	while ((parent = rb_parent(node)) && node == parent->rb_right)
    		node = parent;
    
    	return parent;
    }
    EXPORT_SYMBOL(rb_next);

![20131208210604812][]

注：最低端叶子节点省略了，而且其他分支没有画出，即图示不是完整的红黑树，只是拿树中一部分来说明！

#### 3.4、获取当前节点的有序前驱节点 ####

当前节点的左孩子，或者左子树的最右端节点，或者它的祖先节点

<lib/rbtree.c>
    struct rb_node *rb_prev(const struct rb_node *node)
    {
    	struct rb_node *parent;
    
    	if (RB_EMPTY_NODE(node))
    		return NULL;
    
    	/*
    	 * If we have a left-hand child, go down and then right as far
    	 * as we can.
    	 */
    	if (node->rb_left) {
    		node = node->rb_left; 
    		while (node->rb_right)
    			node=node->rb_right;
    		return (struct rb_node *)node;
    	}
    
    	/*
    	 * No left-hand children. Go up till we find an ancestor which
    	 * is a right-hand child of its parent.
    	 */
    	while ((parent = rb_parent(node)) && node == parent->rb_left)
    		node = parent;
    
    	return parent;
    }
    EXPORT_SYMBOL(rb_prev);

![20131208211407953][]

### 4、有序遍历树节点 ###

<Documentation/rbtree.txt>
    To start iterating, call rb_first() or rb_last() with a pointer to the root
    of the tree, which will return a pointer to the node structure contained in
    the first or last element in the tree.  To continue, fetch the next or previous
    node by calling rb_next() or rb_prev() on the current node.  This will return
    NULL when there are no more nodes left.
    
    The iterator functions return a pointer to the embedded struct rb_node, from
    which the containing data structure may be accessed with the container_of()
    macro, and individual members may be accessed directly via rb_entry(node, type, member).
    
    Example:
    
      struct rb_node *node;
      for (node = rb_first(&mytree); node; node = rb_next(node))
    	printk("key=%s\n", rb_entry(node, struct mytype, node)->keystring);

声明：

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

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

[Link 1]: http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9
[20131208210604812]: /images/20220828/e23b94be18ea40edb8156eadd2d00b21.png
[20131208211407953]: /images/20220828/23cb67898b1c461bb9afebeb1910a046.png