Nginx 基本数据结构

这个数据是在文件里还是在内存里。ngx_list_tngx_list_t 顾名思义，看起来好像是一个 list 的数据结构。这样的说法，算对也不算对。因为它符合 list 类型数据结构的一些特点，比如可以添加元素，实现自增长，不会像数组类型的数据结构，受到初始设定的数组容量的限制，并且它跟我们常见的 list 型数据结构也是一样的，内部实现使用了一个链表。那么它跟我们常见的链表实现的 list 有什么不同呢？不同点就在于它的节点，它的节点不像我们常见的 list 的节点，只能存放一个元素，ngx_list_t 的节点实际上是一个固定大小的数组。在初始化的时候，我们需要设定元素需要占用的空间大小，每个节点数组的容量大小。在添加元素到这个 list 里面的时候，会在最尾部的节点里的数组上添加元素，如果这个节点的数组存满了，就再增加一个新的节点到这个 list 里面去。好了，看到这里，大家应该基本上明白这个 list 结构了吧？还不明白也没有关系，下面我们来具体看一下它的定义，这些定义和相关的操作函数定义在src/core/ngx_list.h|c文件中。 typedef struct { ngx_list_part_t *last; ngx_list_part_t part; size_t size; ngx_uint_t nalloc; ngx_pool_t *pool; } ngx_list_t;last: 指向该链表的最后一个节点。part: 该链表的首个存放具体元素的节点。size: 链表中存放的具体元素所需内存大小。nalloc: 每个节点所含的固定大小的数组的容量。pool: 该 list 使用的分配内存的 pool。好，我们在看一下每个节点的定义。 typedef struct ngx_list_part_s ngx_list_part_t; struct ngx_list_part_s { void *elts; ngx_uint_t nelts; ngx_list_part_t *next; };elts: 节点中存放具体元素的内存的开始地址。nelts: 节点中已有元素个数。这个值是不能大于链表头节点 ngx_list_t 类型中的 nalloc 字段的。next: 指向下一个节点。我们来看一下提供的一个操作的函数。 ngx_list_t *ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);该函数创建一个 ngx_list_t 类型的对象，并对该 list 的第一个节点分配存放元素的内存空间。pool: 分配内存使用的 pool。n: 每个节点（ngx_list_part_t）固定长度的数组的长度，即最多可以存放的元素个数。size: 每个元素所占用的内存大小。返回值: 成功返回指向创建的 ngx_list_t 对象的指针，失败返回 NULL。 void *ngx_list_push(ngx_list_t *list);该函数在给定的 list 的尾部追加一个元素，并返回指向新元素存放空间的指针。如果追加失败，则返回 NULL。 static ngx_inline ngx_int_t ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size);该函数是用于 ngx_list_t 类型的对象已经存在，但是其第一个节点存放元素的内存空间还未分配的情况下，可以调用此函数来给这个 list 的首节点来分配存放元素的内存空间。那么什么时候会出现已经有了 ngx_list_t 类型的对象，而其首节点存放元素的内存尚未分配的情况呢？那就是这个 ngx_list_t 类型的变量并不是通过调用 ngx_list_create 函数创建的。例如：如果某个结构体的一个成员变量是 ngx_list_t 类型的，那么当这个结构体类型的对象被创建出来的时候，这个成员变量也被创建出来了，但是它的首节点的存放元素的内存并未被分配。总之，如果这个 ngx_list_t 类型的变量，如果不是你通过调用函数 ngx_list_create 创建的，那么就必须调用此函数去初始化，否则，你往这个 list 里追加元素就可能引发不可预知的行为，亦或程序会崩溃!ngx_queue_tngx_queue_t 是 Nginx 中的双向链表，在 Nginx 源码目录src/core下面的ngx_queue.h|c里面。它的原型如下： typedef struct ngx_queue_s ngx_queue_t; struct ngx_queue_s { ngx_queue_t *prev; ngx_queue_t *next; };不同于教科书中将链表节点的数据成员声明在链表节点的结构体中，ngx_queue_t 只是声明了前向和后向指针。在使用的时候，我们首先需要定义一个哨兵节点(对于后续具体存放数据的节点，我们称之为数据节点)，比如： ngx_queue_t free;接下来需要进行初始化，通过宏 ngx_queue_init()来实现： ngx_queue_init(&free);ngx_queue_init()的宏定义如下： #define ngx_queue_init(q) \ (q)->prev = q; \ (q)->next = q可见初始的时候哨兵节点的 prev 和 next 都指向自己，因此其实是一个空链表。ngx_queue_empty()可以用来判断一个链表是否为空，其实现也很简单，就是： #define ngx_queue_empty(h) \ (h == (h)->prev)那么如何声明一个具有数据元素的链表节点呢？只要在相应的结构体中加上一个 ngx_queue_t 的成员就行了。比如 ngx_http_upstream_keepalive_module 中的 ngx_http_upstream_keepalive_cache_t： typedef struct { ngx_http_upstream_keepalive_srv_conf_t *conf; ngx_queue_t queue; ngx_connection_t *connection; socklen_t socklen; u_char sockaddr[NGX_SOCKADDRLEN]; } ngx_http_upstream_keepalive_cache_t;对于每一个这样的数据节点，可以通过 ngx_queue_insert_head()来添加到链表中，第一个参数是哨兵节点，第二个参数是数据节点，比如： ngx_http_upstream_keepalive_cache_t cache; ngx_queue_insert_head(&free, &cache.queue);相应的几个宏定义如下： #define ngx_queue_insert_head(h, x) \ (x)->next = (h)->next; \ (x)->next->prev = x; \ (x)->prev = h; \ (h)->next = x #define ngx_queue_insert_after ngx_queue_insert_head #define ngx_queue_insert_tail(h, x) \ (x)->prev = (h)->prev;