Nginx源码分析-数据结构之红黑树rbTree
Nginx 中的红黑树结构 ngx_rbtree_t,定义在 ngx_rbtree.c/h 中,红黑树的详细情况可参见红黑树及其C语言实现。
数据结构定义
红黑树结点中包含结点的键值,结点的左右孩子,父结点,结点颜色数据及结点的数据值,红黑树结点定义:
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; //结点数据
};
nginx 中定义了红黑树的根结点,红黑树的哨兵结点,还有红黑树的插入函数,nginx 红黑树定义:
//红黑树结构
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; //红黑树插入函数
};
红黑树操作
红黑树基本操作:
#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) //将n2结点的颜色赋值给结点n1
/* a sentinel must be black */
//哨兵结点必须置为黑色
#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
//当把红黑树结点信息node放于结构体type类型中的link元素时,求结构体地址
#define ngx_rbtree_data(node, type, link) \
(type *) ((u_char *) (node) - offsetof(type, link))
红黑树调整需要的旋转操作:
左旋:
//红黑树左旋
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;
}
右旋:
//红黑树右旋
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;
}
红黑树插入:
//红黑树插入结点
void
ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
ngx_rbtree_node_t **root, *temp, *sentinel;
/* a binary tree insert */
root = &tree->root;
sentinel = tree->sentinel;
//当红黑根结点为哨兵结点时,说明红黑树没有结点,直接将要插入的结点当做根结点。
if (*root == sentinel) {
node->parent = NULL;
node->left = sentinel;
node->right = sentinel;
ngx_rbt_black(node);
*root = node;
return;
}
//调用不同的插入结点函数(ngx_rbtree_insert_value或ngx_rbtree_insert_timer_value)
tree->insert(*root, node, sentinel);
/* re-balance tree */
//插入结点后对红黑树进行调整
while (node != *root && ngx_rbt_is_red(node->parent)) {
if (node->parent == node->parent->parent->left) {
temp = node->parent->parent->right;
if (ngx_rbt_is_red(temp)) {
ngx_rbt_black(node->parent);
ngx_rbt_black(temp);
ngx_rbt_red(node->parent->parent);
node = node->parent->parent;
} else {
if (node == node->parent->right) {
node = node->parent;
ngx_rbtree_left_rotate(root, sentinel, node);
}
ngx_rbt_black(node->parent);
ngx_rbt_red(node->parent->parent);
ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
}
} else {
temp = node->parent->parent->left;
if (ngx_rbt_is_red(temp)) {
ngx_rbt_black(node->parent);
ngx_rbt_black(temp);
ngx_rbt_red(node->parent->parent);
node = node->parent->parent;
} else {
if (node == node->parent->left) {
node = node->parent;
ngx_rbtree_right_rotate(root, sentinel, node);
}
ngx_rbt_black(node->parent);
ngx_rbt_red(node->parent->parent);
ngx_rbtree_left_rotate(root, sentinel, node->parent->parent);
}
}
}
ngx_rbt_black(*root);
}
根据不同的数据类型选择不同的插入函数:
void
ngx_rbtree_insert_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel)
{
ngx_rbtree_node_t **p;
//通过比较key值查找要插入结点的位置
for ( ;; ) {
p = (node->key < temp->key) ? &temp->left : &temp->right;
if (*p == sentinel) {
break;
}
temp = *p;
}
//p为双指针,直接将其值赋为node,然后对node初始化,需要置为红色
*p = node;
node->parent = temp;
node->left = sentinel;
node->right = sentinel;
ngx_rbt_red(node);
}
void
ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *temp, ngx_rbtree_node_t *node,
ngx_rbtree_node_t *sentinel)
{
ngx_rbtree_node_t **p;
//timer类型key的查找
for ( ;; ) {
/*
* Timer values
* 1) are spread in small range, usually several minutes,
* 2) and overflow each 49 days, if milliseconds are stored in 32 bits.
* The comparison takes into account that overflow.
*/
/* node->key < temp->key */
p = ((ngx_rbtree_key_int_t) (node->key - temp->key) < 0)
? &temp->left : &temp->right;
if (*p == sentinel) {
break;
}
temp = *p;
}
*p = node;
node->parent = temp;
node->left = sentinel;
node->right = sentinel;
ngx_rbt_red(node);
}
红黑树删除结点:
//求node结点的前驱
static ngx_inline ngx_rbtree_node_t *
ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
while (node->left != sentinel) {
node = node->left;
}
return node;
}
//红黑树删除结点
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);
temp = subst->right;
}
//如果要删除的结点为根结点,直接将根结点赋为temp,即删除node后的替代结点
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;
}
ngx_rbt_copy_color(w, temp->parent);
ngx_rbt_black(temp->parent);
ngx_rbt_black(w->right);
ngx_rbtree_left_rotate(root, sentinel, temp->parent);
temp = *root;
}
} else {
w = temp->parent->left;
if (ngx_rbt_is_red(w)) {
ngx_rbt_black(w);
ngx_rbt_red(temp->parent);
ngx_rbtree_right_rotate(root, sentinel, temp->parent);
w = temp->parent->left;
}
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->left)) {
ngx_rbt_black(w->right);
ngx_rbt_red(w);
ngx_rbtree_left_rotate(root, sentinel, w);
w = temp->parent->left;
}
ngx_rbt_copy_color(w, temp->parent);
ngx_rbt_black(temp->parent);
ngx_rbt_black(w->left);
ngx_rbtree_right_rotate(root, sentinel, temp->parent);
temp = *root;
}
}
}
ngx_rbt_black(temp);
}
寻找红黑树下一结点:
//寻找红黑树下一个值结点,当结点有右结点时,找其右结点的前驱即可,当其没有右结点时,需要向根结点寻找,一直找到结点是其父结点的左子树时,此时父结点即是下一个结点
ngx_rbtree_node_t *
ngx_rbtree_next(ngx_rbtree_t *tree, ngx_rbtree_node_t *node)
{
ngx_rbtree_node_t *root, *sentinel, *parent;
sentinel = tree->sentinel;
//当有右结点时,寻找其右结点的前驱
if (node->right != sentinel) {
return ngx_rbtree_min(node->right, sentinel);
}
root = tree->root;
//没有右结点时,向根结点寻找,直到找到结点是父结点的左结点,则将父结点返回
for ( ;; ) {
parent = node->parent;
if (node == root) {
return NULL;
}
if (node == parent->left) {
return parent;
}
node = parent;
}
}
nginx源码基于nginx-1.22.0版本
- 版权声明: