摘要：源文件路徑版本主要作用分析是提供的雙向鏈表。同時，由于這種鏈表沒有節點成員變量，所以需要作為帶有節點變量的結構體的成員變量存在，這種情況下，稱這種鏈表為寄宿鏈表，鏈表所在結構體稱為宿主。和常規的雙向鏈表操作基本相同。

版本：1.8.0

srccoreNgx_queue.h
srccoreNgx_queue.c

ngx_queue_t是Nginx提供的雙向鏈表。

通常意義上的雙向鏈表是長成這個樣子的：

struct double_link_s {
    int            node;
    double_link_t *prev;
    double_link_t *next;
};

包含三個要素：節點數據data，指向前一個節點的指針prev及指向后一下節點的指針next。

然后就是老生常談的對于雙向鏈表的創建、插入、刪除等等。我就不詳說了，自行google即可。

其實，如果你仔細觀察一下，就會發現，對雙向鏈表的操作基本都是圍繞prev和next展開的，與節點數據data關系不大。

所以，將雙向鏈表的操作抽象出來，形成與鏈表節點無關的抽象可以幫助我們更好的去操作各種節點類型的雙向鏈表。

這種鏈表的特點是只有prev和next兩個變量，沒有表示鏈表節點的成員變量。因此，這種鏈表也被稱為輕量級鏈表。

同時，由于這種鏈表沒有節點成員變量，所以需要作為帶有節點變量的結構體的成員變量存在，這種情況下，稱這種鏈表為寄宿鏈表，鏈表所在結構體稱為宿主。

舉個栗子，就是長成這個樣子：

typedef double_link_s double_link_t;
struct double_link_s {
    double_link_t *prev;
    double_link_t *next;
};

struct node_s {
    int             node;
    double_link_t   link;
}

簡單來說，如果想將結構體作為鏈表節點，那么就將這種輕量級鏈表作為成員變量加入到自身。

示意圖如下：

這樣，操作鏈表就是操作鏈表中的輕量級鏈表，因此，可以定義出通用的鏈表結構。

在Nginx中，這個通用的雙向鏈表結構就是ngx_queue_t。這不是Nginx發明的，在Linux內核中也使用這種鏈表。

ngx_queue_t

根據上述分析，定義輕量級鏈表很簡單。

typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {
    ngx_queue_t  *prev;
    ngx_queue_t  *next;
};

既然是雙向鏈表，那么關于雙向鏈表的基本操作是相同的。所以，不需要多解釋，直接看源碼即可。

#define ngx_queue_init(q)                                                     
    (q)->prev = q;                                                            
    (q)->next = q

使用ngx_queue_t類型的變量q初始化鏈表，由于是初始化，因此prev和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

雖然宏的名字叫insert_head，實際上可以是插入的通用操作。所以，在源碼中有

#define ngx_queue_insert_after   ngx_queue_insert_head

這里跟正常的雙鏈表插入操作沒有區別。

采用寄宿鏈表，一個繞不開的問題就是，如何根據鏈表獲得節點的數據。

  
這里解決的基本思路如下：
  
  

寄宿鏈表是鏈表節點結構體的一個成員變量，雖然結構體可能因為對齊的問題使得各個成員變量在空間上不連續，但是，整個結構體本身仍然可以看作一塊連續的內存區域。
  
所以，可以利用offsetof宏計算出寄宿鏈表成員變量相對于結構體起始位置的偏移量

  
寄宿鏈表的起始地址 - 寄宿鏈表成員變量相對于結構體起始位置的偏移量 = 結構體的起始地址
  

所以，ngx_queue_t獲取節點數據就利用了上述方法

#define ngx_queue_data(q, type, link)                                         
    (type *) ((u_char *) q - offsetof(type, link))

其中q為寄宿鏈表變量，type為寄宿鏈表所在結構體的類型，link為寄宿鏈表在type結構體中的變量名。
這個宏返回宿主結構體的首地址。

這屬于雙向鏈表操作的老梗了，就是使用了雙指針，移動速度差一倍，速度快的指針到末尾時，速度慢的所在就是中間位置。

源碼如下

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);

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

當然，還有其他操作，比如排序，移除等等。和常規的雙向鏈表操作基本相同。
這里就不詳細描述了。