Nginx红黑树

Nginx 红黑树设计

用于比较的关键字使用无符号整数
红黑树是一个通用的数据结构，它的节点可以是包含基本红黑树节点的任意结构体（与前面的循环链表类似，与具体业务数据解耦）
Nginx 的核心模块（如定时器管理、文件缓存模块等）在需要快速检索、查找的场合下都使用了红黑树容器

Nginx 红黑树结构

root 指向树的根节点，如果红黑树为空，则指向哨兵节点 sentinel

insert 表示红黑树添加元素的函数指针，它决定在添加新节点时的行为究竟是替换还是新增

struct ngx_rbtree_s {
    ngx_rbtree_node_t     *root;
    ngx_rbtree_node_t     *sentinel;
    ngx_rbtree_insert_pt   insert;
};

ngx_rbtree_insert_pt 的类型如下

typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

Nginx 红黑树节点结构

key 是无符号整形的关键字，以此为基准构造二叉平衡树

color 表示当前节点的颜色，0 表示黑色，1 表示红色

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 红黑树的使用方法

将红黑树节点结构放到自定义结构体中
放置的位置任意，但一般放到第一个成员，这样就可以直接把自定义的结构体强制转换成 ngx_rbtree_node_t 类型
如果放置的位置不确定，可以通过 ngx_rbtree_data 根据成员在结构体中的偏移来获取自定义结构体的地址
```
typedef struct MyDataNode_s {
    int age;
    char name[20];
    ngx_rbtree_node_t node;
} MyDataNode_t;
```

ngx_rbtree_data 是一个宏，定义如下

#define ngx_rbtree_data(node, type, link)                                     \
    (type *) ((u_char *) (node) - offsetof(type, link))

Nginx 支持的添加节点方法

对于不同的结构体，很多场合下是允许不同的节点拥有相同的关键字的，因此在添加元素时需要考虑到这种情况
Nginx 将添加元素的方法抽象出 ngx_rbtree_insert_pt 函数指针可以很好地实现这一思想，用户也可以灵活地定义自己的行为
Nginx 默认支持 3 种添加节点的方法

ngx_rbtree_insert_value

