Nginx源码解析 --红黑树
预读知识
红黑树是一种自平衡二叉树，不仅可以使用二分法快速查找，而且插入和删除操作的效率也很高，常用于构造关联数组（例如C++标准库里的set和 map)。
在Nginx里红黑树主要用在事件机制里的定时器，检查连接超时，此外还在reslover、cache里用于快速查找。
红黑树概要_编程界的谢菲尔德的博客-CSDN博客
- 节点不是黑色，就是红色（非黑即红）
- 根节点为黑色
- 叶节点为黑色（叶节点是指末梢的空节点
Nil或Null） - 一个节点为红色，则其两个子节点必须是黑色的（根到叶子的所有路径，不可能存在两个连续的红色节点）
- 每个节点到叶子节点的所有路径，都包含相同数目的黑色节点（相同的黑色高度）
基本数据结构
typedef ngx_uint_t ngx_rbtree_key_t;
typedef ngx_int_t ngx_rbtree_key_int_t;typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;struct ngx_rbtree_node_s {ngx_rbtree_key_t key;ngx_rbtree_node_t *left;ngx_rbtree_node_t *right;ngx_rbtree_node_t *parent;u_char color;u_char data;
};typedef struct ngx_rbtree_s ngx_rbtree_t;typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);struct ngx_rbtree_s {ngx_rbtree_node_t *root;ngx_rbtree_node_t *sentinel;ngx_rbtree_insert_pt insert;
};结构定义
1.
typedef ngx_uint_t ngx_rbtree_key_t; //无符号
typedef ngx_int_t ngx_rbtree_key_int_t; //有符号
2结点 //侵入容器
ngx_rbtree_key_t key; //红黑树的键 用于排序比较
ngx_rbtree_node_t *left; //左指针
ngx_rbtree_node_t *right; //右指针
ngx_rbtree_node_t *parent; //父结点
u_char color; // 1代表 0代表 黑色
u_char data; // 无意义
3 树
ngx_rbtree_node_t *root; //红黑树的根节点：
ngx_rbtree_node_t *sentinel; //红黑树的哨兵节点，用于简化实现，它总是黑色的；
ngx_rbtree_insert_pt insert; //节点的插入方法，允许对特殊节点定制特殊插入方法
4. 内存布局
2.操作函数
1.初始化（红为一 黑为0 同时也代表 正负）
#define ngx_rbt_red(node) ((node)->color = 1)
#define ngx_rbt_black(node) ((node)->color = 0)
#define ngx_rbt_is_red(node) ((node)->color)
#define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))
#define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color)#define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node)#define ngx_rbtree_init(tree, s, i) \ngx_rbtree_sentinel_init(s); \(tree)->root = s; \(tree)->sentinel = s; \(tree)->insert = i
2.辅助函数 （旋转函数）（个人建议 直接看红黑树概要_编程界的谢菲尔德的博客-CSDN博客）
1.左旋
static ngx_inline void
ngx_rbtree_left_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,ngx_rbtree_node_t *node)
{ngx_rbtree_node_t *temp;temp = node->right;node->right = temp->left;if (temp->left != sentinel) {temp->left->parent = node;}temp->parent = node->parent;if (node == *root) {*root = temp;} else if (node == node->parent->left) {node->parent->left = temp;} else {node->parent->right = temp;}temp->left = node;node->parent = temp;
}
2.右旋
static ngx_inline void
ngx_rbtree_right_rotate(ngx_rbtree_node_t **root, ngx_rbtree_node_t *sentinel,ngx_rbtree_node_t *node)
{ngx_rbtree_node_t *temp;temp = node->left;node->left = temp->right;if (temp->right != sentinel) {temp->right->parent = node;}temp->parent = node->parent;if (node == *root) {*root = temp;} else if (node == node->parent->right) {node->parent->right = temp;} else {node->parent->left = temp;}temp->right = node;node->parent = temp;
}
3.删除
void
ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{ngx_uint_t red;ngx_rbtree_node_t **root, *sentinel, *subst, *temp, *w;/* a binary tree delete */root = &tree->root;sentinel = tree->sentinel;if (node->left == sentinel) {temp = node->right;subst = node;} else if (node->right == sentinel) {temp = node->left;subst = node;} else {subst = ngx_rbtree_min(node->right, sentinel);if (subst->left != sentinel) {temp = subst->left;} else {temp = subst->right;}}
if (subst == *root) {*root = temp;ngx_rbt_black(temp);/* DEBUG stuff */node->left = NULL;node->right = NULL;node->parent = NULL;node->key = 0;return;}red = ngx_rbt_is_red(subst);if (subst == subst->parent->left) {subst->parent->left = temp;} else {subst->parent->right = temp;}if (subst == node) {temp->parent = subst->parent;} else {if (subst->parent == node) {temp->parent = subst;} else {temp->parent = subst->parent;}subst->left = node->left;subst->right = node->right;subst->parent = node->parent;ngx_rbt_copy_color(subst, node);if (node == *root) {*root = subst;} else {if (node == node->parent->left) {node->parent->left = subst;} else {node->parent->right = subst;}}if (subst->left != sentinel) {subst->left->parent = subst;}if (subst->right != sentinel) {subst->right->parent = subst;}}/* DEBUG stuff */node->left = NULL;node->right = NULL;
node->parent = NULL;node->key = 0;if (red) {return;}/* a delete fixup */while (temp != *root && ngx_rbt_is_black(temp)) {if (temp == temp->parent->left) {w = temp->parent->right;if (ngx_rbt_is_red(w)) {ngx_rbt_black(w);ngx_rbt_red(temp->parent);ngx_rbtree_left_rotate(root, sentinel, temp->parent);w = temp->parent->right;}if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {ngx_rbt_red(w);temp = temp->parent;} else {if (ngx_rbt_is_black(w->right)) {ngx_rbt_black(w->left);ngx_rbt_red(w);ngx_rbtree_right_rotate(root, sentinel, w);w = temp->parent->right;}
.....4.插入
1.首先包装一个整的
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
2.分类
2.1void ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel) //这个是一个数值插入
2.2 void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel) 定时器红黑树的专用插入函数，键值是毫秒值
2.3 (字符串头文件里)
void ngx str_rbtree_insert_value ngx_rbtree_node_t *temp ,
ngx_rbtree_node_t *node , ngx_rbtree_node_t *sentinel); //字符串红黑树的专用插入函数，键值是字符串的hash值