nginx 队列结构 ngx_queue_t  介绍

由于nginx 具有跨平台及C语言实现的特点，使nginx不宜使用一些第三方中间件提供的容器和算法，跨平台(linux,windows等)的特点，

因此nginx的代码必须可以跨平台编译运行，nginx选择了完全从头实现一遍基础的数据结构和算法,比如双向链表、动态数组、红黑树、

哈希表等，理解这些基础的数据结构和算法对于我们好处不言而喻。

src/core/ngx_queue.{c|h} 实现了一个双向链表的基础顺序容器。

 Nginx_queue_t 双向链表是nginx提供的轻量级链表容器,它与nginx内存池无关,因此这个链表容器不负责分配内存来存放链表元素。

其中，链表作为顺序容器的特点有: 可以高效的执行插入、删除、合并等操作。

ngx_queue_t 容器的优势在于:

一个纯粹的双向链表，它不负责链表元素所占内存的分配，与Nginx封装的ngx_pool_t内存池完全无关；

具有排序功能；

支持两个链表间的合并；

Nginx 队列的基本结构

nginx的队列是由具有头节点的双向循环链表实现的，每一个节点结构为ngx_queue_t

typedef struct ngx_queue_s  ngx_queue_t;

struct ngx_queue_s {

   ngx_queue_t  *prev;   //前一个

   ngx_queue_t  *next;   //下一个

};

在32位的操作系统上，显然sizeof(ngx_queue_t)=8。

从ngx_queue_t结构定义可以看出，nginx的队列结构里并没有节点的数据内容(Linux内核中的page管理同样也使用到了这样的链接结构)，

可见这不同于教科书中将链表节点的数据成员声明在链表节点的结构体中，这也是C抽象编程的一种技法。

nginx的队列操作和结构只进行指针操作，不负责节点内容空间的分配和保存，所以在定义自己的队列节点的时候，需要自己定义数据结构

并分配空间，并且在其中包含一个ngx_queue_t的指针或者对象，需要获得原始的数据节点的时候，需要使用ngx_queue_data宏：

 #definengx_queue_data(q, type, link)      (type*) ((u_char *) q – offsetof(type, link)) 

关于这个宏的妙用，在我之前的一篇博客中也用介绍，详情请移步 这里 。这里的目的是怎么通过某个struct  结构体中的某一个变量来获取

整个结构的变量？由ngx_queue_data定义可以看出，一般定义队列节点结构(该结构类型为type)时，type类型的结构体中需要定义一个

ngx_queue_t类型的成员，其中offsetof主要用于求结构体中一个成员在该结构体中的偏移量，第一个参数type是结构体的名字，第二个参

数link是结构体成员的名字,注意计算整个节点结构的起始地址(需要进行类型转换)。

基本操作

下面介绍 nginx 中 ngx_queue_t 的相关基本操作。

queue 结构定义了一个 sentinel(哨兵) 节点, 他指向队列的头部,它的定义如下:

#define  ngx_queue_sentinel(h)                  (h)

一些最基本操作如下(比较容易理解，不再敷述):

ngx_queue_head 得到头节点

#define ngx_queue_head(h)               (h)->next

ngx_queue_last 得到尾节点

#define ngx_queue_last(h)               (h)->prev

ngx_queue_next 得到节点的下一个节点

#define ngx_queue_next(q)            (q)->next

ngx_queue_prev 得到节点的上一个节点

#define ngx_queue_prev(q)                         (q)->prev

下面介绍一些相对复杂的操作:

ngx_queue_init初始化队列

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

ngx_queue_empty判断队列是否为空

#define ngx_queue_empty(h)              (h == (h)->prev)

ngx_queue_insert_head在头节点之后插入新节点

#define ngx_queue_insert_head(h, x)                                           \

   (x)->next = (h)->next;                                                   \

   (x)->next->prev = x;                                                      \

   (x)->prev = h;                                                           \

   (h)->next = x

逻辑如下图:

             

ngx_queue_insert_after在指定节点之后插入新节点

#define ngx_queue_insert_after   ngx_queue_insert_head

ngx_queue_insert_tail 在尾节点之后插入新节点。

#define ngx_queue_insert_tail(h, x)                                           \

   (x)->prev = (h)->prev;                                                   \

   (x)->prev->next = x;                                                     \

   (x)->next = h;                                                           \

