nginx数据结构之ngx_radix_tree

NGINX中ngx_radix_tree_t结构

基树一种不太常用的数据结构，是Linux文件系统的一种存储方式。
nginx 的数据结构基树 ngx_radix_tree 是一个较少使用的结构，只在http_module中使用了一次。
core/ngx_radix_tree.h文件中
基树
typedef struct {
    ngx_radix_node_t  *root;
    ngx_pool_t        *pool;
    ngx_radix_node_t  *free;
    char              *start;
    size_t             size;
} ngx_radix_tree_t;
基树节点：
struct ngx_radix_node_s {
    ngx_radix_node_t  *right;
    ngx_radix_node_t  *left;
    ngx_radix_node_t  *parent;
    uintptr_t          value;
};

 如果所示：树结构主要包含三个指针：
root：树的根结点
free：空闲的结点链表
start：空闲的内存块
每个使用中的节点使用parent, left, right指针相互连接，空闲的结点通过right指针连成一个链表。

nginx 的基树只有两个子节点，从二进制最高位开始，如果该位是0，则进入左子树，如果该位是0，则进入右子树。结尾的连续的0忽略掉。
例如
key=00100000 00000000 00000000 00000000 则节点=root->2 left>right
key=10100000 00000000 00000000 00000000 则节点=root->right->left->right
key=00100000 00000000 00000000 00000001 则节点=root->2 left->right->28left->right
key=10000000 00000000 00000000 00000000 则节点=root->right
注: root->2 left->right 表示 root->left->left->right 2表示连续两个->left

创建基树：
1。申请树结构
2。申请root节点
3。预申请一些节点，并加入树
代码见core/ngx_radix_tree.c
tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));   //申请树结构内存，如上图所示的最上一层
tree->root = ngx_radix_alloc(tree);                           //申请root节点结构
//Intel x86默认创建七层树结点
while (preallocate--)                            //预申请空间并创建若干层的树结点。
    ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
基树的内存管理
基树的内存管理主要通过三个指针实现，root,free和start
root表示当前树的根结点，是使用中的结点。
free则是表示当前树的空闲结点，当一个树结点被 删除时，nginx 并没有将内存归还系统或pool，而是加入自己的free链表中，以供下次使用。
start是从内存池中申请的空闲内存，当free链表中的结点用完时，则从start指向的内存块中取一块，然后向后移动start指针，将修改size的值。如果start指向的内存不也不足了，则向内存池pool申请一块内存。
代码如下：
core/ngx_radix_tree.c
ngx_radix_alloc(ngx_radix_tree_t *tree){
    if (tree->free) {//free链表中有空闲的节点，则从链表中取出
        p = (char *) tree->free;//取链表头的节点
        tree->free = tree->free->right;//修改链表头
        return p;//返回
    }  
    //如果free链表为空，则从start内存块中切一块出来
    if (tree->size < sizeof(ngx_radix_node_t)) {//如果start内存块太小，则从内存池中申请一块新的内存块给start
        tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);
        tree->size = ngx_pagesize;
    }  
    //从start内存块中切一块
    p = tree->start;
    tree->start += sizeof(ngx_radix_node_t);
    tree->size -= sizeof(ngx_radix_node_t);
    return p;
}
这里有个小问题，start块太小的时候，申请一个新的块，原来的一小块就丢掉了，成为一个小空洞。这个小空洞的释放留给tree的pool来管理，这也体现了 nginx 设计的的一个方法学：
内存的释放由内存池pool来负责，具体的数据结构则只管申请，既不释放，也不担心内存空洞的问题。

插入元素
nginx 的基树插入方法和一般的二叉树基本一致，需要注意的是分支的选择方式：
如果这一位是1，则进入右子树；否则进入左子树；直到剩下的字节全为0为止。
如00010000，只要走到第4层的1为止，其它的层不用走。

代码core/ngx_radix_tree.c 如下所示
ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
    uintptr_t value)
{
    uint32_t           bit;
    ngx_radix_node_t  *node, *next;
    bit = 0x80000000;//最高位
    node = tree->root;
    next = tree->root;
    while (bit & mask) {//1。定位key对应的节点
        if (key & bit) {//bit位是1，则进入右结点
            next = node->right;
        } else {//bit位是0，则进入左结点
            next = node->left;
        }
        if (next == NULL) {//下面的树结构尚未创建，则退出循环
            break;
        }
        bit >>= 1;//进入下一位
        node = next;
    }
    if (next) {//2。要插入的key已经存在于树结构中了，则只要设置值即可
        if (node->value != NGX_RADIX_NO_VALUE) {//如果这个值已经设置，表示这个key已经插入了，则插入失败
            return NGX_BUSY;
        }
        node->value = value;//设置该节点的值，完成插入。
        return NGX_OK;
    }
    //3。如果要插入的节点尚未创建，则创建相应的树结构
    while (bit & mask) {//
        next = ngx_radix_alloc(tree);//创建节点
        if (next == NULL) {
            return NGX_ERROR;
        }
        next->right = NULL;
        next->left = NULL;
        next->parent = node;
        next->value = NGX_RADIX_NO_VALUE;
        if (key & bit) {
            node->right = next;
        } else {
            node->left = next;
        }
        bit >>= 1;
        node = next;
    }
    node->value = value;//设置节点的值
    return NGX_OK;
}
这段代码非常复杂，因为分了三个步骤，首先在已经建立的节点中游动，然后再创建需要的子节点，并设置节点的值。假如原来的树只有6层，要插入一个新的节点0x 000 000 11，当走到第6层，即第6个0时，已经没有子节点了，所以退出循环，然后进入第二个while循环，创建下面两层相应的节点，最后设置节点的值。

