Nginx 隊列雙向鏈表結構 ngx_queue_t
隊列鏈表結構
隊列雙向循環鏈表實現文件：文件：src/core/ngx_queue.h/.c。在 Nginx 的隊列實現中，實質就是具有頭節點的雙向循環鏈表，這裡的雙向鏈表中的節點是沒有數據區的，只有兩個指向節點的指針。需注意的是隊列鏈表的內存分配不是直接從內存池分配的，即沒有進行內存池管理，而是需要我們自己管理內存，所有我們可以指定它在內存池管理或者直接在堆裡面進行管理，最好使用內存池進行管理。節點結構定義如下：
隊列鏈表操作
其基本操作如下：
下面是隊列鏈表操作源碼的實現：
初始化鏈表
獲取指定的隊列鏈表中的節點
插入節點
在頭節點之後插入新節點：
插入節點比較簡單，只是修改指針的指向即可。下圖是插入節點的過程：注意：虛線表示斷開連接，實線表示原始連接，破折線表示重新連接，圖中的數字與源碼步驟相對應。
下圖是插入節點的過程：
刪除節點
刪除指定的節點，刪除節點只是修改相鄰節點指針的指向，並沒有實際將該節點的內存釋放，內存釋放必須由我們進行處理。
刪除節點過程如下圖所示：
拆分鏈表
該宏有 3 個參數，h 為隊列頭(即鏈表頭指針)，將該隊列從 q 節點將隊列(鏈表)拆分為兩個隊列(鏈表)，q 之後的節點組成的新隊列的頭節點為 n 。鏈表拆分過程如下圖所示：
合併鏈表
獲取中間節點
鏈表排序
隊列鏈表排序採用的是穩定的簡單插入排序方法，即從第一個節點開始遍歷，依次將當前節點(q)插入前面已經排好序的隊列(鏈表)中，下面程序中，前面已經排好序的隊列的尾節點為prev。操作如下：
獲取隊列中節點數據地址
由隊列基本結構和以上操作可知，nginx 的隊列操作只對鏈表指針進行簡單的修改指向操作，並不負責節點數據空間的分配。因此，用戶在使用nginx隊列時，要自己定義數據結構並分配空間，且在其中包含一個 ngx_queue_t 的指針或者對象，當需要獲取隊列節點數據時，使用ngx_queue_data宏，其定義如下：
測試程序：
main函數
輸出結果：
總結
在 Nginx 的隊列鏈表中，其維護的是指向鏈表節點的指針，並沒有實際的數據區，所有對實際數據的操作需要我們自行操作，隊列鏈表實質是雙向循環鏈表，其操作是雙向鏈表的基本操作。
閱讀更多 七度猿人見聞 的文章
