nginx高级数据类型(2) - 红黑树

2018-07-22 21:13:24

红黑树

是一种自平衡二叉树,不仅可以使用二分法快速查找,而且插入和删除操作的效率也很高。内部实现的复杂点就是在插入节点时会打破原来数的平衡,需要通过 "旋转" 来让数能继续平衡。

查找很简单,只是简单的通过 key 来决定是往前还是往后查找直到最终找到目标与 key 匹配的那个。

// 红黑树的key类型,无符号整数
// 通常我们使用这个key类型
typedef ngx_uint_t  ngx_rbtree_key_t;

// 红黑树的key类型,有符号整数
typedef ngx_int_t   ngx_rbtree_key_int_t;

// 红黑树节点
typedef struct ngx_rbtree_node_s  ngx_rbtree_node_t;

// 红黑树节点
// 通常需要以侵入式的方式使用,即作为结构体的一个成员
struct ngx_rbtree_node_s {
    // 节点的key,用于二分查找
    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;

    // 哨兵节点,通常就是root,用于标记查找结束
    ngx_rbtree_node_t     *sentinel;

    // 节点的插入方法
    // 常用的是ngx_rbtree_insert_value、ngx_rbtree_insert_timer_value
    ngx_rbtree_insert_pt   insert;
};

与 ngx_queue_t 一样,ngx_rbtree_node_t 也要作为结构体的一个成员,比如:

typedef struct{
    //红黑树节点,一般定义在第一位,方便类型转换
    ngx_rbtree_node_t node;
    ngx_str_t str;  //节点的其他信息
} ngx_str_node_t;

树结构定义

// 定义红黑树结构
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;

    // 哨兵节点,通常就是root,用于标记查找结束
    ngx_rbtree_node_t     *sentinel;

    // 节点的插入方法
    // 常用的是ngx_rbtree_insert_value、ngx_rbtree_insert_timer_value
    ngx_rbtree_insert_pt   insert;
};

ngx_rbtree_t 的内存布局图如下图:

// 向红黑树插入一个节点
// 插入后旋转红黑树,保持平衡
void ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);

// 在红黑树里删除一个节点
void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);

// 普通红黑树插入函数
void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,
    ngx_rbtree_node_t *sentinel);

// 定时器红黑树专用插入函数
void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,
    ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);

// 1.11.11新增,查找下一个节点,可以用来遍历红黑树
ngx_rbtree_node_t *ngx_rbtree_next(ngx_rbtree_t *tree,
    ngx_rbtree_node_t *node);

// 初始化红黑树,最初根节点就是哨兵节点
#define ngx_rbtree_init(tree, s, i)        \
    ngx_rbtree_sentinel_init(s);            \
    (tree)->root = s;                       \
    (tree)->sentinel = s;                   \
    (tree)->insert = i

// 哨兵节点颜色是黑的
#define ngx_rbtree_sentinel_init(node)  ngx_rbt_black(node)

// 简单的函数宏,检查颜色
#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)

红黑树的插入和查找操作都要自己实现,我们以 nginx 自带的字符串相关的为例阐述:

// 用于字符串红黑树的节点定义
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);

// 字符串红黑树专门的查找函数
// 注意hash值的类型是uint32_t,所以必须用murmurhash计算,不能用ngx_hash_key
ngx_str_node_t *ngx_str_rbtree_lookup(ngx_rbtree_t *rbtree, ngx_str_t *name,
    uint32_t hash);

我们先来看下使用例子():

注意:如果想自己测试下面的例子,必须搭建 nginx 测试环境,请参考 nginx编译成静态库

#include <ngx_core.h>

int main(){
    ngx_rbtree_t      tree;      //声明红黑树
    ngx_rbtree_node_t sentinel;  //声明哨兵节点
 
    //初始化
    ngx_rbtree_init(&tree, &sentinel, ngx_str_rbtree_insert_value);
 
    ngx_str_node_t strNode[5];
 
    //这里的 key 我们一般会取字符串的 hash 值
    //这里为了方便,直接使用随意数字代替
    ngx_str_set(&strNode[0].str, "freecls");
    strNode[0].node.key = ngx_crc32_long(strNode[0].str.data, strNode[0].str.len);  
 
    ngx_str_set(&strNode[1].str, "沧浪水");
    strNode[1].node.key = ngx_crc32_long(strNode[1].str.data, strNode[1].str.len);
 
    ngx_str_set(&strNode[2].str, "nginx");
    strNode[2].node.key = ngx_crc32_long(strNode[2].str.data, strNode[2].str.len);

    ngx_str_set(&strNode[3].str, "linux");
    strNode[3].node.key = ngx_crc32_long(strNode[3].str.data, strNode[3].str.len);

    //遍历加入到红黑树
    ngx_int_t i;
    for (i = 0; i < 5; ++i){
	ngx_rbtree_insert(&tree, &strNode[i].node);
    }
	
    uint32_t hash;
	
    ngx_str_node_t *tmpnode;
    //查找红黑树中最小节点
    tmpnode = (ngx_str_node_t *)ngx_rbtree_min(tree.root, &sentinel);
    printf("key:%d str:%s\n", tmpnode->node.key, tmpnode->str.data);

    ngx_str_t str_1 = ngx_string("freecls");
    hash = ngx_crc32_long(str_1.data, str_1.len);
	
    //超找特定的字符串
    tmpnode = (ngx_str_node_t *)ngx_str_rbtree_lookup(&tree, &str_1, hash);
    printf("hash:%d key:%d str:%s\n", hash, tmpnode->node.key, tmpnode->str.data);
}
[root@localhost c]# gcc main.c -lnginx -lpthread -lpcre -lssl -lcrypto \
                    -lz -lcrypt -ldl -I /usr/include/nginx/
[root@localhost c]# ./a.out 
key:112206672 str:沧浪水
hash:606045235 key:606045235 str:freecls

下面 nginx 帮我们实现了基于 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;
        
        //先比较 key,如果不同则根据key来决定
        if (node->key != temp->key) {
            p = (node->key < temp->key) ? &temp->left : &temp->right;

        //如果 key 相同,则根据字符串长度
        } else if (n->str.len != t->str.len) {

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

        //如果连字符串长度也相同,那么利用 mem_cmp 来比较大小
        } 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);
}

ngx_str_node_t *
ngx_str_rbtree_lookup(ngx_rbtree_t *rbtree, ngx_str_t *val, uint32_t hash)
{
    ngx_int_t           rc;
    ngx_str_node_t     *n;
    ngx_rbtree_node_t  *node, *sentinel;

    node = rbtree->root;
    sentinel = rbtree->sentinel;

    while (node != sentinel) {

        n = (ngx_str_node_t *) node;

        if (hash != node->key) {
            node = (hash < node->key) ? node->left : node->right;
            continue;
        }

        if (val->len != n->str.len) {
            node = (val->len < n->str.len) ? node->left : node->right;
            continue;
        }

        rc = ngx_memcmp(val->data, n->str.data, val->len);

        if (rc < 0) {
            node = node->left;
            continue;
        }

        if (rc > 0) {
            node = node->right;
            continue;
        }

        return n;
    }

    return NULL;
}


备注

1.nginx版本为 1.14.0。
2..原文地址http://www.freecls.com/a/2712/d5


©著作权归作者所有
收藏
推荐阅读
简介
天降大任于斯人也,必先苦其心志。