nginx 基础结构 ngx_radix_tree_t

ngx_radix_tree_t 是nginx里面的基树很少使用

它的学习点是：
typedef struct {
    ngx_radix_node_t  *root; //表示当前树的根结点，是使用中的结点。
    ngx_pool_t        *pool;
    ngx_radix_node_t  *free; //则是表示当前树的空闲结点，当一个树结点被 删除时，nginx 并没有将内存归还系统或pool，而是加入自己的free链表中，以供下次使用。
    char              *start;//是从内存池中申请的空闲内存，当free链表中的结点用完时，则从start指向的内存块中取一块，然后向后移动start指针，将修改size的值。如果start指向的内存不也不足了，则向内存池pool申请一块内存。
    size_t             size;
} ngx_radix_tree_t;

其他内部实现：

/*
 * Copyright (C) Igor Sysoev
 * Copyright (C) Nginx, Inc.
 */


#include
#include


static void *ngx_radix_alloc(ngx_radix_tree_t *tree);

//创建基树
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;

    //    申请root节点
    tree = ngx_palloc(pool, sizeof(ngx_radix_tree_t));//申请树结构内存
    if (tree == NULL) {
        return NULL;
    }

    tree->pool = pool;
    tree->free = NULL;
    tree->start = NULL;
    tree->size = 0;

    tree->root = ngx_radix_alloc(tree); //申请root节点结构
    if (tree->root == NULL) {
        return NULL;
    }

//    预申请一些节点，并加入树
    tree->root->right = NULL;
    tree->root->left = NULL;
    tree->root->parent = NULL;
    tree->root->value = NGX_RADIX_NO_VALUE;

    if (preallocate == 0) {
        return tree;
    }

    /*
     * Preallocation of first nodes : 0, 1, 00, 01, 10, 11, 000, 001, etc.
     * increases TLB hits even if for first lookup iterations.
     * On 32-bit platforms the 7 preallocated bits takes continuous 4K,
     * 8 - 8K, 9 - 16K, etc.  On 64-bit platforms the 6 preallocated bits
     * takes continuous 4K, 7 - 8K, 8 - 16K, etc.  There is no sense to
     * to preallocate more than one page, because further preallocation
     * distributes the only bit per page.  Instead, a random insertion
     * may distribute several bits per page.
     *
     * Thus, by default we preallocate maximum
     *     6 bits on amd64 (64-bit platform and 4K pages)
     *     7 bits on i386 (32-bit platform and 4K pages)
     *     7 bits on sparc64 in 64-bit mode (8K pages)
     *     8 bits on sparc64 in 32-bit mode (8K pages)
     */

    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;
    //预申请空间并创建若干层的树结点。
    while (preallocate--) {//Intel x86默认创建七层树结点

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

        do {
            if (ngx_radix32tree_insert(tree, key, mask, NGX_RADIX_NO_VALUE)
                != NGX_OK)
            {
                return NULL;
            }

            key += inc;

        } while (key);

        inc >>= 1;
    }

    return tree;
}

//基树插入方法和一般的二叉树基本一致，需要注意的是分支的选择方式：
//如果这一位是1，则进入右子树；否则进入左子树；直到剩下的字节全为0为止。
//如00010000，只要走到第4层的1为止，其它的层不用走。
//这段代码非常复杂，因为分了三个步骤，首先在已经建立的节点中游动，然后再创建需要的子节点，并设置节点的值。
//假如原来的树只有6层，要插入一个新的节点 0x 000 000 11，当走到第6层，即第6个0时，已经没有子节点了，所以退出循环，
//然后进入第二个while循环，创建下面两层相应的节点，最后设置节点的值。
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;

    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;
}

//和二叉树的删除不同的是， nginx 的基树删除可能导致祖先同时被删除。
//如果当前有两个元素，一个key=0101，一个key=01，则删除key=01的元素时，因为这个节点的右子树还有效，
//所以只要将 key=01 的节点的值设为NO_VALUE即可。
//但是如果当前只有一个元素，且key=0001，则基树有4层节点，但是当这个元素被删除时，所有的节点都没有用了，
//nginx 就会将这个第四层的节点删除，同时不停的向上删除无用的父节点，直到所有的节点都被删除为止。
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;

    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) {
            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。
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) {//如果该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;
//}

//这里有个小问题，start块太小的时候，申请一个新的块，原来的一小块就丢掉了，成为一个小空洞。这个小空洞的释放留给tree的pool来管理，这也体现了 nginx 设计的的一个方法学：
//内存的释放由内存池pool来负责，具体的数据结构则只管申请，既不释放，也不担心内存空洞的问题。
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;
        return p;
    }

    //如果free链表为空，则从start内存块中切一块出来
    if (tree->size < sizeof(ngx_radix_node_t)) {
        tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);//如果start内存块太小，则从内存池中申请一块新的内存块给start
        if (tree->start == NULL) {
            return NULL;
        }

        tree->size = ngx_pagesize;
    }
    //从start内存块中切一块
    p = tree->start;
    tree->start += sizeof(ngx_radix_node_t);
    tree->size -= sizeof(ngx_radix_node_t);

    return p;
}