频道栏目
首页 > 程序开发 > 软件开发 > C++ > 正文
nginx 学习八 高级数据结构之基数树ngx_radix_tree_t
2014-10-02 11:04:28      个评论    来源:yanziguilai的专栏  
收藏   我要投稿

1 nginx的基数树简介

基数树是一种二叉查找树,它具备二叉查找树的所有优点:检索、插入、删除节点速度快,支持范围查找,支持遍历等。在nginx中仅geo模块使用了基数树。nginx的基数树使用ngx_radix_tree_t这个结构体表示的。ngx_radix_tree_t要求存储的每个节点都必须以32位整形作为区别任意两个节点的唯一标识。ngx_radix_tree_t基数树会负责分配每个节点占用的内存,基数树的每个节点中可存储的值只是一个指针,这个指针指向实际的数据。

节点结构ngx_radix_node_t:

typedef struct ngx_radix_node_s  ngx_radix_node_t;
//基数树的节点
struct ngx_radix_node_s {
    ngx_radix_node_t  *right;//右子指针
    ngx_radix_node_t  *left;//左子指针
    ngx_radix_node_t  *parent;//父节点指针
    uintptr_t          value;//指向存储数据的指针
};

基数树ngx_radix_tree_t:

typedef struct {
    ngx_radix_node_t  *root;//根节点
    ngx_pool_t        *pool;//内存池,负责分配内存
    ngx_radix_node_t  *free;//回收释放的节点,在添加新节点时,会首先查看free中是否有空闲可用的节点
    char              *start;//已分配内存中还未使用内存的首地址
    size_t             size;//已分配内存内中还未使用内存的大小
} ngx_radix_tree_t;
这里要注意free这个成员,它用来回收删除基数树上的节点,并这些节点连接成一个空闲节点链表,当要插入新节点时,首先查看这个链表是否有空闲节点,如果有就不申请节点空间,就从上面取下一个节点。

2ngingx基数的基本操作函数

ngx_radix_tree_t基本操作函数如下:

//创建基数树,preallocate是预分配节点的个数
ngx_radix_tree_t *ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate);

//根据key值和掩码向基数树中插入value,返回值可能是NGX_OK,NGX_ERROR, NGX_BUSY
ngx_int_t ngx_radix32tree_insert(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask, uintptr_t value);

//根据key值和掩码删除节点(value的值)
ngx_int_t ngx_radix32tree_delete(ngx_radix_tree_t *tree, uint32_t key, uint32_t mask);

//根据key值在基数树中查找返回value数据
uintptr_t ngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key);


2.1 ngx_radix_tree_create创建基数树

ngx_radix_tree_create会构造一个基数树。这个函数会根据第二个参数来判断是否预先创建一棵空的基数树:

1)如果preallocate为0,只申请ngx_radix_tree_t这个结构体,并返回

2)如果preallocate为-1,会根据ngx_pagesize/sizeof(ngx_radix_tree_t)的情况来构造一棵深度为7(或者8)的没有存储数据的基数树。

源代码:

ngx_radix_tree_t *
ngx_radix_tree_create(ngx_pool_t *pool, ngx_int_t preallocate)
{
    uint32_t           key, mask, inc;
    ngx_radix_tree_t  *tree;

    tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));//申请ngx_raidx_tree_t,这个tree是返回的指针
    if (tree == NULL) {
        return NULL;
    }
    //初始化ngx_radix_tree_t本身
    tree->pool = pool;
    tree->free = NULL;
    tree->start = NULL;
    tree->size = 0;

    tree->root = ngx_radix_alloc(tree);//申请一个基数节点
    if (tree->root == NULL) {
        return NULL;
    }
	//初始化root节点
    tree->root->right = NULL;
    tree->root->left = NULL;
    tree->root->parent = NULL;
    tree->root->value = NGX_RADIX_NO_VALUE;

	/*prealloc=0时,只创建结构体ngx_radix_tree_t,没有创建任何基数树节点*/
    if (preallocate == 0) {
        return tree;
    }
	/*prealloc=-1时,根据下面的情况创建基数树节点*/
    if (preallocate == -1) {
        switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) {

        /* amd64 */
        case 128:
            preallocate = 6;
            break;

        /* i386, sparc64 */
        case 256:
            preallocate = 7;
            break;

        /* sparc64 in 32-bit mode */
        default:
            preallocate = 8;
        }
    }

    mask = 0;
    inc = 0x80000000;
    //加入preallocate=7,最终建的基数树的节点总个数为2^(preallocate+1)-1,每一层个数为2^(7-preallocate)
    //循环如下:
    //preallocate  =      7         6        5         4         3         2        1
    //mask(最左8位)=      10000000  11000000 11100000  11110000  11111000  11111100 11111110
    //inc          =     10000000  01000000 00100000  00010000  00001000  00000100 00000010
    //增加节点个数    =      2         4        8         16        32        64       128
    while (preallocate--) {

        key = 0;
        mask >>= 1;
        mask |= 0x80000000;

        do {//根据inc的值添加节点
            if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
                != NGX_OK)
            {
                return NULL;
            }

            key += inc;//当preallocate=0时,是最后一层,构建的节点个数为2^preallocate

        } while (key);

        inc >>= 1;
    }

    return tree;
}

