nginx 單向鏈表

ngx_list_t是Nginx封裝的鏈表容器，它在Nginx中使用得很頻繁，例如HTTP的頭部就是用

ngx_list_t來存儲的。當然，C語言封裝的鏈表沒有C++或Java等面向對象語言那麼容易理解。ngx_list_t單向鏈表與ngx_queue_t雙向鏈表是完全不同的，它是負責容器內元素內存分配

的，因此，這兩個容器在通用性的設計思路上是完全不同的。同時它與ngx_array_t也不一

樣，它不是用完全連續的內存來存儲元素，而是用單鏈表將多段內存塊連接起來，每段內存塊也存儲了多個元素，有點像「數組+單鏈表」。先看一下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管理，它已經通過數組分配好了。
小塊的內存使用鏈表訪問效率是低下的，使用數組通過偏移量來直接訪問內存則要高效得多。

下面詳述每個成員的意義

ngx_list_t

part：鏈表的首個數組元素。
last：指向鏈表的最後一個數組元素。
size：前面講過，鏈表中的每個ngx_list_part_t元素都是一個數組。因為數組存儲的是某種類型的數據結構，且ngx_list_t是非常靈活的數據結構，所以它不會限制存儲什麼樣的數據，只是通過size限制每一個數組元素的佔用的空間大小，也就是用戶要存儲的一個數據所佔用的位元組數必須小於或等於size。
nalloc：鏈表的數組元素一旦分配後是不可更改的。nalloc表示每個ngx_list_part_t數組的容量，即最多可存儲多少個數據。
pool：鏈表中管理內存分配的內存池對象。用戶要存放的數據佔用的內存都是由pool分配的，下文中會詳細介紹。

ngx_list_part_t

elts：指向數組的起始地址。
nelts：表示數組中已經使用了多少個元素。當然，nelts必須小於ngx_list_t結構體中的nalloc。
next：下一個鏈表元素ngx_list_part_t的地址。

事實上，ngx_list_t中的所有數據都是由ngx_pool_t類型的pool內存池分配的，它們通常都是連續的內存（在由一個pool內存池分配的情況下）。下圖可以看一下ngx_list_t的內存分布情況。

ngx_list_t的內存分布

如上是由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介面用於添加新的元素，如下所示：

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

list->part.elts = ngx_palloc(pool, n * size);
if (list->part.elts == NULL) {
return NULL;
}

list->part.nelts = 0;
list->part.next = NULL;
list->last = &list->part;
list->size = size;
list->nalloc = n;
list->pool = pool;

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

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_create創建元素時，pool參數是內存池對象，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->data = "Hello world";

遍歷鏈表時Nginx沒有提供相應的介面，實際上也不需要。我們可以用以下方法遍歷鏈表中的元素：

/* * * the iteration through the list: * * part = &list.part; * data = part->elts; * * for (i = 0 ;; i++) { * * if (i >= part->nelts) { * if (part->next == NULL) { * break; * } * * part = part->next; * data = part->elts; * i = 0; * } * * ... data[i] ... * * } */