注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

云水居

云在青山水在天,人在江湖不得闲

 
 
 

日志

 
 

nginx的数据结构(4) 基树ngx_radix_tree  

2010-10-12 23:36:35|  分类: Network |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
基树一种不太常用的数据结构,是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;
};
nginx的数据结构(4) 基树ngx_radix_tree - hankjin - 云水居
 如果所示:树结构主要包含三个指针:
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;
}
  评论这张
 
阅读(2194)| 评论(4)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017