(h)->prev = x

可以画图理解尾插法的方法和头插法异曲同工。

ngx_queue_remove 删除队列中的某一个节点

#define ngx_queue_remove(x)                                                   \
    (x)->next->prev = (x)->prev;                                              \
    (x)->prev->next = (x)->next;                                              \
    (x)->prev = NULL;                                                         \
    (x)->next = NULL

逻辑如下图：

         

ngx_queue_split分割队列

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

ngx_queue_split有3个参数，h为队列头(即链表头指针)，将该队列从q节点将队列分割为两个队列，q之后的节点组成的新队列的头节点为n，图形演示如下。

         

ngx_queue_add 链接队列

#define ngx_queue_add(h, n)                                                   \
    (h)->prev->next = (n)->next;                                              \
    (n)->next->prev = (h)->prev;                                              \
    (h)->prev = (n)->prev;                                                    \
    (h)->prev->next = h;

在此不在敷述，可以自己画图理解。

ngx_queue_middle获取队列的中间节点

若队列有奇数个节点（除头节点外），则返回中间的节点，若队列有偶数个节点，则返回后半个队列的第一个节点。

算法的基本思想: middle指针每次后移一个节点，而next指针每次后移两个节点。

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

ngx_queue_sort 排序队列(稳定的插入排序) 

从第一个节点开始遍历，依次将当前节点q插入到前面已经排好序的队列链表中。

函数声明如下:

Void ngx_queue_sort(ngx_queue_t *queue, ngx_int_t(*cmp)(const ngx_queue_t *, const ngx_queue_t *))

可见这个函数参数中包含一个回调函数，这个回调函数用于链表中两个元素大小比较。熟悉插入排序应该很容易理解这个链表排序算法。

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);
        ngx_queue_remove(q);
        do {
            if (cmp(prev, q) <= 0) {//比较节点
                break;
            }
            prev = ngx_queue_prev(prev);
        } while (prev != ngx_queue_sentinel(queue));// 哨兵节点
        ngx_queue_insert_after(prev, q);//依次将节点插入到已经排好序的队列链表中
    }
}

测试

通过上面的分析，我们知道要想利用nginx 基本数据结构 ngx_queue_t，那么我们的结构体 必须是如下形式的结构体。

即包含变量ngx_queue_t，如图所示。

     

我们自定义一个结构体, 形式如下:

typedef struct
{
    int key;
    char name[32];
    ngx_queue_t link;
}ngx_qTest_t;

在这个结构体中 定义了 编号、名字.

然后根据结构体自定义 ngx_queue的序函数中的回调函数。

// 从大到小的顺序
ngx_int_t cmp(const ngx_queue_t *a, const ngx_queue_t *b)
{
    ngx_qTest_t *aTest = ngx_queue_data(a, ngx_qTest_t, link);
    ngx_qTest_t *bTest = ngx_queue_data(b, ngx_qTest_t, link);
    return aTest->key < bTest->key;
}

main 函数如下：

int main()
{
    ngx_qTest_t arr[5];
    ngx_queue_t head;
    ngx_queue_init(&head);
    int i=0;
    for( ; i<5; ++i)//初始化 队列
    {
        arr[i].key = i;
        sprintf(arr[i].name, "\"My key is:%d.\"", arr[i].key);
        if(i%2)
        {
            ngx_queue_insert_head(&head, &arr[i].link);
        }
        else
        {
            ngx_queue_insert_tail(&head, &arr[i].link);
        }
    }
    printf("*******************************\n");
    printf("Before sort:\n");
    print_queue(&head);
    ngx_queue_sort(&head, cmp);
    printf("*******************************\n");
    printf("After sort:\n");
    print_queue(&head);

    ngx_queue_t * midq = ngx_queue_middle(&head);
    ngx_qTest_t *mid_data = ngx_queue_data(midq, ngx_qTest_t, link);
    printf("*******************************\n");
    // 求取中间节点
    printf("%The middle key is %d.\n", mid_data->key);
    return 0;
}

测试结果如图:

        

完整代码参见 github 点我.

参考：

深入理解 nginx

http://blog.csdn.net/livelylittlefish/article/details/6607324

http://blog.csdn.net/ordeder/article/details/17058399