概述
ngx_list 作为 Nginx 中的链表结构被广泛使用。不同于普通的链表设计，其设计是元素组成定长数组区块，定长数组区块再进一步组成链表。这种形式虽对内存稍有浪费，但却能大幅度减少内存分配与释放的频率。
相关源码文件：
这个数据结构依赖于 Nginx 的内存池设计，提供的接口非常简洁，只有创建、初始化、追加等三种操作（未提供迭代的接口，需要自行参照模板实现）。
如你所见，没有删除元素、释放空间等功能，所有内存都将随着内存池一起释放。虽然这样能大幅降低开发过程的心智负担，但在请求长时间未结束等场景下，容易造成「临时」的内存泄露。因此，Nginx 开发过程中，对象池往往是一个很不错的优化技巧。
数据结构
其最外层结构为 ngx_list_t，里边由一个个区块 ngx_list_part_t 构成，元素最终存储在区块的数组中。
这里涉及的所有结构体，包括区块中存放元素的数组，都由 pool 字段的内存池进行管理。
代码解析
ngx_list_create 创建新链表
// 创建新链表
ngx_list_t *
ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
ngx_list_t *list;
// 从内存池中创建新链表的 ngx_list_t 结构
list = ngx_palloc(pool, sizeof(ngx_list_t));
if (list == NULL) {
return NULL;
}
// 初始化内嵌在 ngx_list_t 结构里的首个区块，大小为 n * size
// 以及填入 ngx_list_t 的其他字段
if (ngx_list_init(list, pool, n, size) != NGX_OK) {
return NULL;
}
return list;
}ngx_list_init 初始化链表
// 初始化链表，ngx_list_create 会调用
static ngx_inline ngx_int_t
ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t size)
{
// 每个区块大小为 n * size
list->part.elts = ngx_palloc(pool, n * size);
if (list->part.elts == NULL) {
return NGX_ERROR;
}
list->part.nelts = 0; // 已使用（已拥有）的元素数量
list->part.next = NULL; // 下一区块，置空
list->last = &list->part;
list->size = size;
list->nalloc = n;
list->pool = pool;
return NGX_OK;
}ngx_list_push 追加元素
值得一提的是，这个函数将返回新元素的指针，至于这个元素里边的取值，需要拿到返回值后由调用者自行填充。
在追加过程中，会判断当前区块（last 字段）是否已满，如果已经满了，将自动从内存池中创建新的区块。新的区块大小与旧区块大小一致。因此，理论上链表能存储的元素数量并无上限。创建过程中传入的相关参数仅控制一个区块的大小，会影响内存使用率、分配区块次数而已，并不是链表体积上限。
// 在链表中追加一个新元素
// 这里有点反直觉，新元素不是作为参数传进来的，而是作为返回值移交出去，需要由调用者自行填充新元素的取值
// 给这个函数取个别名 ngx_alloc_in_list 可能更好理解
void *
ngx_list_push(ngx_list_t *l)
{
void *elt;
ngx_list_part_t *last;
last = l->last;
if (last->nelts == l->nalloc) {
/* the last part is full, allocate a new list part */
// 满了，建新区块
last = ngx_palloc(l->pool, sizeof(ngx_list_part_t));
if (last == NULL) {
return NULL;
}
// 新区块里的数组，注意大小是 nalloc * size
last->elts = ngx_palloc(l->pool, l->nalloc * l->size);
if (last->elts == NULL) {
return NULL;
}
last->nelts = 0; // 下边退出循环后做了自增，所以最后 nelts=1
last->next = NULL;
// 把之前的最后一个区块连上当前的新区块，并修改last区块字段
l->last->next = last;
l->last = last;
}
// 直接对 elts 指针做偏移，得到对应元素的地址
elt = (char *) last->elts + l->size * last->nelts;
last->nelts++;
return elt;
}遍历链表的代码模板
ngx_list 未提供遍历的函数，需要自行实现。但是在源码的注释中，为我们提供了一个很有用的代码模板可以参考：
/*
*
* ngx_list_t 典型的迭代过程
* the iteration through the list:
*
* 拿到链表中的首个区块以及区块中的数组
* part = &list.part;
* data = part->elts;
*
* for (i = 0 ;; i++) {
*
* if (i >= part->nelts) {
* 如果当前数组迭代完毕，而且没有更多区块了，退出迭代过程
* if (part->next == NULL) {
* break;
* }
*
* 否则，切到下一个区块，继续循环处理区块中的 nelts 个元素
* part = part->next;
* data = part->elts;
* i = 0;
* }
*
* 对每个元素的处理
* ... data[i] ...
*
* }
*/题图来自 Photo by Christina Rumpf on Unsplash