Nginx 源码完全剖析（10）ngx_radix_tree

Nginx 源码完全剖析（10）ngx_radix_tree

• 作者：钟超
• 博客：http://Blog.CSDN.net/Poechant
• 邮箱：zhongchao.ustc#gmail.com (#->@)
• 日期：2012年10月12日

  ngx_radix_tree.h

  // 未被使用的节点#define NGX_RADIX_NO_VALUE   (uintptr_t) -1typedef 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;    char              *start;    size_t             size;} ngx_radix_tree_t;

  ngx_radix_tree.c

  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;    // 为该树的结构体分配内存    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;    // 为根节点分配内存（实际上不一定有重新的内存分配操作，具体详见ngx_radix_alloc部分）    tree->root = ngx_radix_alloc(tree);    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;    // 如果指定的预分配节点数为 0，则直接返回这个树就好了    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)     */    // 下面这部分就很有意思了，你可以看上面的英文注释。简单说，一个 x bits 的值，对应其 Radix 树    // 有 x + 1 层，那么节点的个数就是 2^(x+1) -1 个（数据结构常识，你也可以很容易证明这个结论）。    if (preallocate == -1) {        // 根据 pagesize 大小，确定可以分配多少个 radix 树结构        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 为几，最终 mask 就有几个最高位为1，其他为0。整个循环过程中 mask 不断右移并在    // 最高位添置新 1。    while (preallocate--) {        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;}// mask 为掩码，用于截取 key 中的部分比特位，将其插入到 tree 数中，对应的值为 valuengx_int_tngx_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) {        if (key & bit) {            next = node->right;        } else {            next = node->left;        }        // 当前节点为叶子节点，停止循环查找        if (next == NULL) {            break;        }        bit >>= 1;        node = next;    }    // next 不为 NULL，是因 bit & mask 为 0 退出上面的 while 的    if (next) {        if (node->value != NGX_RADIX_NO_VALUE) {            return NGX_BUSY;        }        node->value = value;        return NGX_OK;    }    // next 为 NULL，从 tree 新分配一个节点    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;}ngx_int_tngx_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)) {        // key 该位为 1，表示接下来找右子树        if (key & bit) {            node = node->right;        // key 该位为 0，表示接下来找左子树        } else {            node = node->left;        }        bit >>= 1;    }    // 要删除的节点不存在    if (node == NULL) {        return NGX_ERROR;    }    // 要删除的节点还有子节点    if (node->right || node->left) {        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;        tree->free = node;        node = node->parent;        if (node->right || node->left) {            break;        }        if (node->value != NGX_RADIX_NO_VALUE) {            break;        }        // node 为根节点        if (node->parent == NULL) {            break;        }    }    return NGX_OK;}// 在 tree 树中查找 key 值，key 是一个无符号的32位整数，每一位对应从树根开始// 查找时选择左子树（0）还是右子树（1）uintptr_tngx_radix32tree_find(ngx_radix_tree_t *tree, uint32_t key){    uint32_t           bit;    uintptr_t          value;    ngx_radix_node_t  *node;    // 初始状态下最高位为1，用于后面的“与”操作，确定左右子树    bit = 0x80000000;    value = NGX_RADIX_NO_VALUE;    node = tree->root; // 从树根开始    // 理论上最多循环32次（key为32位），实际上查找到node为NULL，则表明上一轮循环中已经是叶子节点    while (node) {        if (node->value != NGX_RADIX_NO_VALUE) {            value = node->value;        }        // 该位为 1 则右子树        if (key & bit) {            node = node->right;        // 该位为 0 则左子树        } else {            node = node->left;        }        bit >>= 1;    }    // 返回找到的节点的值    return value;}static void *ngx_radix_alloc(ngx_radix_tree_t *tree){    char  *p;    // 创建Radix树时会调用，此时free为NULL，不会进入该if分支    // 插入时调用到这里，free 值非零，则返回 free    if (tree->free) {        p = (char *) tree->free;        tree->free = tree->free->right;        return p;    }    // 创建Radix树时会调用，此时tree->size为0，会进入该if分支    if (tree->size < sizeof(ngx_radix_node_t)) {        // 以ngx_pagesize大小内存对齐的方式，从内存池tree->pool中分配ngx_pagesize大小的内存给start        // ngx_pagesize 是在 src/os/unix/ngx_posix_init.c 和 src/os/win32/ngx_win32_init.c        // 的 ngx_os_init() 函数中初始化的。pagesize 的值与处理器架构有关。        tree->start = ngx_pmemalign(tree->pool, ngx_pagesize, ngx_pagesize);        if (tree->start == NULL) {            return NULL;        }        // tree->size 为刚才分配的内存大小        tree->size = ngx_pagesize;    }    // tree->start 加上 ngx_radix_node_t 将要占用的大小    // tree->size 减去 ngx_radix_node_t 将要占用的大小    p = tree->start;    tree->start += sizeof(ngx_radix_node_t);    tree->size -= sizeof(ngx_radix_node_t);    // 虽然返回值类型是 void*，但是调用处都会转为 ngx_radix_node_t    return p;}

  -

  转载请注明来自钟超的CSDN博客：Blog.CSDN.net/Poechant

  -