nginx データ構造 1 - ngx_int_t および ngx_rbtree_t

./src/core サブディレクトリにある 71 ソース ファイルに直面して、始めるのは少し難しいです。 main 関数を含む nginx.c ファイルを参照すると、nginx が自己カプセル化されたデータ構造を多く使用していることがわかりました。内容が分からないと、main 関数内の操作の意味を理解するのは困難です。これらはデータ構造の種類です。そこで私たちは、一見基本的なデータ構造を選択し、研究を開始しました。 nginxのすべてのデータ構造を整理するのは、ngx_core.hファイルです。最初に ngx_config.h が含まれており、ここで 3 つの型定義が見つかりました。 1、ngx_int_t、

ngx_uint_t

、ngx_flag_t nginx.cで見られる最初の見慣れないデータ型は

ngx_int_t

です。 nginx_config.h その定義が見つかりました。

typedef intptr_t        ngx_int_t;
typedef uintptr_t       ngx_uint_t;
typedef intptr_t        ngx_flag_t;

は手がかりをたどり、3 つのデータ型の定義を見つけました。学部

cの入門教育には

intptr_t/uintptr_tの紹介はありません。私はcのstdint.hヘッダーファイルでそれらの定義を見つけました。まず第一に、これらの2つのタイプはポインタータイプであるとコメントしています。文字通り、intptr_tおよび

uintptr_tは確かに整数ポインタータイプであり、署名されていない整数ポインターですtype ですが、人々は混乱しています。なぜ整数ポインタ型として integer を使用するのでしょうか?最初にそれを再生して、後ろのマクロを見てください。マシンは

64 ビットのワード長なので、intptr_t は long int、uintptr_t は unsigned long int です。 、私だけです このマシンは 64 コンパイラーです。 sizeof() を超えると、 8 バイト64 よりも小さくなります。ちょっと長い intptr_t は int、uintptr_t は unsigned int であり、表は 32 ビット コンパイラーであることを示していますint と unsigned は 4バイト、16ビットコンパイラは2バイトです。次に、intptr_t/uintptr_t は、プラットフォームの語長の変化に応じて変化する整数型である必要があります。理解したところ、「Linuxカーネルソースコードの詳細な分析」の説明では、システムカーネルがメモリを操作する際、メモリを大きな配列として扱い、ポインタは配列のインデックスであることがわかりました / 添字、カーネル プログラマは、この特殊な整数型を使用してメモリ アドレス値を受け入れ、ポインタを使用するよりも直感的にメモリを操作できるため、間違いを犯す可能性が低くなります。 nginxでは、プラットフォーム関連のint、unsigned int型変数を使用したいだけのようです。 2、ngx_rbtree_t2.1、赤黒木とは何ですか

競争でパドリングするプレーヤー、はい、赤のような有名なデータ構造黒い木は比較的敏感です。赤黒ツリーは、特殊な制約形式の下でバランスの取れた二分探索ツリーを実装したものです。データ構造の授業を学んだ生徒は、教科書に載っている最も初期の自己平衡二分木である

AVL

ツリーでは、ルート ノードからすべてのリーフ ノードまでの距離は、基本的に同じ (バランスの取れた) プロパティです。

赤黒の木は厳密なバランスを追求するのではなく、5

の制約によって基本的なバランスを実現します。

① ノードは赤または黒です。

② 根は黒です。

④赤いノードの子ノードはすべて黒です。 ⑤任意のノードからその葉ノードまでの単純なパス内の黒いノードの数は同じです。 AVLツリーのルートからリーフノードまでの最長距離と最短距離の比は2を超えません。赤黒ツリーの制約もこの特性を保証します (最長パスは赤と黒で、最短パスはすべて黒です。この場合、最長パスは最短パスのちょうど 2 倍の長さです)。 バランスの取れた二分探索ツリーの実装であるため、赤黒ツリーは当然内部的に順序付けされており、AVL ツリーと同様に O(log2n) 時間計算量の検索、挿入、削除をサポートします。

    相比AVL树，红黑可以保证在每次插入或删除操作之后的重平衡过程中，全树拓扑结构的更新仅涉及常数个结点。尽管最坏情况下需对O(log2n)个结点重染色，但就分摊意义（平均效率）而言，仅为O(1)个。但是因为没有严格约束树的平衡特性，红黑树的左右子树高度差比AVL树要大。

2.2、ngx_rbtree.h

    机会难得，我们就把nginx的源码作为素材来深入了解一下红黑树的实现。首先是结点的结构：

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;//<span style="font-family:宋体;">右</span>子结点指针
    ngx_rbtree_node_t     *parent;//父结点指针
    u_char                 color;//结点颜色
    u_char                 data;//结点数据
};

    然后是红黑树的结构定义：

