5.ngx_rbtree_t

红黑树特性

1.节点是红色或黑色。
2.根节点是黑色。
3.每个叶子节点都是黑色的空节点（NIL节点）。
4.每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)
5.从任一节点到其每个叶子节点的所有路径都包含相同数目的黑色节点。

ngx 红黑树结构

/* 红黑树节点结构 */
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;
};

/* 红黑树结构 */
struct ngx_rbtree_s {
    ngx_rbtree_node_t     *root;        /* 指向树的根节点 */
    ngx_rbtree_node_t     *sentinel;    /* 指向树的叶子节点NIL */
    ngx_rbtree_insert_pt   insert;      /* 添加元素节点的函数指针，解决具有相同键值问题，在初始化时需要指定*/
};

实例

#include <stdio.h>
#include <ngx_config.h>
#include <ngx_conf_file.h>
#include <nginx.h>
#include <ngx_core.h>
#include <ngx_string.h>
#include <ngx_palloc.h>
#include <ngx_rbtree.h>

volatile ngx_cycle_t *ngx_cycle;

void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err,
    const char *fmt, ...)
{
    //...
}

void ngx_rbtree_dump(ngx_rbtree_node_t *root, ngx_rbtree_node_t *sentinel);


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

    ngx_rbtree_init(&rbtree, &sentinel, ngx_str_rbtree_insert_value);
    //printf("root color: %d\n", rbtree.root->color);

    ngx_str_node_t sn[10];
    ngx_str_set(&sn[0].str, "a");
    ngx_str_set(&sn[1].str, "b");
    ngx_str_set(&sn[2].str, "c");
    ngx_str_set(&sn[3].str, "d");
    ngx_str_set(&sn[4].str, "e");
    ngx_str_set(&sn[5].str, "f");
    ngx_str_set(&sn[6].str, "g");
    ngx_str_set(&sn[7].str, "h");
    ngx_str_set(&sn[8].str, "i");
    ngx_str_set(&sn[9].str, "j");

    ngx_int_t i;
    for (i = 0; i < 10; i++) {
        sn[i].node.key = i;
        ngx_rbtree_insert(&rbtree, &sn[i].node);
    }

    ngx_str_t word = ngx_string("a");
    ngx_int_t hash = 0;

    ngx_str_node_t *str_node = ngx_str_rbtree_lookup(&rbtree, &word, hash);
    if (str_node != NULL) {
        printf("\x1b[31mfind\x1b[0m: name: %s, key: %lu, color: %d\n", 
            str_node->str.data, str_node->node.key, str_node->node.color);
    } else {
        printf("not find\n");
    }

    ngx_rbtree_dump(rbtree.root, &sentinel);

    /*
    while (rbtree.root != &sentinel) {
        ngx_rbtree_node_t *min_node = ngx_rbtree_min(rbtree.root, &sentinel);
        ngx_str_node_t *str_node = (ngx_str_node_t *)min_node;
        printf("name: %s, key: %ld, color: %d\n", 
            str_node->str.data, min_node->key, min_node->color);
        ngx_rbtree_delete(&rbtree, min_node);
    }
    */

    return 0;
}

void
ngx_rbtree_dump(ngx_rbtree_node_t *root, ngx_rbtree_node_t *sentinel)
{
    if (root != sentinel) {
        ngx_str_node_t *str_node = (ngx_str_node_t *)root;
        printf("str: %s, key: %ld, color: %d\n",
            str_node->str.data, str_node->node.key, str_node->node.color);
    } else {
        printf("nil\n");
        return;
    }

    ngx_rbtree_dump(root->left, sentinel);
    ngx_rbtree_dump(root->right, sentinel);

    return;
}

执行

gcc -c -O -pipe -O -W -Wall -Wpointer-arith -Wno-unused-parameter -Wunused-function -Wunused-variable -Wunused-value -Werror -g 
    -I ../../objs/ 
    -I ../os/unix/ 
    -I../core/ 
    -I /usr/local/opt/pcre/include/ 
    -I../event/ 
    -I../os/ 
    ./t_ngx_rbtree.c -o ./t_ngx_rbtree.o

gcc -o ./t_ngx_rbtree ./t_ngx_rbtree.o 
    ../../objs/src/core/ngx_string.o       
    ../../objs/src/os/unix/ngx_alloc.o 
    ../../objs/src/core/ngx_palloc.o
../../objs/src/core/ngx_rbtree.o

结果

find: name: a, key: 0, color: 0
str: d, key: 3, color: 0
str: b, key: 1, color: 0
str: a, key: 0, color: 0
nil
nil
str: c, key: 2, color: 0
nil
nil
str: f, key: 5, color: 0
str: e, key: 4, color: 0
nil
nil
str: h, key: 7, color: 1
str: g, key: 6, color: 0
nil
nil
str: i, key: 8, color: 0
nil
str: j, key: 9, color: 1
nil
nil