首页 > 代码库 > Nginx 源码完全注释(10)ngx_radix_tree
Nginx 源码完全注释(10)ngx_radix_tree
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; // 空闲的节点由free开始连成一个链表,节点间通过right指针连接 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 = http://www.mamicode.com/NGX_RADIX_NO_VALUE;"comment" style="color: #888888;">// 如果指定的预分配节点数为 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 = http://www.mamicode.com/value;"keyword" style="font-weight: bold;">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 = http://www.mamicode.com/NGX_RADIX_NO_VALUE;"keyword" style="font-weight: bold;">if (key & bit) { node->right = next; } else { node->left = next; } bit >>= 1; node = next; } node->value = http://www.mamicode.com/value;"keyword" style="font-weight: bold;">return NGX_OK;}// 节点从 Radix 树中删除后,会放入到 free 链表中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 = http://www.mamicode.com/NGX_RADIX_NO_VALUE;"keyword" style="font-weight: bold;">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 = http://www.mamicode.com/NGX_RADIX_NO_VALUE;"comment" style="color: #888888;">// 从树根开始 // 理论上最多循环32次(key为32位),实际上查找到node为NULL,则表明上一轮循环中已经是叶子节点 while (node) { if (node->value != NGX_RADIX_NO_VALUE) { value = http://www.mamicode.com/node->value;"comment" style="color: #888888;">// 该位为 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;}
Nginx 源码完全注释(10)ngx_radix_tree
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。