Nginx 高级数据结构 1
本文主要描述 Nginx 中的几种高级数据结构，参考《深入理解 Nginx》，结合源码，对这些数据结构进行一些解剖。文章中的代码可以在这里找到。
1. ngx_queue_t 双向链表
首先，ngx_queue_t 是不从内存池分配内存的，所以有关双向链表的所有内存都由程序员自己负责。ngx_queue_t 的定义如下（src/core/ngx_queue.h）
struct ngx_queue_s {
ngx_queue_t prev
ngx_queue_t next
}
这里定义的其实是两个指针，一个指向前一个节点，一个指向后一个节点，在需要使用双链表的地方加上一个 ngx_queue_t 变量即可。ngx_queue_t 有关的操作函数如下：
ngx_queue_empty(h) //h 为链表容器结构体 ngx_queue_t 的指针。 判断链表是否为空
ngx_queue_insert_head(h, x) //h 为链表容器结构体 ngx_queue_t 的指针，x 为插入元素结构体中 ngx_queue_t 成员的指针。将 x 插入到链表头部
ngx_queue_insert_tail(h, x) //h 为链表容器结构体 ngx_queue_t 的指针,x 为插入元素结构体中 ngx_queue_t 成员的指针。将 x 插入到链表尾部
ngx_queue_head(h) //h 为链表容器结构体 ngx_queue_t 的指针。返回链表容器 h 中的第一个元素的 ngx_queue_t 结构体指针
ngx_queue_last(h) //h 为链表容器结构体 ngx_queue_t 的指针。返回链表容器 h 中的最后一个元素的 ngx_queue_t 结构体指针
ngx_queue_sentinel(h) //h 为链表容器结构体 ngx_queue_t 的指针。返回链表结构体的指针
ngx_queue_remove(x) //x 为链表容器结构体 ngx_queue_t 的指针。从容器中移除 x 元素
ngx_queue_split(h, q, n)//h 为链表容器结构体 ngx_queue_t 的指针。该函数用于拆分链表，h 是链表容器，而 q 是链表 h 中的一个元素。这个方法将链表 h 以元素 q 为界拆分成两个链表 h 和 n
ngx_queue_add(h, n) //h 为链表容器结构体 ngx_queue_t 的指针， n为另一个链表容器结构体 ngx_queue_t 的指针。合并链表，将 n 链表添加到 h 链表的末尾
ngx_queue_middle(h) //h 为链表容器结构体 ngx_queue_t 的指针。返回链表中心元素，即第 N/2 + 1 个
ngx_queue_sort(h, cmpfunc) //h 为链表容器结构体 ngx_queue_t 的指针，cmpfunc 是比较回调函数。使用插入排序对链表进行排序
ngx_queue_next(q) //q 为链表中某一个元素结构体的 ngx_queue_t 成员的指针。返回 q 元素的下一个元素。
ngx_queue_prev(q) //q 为链表中某一个元素结构体的 ngx_queue_t 成员的指针。返回 q 元素的上一个元素。
ngx_queue_data(q, type, link) //q 为链表中某一个元素结构体的 ngx_queue_t 成员的指针，type 是链表元素的结构体类型名称，link 是上面这个结构体中 ngx_queue_t 类型的成员名字。返回 q 元素所属结构体的地址
ngx_queue_insert_after(q, x) //q 为链表中某一个元素结构体的 ngx_queue_t 成员的指针，x 为插入元素结构体中 ngx_queue_t 成员的指针。 在 nginx 1.2 中 这个函数是 ngx_queue_insert_head 的一个别名
下面这段代码能够大致说明这个数据结构的一些用法：
#include “ngx_queue.h”typedef struct{ //这个结构体实际上是我们真正使用的
char str
ngx_queue_t qEle //这里的 ngx_queue_t 变量是用来连接双向链表的
int num
}TestNodengx_int_t comp(const ngx_queue_t a, const ngx_queue_t b)
{//这个是排序用的比较函数
TestNode aNode = ngx_queue_data(a, TestNode, qEle); //首先得到 a 所在的结构体的指针
TestNode bNode = ngx_queue_data(b, TestNode, qEle);return aNode->num > bNode->num; //比较两个结构体中的 num 的大小
}int main(void)
{
int i = 0
TestNode node[5], tmp
ngx_queue_t queueContainer, *q
ngx_queue_init(queueContainer); //初始化双向链表for(; i<5 ++i)
{
node[i].num = i
}
ngx_queue_insert_tail(queueContainer, &node[0].qEle);
ngx_queue_insert_head(queueContainer, &node[1].qEle);
ngx_queue_insert_tail(queueContainer, &node[2].qEle);
ngx_queue_insert_after(queueContainer, &node[3].qEle);
ngx_queue_insert_tail(queueContainer, &node[4].qEle);
ngx_queue_sort(queueContainer, comp);for(q = ngx_queue_head(&queueContainer);
q != ngx_queue_sentinel(queueContainer);
q = ngx_queue_next(q))
{//遍历整个链表
tmp = ngx_queue_data(q, TestNode, qEle);
printf(“%d\t“, tmp->num);
}
printf(“\n“);
return 0
}
2. ngx_array_t 动态数组，类似于 STL 中的 vector。代码可以参考这里
//数组首地址
void elts
//数组中已经使用的元素个数
ngx_uint_t nelts
//每个数组元素占用的内存大小
size_t size
//当前数组中能够容纳的元素个数的总大小
ngx_uint_t nalloc
//内存池对象
ngx_pool_t pool
} ngx_array_t
几个操作函数如下：
ngx_array_init(ngx_array_t a, ngx_pool_t p, ngx_uint_t n, size_t size); //初始化 1 个已经存在的动态数组，并预分配 n 个大小为 size 的内存空间
ngx_array_destroy(ngx_array_t a) //销毁已分配的数组元素空间和 ngx_array_t 动态数组对象
ngx_array_push(ngx_array_t a) //向当前动态数组中添加 1 个元素，返回的是这个新添元素的地址。如果动态数组已经达到容量上限，会导致自动扩容
ngx_array_push_n(ngx_array_t a, ngx_uint_t n) //向当前动态数组中添加 n 个元素，返回的是新添加的这批元素中第一个元素的地址。如果动态数组已经达到容量上限，会导致自动扩容
其中有关扩容的情况，如果是添加 1 个元素的话，那么该内存池有空间就直接添加，没空间的话，会导致先扩成原来的2倍。如果是添加 n 个元素的话，如果内存池空间够的话，直接分配 n 个元素的内存，如果不够的话，分配 2X 的空间，其中 X = (n>=a->nalloc)?n:a->nalloc. 也就是 n 和动态数组中已分配空间的较大值
3. ngx_list_t 链表，定义如下：
typedef struct ngx_list_part_s ngx_list_part_t
//链表中每个元素的结构
struct ngx_list_part_s {
//指向数组的起始地址
void elts
//表示数组中已经使用了多少个元素。必须小于 链表中的 nalloc
ngx_uint_t nelts
//下一个元素的 ngx_list_pars_s 地址
ngx_list_part_t next
};
typedef struct {
//最后一个已使用元素的地址
ngx_list_part_t last
//第一个元素
ngx_list_part_t part
//每个元素的数组中存储的每个值的字节数不能超过 size
size_t size
//每个 ngx_list_part_s 数组的容量，即最多可存储多少个数据
ngx_uint_t nalloc
//内存池对象
ngx_pool_t pool
} ngx_list_t
针对 ngx_list_t 的几个操作函数为 ngx_list_init(ngx_list_t list, ngx_pool_t pool, ngx_uint_tn, size_t size),这个函数会对 list 对应的链表进行初始化。
创建链表函数 ngx_list_create(ngx_pool_t *pool, ngx_uint_tn, size_t size) 这个函数首先创建一个 ngx_list_t 的对象 list，然后调用 ngx_list_init 进行初始化
往链表中添加元素的函数 ngx_list_push(ngx_list_t *l) 这个函数会添加一个新元素，返回的是新元素的首地址。如果失败，返回 NULL。首先检测链表的最后一个数组是否已满，没满就直接返回，已满的话就分配新的数组，添加到链表中，然后返回相应的地址。
