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;//指向存储数据的指针
};

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;

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向基数树中插入树节点