typedef struct ngx_rbtree_s  ngx_rbtree_t;	//“_s”是结构体“_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;	//插入函数指针
};

    将函数指针变量作为结构体成员变量以达成可以把结构体当做类来使用（既有成员变量又有成员方法）的效果，这种手法在nginx的源码中相当普遍。关于函数，nginx还有一种更神奇的手段——宏：

#define ngx_rbtree_init(tree, s, i)                                         \
    ngx_rbtree_sentinel_init(s);                                               \
    (tree)->root = s;                                                                  \
    (tree)->sentinel = s;                                                            \
    (tree)->insert = i//这里insert函数指针的赋值实现了多态

    借助宏来达成内联函数的效果（函数实现如果比较简单，就干脆把实现过程整个搬到类中），令人费解的是，C不是没有内联关键字，甚至同一个头文件中就有一个内联函数的定义。研究内联函数之前，下面还有几个宏要看一看：

#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)

    nginx源码中的变量都很容易看懂以至于我们不怎么需要查资料或找注释。color置1染红置0染黑，color为1则结点为红色，不为红色的则为黑色，复制结点颜色即复制color值，哨兵结点一定要染成黑色。

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

    ngx_inline是一个宏，实际值就是关键字inline。这个内联函数非常好懂，目的看起来是寻找以任意结点为根结点的子树中结点值最小的结点。实现方法是找到红黑树子树最边缘的左子结点。那么我们有理由猜测，哨兵结点是空结点或边缘标识。

2.3、红黑树的结点插入

    接下来我们来深入ngx_rbtree.c看看nginx如何实现几个关键的红黑树方法。

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 = (ngx_rbtree_node_t **) &tree->root;//树根指针的指针赋给了root
    sentinel = tree->sentinel;//哨兵指针赋给了哨兵指针
 
    if (*root == sentinel) {//特判，如果根是哨兵，即树是空的
        node->parent = NULL;//新插入的结点变成了根
        node->left = sentinel;//新结点的左子结点是哨兵
        node->right = sentinel;//新结点的右子结点也是哨兵
        ngx_rbt_black(node);//新根染黑
        *root = node;//确认新结点为新根
 
        return;//插入结束
    }
 
    //树初始化时给了insert指针一个函数地址
    //查看前面的宏ngx_rbtree_init(tree, s, i)
    //发现只是把指定结点染黑，同时赋为根和哨兵，给insert指针指定一个函数
    //ngx_rbtree.c中有两个参数表符合的可选函数：插入值、插入计时器值
    //稍后来看两种插入分别如何实现又有什么区别
    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;//父结点成为新node
                    ngx_rbtree_left_rotate(root, sentinel, node);//node左旋
 
                }
 
                ngx_rbt_black(node->parent);//node的父结点染黑
                //node的父结点的父结点染红
                ngx_rbt_red(node->parent->parent);
                ngx_rbtree_right_rotate(root, sentinel, node->parent->parent);//node的父结点的父结点右旋
            }
 
        } 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);//根结点染黑
}

    然后是对应ngx_rbtree_insert_pt指针的基础的结点插入函数：

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 ( ;; ) {//无条件循环或者说死循环，等同于while(1)但节省了一个字符
 
        p = (node->key key) ? &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);
}

    ngx_rbtree_insert_timer_value函数跟ngx_rbtree_insert_value函数唯一区别就是判断大小时，采用了两个值相减，避免溢出。

    以上是插入结点涉及的函数，老实说我不太喜欢这么长的函数实现，换我自己写肯定分块了。分支操作太多，看代码逻辑已经乱了，我们需要画几个图。首先，如果树为空：

    如果树中只有一个根结点：

    如果C>A：

    如果C，C染红，B染黑A染红，A右旋。右旋函数如下：

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

    显然B将成为新的根，左C右A：

    如果B，会先做一次左旋再做一次右旋，其实除开染色过程，我觉得这跟AVL树的插入过程没有什么区别：

    其他的插入情景要么与以上几个对称，要么发生在树的其他子树中，实际过程完全一样。LL型右旋，RR型左旋，LR型先右旋后左旋，RL型先左旋后右旋。与AVL树不同的是，插入结点时红黑树左旋或右旋的判定条件明确为附近一两个结点的颜色，其他过程没有任何区别。

2.4、红黑树的结点删除

    据说红黑树和AVL树的区别主要体现在删除节点时，我们就来看一看。我刚说什么来着，删除结点的函数体更长了，足足165行，我决定分段研究，先看第一部分：

