摘要：源碼路徑版本主要作用分析是對通常的這種數據結構重復的造輪子。鏈表使用的內存池。在堆上創建調用函數與的分析類似，調用該函數會自動向申請內存空間。

版本：1.8.0

srccoreNgx_list.h
srccoreNgx_list.c

ngx_list_t是Nginx對通常的list這種數據結構重復的造輪子。

在本篇中，我們先來分析Nginx是如何造這個輪子的，然后對比說明，ngx_list_t和list有什么不同，最后再分析Nginx作者Igor Sysoev重復造輪子的原因。

如果你看過我對ngx_pool_t的分析，很容易就會想到，構造一個list需要定義兩個結構：

用于管理鏈表節點自身的結構體；

比如，可以這么定義

typedef struct list_s list_t;
typedef struct node_s node_t;
struct node_s {
    void     *elt;  // 節點使用的內存塊起始位置；
    size_t    max;  // 節點內存塊的大小；
    node_t   *next; // 下一個內存塊的地址；
};

用于管理整個鏈表的結構體；

比如，可以這么定義

struct list_s {
    node_t    node;    //鏈表節點
    list_t    *curr;   //當前使用的鏈表節點
};

Nginx使用ngx_pool_t來管理內存的使用，所以向鏈表中增加元素時，就意味著需要使用ngx_pool_t的操作函數ngx_palloc。因此，增加一個元素，就對應一次ngx_palloc調用。

這是相對效率低下的操作方式。Nginx為了提高效率，做了這樣的改動：

  
初始化鏈表時，規定鏈表中元素的內存占用大小為size，一次性向ngx_pool_t內存池申請size * nelts大小的內存空間，作為鏈表的節點

示意圖如下：

這樣做的目的在于減少內存的申請次數，從而提高效率

基于以上分析，就很容易理解ngx_list_t結構體的含義。ngx_list_t 是用來管理整個鏈表的結構體。

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各成員變量含義如下：

last：指向鏈表中最后一個ngx_list_part_t，用于管理整個鏈表，含義很明確。

part：鏈表第一個節點，表示一塊連續的內存空間。

size：鏈表中每個節點中存放元素大小。

size：鏈表中每個節點可以存放的元素個數。

pool：鏈表使用的內存池。

ngx_list_part_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;
};

elts：鏈表節點使用的內存塊地址。

nelts：當前鏈表節點已經存放的元素個數。

next：指向鏈表的下一個節點。

分兩點來分析：

1）ngx_list_t的創建；
2）ngx_list_t添加元素；

ngx_list_t的創建分成兩部分：

創建ngx_list_t結構體本身

向ngx_pool_t申請ngx_list_t使用的內存空間

兩種方式：

在堆上創建，即，向ngx_pool_t申請空間。

在棧上創建，即，直接創建ngx_pool_t局部變量。

在堆上創建調用函數：

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

    list = ngx_palloc(pool, sizeof(ngx_list_t));
    if (list == NULL) {
        return NULL;
    }

    if (ngx_list_init(list, pool, n, size) != NGX_OK) {
        return NULL;
    }

    return list;
}

與ngx_array_t的分析類似，調用該函數會自動向ngx_pool_t申請內存空間。

調用函數：

static ngx_inline ngx_int_t
ngx_list_init(ngx_list_t *list, ngx_pool_t *pool, ngx_uint_t n, size_t 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_t已經預先開辟了內存空間，所以，所謂的添加元素就是從ngx_list_t中分配出元素空間，并返回其指針。

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;
        }

        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;
    }

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

    return elt;
}

這個問題其實在上述的分析已經說了，這里作個總結：

ngx_list_t的鏈表節點不是list中的節點，而是將list中的節點作為元素，組成一個內存塊，作為ngx_list_t的鏈表節點存在。

ngx_list_t使用ngx_pool_t內存池來管理內存。

一句話：為了提高效率。

通常list在使用過程中每個節點意味著一次內存申請，這是一種效率低下的內存使用方式，ngx_list_t使用一次申請一塊內存的方式減少內存申請次數，提高效率。