### 隊列鏈表結構 ? ? ? 隊列雙向循環鏈表實現文件：文件：src/core/ngx_queue.h/.c。在 Nginx 的隊列實現中，實質就是具有頭節點的雙向循環鏈表，這里的雙向鏈表中的節點是沒有數據區的，只有兩個指向節點的指針。需注意的是隊列鏈表的內存分配不是直接從內存池分配的，即沒有進行內存池管理，而是需要我們自己管理內存，所有我們可以指定它在內存池管理或者直接在堆里面進行管理，最好使用內存池進行管理。節點結構定義如下： ~~~ /* 隊列結構，其實質是具有有頭節點的雙向循環鏈表 */ typedef struct ngx_queue_s ngx_queue_t; /* 隊列中每個節點結構，只有兩個指針，并沒有數據區 */ struct ngx_queue_s { ngx_queue_t *prev; ngx_queue_t *next; }; ~~~ ### 隊列鏈表操作 其基本操作如下： ~~~ /* h 為鏈表結構體 ngx_queue_t 的指針；初始化雙鏈表 */ ngx_queue_int(h) /* h 為鏈表容器結構體 ngx_queue_t 的指針； 判斷鏈表是否為空 */ ngx_queue_empty(h) /* h 為鏈表容器結構體 ngx_queue_t 的指針，x 為插入元素結構體中 ngx_queue_t 成員的指針；將 x 插入到鏈表頭部 */ ngx_queue_insert_head(h, x) /* h 為鏈表容器結構體 ngx_queue_t 的指針，x 為插入元素結構體中 ngx_queue_t 成員的指針。將 x 插入到鏈表尾部 */ ngx_queue_insert_tail(h, x) /* h 為鏈表容器結構體 ngx_queue_t 的指針。返回鏈表容器 h 中的第一個元素的 ngx_queue_t 結構體指針 */ ngx_queue_head(h) /* h 為鏈表容器結構體 ngx_queue_t 的指針。返回鏈表容器 h 中的最后一個元素的 ngx_queue_t 結構體指針 */ ngx_queue_last(h) /* h 為鏈表容器結構體 ngx_queue_t 的指針。返回鏈表結構體的指針 */ ngx_queue_sentinel(h) /* x 為鏈表容器結構體 ngx_queue_t 的指針。從容器中移除 x 元素 */ ngx_queue_remove(x) /* h 為鏈表容器結構體 ngx_queue_t 的指針。該函數用于拆分鏈表， * h 是鏈表容器，而 q 是鏈表 h 中的一個元素。 * 將鏈表 h 以元素 q 為界拆分成兩個鏈表 h 和 n */ ngx_queue_split(h, q, n) /* h 為鏈表容器結構體 ngx_queue_t 的指針， n為另一個鏈表容器結構體 ngx_queue_t 的指針 * 合并鏈表，將 n 鏈表添加到 h 鏈表的末尾 */ ngx_queue_add(h, n) /* h 為鏈表容器結構體 ngx_queue_t 的指針。返回鏈表中心元素，即第 N/2 + 1 個 */ ngx_queue_middle(h) /* h 為鏈表容器結構體 ngx_queue_t 的指針，cmpfunc 是比較回調函數。使用插入排序對鏈表進行排序 */ ngx_queue_sort(h, cmpfunc) /* q 為鏈表中某一個元素結構體的 ngx_queue_t 成員的指針。返回 q 元素的下一個元素。*/ ngx_queue_next(q) /* q 為鏈表中某一個元素結構體的 ngx_queue_t 成員的指針。返回 q 元素的上一個元素。*/ ngx_queue_prev(q) /* q 為鏈表中某一個元素結構體的 ngx_queue_t 成員的指針，type 是鏈表元素的結構體類型名稱， * link 是上面這個結構體中 ngx_queue_t 類型的成員名字。返回 q 元素所屬結構體的地址 */ ngx_queue_data(q, type, link) /* q 為鏈表中某一個元素結構體的 ngx_queue_t 成員的指針，x 為插入元素結構體中 ngx_queue_t 成員的指針 */ ngx_queue_insert_after(q, x) ~~~ 下面是隊列鏈表操作源碼的實現： #### 初始化鏈表 ~~~ /* 初始化隊列，即節點指針都指向自己，表示為空隊列 */ #define ngx_queue_init(q) \ (q)->prev = q; \ (q)->next = q /* 判斷隊列是否為空 */ #define ngx_queue_empty(h) \ (h == (h)->prev) ~~~ #### 獲取指定的隊列鏈表中的節點 ~~~ /* 獲取隊列頭節點 */ #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 ~~~ #### 插入節點 在頭節點之后插入新節點： ~~~ /* 在隊列頭節點的下一節點插入新節點，其中h為頭節點，x為新節點 */ #define ngx_queue_insert_head(h, x) \ (x)->next = (h)->next; \ (x)->next->prev = x; \ (x)->prev = h; \ (h)->next = x ~~~ ? ? ? 插入節點比較簡單，只是修改指針的指向即可。下圖是插入節點的過程：注意：虛線表示斷開連接，實線表示原始連接，破折線表示重新連接，圖中的數字與源碼步驟相對應。  在尾節點之后插入節點 ~~~ /* 在隊列尾節點之后插入新節點，其中h為尾節點，x為新節點 */ #define ngx_queue_insert_tail(h, x) \ (x)->prev = (h)->prev; \ (x)->prev->next = x; \ (x)->next = h; \ (h)->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 ~~~ 刪除節點過程如下圖所示：  #### 拆分鏈表 ~~~ /* 拆分隊列鏈表，使其稱為兩個獨立的隊列鏈表； * 其中h是原始隊列的頭節點，q是原始隊列中的一個元素節點，n是新的節點， * 拆分后，原始隊列以q為分界，頭節點h到q之前的節點作為一個隊列（不包括q節點）， * 另一個隊列是以n為頭節點，以節點q及其之后的節點作為新的隊列鏈表； */ #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; ~~~ ? ? ?該宏有 3 個參數，h 為隊列頭(即鏈表頭指針)，將該隊列從 q 節點將隊列(鏈表)拆分為兩個隊列(鏈表)，q 之后的節點組成的新隊列的頭節點為 n 。鏈表拆分過程如下圖所示：  #### 合并鏈表 ~~~ /* 合并兩個隊列鏈表，把n隊列鏈表連接到h隊列鏈表的尾部 */ #define ngx_queue_add(h, n) \ (h)->prev->next = (n)->next; \ (n)->next->prev = (h)->prev; \ (h)->prev = (n)->prev; \ (h)->prev->next = h; \ (n)->prev = (n)->next = n;/* 這是我個人增加的語句，若加上該語句，就不會出現頭節點n會指向隊列鏈表的節點 */ ~~~ 其中，h、n分別為兩個隊列的指針，即頭節點指針，該操作將n隊列鏈接在h隊列之后。具體操作如下圖所示：  #### 獲取中間節點 ~~~ /* 返回隊列鏈表中心元素 */ 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作為臨時指針，首先指向隊列鏈表的頭節點 */ next = ngx_queue_head(queue); for ( ;; ) { /* 若隊列鏈表不止一個元素，則等價于middle = middle->next */ 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; } } } ~~~ #### 鏈表排序 ? ? ? 隊列鏈表排序采用的是穩定的簡單插入排序方法，即從第一個節點開始遍歷，依次將當前節點(q)插入前面已經排好序的隊列(鏈表)中，下面程序中，前面已經排好序的隊列的尾節點為prev。操作如下： ~~~ /* 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; } /* 遍歷整個隊列鏈表 */ for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) { prev = ngx_queue_prev(q); next = ngx_queue_next(q); /* 首先把元素節點q獨立出來 */ ngx_queue_remove(q); /* 找到適合q插入的位置 */ do { if (cmp(prev, q) <= 0) { break; } prev = ngx_queue_prev(prev); } while (prev != ngx_queue_sentinel(queue)); /* 插入元素節點q */ ngx_queue_insert_after(prev, q); } } ~~~ #### 獲取隊列中節點數據地址 ? ? ? 由隊列基本結構和以上操作可知，nginx 的隊列操作只對鏈表指針進行簡單的修改指向操作，并不負責節點數據空間的分配。因此，用戶在使用nginx隊列時，要自己定義數據結構并分配空間，且在其中包含一個 ngx_queue_t 的指針或者對象，當需要獲取隊列節點數據時，使用ngx_queue_data宏，其定義如下： ~~~ /* 返回q在所屬結構類型的地址，type是鏈表元素的結構類型 */ #define ngx_queue_data(q, type, link) \ (type *) ((u_char *) q - offsetof(type, link)) /* ~~~ 測試程序： ~~~ #include <stdio.h> #include "ngx_queue.h" #include "ngx_conf_file.h" #include "ngx_config.h" #include "ngx_palloc.h" #include "nginx.h" #include "ngx_core.h" #define MAX 10 typedef struct Score { unsigned int score; ngx_queue_t Que; }ngx_queue_score; volatile ngx_cycle_t *ngx_cycle; void ngx_log_error_core(ngx_uint_t level, ngx_log_t *log, ngx_err_t err, const char *fmt, ...) { } ngx_int_t CMP(const ngx_queue_t *x, const ngx_queue_t *y) { ngx_queue_score *xinfo = ngx_queue_data(x, ngx_queue_score, Que); ngx_queue_score *yinfo = ngx_queue_data(y, ngx_queue_score, Que); return(xinfo->score > yinfo->score); } void print_ngx_queue(ngx_queue_t *queue) { ngx_queue_t *q = ngx_queue_head(queue); printf("score: "); for( ; q != ngx_queue_sentinel(queue); q = ngx_queue_next(q)) { ngx_queue_score *ptr = ngx_queue_data(q, ngx_queue_score, Que); if(ptr != NULL) printf(" %d\t", ptr->score); } printf("\n"); } int main() { ngx_pool_t *pool; ngx_queue_t *queue; ngx_queue_score *Qscore; pool = ngx_create_pool(1024, NULL); queue = ngx_palloc(pool, sizeof(ngx_queue_t)); ngx_queue_init(queue); int i; for(i = 1; i < MAX; i++) { Qscore = (ngx_queue_score*)ngx_palloc(pool, sizeof(ngx_queue_score)); Qscore->score = i; ngx_queue_init(&Qscore->Que); if(i%2) { ngx_queue_insert_tail(queue, &Qscore->Que); } else { ngx_queue_insert_head(queue, &Qscore->Que); } } printf("Before sort: "); print_ngx_queue(queue); ngx_queue_sort(queue, CMP); printf("After sort: "); print_ngx_queue(queue); ngx_destroy_pool(pool); return 0; } ~~~ 輸出結果： ~~~ $./queue_test Before sort: score: 8 6 4 2 1 3 5 7 9 After sort: score: 1 2 3 4 5 6 7 8 9 ~~~ ### 總結 ? ? ? 在 Nginx 的隊列鏈表中，其維護的是指向鏈表節點的指針，并沒有實際的數據區，所有對實際數據的操作需要我們自行操作，隊列鏈表實質是雙向循環鏈表，其操作是雙向鏈表的基本操作。