nginx学习六 高级数据结构之双向链表ngx_queue_t

  1 简介

  是nginx提供的一个轻量级的双向链表容器，它不负责存储数据，既不提供数据的内存分配，它只有两个指针负责把数据链入链表，它跟stl提供的queue不同，stl提供的queue帮助用户存储数据，用户只需要相容器里添加数据即可，而,用户必须自己提供存储数据的内存，并且必须定义一种数据结构把包含在其中，然后利用提供的函数来进行相应的操作。

  2 结构及其操作

  2.1

   struct ngx_queue_s {

        ngx_queue_t  *prev;
        ngx_queue_t  *next;
    };

  只提供一个指向前驱和一个指向后继的指针，结构非常简单，这也是其能够通用性的原因。

  2.2 操作函数

   ngx_queue_init(q) //初始化链表

    ngx_queue_empty(h)           //判断链表是否为空                                                   
    ngx_queue_insert_head(h, x)  //在头部插入一个元素                                       
    ngx_queue_insert_after       //在h元素前面插入一个元素
    ngx_queue_insert_tail(h, x)  //在h尾部插入一个元素 
    ngx_queue_head(h)            //返回第一个元素
    #define ngx_queue_last(h)    //返回最后一个元素 
    ngx_queue_sentinel(h)        //返回链表容器结构体的指针
    ngx_queue_next(q)            //返回下一个q的下一个元素  
    ngx_queue_prev(q)            //返回q的前一个元素
    ngx_queue_remove(x)          //删除x结点                                           
    ngx_queue_split(h, q, n)     //把h分为两个链表h和n，并且n的第一元素为q
    ngx_queue_add(h, n)          //把链表n增加到h链表的尾部

  提供了14个常用的操作给用户使用，基本涵盖了插入、删除、移动双向链表结构，访问数据等等操作，这14个函数都是宏定义，有兴趣的可以看下源码，非常简单。这里说一个最后一个操作函数:

   #define ngx_queue_data(q, type, link) \

        (type *) ((u_char *) q - offsetof(type, link))

  q为的指针， type是用户自定义的包含的数据类型type，link是type的成员，类型是。

  这里举个列子来说明这个操作的用法。

  先看一个自定义的结构体：

   typedef struct

    {
        ngx_int_t num;
        ngx_str_t str;
        ngx_queue_t queue;

  如果我们有一个的指针q指向.queue,现在我们不知到的地址，只知道queue，如果我们想访问里面的成员num，我们必须知道的地址，这样才能访问其num成员。怎样知道的地址呢？这时候就闪亮登场了。我们可以用一下语句来取得的地址：

  TestNode* testnode = ngx_queue_data(q, TestNode, queue);

  这样我们就可以访问num了。

  2.3

  这个函数取出链表中间位置的节点。用一个慢指针midlle和一个快指针next,middle没走一步双向链表结构，next走两步，当next指针到达链表未的时候，midlle就指向链表的中间位置。

   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每前进 一步，next都要前进两步，直到链表的尾部
            middle = ngx_queue_next(middle);
            next = ngx_queue_next(next);
    <p>![双向链表结构_双向动态链表元素删除_掺铒光纤放大器双向泵浦结构][1]

            if (next == ngx_queue_last(queue)) {
                return middle;
            }
            next = ngx_queue_next(next);
            if (next == ngx_queue_last(queue)) {
                return middle;
            }
        }

   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) num > right_node->num;
    }
    int main()
    {
        ngx_queue_t QueHead;
        ngx_queue_init(&QueHead);
        TestNode Node[10];
        ngx_int_t i;
        for (i=0; inum);
        }
        ngx_queue_sort(&QueHead, compare_node);
        
        printf("\n");
        for (q = ngx_queue_head(&QueHead); q != ngx_queue_sentinel(&QueHead); q = ngx_queue_next(q))
        {
            TestNode* Node = ngx_queue_data(q, TestNode, queue);
            printf("Num=%d\n", Node->num);
        }
        
        return 0;