2.2 ngx_radix32tree_insert向基数树中插入树节点

nginx的基数树只处理key值为整形的情况,所以每个整形被转化为二进制数,并且树的最大深度是32层。根据二进制位数从左到右,如果当前位为1,就向右子树,否则向左子树插入。当然有时候我们不想构建深度为32的基数树,nginx为此提供了一个掩码mask,这个掩码中1的个数决定了基数树的深度。

代码:

ngx_int_t
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;//从最左位开始,判断key值

    node = tree->root;
    next = tree->root;

    while (bit & mask) {
        if (key & bit) {//等于1向右查找
            next = node->right;

        } else {//等于0向左查找
            next = node->left;
        }

        if (next == NULL) {
            break;
        }

        bit >>= 1;
        node = next;
    }

    if (next) {//如果next不为空
        if (node->value != NGX_RADIX_NO_VALUE) {//如果数据不为空
            return NGX_BUSY;//返回NGX_BUSY
        }

        node->value = value;//直接赋值
        return NGX_OK;
    }

    //如果next为中间节点,且为空,继续查找且申请路径上为空的节点
    //比如找key=1000111,在找到10001时next为空,那要就要申请三个节点分别存10001,100011,1000111,
    //1000111最后一个节点为key要插入的节点
    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;
}
2.3ngx_radix32tree_delete删除节点

删除一个节点和插入节点的操作几乎一样,不过要注意两点:

1)如果删除的是叶子节点,直接从基数树中删除,并把这个节点放入free链表

2)如果不是叶子节点,把value值置为NGX_RADIX_NO_VALUE

代码:

ngx_int_t
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;
    //根据key和掩码查找
    while (node && (bit & mask)) {
        if (key & bit) {
            node = node->right;

        } else {
            node = node->left;
        }

        bit >>= 1;
    }

    if (node == NULL) {//没有找到
        return NGX_ERROR;
    }

	//node不为叶节点直接把value置为空
    if (node->right || node->left) {
        if (node->value != NGX_RADIX_NO_VALUE) {//value不为空
            node->value = NGX_RADIX_NO_VALUE;//置空value
            return NGX_OK;
        }

        return NGX_ERROR;//value为空,返回error
    }

	//node为叶子节点,直接放到free区域
    for ( ;; ) {//删除叶子节点
        if (node->parent->right == node) {
            node->parent->right = NULL;//

        } else {
            node->parent->left = NULL;
        }

		//把node链入free链表
        node->right = tree->free;//放到free区域
        tree->free = node;//free指向node
        //假如删除node以后,父节点是叶子节点,就继续删除父节点,
		//一直到node不是叶子节点
        node = node->parent;

        if (node->right || node->left) {//node不为叶子节点
            break;
        }

        if (node->value != NGX_RADIX_NO_VALUE) {//node的value不为空
            break;
        }

        if (node->parent == NULL) {//node的parent为空
            break;
        }
    }

    return NGX_OK;
}

2.4ngx_radix32tree_find查找节点返回数据

这个函数是这四个函数中最简单的一个,就是根据key值查询,如果找到返回value值,没有找到返回NGX_RADIX_NO_VALUE。

代码:

uintptr_t
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) {
            node = node->right;

        } else {
            node = node->left;
        }

        bit >>= 1;//往下层查找
    }

    return value;
}

2.5ngx_radix_alloc申请节点函数

ngx_radix_alloc为基数树申请节点:

1)如果free链表不为空,直接从上面取下一个空闲节点

2)free链表为空,则申请一个节点

代码:

static void *
ngx_radix_alloc(ngx_radix_tree_t *tree)
{
    char  *p;

    if (tree->free) {//如果free中有可利用的空间节点
        p = (char *) tree->free;//指向第一个可利用的空间节点
        tree->free = tree->free->right;//修改free
        return p;
    }

    if (tree->size < sizeof(ngx_radix_node_t)) {//如果空闲内存大小不够分配一个节点就申请一页大小的内存
        tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);
        if (tree->start == NULL) {
            return NULL;
        }

        tree->size = ngx_pagesize;//修改空闲内存大小
    }

    //分配一个节点的空间
    p = tree->start;
    tree->start += sizeof(ngx_radix_node_t);
    tree->size -= sizeof(ngx_radix_node_t);

    return p;
}
3测试例子

下面是一个测试ngx_radix_tree_t的例子,在写完这个测试列子运行的时候,出现“核心错误(存储已转移)”,先按老办法调试--直接打印定位错误代码范围,找过了错误是在这个函数里面:ngx_radix32tree_create,尼码,源代码有错误,蒙了,不知到怎么调试下去,因为以前没在linux跟踪代码执行,没法了,直接搜资料学gdb调试程序,单步跟踪调试了整整一个晚上,发现在下面这句代码中出错:

tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);
gdb p ngx_pagesize 竟然是0,晕了很久找到这个ngx_pagesize的定义,是个全局变量没有初始化。

谁能知道系统中的全局变量在哪里用,在哪里初始化?

https://blog.csdn.net/xiaoliangsky/article/details/39695591

测试代码:

/********************************************************
author: smtl
date: 2014-10-01--4:50
*********************************************************/
#include 
#include 
#include 
#include 
#include 
#include 
#include 

////////////////////////////////////////////////////////////////////////////////////
//不加下面这两个定义编译会出错
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, ...)
{
}
////////////////////////////////////////////////////////////////////////////////////

//先序遍历radix_tree
void travel_radix_tree(ngx_radix_node_t *root);

int main()
{
	/*基数树节点的数据集:ngx_int_t类型,只是测试,实际上可以为任何类型*/
	ngx_int_t data[64];
	ngx_int_t i = 0;
	for (i = 0; i < 64; ++i)
	{
		data[i] = rand()%10000;
	}

	/*创建内存池对象*/
	ngx_pool_t* pool = ngx_create_pool(1024, NULL);
	if (pool == NULL)
	{
		printf("create pool failed!\n");
		exit(1);
	}
	
    //printf("xxxxx\n");
	////////////////////////////////////////////////////////////////////////////////
	//一定要初始化ngx_pagesize这个全局变量,调试了一个晚上
	//不初始化,会出现段错误(核心已转储),这也是全局变量的潜在危害:
	//你不知道你的程序中是否用到这个全局变量,如果用到,这个全局变量初始化了没有
	//在一些大的程序中,你根本无法快速知道这些,所以应尽量避免使用全局变量
    ngx_pagesize = getpagesize();
	printf("pagesize = %d\n", ngx_pagesize);
	////////////////////////////////////////////////////////////////////////////////

    /*创建基数树,prealloc=0时,只创建结构体ngx_radix_tree_t,没有创建任何基数树节点*/
	ngx_radix_tree_t *tree = ngx_radix_tree_create(pool, -1);
	//printf("xxxxxY\n");
	if (tree == NULL)
	{
		printf("crate radix tree failed!\n");
		exit(1);
	}
	
	
	/*插入data*/
	ngx_uint_t deep = 5;//树的最大深度为4
	ngx_uint_t mask = 0;
	ngx_uint_t inc  = 0x80000000;
	ngx_uint_t key  = 0;
	ngx_uint_t cunt = 0;//data数组的索引

	while (deep--)
	{
		key    = 0;
		mask >>= 1;
		mask  |= 0x80000000;
		do 
		{
			if (NGX_OK != ngx_radix32tree_insert(tree, key, mask, &data[cunt]))
			{
				printf("insert error\n");
				exit(1);
			}

			key += inc;

			++cunt;
			if (cunt > 63)
			{
				cunt = 63;
			}
		}while(key);

		inc >>= 1;
	}

	/*先序打印数据*/
	travel_radix_tree(tree->root);
	printf("\n");

	/*查找测试*/
	ngx_uint_t tkey  = 0x58000000;
	ngx_int_t* value = ngx_radix32tree_find(tree, 0x58000000);
	if (value != NGX_RADIX_NO_VALUE)
	{
		printf("find the value: %d with the key = %x\n", *value, tkey);
	}
	else
	{
		printf("not find the the value with the key = %x\n", tkey);
	}
    
	/*删除测试*/
	if (NGX_OK == ngx_radix32tree_delete(tree, tkey, mask))
	{
		printf("delete the the value with the key = %x is succeed\n", tkey);
	}
	else
	{
		printf("delete the the value with the key = %x is failed\n", tkey);
	}

    value = ngx_radix32tree_find(tree, 0x58000000);
	if (value != NGX_RADIX_NO_VALUE)
	{
		printf("find the value: %d with the key = %x\n", *value, tkey);
	}
	else
	{
		printf("not find the the value with the key = %x\n", tkey);
	}

	return 0;
}

void travel_radix_tree(ngx_radix_node_t *root)
{
	if (root->left != NULL)
	{
		travel_radix_tree(root->left);
	}
	
	if (root->value != NGX_RADIX_NO_VALUE)
	{
		ngx_int_t* value = root->value;
		printf("%d\n", *value);
	}

	if (root->right != NULL)
	{
		travel_radix_tree(root->right);
	}
}


work hard!


https://blog.csdn.net/xiaoliangsky/article/details/39695591

点击复制链接 与好友分享!回本站首页
相关TAG标签 数据结构 基数
上一篇:[思路题] spoj 11354 Amusing numbers
下一篇:Hnu 11187 Emoticons :-) (ac自动机+贪心)
相关文章
图文推荐
点击排行

关于我们 | 联系我们 | 广告服务 | 投资合作 | 版权申明 | 在线帮助 | 网站地图 | 作品发布 | Vip技术培训 | 举报中心

版权所有: 红黑联盟--致力于做实用的IT技术学习网站