执行意义：向红黑树添加数据节点，每个数据节点的关键字都是唯一的，不存在同一个关键字有多个节点的问题，如果先后添加同一个关键字的节点，后面的节点会替换前面插入的节点

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 ( ;; ) {

        p = (node->key < temp->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

执行意义：向红黑树添加数据节点，每个数据节点的关键字表示时间或者时间差

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

ngx_str_rbtree_insert_value

执行意义：向红黑树添加数据节点，每个数据节点的关键字可以不是唯一的，但它们是以字符串作为唯一的标识，存放在 ngx_str_node_t 结构体的 str 成员中

这部分的定义和实现分别放在 ngx_string.h 和 ngx_string.c 中

typedef struct {
    ngx_rbtree_node_t         node;
    ngx_str_t                 str;
} ngx_str_node_t;

插入方法如下，在关键字相同的情况下，比较字符串大小，大小相同比较内存序

void
ngx_str_rbtree_insert_value(ngx_rbtree_node_t *temp,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{
    ngx_str_node_t      *n, *t;
    ngx_rbtree_node_t  **p;

    for ( ;; ) {

        n = (ngx_str_node_t *) node;
        t = (ngx_str_node_t *) temp;

        if (node->key != temp->key) {

            p = (node->key < temp->key) ? &temp->left : &temp->right;

        } else if (n->str.len != t->str.len) {

            p = (n->str.len < t->str.len) ? &temp->left : &temp->right;

        } else {
            p = (ngx_memcmp(n->str.data, t->str.data, n->str.len) < 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);
}

Nginx 红黑树提供的方法

红黑树容器提供的方法

方法名	参数含义	执行意义
ngx_rbtree_init(tree, s, i)	tree 是红黑树容器的指针；s 是哨兵节点的指针；i 是 ngx_rbtree_insert_pt 类型的节点添加方法	初始化红黑树，包括初始化根节点、哨兵节点、ngx_rbtree_insert_pt 节点添加方法
void ngx_rbtree_insert(ngx_rbtree_t tree, ngx_rbtree_node_t node)	tree 是红黑树容器的指针；node 是需要添加到红黑树的节点指针	向红黑树中添加节点，该方法会通过旋转红黑树保持树的平衡
void ngx_rbtree_delete(ngx_rbtree_t tree, ngx_rbtree_node_t node)	tree 是红黑树容器的指针；node 是红黑树中需要删除的节点的指针	从红黑树中删除节点，该方法会通过旋转红黑树保持树的平衡

红黑树节点提供的方法

方法名	参数含义	执行意义
ngx_rbtree_node_t ngx_rbtree_min(ngx_rbtree_node_t node, ngx_rbtree_node_t *sentinel)	node 是红黑树中的 ngx_rbtree_node_t 类型的节点指针；sentinel 是这棵红黑树的哨兵节点	找到当前节点及其子树中的最小节点（按照 key 关键字）

Nginx 红黑树使用例子

注意使用 ngx_rbtree_min 方法时，需要保证红黑树中存在节点，不然会引发 Segmentation fault

判断红黑树为空，可以通过判断 root 是不是指向哨兵节点

#include <stdio.h>
#include <string.h>
#include "ngx_rbtree.h"

typedef struct MyDataNode_s {
    int age;
    char name[20];
    ngx_rbtree_node_t node;
} MyDataNode_t;


int main(int argc, char* argv[]) {
    ngx_rbtree_t rbtree;
    ngx_rbtree_node_t sentinel;

    MyDataNode_t rbTreeNode[5];
    rbTreeNode[0].age = 6;
    strcpy(rbTreeNode[0].name, "Tom");
    rbTreeNode[1].age = 3;
    strcpy(rbTreeNode[1].name, "Jack");
    rbTreeNode[2].age = 18;
    strcpy(rbTreeNode[2].name, "Luic");
    rbTreeNode[3].age = 100;
    strcpy(rbTreeNode[3].name, "Kouou");
    rbTreeNode[4].age = 18;
    strcpy(rbTreeNode[4].name, "Naki");

    ngx_rbtree_init(&rbtree, &sentinel, ngx_rbtree_insert_value);

    // ngx_rbtree_empty 是否为空可以判断 root 是否是哨兵 sentinel
    printf("root : %p, sentinel : %p\n", rbtree.root, &sentinel);

    // core dumped
    //ngx_rbtree_node_t *empty = ngx_rbtree_min(rbtree.root, &sentinel);
    //printf("empty %p sentinel %p\n", empty, &sentinel);

    for (int i = 0; i < 5; i++) {
        rbTreeNode[i].node.key = rbTreeNode[i].age;
        ngx_rbtree_insert(&rbtree, &rbTreeNode[i].node);
    }

    ngx_rbtree_node_t *min_node = ngx_rbtree_min(rbtree.root, &sentinel);
    MyDataNode_t *min_data = ngx_rbtree_data(min_node, MyDataNode_t, node);
    printf("min age is : %d name is: %s\n", min_data->age, min_data->name);

    ngx_uint_t lookupKey = 18;
    ngx_rbtree_node_t *tmpnode = rbtree.root;
    MyDataNode_t *lookupNode = NULL;
    while (tmpnode != &sentinel) {
        if (lookupKey != tmpnode->key) {
            tmpnode = (lookupKey < tmpnode->key) ? tmpnode->left : tmpnode->right;
            continue;
        }
        lookupNode = ngx_rbtree_data(tmpnode, MyDataNode_t, node);
        break;
    }

    if (lookupNode != NULL) {
        printf("age is : %d, name is : %s\n", lookupNode->age, lookupNode->name);
    }

    return 0;
}