摘要：源碼路徑版本主要作用分析是對(duì)通常的這種數(shù)據(jù)結(jié)構(gòu)重復(fù)的造輪子。鏈表使用的內(nèi)存池。在堆上創(chuàng)建調(diào)用函數(shù)與的分析類似，調(diào)用該函數(shù)會(huì)自動(dòng)向申請(qǐng)內(nèi)存空間。

版本：1.8.0

srccoreNgx_list.h
srccoreNgx_list.c

ngx_list_t是Nginx對(duì)通常的list這種數(shù)據(jù)結(jié)構(gòu)重復(fù)的造輪子。

在本篇中，我們先來(lái)分析Nginx是如何造這個(gè)輪子的，然后對(duì)比說(shuō)明，ngx_list_t和list有什么不同，最后再分析Nginx作者Igor Sysoev重復(fù)造輪子的原因。

如果你看過(guò)我對(duì)ngx_pool_t的分析，很容易就會(huì)想到，構(gòu)造一個(gè)list需要定義兩個(gè)結(jié)構(gòu)：

用于管理鏈表節(jié)點(diǎn)自身的結(jié)構(gòu)體；

比如，可以這么定義

typedef struct list_s list_t;
typedef struct node_s node_t;
struct node_s {
    void     *elt;  // 節(jié)點(diǎn)使用的內(nèi)存塊起始位置；
    size_t    max;  // 節(jié)點(diǎn)內(nèi)存塊的大??；
    node_t   *next; // 下一個(gè)內(nèi)存塊的地址；
};

用于管理整個(gè)鏈表的結(jié)構(gòu)體；

比如，可以這么定義

struct list_s {
    node_t    node;    //鏈表節(jié)點(diǎn)
    list_t    *curr;   //當(dāng)前使用的鏈表節(jié)點(diǎn)
};

Nginx使用ngx_pool_t來(lái)管理內(nèi)存的使用，所以向鏈表中增加元素時(shí)，就意味著需要使用ngx_pool_t的操作函數(shù)ngx_palloc。因此，增加一個(gè)元素，就對(duì)應(yīng)一次ngx_palloc調(diào)用。

這是相對(duì)效率低下的操作方式。Nginx為了提高效率，做了這樣的改動(dòng)：

  
初始化鏈表時(shí)，規(guī)定鏈表中元素的內(nèi)存占用大小為size，一次性向ngx_pool_t內(nèi)存池申請(qǐng)size * nelts大小的內(nèi)存空間，作為鏈表的節(jié)點(diǎn)

示意圖如下：

這樣做的目的在于減少內(nèi)存的申請(qǐng)次數(shù)，從而提高效率

基于以上分析，就很容易理解ngx_list_t結(jié)構(gòu)體的含義。ngx_list_t 是用來(lái)管理整個(gè)鏈表的結(jié)構(gòu)體。

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：指向鏈表中最后一個(gè)ngx_list_part_t，用于管理整個(gè)鏈表，含義很明確。

part：鏈表第一個(gè)節(jié)點(diǎn)，表示一塊連續(xù)的內(nèi)存空間。

size：鏈表中每個(gè)節(jié)點(diǎn)中存放元素大小。

size：鏈表中每個(gè)節(jié)點(diǎn)可以存放的元素個(gè)數(shù)。

pool：鏈表使用的內(nèi)存池。

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：鏈表節(jié)點(diǎn)使用的內(nèi)存塊地址。

nelts：當(dāng)前鏈表節(jié)點(diǎn)已經(jīng)存放的元素個(gè)數(shù)。

next：指向鏈表的下一個(gè)節(jié)點(diǎn)。

分兩點(diǎn)來(lái)分析：

1）ngx_list_t的創(chuàng)建；
2）ngx_list_t添加元素；

ngx_list_t的創(chuàng)建分成兩部分：

創(chuàng)建ngx_list_t結(jié)構(gòu)體本身

向ngx_pool_t申請(qǐng)ngx_list_t使用的內(nèi)存空間

兩種方式：

在堆上創(chuàng)建，即，向ngx_pool_t申請(qǐng)空間。

在棧上創(chuàng)建，即，直接創(chuàng)建ngx_pool_t局部變量。

在堆上創(chuàng)建調(diào)用函數(shù)：

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的分析類似，調(diào)用該函數(shù)會(huì)自動(dòng)向ngx_pool_t申請(qǐng)內(nèi)存空間。

調(diào)用函數(shù)：

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

很容易理解，不多解釋了。

因?yàn)?b>ngx_list_t已經(jīng)預(yù)先開(kāi)辟了內(nèi)存空間，所以，所謂的添加元素就是從ngx_list_t中分配出元素空間，并返回其指針。

void *
ngx_list_push(ngx_list_t *l)
{
    void             *elt;
    ngx_list_part_t  *last;

    last = l->last;
    // 當(dāng)預(yù)開(kāi)辟的空間不足的情況下，會(huì)向內(nèi)存池重新申請(qǐng)空間
    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;
}

這個(gè)問(wèn)題其實(shí)在上述的分析已經(jīng)說(shuō)了，這里作個(gè)總結(jié)：

ngx_list_t的鏈表節(jié)點(diǎn)不是list中的節(jié)點(diǎn)，而是將list中的節(jié)點(diǎn)作為元素，組成一個(gè)內(nèi)存塊，作為ngx_list_t的鏈表節(jié)點(diǎn)存在。

ngx_list_t使用ngx_pool_t內(nèi)存池來(lái)管理內(nèi)存。

一句話：為了提高效率。

通常list在使用過(guò)程中每個(gè)節(jié)點(diǎn)意味著一次內(nèi)存申請(qǐng)，這是一種效率低下的內(nèi)存使用方式，ngx_list_t使用一次申請(qǐng)一塊內(nèi)存的方式減少內(nèi)存申請(qǐng)次數(shù)，提高效率。