nginx哪些地方用了红黑树
- 一、Nginx定义的红黑树
- 二、Nginx使用红黑树的地方
- 2.1、ngx_cycle
- 2.2、ngx_open_file_cache
- 总结
一、Nginx定义的红黑树
Nginx定义的红黑树在/src/core/ngx_rbtree.h和/src/core/ngx_rbtree.c。定义了红黑树节点、红黑树、红黑树插入函数等等。
其中/src/core/ngx_rbtree.h的代码如下：
#ifndef _NGX_RBTREE_H_INCLUDED_
#define _NGX_RBTREE_H_INCLUDED_#include <ngx_config.h>
#include <ngx_core.h>typedef ngx_uint_t ngx_rbtree_key_t;
typedef ngx_int_t ngx_rbtree_key_int_t;typedef struct ngx_rbtree_node_s ngx_rbtree_node_t;struct ngx_rbtree_node_s {ngx_rbtree_key_t key;ngx_rbtree_node_t *left;ngx_rbtree_node_t *right;ngx_rbtree_node_t *parent;u_char color;u_char data;
};typedef struct ngx_rbtree_s ngx_rbtree_t;typedef void (*ngx_rbtree_insert_pt) (ngx_rbtree_node_t *root,ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);struct ngx_rbtree_s {ngx_rbtree_node_t *root;ngx_rbtree_node_t *sentinel;ngx_rbtree_insert_pt insert;
};#define ngx_rbtree_init(tree, s, i) \ngx_rbtree_sentinel_init(s); \(tree)->root = s; \(tree)->sentinel = s; \(tree)->insert = ivoid ngx_rbtree_insert(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
void ngx_rbtree_delete(ngx_rbtree_t *tree, ngx_rbtree_node_t *node);
void ngx_rbtree_insert_value(ngx_rbtree_node_t *root, ngx_rbtree_node_t *node,ngx_rbtree_node_t *sentinel);
void ngx_rbtree_insert_timer_value(ngx_rbtree_node_t *root,ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel);
ngx_rbtree_node_t *ngx_rbtree_next(ngx_rbtree_t *tree,ngx_rbtree_node_t *node);#define ngx_rbt_red(node) ((node)->color = 1)
#define ngx_rbt_black(node) ((node)->color = 0)
#define ngx_rbt_is_red(node) ((node)->color)
#define ngx_rbt_is_black(node) (!ngx_rbt_is_red(node))
#define ngx_rbt_copy_color(n1, n2) (n1->color = n2->color)/* a sentinel must be black */#define ngx_rbtree_sentinel_init(node) ngx_rbt_black(node)static ngx_inline ngx_rbtree_node_t *
ngx_rbtree_min(ngx_rbtree_node_t *node, ngx_rbtree_node_t *sentinel)
{while (node->left != sentinel) {node = node->left;}return node;
}#endif /* _NGX_RBTREE_H_INCLUDED_ */二、Nginx使用红黑树的地方
Nginx使用红黑树的地方有：
- ngx_cycle。
- ngx_open_file_cache。
- ngx_resolver。
- ngx_event_openssl。
- ngx_event_timer。
- ngx_http_file_cache。
- ngx_http_geo_module。
- ngx_http_limit_conn_module。
- ngx_http_limit_req_module。
- ngx_stream_geo_module 。
- ngx_stream_limit_conn_module。
2.1、ngx_cycle
nginx的每个工作进程都有其自己的ngx_cycle。
在/src/core/ngx_cycle.h中定义的数据结构struct ngx_cycle_s引用了红黑树变量：
struct ngx_cycle_s{// ...ngx_rbtree_t config_dump_rbtree;ngx_rbtree_node_t config_dump_sentinel;// ...
}
（1）在nginx的main()函数中，会调用nginx_init_cycle函数初始化ngx_cycle_t。
/src/core/nginx.c
int ngx_cdecl
main(int argc, char *const *argv)
{// ...cycle = ngx_init_cycle(&init_cycle);if (cycle == NULL) {if (ngx_test_config) {ngx_log_stderr(0, "configuration file %s test failed",init_cycle.conf_file.data);}return 1;}// ...
}
（2）在nginx_init_cycle函数初始化红黑树。提供红黑树插入函数ngx_str_rbtree_insert_value。
/src/core/ngx_cycle.c
ngx_cycle_t *
ngx_init_cycle(ngx_cycle_t *old_cycle)
{
// ...ngx_rbtree_init(&cycle->config_dump_rbtree, &cycle->config_dump_sentinel,ngx_str_rbtree_insert_value);// ...
}
（3）在ngx_conf_add_dump函数轮询和插入红黑树节点。
/src/core/ngx_conf_file.c
static ngx_int_t
ngx_conf_add_dump(ngx_conf_t *cf, ngx_str_t *filename)
{off_t size;u_char *p;uint32_t hash;ngx_buf_t *buf;ngx_str_node_t *sn;ngx_conf_dump_t *cd;hash = ngx_crc32_long(filename->data, filename->len);sn = ngx_str_rbtree_lookup(&cf->cycle->config_dump_rbtree, filename, hash);if (sn) {cf->conf_file->dump = NULL;return NGX_OK;}p = ngx_pstrdup(cf->cycle->pool, filename);if (p == NULL) {return NGX_ERROR;}cd = ngx_array_push(&cf->cycle->config_dump);if (cd == NULL) {return NGX_ERROR;}size = ngx_file_size(&cf->conf_file->file.info);buf = ngx_create_temp_buf(cf->cycle->pool, (size_t) size);if (buf == NULL) {return NGX_ERROR;}cd->name.data = p;cd->name.len = filename->len;cd->buffer = buf;cf->conf_file->dump = buf;sn = ngx_palloc(cf->temp_pool, sizeof(ngx_str_node_t));if (sn == NULL) {return NGX_ERROR;}sn->node.key = hash;sn->str = cd->name;ngx_rbtree_insert(&cf->cycle->config_dump_rbtree, &sn->node);return NGX_OK;
}
（4）ngx_conf_add_dump被ngx_conf_parse调用
/src/core/ngx_conf_file.c
char *
ngx_conf_parse(ngx_conf_t *cf, ngx_str_t *filename)
{
// ...if (ngx_dump_config
#if (NGX_DEBUG)|| 1
#endif){if (ngx_conf_add_dump(cf, filename) != NGX_OK) {goto failed;}} else {cf->conf_file->dump = NULL;}
// ...
}
（5）红黑树使用流程图：
2.2、ngx_open_file_cache
ngx_open_file_cache_t是文件缓存，主要在ngx_http_log_module、ngx_http_core_module、ngx_stream_log_module几个模块中使用。
在/src/core/ngx_open_file_cache.h中定义的数据结构struct ngx_cycle_s引用了红黑树变量：
// ...
struct ngx_cached_open_file_s {ngx_rbtree_node_t node;ngx_queue_t queue;u_char *name;time_t created;time_t accessed;ngx_fd_t fd;ngx_file_uniq_t uniq;time_t mtime;off_t size;ngx_err_t err;uint32_t uses;#if (NGX_HAVE_OPENAT)size_t disable_symlinks_from;unsigned disable_symlinks:2;
#endifunsigned count:24;unsigned close:1;unsigned use_event:1;unsigned is_dir:1;unsigned is_file:1;unsigned is_link:1;unsigned is_exec:1;unsigned is_directio:1;ngx_event_t *event;
};typedef struct {ngx_rbtree_t rbtree;ngx_rbtree_node_t sentinel;ngx_queue_t expire_queue;ngx_uint_t current;ngx_uint_t max;time_t inactive;
} ngx_open_file_cache_t;// ...
（1）红黑树的初始化在ngx_open_file_cache_init函数中调用。
/src /core/ngx_open_file_cache.c
ngx_open_file_cache_t *
ngx_open_file_cache_init(ngx_pool_t *pool, ngx_uint_t max, time_t inactive)
{
// ...ngx_rbtree_init(&cache->rbtree, &cache->sentinel,ngx_open_file_cache_rbtree_insert_value);
// ...
}
（2）ngx_http_log_module模块的ngx_http_log_commands中注册了ngx_http_log_open_file_cache。ngx_http_log_open_file_cache会调用ngx_open_file_cache_init做初始化。
/src/http/modules/ngx_http_log_module.c
static char *
ngx_http_log_open_file_cache(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
{// ...llcf->open_file_cache = ngx_open_file_cache_init(cf->pool, max, inactive);if (llcf->open_file_cache) {llcf->open_file_cache_valid = valid;llcf->open_file_cache_min_uses = min_uses;return NGX_CONF_OK;}return NGX_CONF_ERROR;
}static ngx_command_t ngx_http_log_commands[] = {{ ngx_string("log_format"),NGX_HTTP_MAIN_CONF|NGX_CONF_2MORE,ngx_http_log_set_format,NGX_HTTP_MAIN_CONF_OFFSET,0,NULL },{ ngx_string("access_log"),NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_HTTP_LOC_CONF|NGX_HTTP_LIF_CONF|NGX_HTTP_LMT_CONF|NGX_CONF_1MORE,ngx_http_log_set_log,NGX_HTTP_LOC_CONF_OFFSET,0,NULL },{ ngx_string("open_log_file_cache"),NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_HTTP_LOC_CONF|NGX_CONF_TAKE1234,ngx_http_log_open_file_cache,NGX_HTTP_LOC_CONF_OFFSET,0,NULL },ngx_null_command
};ngx_module_t ngx_http_log_module = {NGX_MODULE_V1,&ngx_http_log_module_ctx, /* module context */ngx_http_log_commands, /* module directives */NGX_HTTP_MODULE, /* module type */NULL, /* init master */NULL, /* init module */NULL, /* init process */NULL, /* init thread */NULL, /* exit thread */NULL, /* exit process */NULL, /* exit master */NGX_MODULE_V1_PADDING
};（3）ngx_http_core_module模块的ngx_http_core_commands中注册了ngx_http_core_open_file_cache。ngx_http_core_open_file_cache会调用ngx_open_file_cache_init做初始化。
/src/http/modules/ngx_http_core_module.c
static char *
ngx_http_core_open_file_cache(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
{// ...clcf->open_file_cache = ngx_open_file_cache_init(cf->pool, max, inactive);if (clcf->open_file_cache) {return NGX_CONF_OK;}return NGX_CONF_ERROR;
}static ngx_command_t ngx_http_core_commands[] = {// ...{ ngx_string("open_file_cache"),NGX_HTTP_MAIN_CONF|NGX_HTTP_SRV_CONF|NGX_HTTP_LOC_CONF|NGX_CONF_TAKE12,ngx_http_core_open_file_cache,NGX_HTTP_LOC_CONF_OFFSET,offsetof(ngx_http_core_loc_conf_t, open_file_cache),NULL },// ...
}ngx_module_t ngx_http_core_module = {NGX_MODULE_V1,&ngx_http_core_module_ctx, /* module context */ngx_http_core_commands, /* module directives */NGX_HTTP_MODULE, /* module type */NULL, /* init master */NULL, /* init module */NULL, /* init process */NULL, /* init thread */NULL, /* exit thread */NULL, /* exit process */NULL, /* exit master */NGX_MODULE_V1_PADDING
};
（4）ngx_stream_log_module模块的ngx_stream_log_commands中注册了ngx_stream_log_open_file_cache。ngx_stream_log_open_file_cache会调用ngx_open_file_cache_init做初始化。
/src/http/modules/ngx_stream_log_module.c
static char *
ngx_stream_log_open_file_cache(ngx_conf_t *cf, ngx_command_t *cmd, void *conf)
{// ...lscf->open_file_cache = ngx_open_file_cache_init(cf->pool, max, inactive);if (lscf->open_file_cache) {lscf->open_file_cache_valid = valid;lscf->open_file_cache_min_uses = min_uses;return NGX_CONF_OK;}return NGX_CONF_ERROR;
}static ngx_command_t ngx_stream_log_commands[] = {{ ngx_string("log_format"),NGX_STREAM_MAIN_CONF|NGX_CONF_2MORE,ngx_stream_log_set_format,NGX_STREAM_MAIN_CONF_OFFSET,0,NULL },{ ngx_string("access_log"),NGX_STREAM_MAIN_CONF|NGX_STREAM_SRV_CONF|NGX_CONF_1MORE,ngx_stream_log_set_log,NGX_STREAM_SRV_CONF_OFFSET,0,NULL },{ ngx_string("open_log_file_cache"),NGX_STREAM_MAIN_CONF|NGX_STREAM_SRV_CONF|NGX_CONF_TAKE1234,ngx_stream_log_open_file_cache,NGX_STREAM_SRV_CONF_OFFSET,0,NULL },ngx_null_command
};static ngx_stream_module_t ngx_stream_log_module_ctx = {NULL, /* preconfiguration */ngx_stream_log_init, /* postconfiguration */ngx_stream_log_create_main_conf, /* create main configuration */NULL, /* init main configuration */ngx_stream_log_create_srv_conf, /* create server configuration */ngx_stream_log_merge_srv_conf /* merge server configuration */
};ngx_module_t ngx_stream_log_module = {NGX_MODULE_V1,&ngx_stream_log_module_ctx, /* module context */ngx_stream_log_commands, /* module directives */NGX_STREAM_MODULE, /* module type */NULL, /* init master */NULL, /* init module */NULL, /* init process */NULL, /* init thread */NULL, /* exit thread */NULL, /* exit process */NULL, /* exit master */NGX_MODULE_V1_PADDING
};（5）红黑树使用流程图：
总结
Nginx在很多地方使用了红黑树，nginx红黑树的使用基本是这样的流程：
- 定义红黑树变量。可以是在单独定义或者作为结构体的成员。
- 初始化红黑树，ngx_rbtree_init()，并提供插入value的函数，比如nginx内部实现的ngx_str_rbtree_insert_value() 。
- 初始化完成后，就可以在需要的地方调用ngx_rbtree_delete()、ngx_rbtree_insert()等函数。
