一 雙向連結清單結構
Nginx的連結清單結構非常小巧和簡單。設計的非常精巧。通過連結清單的簡單和精巧的設計，讓Nginx的連結清單的資料結構和具體業務依賴進行了解耦。
1 雙向連結清單的資料結構
非常簡單，不存任何其它類型的内容，隻包含了連結清單的前後節點，使用時通過作為其它資料結構的成員使用。
typedef struct ngx_queue_s ngx_queue_t;
struct ngx_queue_s {
ngx_queue_t *prev;
ngx_queue_t *next;
};
例如雙向連結清單在業務上被使用在網絡中。
/**
* 該結構體用于描述一個網絡連接配接
*/
struct ngx_connection_s {
void *data; //連接配接未使用時，data用于充當連接配接池中空閑連結清單中的next指針。連接配接使用時由子產品而定，HTTP中，data指向ngx_http_request_t
ngx_event_t *read; //連接配接對應的讀事件
ngx_event_t *write; //連接配接對應的寫事件
ngx_socket_t fd; //套接字句柄
ngx_recv_pt recv; //直接接受網絡位元組流
ngx_send_pt send; //直接發送網絡位元組流
ngx_recv_chain_pt recv_chain; //網絡位元組流接收連結清單
ngx_send_chain_pt send_chain; //網絡位元組流發送連結清單
/*用來将目前連接配接以雙向連結清單元素的形式添加到ngx_cycle_t核心結構體
* 的reuseable_connection_queue雙向連結清單中，表示可以重用的連接配接*/
ngx_queue_t queue;
/* 省去部分 */
};
雙向連結清單圖，對于下面了解非常有幫助。
二 具體函數實作
Nginx的連結清單主要使用宏來代替函數的操作。
//注意雙向連結清單的有效節點不包含h頭節點。
/**
* 初始化一個雙向連結清單。
*/
#define ngx_queue_init(q) \
(q)->prev = q; \
(q)->next = q
/**
* 判斷雙向連結清單是否為空，隻有一個節點而沒有實際的節點也是空，例如隻有h為空，h->a共h與a節點則不是空。
*/
#define ngx_queue_empty(h) \
(h == (h)->prev)
/**
* 往h後面插入一個節點x。
*/
#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
/**
* 往h末尾插入一個節點x。
* 注意第一行的(h)->prev代表末尾節點，因為h是一個雙向連結清單。
*/
#define ngx_queue_insert_tail(h, x) \
(x)->prev = (h)->prev; \
(x)->prev->next = x; \
(x)->next = h; \
(h)->prev = x
/**
* 擷取雙向連結清單的頭節點，即h的下一節點。
*/
#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
/**
* 移除連結清單的節點x。
*/
#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 *));
1 解釋ngx_queue_split
#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;
h為連結清單，q為連結清單h中的一個元素，這個方法可以将連結清單h以元素q為界拆分為兩個連結清單h和n，其中h由原連結清單的前半部分組成（不包含q），而n由後半部分組成，n為節點頭，q為包含實際資料的首元素。最終通過分割後擷取到兩個連結清單，即h->有效節點，n->有效節點。
大家可以根據下圖自己畫一下即可，我這裡不畫了。并且注意，本章使用畫圖了解是非常必要的。
2 解釋ngx_queue_add
#define ngx_queue_add(h, n) \
(h)->prev->next = (n)->next; \
(n)->next->prev = (h)->prev; \
(h)->prev = (n)->prev; \
(h)->prev->next = h;
該宏函數的作用是在連結清單h尾部添加一個新的連結清單，但是不包含節點n，即不包含無效的節點n，非常牛逼，我開始看的時候看得很懵，不知道為啥不包含節點n，最終看完整篇文章才知道連結清單的首節點是無效節點才了解。n=1無意義。
如圖解釋：
3 解釋ngx_queue_data
#define ngx_queue_data(q, type, link) \
(type *) ((u_char *) q - offsetof(type, link))
ngx_queue_data就簡單得多了，實際上該函數就是調用offsetof函數去實作的。
例子：
/**
* 通過連結清單可以找到結構體所在的指針
* typedef struct {
* ngx_queue_s queue;
* char * x;
* ....
* } TYPE
*
* 調用時：
* TYPE *a = ngx_queue_data(&type->queue, TYPE, queue);
* 其中：參1為結構體變量，參2為該變量的類型，參3為結構體的成員名(必須與定義時一緻，否則報錯)。
* 注意：
* offsetof(TYPE, link))傳回的是結構體的偏移量，((struct_name*)0為絕對偏移位址0。
* 是以我們這個例子最終的結果就是&type->queue-0=&type->queue，也就是該結構體變量的首位址。牛逼吧，即使将成員queue不放在第一個位置，結果也是一樣。
*
* #define OFFSETOF(struct_name, member_name) \
* (int) &( ((struct_name*)0)->member_name )
*/
說白了，這個宏主要是考你對結構體的偏移位址的了解，絕對偏移位址為0。
關于類似ngx_queue_data的用法，使用結構體變量某個成員的位址來擷取變量的首位址的具體說明，請參考以下部落格。
4 解釋ngx_queue_t *ngx_queue_middle
ngx_queue_t *
ngx_queue_middle(ngx_queue_t *queue)
{
ngx_queue_t *middle, *next;
middle = ngx_queue_head(queue);//擷取首個有效節點
if (middle == ngx_queue_last(queue)) {//隻有一個有效節點或者為空連結清單則直接傳回
return middle;
}
next = ngx_queue_head(queue);
//此時middle和next均指向連結清單的首個有效節點
for ( ;; ) {
middle = ngx_queue_next(middle);
next = ngx_queue_next(next);
if (next == ngx_queue_last(queue)) {
return middle;
}
next = ngx_queue_next(next);
if (next == ngx_queue_last(queue)) {
return middle;
}
}
}
- 1）該函數作用：擷取queue連結清單的中間節點。
- 2）算法的基本思想: middle指針每次後移一個節點，而next指針每次後移兩個節點。時間複雜度就是O(N)。這是一道經典的面試題，今天在這裡看到了源碼，似成相識啊，果然經典面試題目都不是憑空而來。
- 3）通過代入8個節點發現(包括無效資料的頭節點)，看下面：
2個以下時直接傳回了。是以從3開始判斷(建議必須畫圖觀察)：
節點數=3時，middle下标=2；
節點數=4時，middle下标=2；
節點數=5時，middle下标=3；
節點數=6時，middle下标=3；
節點數=7時，middle下标=4；
節點數=8時，middle下标=4；
總結公式有：
1）總節點為奇數時：n/2+1。
2）總節點為偶數時：n/2。
這~就是nginx源碼的魅力。
5 解釋void ngx_queue_sort
ngx_queue_sort的作用是穩定将雙向連結清單内的元素進行排序，規則由傳進的回調函數設定，可從小到大或者從大到小。該函數使用的排序方法為插入排序法，兩兩比較，每次确定一個元素進行插入。
/* the stable insertion sort */
void
ngx_queue_sort(ngx_queue_t *queue,
ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
{
ngx_queue_t *q, *prev, *next;
q = ngx_queue_head(queue);
//如果連結清單隻有一個有效節點則直接傳回
if (q == ngx_queue_last(queue)) {
return;
}
/*
主要思想是：通過p和q操作兩兩比較(next為自增不考慮分析避免繁瑣)，每次确定一個元
素放在h連結清單的最後面，注意此時h可以認為是新的連結清單，舊的連結清單由p，q儲存，若出現不
滿足if條件的情況，則一直往排序好的元素前面繼續比較。
例如，這裡以從小到大舉例，即回調函數傳回prev>q即可。元素：10,5,11 (注：這裡的數字是儲存
的一個結構體的，為了友善直接寫出來了。)
1）首先p指向10，q指向5.
2）由于10>5傳回ture故不滿足if，繼續往排序好的連結清單前查找，由于第一次排序好的連結清單為空，故
直接跳出循環(dowhile)，将5插入prev(此時prev=h)，即h->5->10->11
3）然後繼續循環，p指向10，q指向11，滿足if直接跳出。然後将11插入10的後面，即h->5->10->11
4）然後繼續循環，由于q=next時指向h(h為哨兵節點)，是以for循環退出，共排n-1次。
明白後以後可以這樣直接分析：
1）q=5,p=10,n=11. 結果=>h->5->10->11
2）q=11,p=10(dowhile向前導緻),n=h. 結果=>h->5->10->11
3）for循環條件不滿足，直接退出。
*/
for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
prev = ngx_queue_prev(q);
next = ngx_queue_next(q);//自增
ngx_queue_remove(q);
do {
if (cmp(prev, q) <= 0) {
break;
}
prev = ngx_queue_prev(prev);
} while (prev != ngx_queue_sentinel(queue));//ngx_queue_sentinel(queue)為哨兵，即連結清單頭結點h。
ngx_queue_insert_after(prev, q);//依次往已經排好的節點後面添加節點。
}
}