nginx 雙向鏈表
ngx_queue_t雙向鏈表是Nginx提供的輕量級鏈表容器，它與Nginx的內存池無關，因此，這個鏈表將不會負責分配內存來存放鏈表元素。這意味著，任何鏈表元素都需要通過其他方式來分配它所需要的內存空間，不要指望ngx_queue_t幫助存儲元素。ngx_queue_t只是把這些已經分配好內存的元素用雙向鏈表連接起來。ngx_queue_t的功能雖然很簡單，但它非常輕量級，對每個用戶數據而言，只需要增加兩個指針的空間即可，消耗的內存很少。同時，ngx_queue_t還提供了一個非常簡易的插入排序法，雖然不太適合超大規模數據的排序，但它勝在簡單實用。ngx_queue_t作為C語言提供的通用雙向鏈表，其設計思路值得用戶參考。
為什麼設計 ngx_queue_t 雙向鏈表
鏈表作為順序容器的優勢在於，它可以高效地執行插入、刪除、合併等操作，在移動鏈
表中的元素時只需要修改指針的指向，因此，它很適合頻繁修改容器的場合。在Nginx中，鏈表是必不可少的，而ngx_queue_t雙向鏈表就被設計用於達成以上目的。
相對於Nginx其他順序容器，ngx_queue_t容器的優勢在於：
- 實現了排序功能。
- 它非常輕量級，是一個純粹的雙向鏈表。它不負責鏈表元素所佔內存的分配，與Nginx封裝的ngx_pool_t內存池完全無關。
- 支持兩個鏈表間的合併。
ngx_queue_t容器的實現只用了一個數據結構ngx_queue_t，它僅有兩個成員：prev、next，如下所示：
typedef struct ngx_queue_s ngx_queue_t;
struct ngx_queue_s {
ngx_queue_t *prev;
ngx_queue_t *next;
};
因此，對於鏈表中的每個元素來說，空間上只會增加兩個指針的內存消耗。
使用ngx_queue_t時可能會遇到有些讓人費解的情況，因為鏈表容器自身是使用ngx_queue_t來標識的，而鏈表中的每個元素同樣使用ngx_queue_t結構來標識自己，並以ngx_queue_t結構維持其與相鄰元素的關係。下面開始介紹ngx_queue_t的使用方法。
雙向鏈表的使用方法
Nginx在設計這個雙向鏈表時，由於容器與元素共用了ngx_queue_t結構體，為了避免ngx_queue_t結構體成員的意義混亂，Nginx封裝了鏈表容器與元素的所有方法，這種情況非常少見，而且從接下來的幾節中可以看到，其他容器都需要直接使用成員變數來訪問，唯有ngx_queue_t雙向鏈表只能使用如下中列出的方法訪問容器。
#define ngx_queue_init(q)
(q)->prev = q;
(q)->next = q
#define ngx_queue_empty(h)
(h == (h)->prev)
#define ngx_queue_insert_head(h, x)
(x)->next = (h)->next;
(x)->next->prev = x;
(x)->prev = h;
(h)->next = x
#define ngx_queue_insert_after ngx_queue_insert_head
#define ngx_queue_insert_tail(h, x)
(x)->prev = (h)->prev;
(x)->prev->next = x;
(x)->next = h;
(h)->prev = x
#define ngx_queue_head(h)
(h)->next
#define ngx_queue_last(h)
(h)->prev
#define ngx_queue_sentinel(h)
(h)
#define ngx_queue_next(q)
(q)->next
#define ngx_queue_prev(q)
(q)->prev
#if (NGX_DEBUG)
#define ngx_queue_remove(x)
(x)->next->prev = (x)->prev;
(x)->prev->next = (x)->next;
(x)->prev = NULL;
(x)->next = NULL
#else
#define ngx_queue_remove(x)
(x)->next->prev = (x)->prev;
(x)->prev->next = (x)->next
#endif
#define ngx_queue_split(h, q, n)
(n)->prev = (h)->prev;
(n)->prev->next = n;
(n)->next = q;
(h)->prev = (q)->prev;
(h)->prev->next = h;
(q)->prev = n;
#define ngx_queue_add(h, n)
(h)->prev->next = (n)->next;
(n)->next->prev = (h)->prev;
(h)->prev = (n)->prev;
(h)->prev->next = h;
#define ngx_queue_data(q, type, link)
(type *) ((u_char *) q - offsetof(type, link))
ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue);
void ngx_queue_sort(ngx_queue_t *queue,
ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *));
使用雙向鏈表容器時，需要用一個ngx_queue_t結構體表示容器本身，而這個結構體有若干方法可供使用。
對於鏈表中的每一個元素，其類型可以是任意的struct結構體，但這個結構體中必須要有一個ngx_queue_t類型的成員，在向鏈表容器中添加、刪除元素時都是使用的結構體中ngx_queue_t類型成員的指針。當ngx_queue_t作為鏈表的元素成員使用時，它具有表7-2中列出的4種方法。
如上代碼已經列出了鏈表支持的所有方法，下面將以一個簡單的例子來說明如何使用ngx_queue_t雙向鏈表。
使用雙向鏈表排序的例子
本節定義一個簡單的鏈表，並使用ngx_queue_sort方法對所有元素排序。在這個例子中，可以看到如何定義、初始化ngx_queue_t容器，如何定義任意類型的鏈表元素，如何遍歷鏈表，如何自定義排序方法並執行排序。
首先，定義鏈表元素的結構體，如下面的TestNode結構體：
typedef struct {
u_char* str;
ngx_queue_t qEle;
int num;
} TestNode;
鏈表元素結構體中必須包含ngx_queue_t類型的成員，當然它可以在任意的位置上。本例中它的上面有一個char*指針，下面有一個整型成員num，這樣是允許的。
排序方法需要自定義。下面以TestNode結構體中的num成員作為排序依據，實現compTestNode方法作為排序過程中任意兩元素間的比較方法。
ngx_int_t compTestNode(const ngx_queue_t* a, const ngx_queue_t* b)
{
/*
*首先使用ngx_queue_data方法由ngx_queue_t變數獲取元素結構體TestNode的地址
*/
TestNode aNode = ngx_queue_data(a, TestNode, qEle);
TestNode* bNode = ngx_queue_data(b, TestNode, qEle);
/*
* 返回num成員的比較結果
*/
return aNode->num > bNode->num;
}
這個比較方法結合ngx_queue_sort方法可以把鏈表中的元素按照num的大小以升序排列。
在此例中，可以看到ngx_queue_data的用法，即可以根據鏈表元素結構體TestNode中的qEle成員地址換算出TestNode結構體變數的地址，這是面向過程的C語言編寫的ngx_queue_t鏈表之所以能夠通用化的關鍵。下面來看一下ngx_queue_data的定義：
#define ngx_queue_data(q, type, link)
(type *) ((u_char *) q - offsetof(type, link))
此處offset會返回link成員在type結構體中的偏移量。
這裡可以看出，ngx_queue_data中，可以通過ngx_queue_t類型的指針減去qEle相對於TestNode的地址偏移量，得到TestNode結構體的地址。
下面開始定義雙向鏈表容器queueContainer，並將其初始化為空鏈表，如下所示。
ngx_queue_t queueContainer;
ngx_queue_init(&queueContainer);
鏈表容器以ngx_queue_t定義即可。注意，對於表示鏈表容器的ngx_queue_t結構體，必須調用ngx_queue_init進行初始化。
ngx_queue_t雙向鏈表是完全不負責分配內存的，每一個鏈表元素必須自己管理自己所佔用的內存。因此，本例在進程棧中定義了5個TestNode結構體作為鏈表元素，並把它們的num成員初始化為0、1、2、3、4，如下所示。
int i = 0;
TestNode node[5];
for (; i < 5; i++)
{
node[i].num = i;
}
下面把這5個TestNode結構體添加到queueContainer鏈表中，注意，這裡同時使用了ngx_queue_insert_tail、ngx_queue_insert_head、ngx_queue_insert_after 3個添加方法，讀者不妨思考一下鏈表中元素的順序是什麼樣的。
ngx_queue_insert_tail(&queueContainer, &node[0].qEle);
ngx_queue_insert_head(&queueContainer, &node[1].qEle);
ngx_queue_insert_tail(&queueContainer, &node[2].qEle);
ngx_queue_insert_after(&queueContainer, &node[3].qEle);
ngx_queue_insert_tail(&queueContainer, &node[4].qEle);
根據表7-1中介紹的方法可以得出，如果此時的鏈表元素順序以num成員標識，那麼應該是這樣的：3、1、0、2、4。如果有疑問，不妨寫個遍歷鏈表的程序檢驗一下順序是否如此。下面就根據如上方法說明編寫一段簡單的遍歷鏈表的程序。
ngx_queue_t* q;
for (q = ngx_queue_head(&queueContainer); q != ngx_queue_sentinel(&queueContainer); q = ngx_queue_next(q))
{
TestNode* eleNode = ngx_queue_data(q, TestNode, qEle);
// 處理當前的鏈表元素eleNode
…
}
上面這段程序將會依次從鏈表頭部遍歷到尾部。反向遍歷也很簡單。讀者可以嘗試使用ngx_queue_last和ngx_queue_prev方法編寫相關代碼。
下面開始執行排序，代碼如下所示。
ngx_queue_sort(&queueContainer, compTestNode);
這樣，鏈表中的元素就會以0、1、2、3、4（num成員的值）的升序排列了。
雙向鏈表是如何實現的
本節將說明ngx_queue_t鏈表容器以及元素中prev成員、next成員的意義，整個鏈表就是通過這兩個指針成員實現的。
下面先來看一下ngx_queue_t結構體作為容器時其prev成員、next成員的意義。當容器為空時，prev和next都將指向容器本身。如下所示，如果在某個結構體中定義了ngx_queue_t容器，其prev指針和next指針都會指向ngx_queue_t成員的地址。
當容器不為空時，ngx_queue_t容器的next指針會指向鏈表的第1個元素，而prev指針會指向鏈表的最後1個元素。如下圖所示，這時鏈表中只有1個鏈表元素，容器的next指針和prev指針都將指向這個唯一的鏈表元素。
對於每個鏈表元素來說，其prev成員都指向前一個元素（不存在時指向鏈表容器），而next成員則指向下一個元素（不存在時指向鏈表容器），這如上可以看到。
當容器中有兩個元素時，prev和next的指向如下圖所示。
如上很好地詮釋了前面的定義，容器中的prev成員指向最後1個也就是第2個元素，next成員指向第1個元素。第1個元素的prev成員指向容器本身，而其next成員指向第2個元素。第2個元素的prev成員指向第1個元素，其next成員則指向容器本身。
ngx_queue_t的實現就是這麼簡單，但它的排序演算法ngx_queue_sort使用的插入排序，並不適合為龐大的數據排序。
本文暫取自代碼、網路或書籍，只用作學習備忘，不作盈利等他用。
如有侵權，請聯繫Linkerist@163.com
推薦閱讀：