删除元素
和二叉树的删除不同的是， nginx 的基树删除可能导致祖先同时被删除。
如果当前有两个元素，一个key=0101，一个key=01，则删除key=01的元素时，因为这个节点的右子树还有效，所以只要将 key=01 的节点的值设为NO_VALUE即可。
但是如果当前只有一个元素，且key=0001，则基树有4层节点，但是当这个元素被删除时，所有的节点都没有用了，nginx 就会将这个第四层的节点删除，同时不停的向上删除无用的父节点，直到所有的节点都被删除为止。
代码core/ngx_radix_tree.c 如下所示
ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask)
{
    uint32_t           bit;
    ngx_radix_node_t  *node;
    bit = 0x80000000;
    node = tree->root;
    while (node && (bit & mask)) {//定位到要删除的节点
        if (key & bit) {
            node = node->right;
        } else {
            node = node->left;
        }
        bit >>= 1;
    }
    if (node == NULL) {//如果要删除的节点不存在，则返回错误。
        return NGX_ERROR;
    }
    if (node->right || node->left) {//如果有子节点存在，则设置该节点为NO_VALUE
        if (node->value != NGX_RADIX_NO_VALUE) {
            node->value = NGX_RADIX_NO_VALUE;
            return NGX_OK;
        }
        return NGX_ERROR;
    }
    for ( ;; ) {//如果没有子节点，则递归删除空的父节点。
        if (node->parent->right == node) {//rm parent's son pointer
            node->parent->right = NULL;
        } else {
            node->parent->left = NULL;
        }
        node->right = tree->free;       //give it back to tree's free list
        tree->free = node;
        node = node->parent;            //up one step
        if (node->right || node->left) {
            break;
        }
        if (node->value != NGX_RADIX_NO_VALUE) {
            break;
        }
        if (node->parent == NULL) {
            break;
        }
    }
    return NGX_OK;
}

查找元素
和二叉树的查找相似，对于这个key从高到底的每个字节，如果是0则进入左节点，如果是1则进入右节点。
如 0011，则返回root->left->left->right->right的值。
和二叉树不同的是，nginx 的基树并不一定返回第32层节点的值，而是返回离根节点最近的祖先节点的值。
如 0011，不一定返回root->l->l->r->r的值，如果root->l->l->r->r无值，则取root->l->l->r的值，如果root->l->l->r无值，则取root->l->l的值，如果root->l->l也无值，则取root->l也无值，则取root的的值，如果root也无值，则返回NO_VALUE。
代码core/ngx_radix_tree.c 如下所示
ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key)
{
    uint32_t           bit;
    uintptr_t          value;
    ngx_radix_node_t  *node;
    bit = 0x80000000;
    value = NGX_RADIX_NO_VALUE;
    node = tree->root;
    while (node) {
        if (node->value != NGX_RADIX_NO_VALUE) {
            value = node->value;
        }
        if (key & bit) {//如果该bit=1，则进入右子树
            node = node->right;
        } else {//如果该bit=0，则进入左子树。
            node = node->left;
        }
        bit >>= 1;
    }
    return value;
}
问题：
nginx 的基树的find方法，返回的不一定是确切节点的值，而有可能是祖先节点的值，这是nginx期望的？还是个bug呢？
在 nginx 的源代码中查找调用 ngx_radix32tree_find 方法的代码，发现这个函数只出现在 http/modules/ngx_http_geo_module.c 中，用来查找网络号：
vv = (ngx_http_variable_value_t *)
               ngx_radix32tree_find(ctx->u.tree, ngx_http_geo_addr(r, ctx));
灰常像个bug

代码优化：
nginx 的基树插入操作的代码太过复杂，因为它将遍历己创建节点和未创建节点的过程分别放在两个while循环中，其实 nginx 的基树与一般的二叉树没什么区别。所以可以采取一般二叉树的插入方法，将两个while循环放到一起，这样代码的可读性会有很在的提升：
原来的代码44行，现在的代码35行，原来是while+if+while的结构，现在是一个while的结构，优化结果还是很令人欣慰的。
ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask,
    uintptr_t value)
{
    uint32_t           bit;
    ngx_radix_node_t  *node, *next;
    bit = 0x80000000;//highest bit
    node = tree->root;
    next = tree->root;
    while (bit & mask) {
        if (key & bit) {
            next = node->right;
        } else {
            next = node->left;
        }
        if (next == NULL) {//create if not present but need to be.
            next = ngx_radix_alloc(tree);
            if (next == NULL) {
                return NGX_ERROR;
            }
            next->right = NULL;
            next->left = NULL;
            next->parent = node;
            next->value = NGX_RADIX_NO_VALUE;
            if (key & bit) {
                node->right = next;
           } else {
                node->left = next;
            }
        }
        bit >>= 1;
        node = next;
    }
    if (node->value != NGX_RADIX_NO_VALUE) {//already used
        return NGX_BUSY;
    }
    node->value = value;
    return NGX_OK;
}

 

本文摘自：http://hankjin.blog.163.com/blog/static/337319372010912104443939/感谢作者的辛勤成果，同时也希望更多的人能把更多的思想分享给大家。