Nginx 源码完全剖析(10)ngx_radix_tree
ngx_radix_tree.h
#define NGX_RADIX_NO_VALUE (uintptr_t) -1
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开始连成一个链表,节点间通过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;
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;
if (preallocate == 0) {
return tree;
}
if (preallocate == -1) {
switch (ngx_pagesize / sizeof(ngx_radix_tree_t)) {
case 128:
preallocate = 6;
break;
case 256:
preallocate = 7;
break;
default:
preallocate = 8;
}
}
mask = 0;
inc = 0x80000000;
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;
}
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) {
if (key & bit) {
next = node->right;
} else {
next = node->left;
}
if (next == NULL) {
break;
}
bit >>= 1;
node = next;
}
if (next) {
if (node->value != NGX_RADIX_NO_VALUE) {
return NGX_BUSY;
}
node->value = value;
return NGX_OK;
}
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;
}
// 节点从 Radix 树中删除后,会放入到 free 链表中
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) {
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;
}
if (node->parent == NULL) {
break;
}
}
return NGX_OK;
}
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) {
node = node->right;
} else {
node = node->left;
}
bit >>= 1;
}
return value;
}
static void *
ngx_radix_alloc(ngx_radix_tree_t *tree)
{
char *p;
if (tree->free) {
p = (char *) tree->free;
tree->free = tree->free->right;
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;
}
-
转载请注明来自钟超的CSDN博客:Blog.CSDN.net/Poechant
-
分享到:
相关推荐
ngx_cache_purge 是 nginx 模块,此模块可以清理 nginx 的 FastCGI、proxy、 SCGI 和 uWSGI 的缓存。配置指令(相同位置语法)fastcgi_cache_purgesyntax: fastcgi_cache_purge on|off|<method> [from all|<ip> [.....
lua-upstream-nginx-module, Nginx C 模块将Lua向ngx_lua公开,用于 Nginx upstreams 电子邮件名称ngx_http_lua_upstream - Nginx MODULE,用于向 Nginx upstreams公开Lua到 ngx_lua目录NAME状态概要说明函数get_...
备用nginx代理模块
二. ngx_http_limit_conn_module指令解释limit_conn_zone语法: limit_conn_zone $variable zo
ngx_http_dav_ext_module.so centos7 nginx 1.18 可以作为模块加载
ngx_sqlite 是嵌入 sqlite 数据库的 nginx 模块。通过强大的nginx server,可以使用http协议访问sqlite数据库。环境- sqlite 3- nginx-1.6.3 安装```sh $ git clone https://github.com/rryqszq4/ngx_sqlite.git...
nginx1.20.2
通过把nginx slab的精简,把需要的头文件单独整理出来,增加了main方法,可以单独运行,代码包含了大量的中文注释,方便了了解和学习slab的运行机制 int main(int argc, char **argv) { ngx_log_t log; ngx_shm_t ...
ngx_devel_kit-0.3.0
nginx lua module for windows 详细请访问 http://blog.csdn.net/ngwsx/
ngx_realtime_request是nginx用来统计虚拟主机流量的模块, 首先和大家说下这个模块是基于域名的,将会记录这个域名的请求量、发送字节、返回http状态码的数量,特性如下: 1、基于域名记录 2、记录请求数据量 3、...
用于nginx的http正向代理https使用的模块
ngx_req_status用来展示nginx请求状态信息,类似于apache的status,nginx自带的模块只能显示连接数等等信息,我们并不能知道到底有哪些请求、以及各url域名所消耗的带宽是多少。ngx_req_status提供了这些功能. 1、按...
ngx_python 是为 nginx 嵌入 python 脚本的模块。环境- python 2.7.*- nginx-1.6.3 安装```sh git clone https://github.com/rryqszq4/ngx_python.git wget 'http://nginx.org/download/nginx-1.6.3.tar.gz' ...
Nginx:一致性哈希(第三方模块ngx_http_consistent_hash):ngx_http_consistent_hash-master.zip
包含yamdi-1.9.tar.gz nginx_mod_h264_streaming-2.2.7.tar.gz nginx-1.8.1
ngx_http_enhance_mp4_module 该模块是原始 nginx mp4 模块(附带在 nginx 源代码中)的增强版本。 请注意,这是我自己的项目,除了需要ngx_http_mp4_module所有源代码外,它与 nginx 的源代码没有任何关系。 该模块...
增加了ngx_http_proxy_connect_module模块的,已经编译好的windows exe文件。 可以正向代理https请求。来源地址:https://github.com/dyq94310/nginx-build-msys2/releases 使用方法,放到从官网下的nginx windows...
ngx_security_headers 此NGINX模块以正确的方式(c)添加了安全标头,并删除了不安全的标头。概要http { security_headers on; ...} 运行curl -IL https://example.com/将产生添加的安全标头: ...