4.3　链表

链表和数组一样，也是基本的数据结构。它的数据在内存中不连续，但其插入数据的时间复杂度仅为O(1)。下面我们来看一下Nginx中是如何实现链表的。

链表节点的数据结构如下：

struct ngx_list_part_s {
    void             *elts;
    ngx_uint_t        nelts;
    ngx_list_part_t  *next;
};

代码中的参数说明如下。

• elts：指向节点数据的实际存储区域。
• nelts：当前链表节点上已分配的数据数量。
• next：指向链表的下一个节点。

我们知道，链表中每个节点只有一个数据，通过next指针指向下一个数据，这里是怎么回事呢？事实上，Nginx链表上的一个节点并不只存储一个数据，而是存储多个数据。一个节点内的数据是在内存池上连续存放的，当内存池不够用时，才会申请内存池节点，并通过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;

代码中的参数说明如下。

• last：链表最后一个节点。
• part：链表的第一个节点。
• size：每个数据的大小。
• nalloc：链表每个节点所包含的数据个数。
• pool：链表头部所在的内存池。

Nginx用ngx_list_create函数来创建链表。ngx_list_create函数定义如下：

ngx_list_t *ngx_list_create(ngx_pool_t *pool, ngx_uint_t n, size_t size);

与数组创建一样，链表在创建时会先从内存池中申请头部所占用的空间，并对ngx_list_t结构体进行初始化。初始化完成之后，part为链表的第一个节点，分配有n×size的存储空间。由于还没有插入数据，part的nelts参数值为0，next指向NULL。头部的last节点指向当前插入的节点，可分配的数据数量为函数参数n。

链表初始化完成之后，通过ngx_list_push函数向链表插入数据，函数定义如下：

void *ngx_list_push(ngx_list_t *list);

同数组一样，链表插入数据时，并不会直接将值赋值到数据节点上，而是返回内存地址，由用户自定义内存区域的值。

链表插入数据时，如果节点上已分配的数据数量还未达到nalloc值，表示内存池中有足够的空间存放新数据，此时直接返回数据所需要的内存空间，并将节点已使用的个数加1，代码如下：

elt = (char *) last->elts + l->size * last->nelts;
last->nelts++;

当链表节点上已分配的数据数量等于nalloc时，表示当前链表节点已经存满，需要重新开辟一个内存池来存放链表的新节点。

if (last->nelts == l->nalloc) {
    last = ngx_palloc(l->pool, sizeof(ngx_list_part_t));
    if (last == NULL) {
        return NULL;
    }

    last->elts = ngx_palloc(l->pool, l->nalloc * l->size);
    if (last->elts == NULL) {
        return NULL;
    }

    last->nelts = 0;
    last->next = NULL;

    l->last->next = last;
    l->last = last;
}

从上述代码可以看到，新插入的数据需要从新的内存池上分配链表节点所占用的空间，并分配l->nalloc * l->size空间来存放本链表节点的数据。当存储空间分配好之后，将链表头部的last节点指向当前新申请的链表节点，这样就完成了在链表节点插入数据的操作。

Nginx在链表使用完毕之后，直接释放链表所在的内存池上的空间，这样的操作更简单而且不用考虑单个节点的内存释放，易于维护。