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成员的值）的升序排列了。
表7-1中列出的其他方法就不在这里一一举例了，使用方法非常相似。
双向链表是如何实现的
本节将说明ngx_queue_t链表容器以及元素中prev成员、next成员的意义，整个链表就是通过这两个指针成员实现的。
下面先来看一下ngx_queue_t结构体作为容器时其prev成员、next成员的意义。当容器为空时，prev和next都将指向容器本身。如下所示，如果在某个结构体中定义了ngx_queue_t容器，其prev指针和next指针都会指向ngx_queue_t成员的地址。
空容器时ngx_queue_t结构体成员的值
当容器不为空时，ngx_queue_t容器的next指针会指向链表的第1个元素，而prev指针会指向链表的最后1个元素。如下图所示，这时链表中只有1个链表元素，容器的next指针和prev指针都将指向这个唯一的链表元素。
当仅含1个元素时，容器、元素中的ngx_queue_t结构体成员的值
对于每个链表元素来说，其prev成员都指向前一个元素（不存在时指向链表容器），而next成员则指向下一个元素（不存在时指向链表容器），这如上可以看到。
当容器中有两个元素时，prev和next的指向如下图所示。
当含有两个或多个元素时，容器、元素中的ngx_queue_t结构体中prev、next成员的值
如上很好地诠释了前面的定义，容器中的prev成员指向最后1个也就是第2个元素，next成员指向第1个元素。第1个元素的prev成员指向容器本身，而其next成员指向第2个元素。第2个元素的prev成员指向第1个元素，其next成员则指向容器本身。
ngx_queue_t的实现就是这么简单，但它的排序算法ngx_queue_sort使用的插入排序，并不适合为庞大的数据排序。
本文暂取自网络或书籍，只用作学习备忘，不作盈利等他用，如有侵权，请联系Linkerist@163.com
