Nginx赤黒樹構造ngx_rbtree_t
概要
赤と黒の木の基礎知識については、前の文章で紹介しましたが、赤と黒の木をもっと詳しく知るためには、記事「データ構造-赤と黒の木」を参照してください.ここでは、単にNgixの中の赤と黒の木のソースコードを解析するだけです.
マホガニー構造
初期化操作
赤と黒の木の基礎知識については、前の文章で紹介しましたが、赤と黒の木をもっと詳しく知るためには、記事「データ構造-赤と黒の木」を参照してください.ここでは、単にNgixの中の赤と黒の木のソースコードを解析するだけです.
マホガニー構造
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;/* NIL */
ngx_rbtree_insert_pt insert; /* ， ， ；
* */
};
初期化操作
/* ，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)
/* */
/* a sentinel must be black */
#define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node)
/* ， */
/* tree ，
* s NIL ，
* i ，
*/
#define ngx_rbtree_init(tree, s, i) \
ngx_rbtree_sentinel_init(s); \
(tree)->root = s; \
(tree)->sentinel = s; \
(tree)->insert = i
/* */
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;/* temp node */
node->right = temp->left;/* node temp */
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;
}
/* */
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;
}
/* */
/* ：
* 1、 ；
* 2、 （ 5）；
* 3、 ， （ ）， ；
*/
void
ngx_rbtree_insert(ngx_thread_volatile ngx_rbtree_t *tree,
ngx_rbtree_node_t *node)
{
ngx_rbtree_node_t **root, *temp, *sentinel;
/* a binary tree insert */
root = (ngx_rbtree_node_t **) &tree->root;
sentinel = tree->sentinel;
/* ， ， ，
*
*/
if (*root == sentinel) {
node->parent = NULL;
node->left = sentinel;
node->right = sentinel;
ngx_rbt_black(node);
*root = node;
return;
}
/* ，
*
*/
tree->insert(*root, node, sentinel);
/* re-balance tree */
/* ， ，
* 4： ， ；
* 4， node node->parent ；
*/
while (node != *root && ngx_rbt_is_red(node->parent)) {
/* node */
if (node->parent == node->parent->parent->left) {
temp = node->parent->parent->right;/* temp node */
/* case1：node */
/* ，node ；
* ： node ， node ；
* ；
*/
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 {
/* case2：node node */
/* ， node ， case2 case3；
*/
if (node == node->parent->right) {
node = node->parent;
ngx_rbtree_left_rotate(root, sentinel, node);
}
/* case3：node node */
/* ， node ， ；
* ；
*/
ngx_rbt_black(node->parent);
ngx_rbt_red(node->parent->parent);
ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);
}
} else {/* node */
/* ，
*/
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;
for ( ;; ) {
/* node temp ， node temp */
p = (node->key < temp->key) ? &temp->left : &temp->right;
if (*p == sentinel) {
break;
}
temp = *p;
}
/* 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;
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);
}
/* */
void
ngx_rbtree_delete(ngx_thread_volatile 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 = (ngx_rbtree_node_t **) &tree->root;
sentinel = tree->sentinel;
/* temp ，temp node ；
* subst ；
*/
/* case1： node （ ）*/
if (node->left == sentinel) {
temp = node->right;
subst = node;
} else if (node->right == sentinel) {/* case2：node ， */
temp = node->left;
subst = node;
} else {/* case3：node ， */
subst = ngx_rbtree_min(node->right, sentinel);/* node */
if (subst->left != sentinel) {
temp = subst->left;
} else {
temp = subst->right;
}
}
/* subst ， temp subst */
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 subst */
red = ngx_rbt_is_red(subst);
/* temp subst */
if (subst == subst->parent->left) {
subst->parent->left = temp;
} else {
subst->parent->right = temp;
}
/* subst node */
if (subst == node) {
temp->parent = subst->parent;
} else {
if (subst->parent == node) {
temp->parent = subst;
} else {
temp->parent = subst->parent;
}
/* node */
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 */
/* temp ， temp */
while (temp != *root && ngx_rbt_is_black(temp)) {
/* temp */
if (temp == temp->parent->left) {
w = temp->parent->right;/* w temp */
/* case A：temp */
/* ：
* 1、 w temp ；
* 2、 temp ， ，temp w ， ；
* 3、 ，case A case B、case C case D；
*/
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;
}
/* case B：temp w ， w */
/* ：
* 1、 w ；
* 2、 temp temp ；
*/
if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
ngx_rbt_red(w);
temp = temp->parent;
} else {/* case C：temp ， w ， */
/* ：
* 1、 w ；
* 2、 w ；
* 3、 ，temp w ， case D；
*/
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;
}
/* case D：temp w ， w */
/* ：
* 1、 w temp ，temp ；
* 2、w ；
* 3、 temp ；
* 4、 root temp ；*/
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 {/* temp */
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);
}