7.2.3　使用双向链表排序的例子

本节定义一个简单的链表，并使用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_ta,const ngx_queue_tb）

{

/首先使用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））

在4.2.2节中曾经提到过offsetof函数是如何实现的，即它会返回link成员在type结构体中的偏移量。例如，在上例中，可以通过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。如果有疑问，不妨写个遍历链表的程序检验一下顺序是否如此。下面就根据表7-1中的方法说明编写一段简单的遍历链表的程序。

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中列出的其他方法就不在这里一一举例了，使用方法非常相似。