if (node->left == sentinel) {//如果左子结点是哨兵或左右子结点都是哨兵
    temp = node->right;//获得右子结点，后面让它接替node位置
    subst = node;//node赋给subst
 
} else if (node->right == sentinel) {//如果右子结点是哨兵
    temp = node->left;//获得左子结点，后面让它接替node位置
    subst = node;//node赋给subst
 
} else {//如果左右子结点都不是哨兵
    subst = ngx_rbtree_min(node->right, sentinel);//获得右子树中最小的结点
 
    if (subst->left != sentinel) {//如果右子树的最小结点的左子结点不是哨兵
        temp = subst->left;//获得右子树的最小结点的左子结点
    } else {//否则获得右子树最小结点的右子结点
        temp = subst->right;
    }//看起来subst将被从原位置删掉然后接替node的位置
}

    下面我们来看看temp和subst要干什么用：

if (subst == *root) {//如果subst是根
    *root = temp;//temp接替根
    ngx_rbt_black(temp);//染黑temp
 
    /* DEBUG stuff */
    node->left = NULL;//清空了待删结点
    node->right = NULL;
    node->parent = NULL;
    node->key = 0;
 
    return;
}
 
red = ngx_rbt_is_red(subst);//获得subst是否是红色
 
if (subst == subst->parent->left) {//如果subst是左子结点
    subst->parent->left = temp;//把接替结点挂到subst位置
 
} else {//如果subst是右子结点
    subst->parent->right = temp;//把接替结点挂到subst位置
}

    下一段：

if (subst == node) {//如果subst是待删结点
    temp->parent = subst->parent;//接替结点直接接替，删除完成
 
} else {//如果subst不是待删结点
     if (subst->parent == node) {//如果subst的父结点就是待删结点
        temp->parent = subst;//接替结点挂在subst上
     } else {//如果待删结点比subst的父结点更高
        temp->parent = subst->parent;//把接替结点挂在subst的父结点上
    }
    //subst接替待删结点node的位置，复制待删结点跟周围结点的关系
    subst->left = node->left;
    subst->right = node->right;
    subst->parent = node->parent;
    ngx_rbt_copy_color(subst, node);//复制颜色
 
    if (node == *root) {//如果待删结点是根
        *root = subst;//subst接替根
    } else {//如果待删结点不是根，subst接替它
        if (node == node->parent->left) {
            node->parent->left = subst;
        } else {
            node->parent->right = subst;
        }
    }
 
    if (subst->left != sentinel) {//如果subst左子结点不是哨兵
        subst->left->parent = subst;//subst的左子结点放弃node，挂上来
    }
 
    if (subst->right != sentinel) {//如果subst右子结点不是哨兵
        subst->right->parent = subst;//subst右子结点放弃node，挂上来
    }
}
//清空待删结点node
/* DEBUG stuff */
node->left = NULL;
node->right = NULL;
node->parent = NULL;
node->key = 0;
//如果subst是红色，红黑树约束依然被遵守，删除工作就可以结束了
if (red) {
    return;
}

    看起来结点的删除过程已经顺利完成了，但是如果subst是黑色，我们需要修复红黑树的约束。下面这一段代码的主角是接替subst位置的temp结点：

