3.2.3　ngx_list_t数据结构

ngx_list_t是Nginx封装的链表容器，它在Nginx中使用得很频繁，例如HTTP的头部就是用ngx_list_t来存储的。当然，C语言封装的链表没有C++或Java等面向对象语言那么容易理解。先看一下ngx_list_t相关成员的定义：

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；

}；

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；

ngx_list_t描述整个链表，而ngx_list_part_t只描述链表的一个元素。这里要注意的是，ngx_list_t不是一个单纯的链表，为了便于理解，我们姑且称它为存储数组的链表，什么意思呢？抽象地说，就是每个链表元素ngx_list_part_t又是一个数组，拥有连续的内存，它既依赖于ngx_list_t里的size和nalloc来表示数组的容量，同时又依靠每个ngx_list_part_t成员中的nelts来表示数组当前已使用了多少容量。因此，ngx_list_t是一个链表容器，而链表中的元素又是一个数组。事实上，ngx_list_part_t数组中的元素才是用户想要存储的东西，ngx_list_t链表能够容纳的元素数量由ngx_list_part_t数组元素的个数与每个数组所能容纳的元素相乘得到。

这样设计有什么好处呢？

❑链表中存储的元素是灵活的，它可以是任何一种数据结构。

❑链表元素需要占用的内存由ngx_list_t管理，它已经通过数组分配好了。

❑小块的内存使用链表访问效率是低下的，使用数组通过偏移量来直接访问内存则要高效得多。

下面详述每个成员的意义。

（1）ngx_list_t

❑part：链表的首个数组元素。

❑last：指向链表的最后一个数组元素。

❑size：前面讲过，链表中的每个ngx_list_part_t元素都是一个数组。因为数组存储的是某种类型的数据结构，且ngx_list_t是非常灵活的数据结构，所以它不会限制存储什么样的数据，只是通过size限制每一个数组元素的占用的空间大小，也就是用户要存储的一个数据所占用的字节数必须小于或等于size。

❑nalloc：链表的数组元素一旦分配后是不可更改的。nalloc表示每个ngx_list_part_t数组的容量，即最多可存储多少个数据。

❑pool：链表中管理内存分配的内存池对象。用户要存放的数据占用的内存都是由pool分配的，下文中会详细介绍。

（2）ngx_list_part_t

❑elts：指向数组的起始地址。

❑nelts：表示数组中已经使用了多少个元素。当然，nelts必须小于ngx_list_t结构体中的nalloc。

❑next：下一个链表元素ngx_list_part_t的地址。

事实上，ngx_list_t中的所有数据都是由ngx_pool_t类型的pool内存池分配的，它们通常都是连续的内存（在由一个pool内存池分配的情况下）。下面以图3-2为例来看一下ngx_list_t的内存分布情况。

图　3-2　ngx_list_t的内存分布

图3-2中是由3个ngx_list_part_t数组元素组成的ngx_list_t链表可能拥有的一种内存分布结构，读者可以从这种较为常见的内存分布中看到ngx_list_t链表的用法。这里，pool内存池为其分配了连续的内存，最前端内存存储的是ngx_list_t结构中的成员，紧接着是第一个ngx_list_part_t结构占用的内存，然后是ngx_list_part_t结构指向的数组，它们一共占用size*nalloc字节，表示数组中拥有nalloc个大小为size的元素。其后面是第2个ngx_list_part_t结构以及它所指向的数组，依此类推。

对于链表，Nginx提供的接口包括：ngx_list_create接口用于创建新的链表，ngx_list_init接口用于初始化一个已有的链表，ngx_list_push接口用于添加新的元素，如下所示：

ngx_list_tngx_list_create（ngx_pool_tpool,ngx_uint_t n,size_t size）；

static ngx_inline ngx_int_t

ngx_list_init（ngx_list_tlist,ngx_pool_tpool,ngx_uint_t n,size_t size）；

voidngx_list_push（ngx_list_tlist）；

调用ngx_list_create创建元素时，pool参数是内存池对象（参见3.7.2节），size是每个元素的大小，n是每个链表数组可容纳元素的个数（相当于ngx_list_t结构中的nalloc成员）。ngx_list_create返回新创建的链表地址，如果创建失败，则返回NULL空指针。ngx_list_create被调用后至少会创建一个数组（不会创建空链表），其中包含n个大小为size字节的连续内存块，也就是ngx_list_t结构中的part成员。

下面看一个简单的例子，我们首先建立一个链表，它存储的元素是ngx_str_t，其中每个链表数组中存储4个元素，代码如下所示：

ngx_list_t*testlist=ngx_list_create（r-＞pool，4，sizeof（ngx_str_t））；

if（testlist==NULL）{

return NGX_ERROR；

}

ngx_list_init的使用方法与ngx_list_create非常类似，需要注意的是，这时链表数据结构已经创建好了，若ngx_list_init返回NGX_OK，则表示初始化成功，若返回NGX_ERROR，则表示失败。

调用ngx_list_push表示添加新的元素，传入的参数是ngx_list_t链表。正常情况下，返回的是新分配的元素首地址。如果返回NULL空指针，则表示添加失败。在使用它时通常先调用ngx_list_push得到返回的元素地址，再对返回的地址进行赋值。例如：

ngx_str_t*str=ngx_list_push（testlist）；

if（str==NULL）{

return NGX_ERROR；

}

str-＞len=sizeof（"Hello world"）；

str-＞value="Hello world"；

遍历链表时Nginx没有提供相应的接口，实际上也不需要。我们可以用以下方法遍历链表中的元素：

//part用于指向链表中的每一个ngx_list_part_t数组

ngx_list_part_t*part=＆testlist.part；

//根据链表中的数据类型，把数组里的elts转化为该类型使用

ngx_str_t*str=part-＞elts；

//i表示元素在链表的每个ngx_list_part_t数组里的序号

for（i=0；/void/；i++）{

if（i＞=part-＞nelts）{

if（part-＞next==NULL）{

//如果某个ngx_list_part_t数组的next指针为空，

//则说明已经遍历完链表

break；

}

//访问下一个ngx_list_part_t

part=part-＞next；

header=part-＞elts；

//将i序号置为0，准备重新访问下一个数组

i=0；

}

//这里可以很方便地取到当前遍历到的链表元素

printf（"list element：%*s\n"，str[i].len,str[i].data）；

}