新秀nginx源代码分析数据结构篇（两） 双链表ngx_queue_t

 

nginx源代码分析数据结构篇（两） 双链表ngx_queue_t

Author：Echo Chen（陈斌）

Email：chenb19870707@gmail.com

Blog：Blog.csdn.net/chen19870707

Date：October 20h, 2014

1.ngx_queue优势和特点

ngx_queue作为顺序容器链表。它优势在于其能够高效地运行插入、删除、合并操作，在插入删除的过程中，仅仅须要改动指针指向。而不须要拷贝数据，因此。对于频繁改动的容器非常适合。

此外，相对于STL list，它还具有下面特点：

• 自身实现了排序功能
• 轻量级，不负责内存的分配
• 自身支持两个链表的合并

2.源码位置

头文件：http://trac.nginx.org/nginx/browser/nginx/src/core/ngx_queue.h

源文件：http://trac.nginx.org/nginx/browser/nginx/src/core/ngx_queue.c

3.数据结构定义

typedef struct ngx_queue_s  ngx_queue_t;

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

    能够看到，它的结构很easy，仅有两个成员：prev、next。这样对于链表中元素来说，空间上仅仅添加了两个指针的消耗。

4.初始化ngx_queue_init

//q 为链表容器结构体ngx_queue_t的指针，将头尾指针指向自己
#define ngx_queue_init(q)
    (q)->prev = q;
    (q)->next = q

初始状态的链表如图所看到的：

5.推断链表容器是否为空ngx_queue_empty

推断方法很easy，即推断链表的prev指针是否指向自己。如上图所看到的

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

6.头部插入ngx_queue_insert_head

//h为链表指针，x为要插入的元素
#define ngx_queue_insert_head(h, x)
    (x)->next = (h)->next;
    (x)->next->prev = x;
    (x)->prev = h;
    (h)->next = x

标准的双链表插入四步操作，如图所看到的：

7.尾部插入ngx_queue_insert_tail

与头部插入类似，仅仅是第一步给的h->prev 。即为最后一个结点：

#define ngx_queue_insert_tail(h, x)
    (x)->prev = (h)->prev;
    (x)->prev->next = x;
    (x)->next = h;
    (h)->prev = x

8.链表删除ngx_queue_remove

x为要删除的结点，将x的下一个的结点的prev指针指向x的上一个结点，再将x的前一个结点的next指针指向x的下一个结点。常规链表双链表结点删除操作，不处理内存释放

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

9.链表拆分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;

h为链表容器，q为链表h中的一个元素。这种方法能够将链表h以元素q为界拆分为两个链表h和n，当中h由原链表的前半部分组成（不包括q）。而n由后半部分组成。q为首元素，操作也非常easy，如图所看到的：

10.链表合并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;

将链表n 合并到链表h的尾部，如图所看到的：

11. 链表中心元素ngx_queue_middle

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

这里用到的技巧是每次middle向后移动一步，next向后移动两步，这样next指到队尾的时候，middle就指到了中间，时间复杂度就是O(N)，这是一道经典的面试题。今天在这里看到了源代码，似成相识啊，果然经典面试题目都不是凭空而来。

12.链表排序ngx_queue_sort

能够看到，这里採用的是插入排序算法。时间复杂度为O(n)。整个代码很简洁。

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

 

13.依据ngx_queue_t 找到链表元素

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

当中q为ngx_queue_t* 类型。函数作用为依据q算出。算出链表元素的地址，当中linux接口offsetof是算出link在type中的偏移。

14.其他方法

#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

15.实战

#include <iostream>
#include <algorithm>
#include <pthread.h>
#include <time.h>
#include <stdio.h>
#include <errno.h>
#include <string.h>
#include "ngx_queue.h"

struct student_info
{
   long stu_id;
   unsigned int age;
   unsigned int score;
   ngx_queue_t qEle;
};

ngx_int_t compareStudent(const ngx_queue_t *a, const ngx_queue_t *b)
{
    //分别取得a b 对象指针
    student_info *ainfo = ngx_queue_data(a,student_info,qEle);
    student_info *binfo = ngx_queue_data(b,student_info,qEle);

    return ainfo->score >binfo->score;
}

void print_ngx_queue(ngx_queue_t *queue)
{
    //遍历输出
    for(ngx_queue_t *q = ngx_queue_head(queue);q != ngx_queue_sentinel(queue);q = ngx_queue_next(q))
    {
        student_info *info = ngx_queue_data(q,student_info,qEle);
        if(info != NULL)
        {
            std::cout <<info->score << "  ";
        }
    }

    std::cout << std::endl;
}

int main()
{

    ngx_queue_t queue;
    ngx_queue_init(&queue);

    student_info info[5];
    for(int i = 0;i < 5;i++)
    {
        info[i].stu_id = i;
        info[i].age = i;
        info[i].score = i;

        if(i%2)
        {
            ngx_queue_insert_tail(&queue,&info[i].qEle);
        }
        else
        {
            ngx_queue_insert_head(&queue,&info[i].qEle);
        }
    }

    print_ngx_queue(&queue);

    ngx_queue_sort(&queue,compareStudent);

    print_ngx_queue(&queue);

    return 0;
}

输出结果：

16.总结

     

       ngx_queue设计非常静止，基本涵盖了双链表的全部操作，建议须要面试的童鞋看一看，非常多链表的题目都迎刃而解。此外，ngx_queue与其他nginx 代码耦合度低，有须要这样的双向链表的实现时最好还是直接拿过来使用。

-

Echo Chen：Blog.csdn.net/chen19870707

-

版权声明：本文博客原创文章。博客，未经同意，不得转载。