//当subst的接替结点不是根且为黑色，循环
while (temp != *root && ngx_rbt_is_black(temp)) {
        if (temp == temp->parent->left) {//如果temp是左子结点
            w = temp->parent->right;//获得其右兄弟
 
            if (ngx_rbt_is_red(w)) {//如果temp的右兄弟是红色
                ngx_rbt_black(w);//染黑temp的右兄弟
                ngx_rbt_red(temp->parent);//染红temp的父结点
                //temp的父结点左旋
                ngx_rbtree_left_rotate(root, sentinel, temp->parent);
                w = temp->parent->right;//获得temp的新右兄弟
            }
            //如果temp右兄弟的左右子结点都是黑的
            if (ngx_rbt_is_black(w->left) && ngx_rbt_is_black(w->right)) {
                ngx_rbt_red(w);//染红temp的右兄弟
                temp = temp->parent;//获得temp的父结点为新temp
 
            } else {//如果temp右兄弟的子结点不全为黑
                if (ngx_rbt_is_black(w->right)) {//如果其右子结点是黑色
                    ngx_rbt_black(w->left);//染黑左子结点
                    ngx_rbt_red(w);//染红temp的右兄弟
                    ngx_rbtree_right_rotate(root, sentinel, w);//右兄弟右旋
                    w = temp->parent->right;//获得temp的新右兄弟
                }
                //temp右兄弟复制temp父结点颜色
                ngx_rbt_copy_color(w, temp->parent);
                ngx_rbt_black(temp->parent);//染黑temp父结点
                ngx_rbt_black(w->right);//染黑temp右兄弟的右子结点
                //temp父结点左旋
                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);//染黑当前temp

    跟插入结点时一样乱，我们梳理一下。

    首先忽略红黑树的约束进行删除：

    ①如果删除的是一个叶结点，即没有后继或后继全为哨兵的结点，直接删除即可；

    ②如果只有一个后继，让其替换待删除结点即可；

    ③如果有两个后继，需要从树的边缘选择一个结点，有两种等价的选择，待删结点左子树的最大结点和右子树的最小结点，nginx选择的是后者，以这个结点的键与值（key与value/data）替换待删结点的键与值，然后删除这个替身。

    不论是①、②情景中的待删结点还是③情景中替身，在源码中都是subst。下面要围绕着它来进行讨论。

    以上是不考虑红黑树平衡性的纯拓扑结构变动。下面要考虑是否调整树的拓扑结构使树重新平衡，是否调整结点的颜色使树重新符合红黑树的约束条件。我们知道红黑树有一条关键约束是任意结点到其子树中叶结点的简单路径中黑色结点数相同。那么如果subst是一个红色结点，我们不需要对红黑树做任何调整，它仍是一棵红黑树；如果subst是黑色的，所有经过subst的简单路径上都会少一个黑色结点数，所以需要进行调整。

    下面来根据不同情景分情况讨论，因为二叉树的情景左右颠倒时调整方式也可以左右颠倒，我们只讨论subst是左子结点的情况。设刚接替subst的temp为X，X的新右兄弟为W。从经过简化的源码来看，关于结点颜色的变化很令人费解，我们不妨先来看一看：

    ①W为红色：将W染黑，将X与W的父结点X->parent染红，X->parent左旋，W重设为X的新右兄弟，然后转入情景①、②或③；

    ②W为黑色，W两个后继都是黑色：将W染红，X重设为X->parent；

    ③W为黑色，W右子结点为黑色：将W左子结点染黑，将W染红，W右旋，W重设为X的新右兄弟，然后将X->parent的颜色赋给W，将X->parent染黑，X->parent左旋，根赋给temp；

    ④W为黑色，W右子结点为红色：将W左子结点染黑，将W染红，W右旋，W重设为X的新右兄弟，然后将X->parent的颜色赋给W，将X->parent染黑，将W右子结点染黑，X->parent左旋，根赋给temp。

    最后还要把temp染黑。我们可以看到情景①中进行了一次左旋，情景②只进行了染色，情景③、④都进行了一次右旋和一次左旋。情景①处理结束时一定还要转入别的情景，情景②、③、④的出现则标志着本次调整的结束。那么，红黑树删除结点后的调整过程中，依情景①循环出现的次数，调整过程中旋转的最多见的次数将是1次、2次、3次，再往上次数越多越罕见（依情景①循环出现的次数），最多旋转次数将可能到达树高即log2n次。生产环境中，删除结点后平均每次调整中旋转的次数就像分析源码之前提到的，将是常数规模的。

次に、赤黒ツリーのデータ構造をより詳細かつ直感的に理解できるように、段階的な改修バージョンで赤黒ツリーを書き直す予定です。書き換える前に、nginx の赤黒ツリーのすべてのリーフ ノードがセンチネルであることを理解する必要があります。これにより、赤黒ツリーを調整するときに赤黒ツリーの最適化が実現されます。全黒のサブノードのレイヤーを追加することで、実際に赤黒ツリー内の値を持つサブツリーに赤いノードが表示されるようになります。証明したわけではありませんが、この一定のスケールによりノード削除時の回転数が増加するとともに、新規ノード挿入時の調整確率も促進され（赤いノードの下に新規ノードが挿入される確率が増加します）、また、ノードの挿入確率も増加します。赤いノードの下にある新しいノードは回転数です。回転により、赤黒ツリーのサブツリーの高さが圧縮され、クエリの効率が向上します。

赤黒ツリーをシンプルから洗練に書き直す過程で、nginx を使用して赤黒ツリーを最小から最大まで最適化するか、独自の最適化を追加することを検討します。

著作権声明: この記事はブロガーによるオリジナルの記事であり、ブロガーの許可なく複製することはできません。

上記は、nginx のデータ構造 1 である ngx_int_t と ngx_rbtree_t を、関連する内容も含めて紹介しています。PHP チュートリアルに興味のある友人に役立つことを願っています。