Documentation/translations/zh_CN/core-api/rbtree.rst

Source file repositories/reference/linux-study-clean/Documentation/translations/zh_CN/core-api/rbtree.rst

File Facts

System
Linux kernel
Corpus path
Documentation/translations/zh_CN/core-api/rbtree.rst
Extension
.rst
Size
14490 bytes
Lines
392
Domain
Support Tooling And Documentation
Bucket
Documentation
Inferred role
Support Tooling And Documentation: documentation
Status
atlas-only

Why This File Exists

Repository support layer: documentation, build tooling, samples, user-space helper tools, generated initramfs support, licenses, and validation utilities.

Dependency Surface

Detected Declarations

Annotated Snippet

struct mytype {
  	struct rb_node node;
  	char *keystring;
  };

当处理一个指向内嵌rb_node结构体的指针时，包住rb_node的结构体可用标准的container_of()
宏访问。此外，个体成员可直接用rb_entry(node, type, member)访问。

每颗红黑树的根是一个rb_root数据结构，它由以下方式初始化为空:

  struct rb_root mytree = RB_ROOT;

在一颗红黑树中搜索值
--------------------

为你的树写一个搜索函数是相当简单的：从树根开始，比较每个值，然后根据需要继续前往左边或
右边的分支。

示例::

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

在一颗红黑树中插入数据
----------------------

在树中插入数据的步骤包括：首先搜索插入新结点的位置，然后插入结点并对树再平衡
（"recoloring"）。

插入的搜索和上文的搜索不同，它要找到嫁接新结点的位置。新结点也需要一个指向它的父节点
的链接，以达到再平衡的目的。

示例::

  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 < 0)
  			new = &((*new)->rb_left);
  		else if (result > 0)
  			new = &((*new)->rb_right);
  		else
  			return FALSE;
  	}

  	/* Add new node and rebalance tree. */

Annotation

Implementation Notes