首页 > 代码库 > nginx 学习八 高级数据结构之基数树ngx_radix_tree_t
nginx 学习八 高级数据结构之基数树ngx_radix_tree_t
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 = http://www.mamicode.com/NGX_RADIX_NO_VALUE;>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 = http://www.mamicode.com/value;//直接赋值>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 = http://www.mamicode.com/NGX_RADIX_NO_VALUE;//置空value>
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 = http://www.mamicode.com/NGX_RADIX_NO_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的定义，是个全局变量没有初始化。谁能知道系统中的全局变量在哪里用，在哪里初始化？
http://blog.csdn.net/xiaoliangsky/article/details/39695591
测试代码：
/*
* Copyright (C) Igor Sysoev
* Copyright (C) Nginx, Inc.
*/
#include <ngx_config.h>
#include <ngx_core.h>
static void *ngx_radix_alloc(ngx_radix_tree_t *tree);
/*
基数树有点类似字典树，树的最大深度为32层，因为key值是由二进制树，且插入的时候
从左到右检测每一位，如果为1向右孩子，为0向左孩子。
*/
/*
创建基数树
*/
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 = http://www.mamicode.com/NGX_RADIX_NO_VALUE;>
work hard!
http://blog.csdn.net/xiaoliangsky/article/details/39695591
nginx 学习八 高级数据结构之基数树ngx_radix_tree_t