首页 > 代码库 > 菜鸟nginx源码剖析数据结构篇(二) 双向链表ngx_queue_t[转]

菜鸟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.数据结构定义

     

       1: typedef struct ngx_queue_s  ngx_queue_t;
       2:  
       3: struct ngx_queue_s {
       4:     ngx_queue_t  *prev;
       5:     ngx_queue_t  *next;
       6: };

     

        可以看到,它的结构非常简单,仅有两个成员:prev、next,这样对于链表中元素来说,空间上只增加了两个指针的消耗。

     

    4.初始化ngx_queue_init

     

       1: //q 为链表容器结构体ngx_queue_t的指针,将头尾指针指向自己
       2: #define ngx_queue_init(q)                                                     \
       3:     (q)->prev = q;                                                            \
       4:     (q)->next = q

     

    初始状态的链表如图所示:

    image

     

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

     

    判断方法非常简单,即判断链表的prev指针是否指向自己,如上图所示

       1: #define ngx_queue_empty(h)                                                    \
       2:     (h == (h)->prev)

     

     

    6.头部插入ngx_queue_insert_head

     

       1: //h为链表指针,x为要插入的元素
       2: #define ngx_queue_insert_head(h, x)                                           \
       3:     (x)->next = (h)->next;                                                    \
       4:     (x)->next->prev = x;                                                      \
       5:     (x)->prev = h;                                                            \
       6:     (h)->next = x

     

    标准的双链表插入四步操作,如图所示:

    image

     

    7.尾部插入ngx_queue_insert_tail

     

    与头部插入类似,只是第一步给的h->prev ,即为最后一个结点:

     

       1: #define ngx_queue_insert_tail(h, x)                                           \
       2:     (x)->prev = (h)->prev;                                                    \
       3:     (x)->prev->next = x;                                                      \
       4:     (x)->next = h;                                                            \
       5:     (h)->prev = x

     

    8.链表删除ngx_queue_remove

     

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

     

       1: #define ngx_queue_remove(x)                                                   \
       2:     (x)->next->prev = (x)->prev;                                              \
       3:     (x)->prev->next = (x)->next
       4:  

     

    9.链表拆分ngx_queue_split

     

       1: #define ngx_queue_split(h, q, n)                                              \
       2:     (n)->prev = (h)->prev;                                                    \
       3:     (n)->prev->next = n;                                                      \
       4:     (n)->next = q;                                                            \
       5:     (h)->prev = (q)->prev;                                                    \
       6:     (h)->prev->next = h;                                                      \
       7:     (q)->prev = n;

     

    h为链表容器,q为链表h中的一个元素,这个方法可以将链表h以元素q为界拆分为两个链表h和n,其中h由原链表的前半部分组成(不包含q),而n由后半部分组成,q为首元素,操作也很简单,如图所示:

    048644D883FB5C91A33920AE9345A329

     

    10.链表合并ngx_queue_add

     

       1: #define ngx_queue_add(h, n)                                                   \
       2:     (h)->prev->next = (n)->next;                                              \
       3:     (n)->next->prev = (h)->prev;                                              \
       4:     (h)->prev = (n)->prev;                                                    \
       5:     (h)->prev->next = h;

     

    将链表n 合并到链表h的尾部,如图所示:

    8DBB8AC04328FBB9A11F0F4A856E65EA

     

    11. 链表中心元素ngx_queue_middle

     

       1: ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue)
       2: {
       3:     ngx_queue_t  *middle, *next;
       4:  
       5:     middle = ngx_queue_head(queue);
       6:     
       7:     //头尾相等,空链表,返回头即可
       8:     if (middle == ngx_queue_last(queue)) {
       9:         return middle;
      10:     }
      11:  
      12:     next = ngx_queue_head(queue);
      13:  
      14:     for ( ;; ) {
      15:         middle = ngx_queue_next(middle);
      16:         next = ngx_queue_next(next);
      17:  
      18:         if (next == ngx_queue_last(queue)) {
      19:             return middle;
      20:         }
      21:         
      22:         next = ngx_queue_next(next);
      23:  
      24:         if (next == ngx_queue_last(queue)) {
      25:             return middle;
      26:         }
      27:     }
      28: }

     

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

     

     

    12.链表排序ngx_queue_sort

     

    可以看到,这里采用的是插入排序算法,时间复杂度为O(n),整个代码非常简洁。

       1: void ngx_queue_sort(ngx_queue_t *queue, ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *))
       2: {
       3:     ngx_queue_t  *q, *prev, *next;
       4:  
       5:     q = ngx_queue_head(queue);
       6:  
       7:     //如果是空链表,直接返回
       8:     if (q == ngx_queue_last(queue)) {
       9:         return;
      10:     }
      11:  
      12:     for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = next) {
      13:  
      14:         prev = ngx_queue_prev(q);
      15:         next = ngx_queue_next(q);
      16:  
      17:         ngx_queue_remove(q);
      18:  
      19:         //找到插入位置
      20:         do {
      21:             if (cmp(prev, q) <= 0) {
      22:                 break;
      23:             }
      24:  
      25:             prev = ngx_queue_prev(prev);
      26:  
      27:         } while (prev != ngx_queue_sentinel(queue));
      28:  
      29:         //插入
      30:         ngx_queue_insert_after(prev, q);
      31:     }
      32: }

     

    13.根据ngx_queue_t 找到链表元素

     

       1: #define ngx_queue_data(q, type, link)                                         \
       2:     (type *) ((u_char *) q - offsetof(type, link))

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

     

     

    14.其它方法

     

       1: #define ngx_queue_head(h)                                                     \
       2:     (h)->next
       3:  
       4:  
       5: #define ngx_queue_last(h)                                                     \
       6:     (h)->prev
       7:  
       8:  
       9: #define ngx_queue_sentinel(h)                                                 \
      10:     (h)
      11:  
      12:  
      13: #define ngx_queue_next(q)                                                     \
      14:     (q)->next
      15:  
      16:  
      17: #define ngx_queue_prev(q)                                                     \
      18:     (q)->prev

     

    15.实战

     

       1: #include <iostream>
       2: #include <algorithm>
       3: #include <pthread.h>
       4: #include <time.h>
       5: #include <stdio.h>
       6: #include <errno.h>
       7: #include <string.h>
       8: #include "ngx_queue.h"
       9:  
      10: struct student_info
      11: {
      12:    long stu_id;
      13:    unsigned int age;
      14:    unsigned int score;
      15:    ngx_queue_t qEle;
      16: };
      17:  
      18: ngx_int_t compareStudent(const ngx_queue_t *a, const ngx_queue_t *b)
      19: {
      20:     //分别取得a b 对象指针
      21:     student_info *ainfo = ngx_queue_data(a,student_info,qEle);
      22:     student_info *binfo = ngx_queue_data(b,student_info,qEle);
      23:  
      24:     return ainfo->score >binfo->score;
      25: }
      26:  
      27: void print_ngx_queue(ngx_queue_t *queue)
      28: {
      29:     //遍历输出
      30:     for(ngx_queue_t *q = ngx_queue_head(queue);q != ngx_queue_sentinel(queue);q = ngx_queue_next(q))
      31:     {
      32:         student_info *info = ngx_queue_data(q,student_info,qEle);
      33:         if(info != NULL)
      34:         {
      35:             std::cout <<info->score << "  ";
      36:         }
      37:     }
      38:  
      39:     std::cout << std::endl;
      40: }
      41:  
      42: int main()
      43: {
      44:  
      45:     ngx_queue_t queue;
      46:     ngx_queue_init(&queue);
      47:  
      48:     student_info info[5];
      49:     for(int i = 0;i < 5;i++)
      50:     {
      51:         info[i].stu_id = i;
      52:         info[i].age = i;
      53:         info[i].score = i;
      54:  
      55:         if(i%2)
      56:         {
      57:             ngx_queue_insert_tail(&queue,&info[i].qEle);
      58:         }
      59:         else
      60:         {
      61:             ngx_queue_insert_head(&queue,&info[i].qEle);
      62:         }
      63:     }
      64:  
      65:     print_ngx_queue(&queue);
      66:  
      67:     ngx_queue_sort(&queue,compareStudent);
      68:  
      69:     print_ngx_queue(&queue);
      70:  
      71:     return 0;
      72: }

     

    输出结果:

    image

     

    16.总结

         

           ngx_queue设计非常精巧,基本涵盖了双链表的所有操作,建议需要面试的童鞋看一看,很多链表的题目都迎刃而解。此外,ngx_queue与其它nginx 代码耦合度低,有需要这种双向链表的实现时不妨直接拿过来使用。

     

    -

菜鸟nginx源码剖析数据结构篇(二) 双向链表ngx_queue_t[转]