首页 > 代码库 > 菜鸟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
初始状态的链表如图所示：
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
标准的双链表插入四步操作，如图所示：
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为首元素，操作也很简单，如图所示：
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的尾部，如图所示：
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: }
输出结果：
16.总结
ngx_queue设计非常精巧，基本涵盖了双链表的所有操作，建议需要面试的童鞋看一看，很多链表的题目都迎刃而解。此外，ngx_queue与其它nginx 代码耦合度低，有需要这种双向链表的实现时不妨直接拿过来使用。
-
Echo Chen：Blog.csdn.net/chen19870707
-
菜鸟nginx源码剖析数据结构篇（二） 双向链表ngx_queue_t