原文链接: http://blog.csdn.net/ordeder/article/details/17058399
1. 背景
Nginx双向链表ngx_queue_t是采用"寄宿"在元素中的包含prev和next的ngx_queue_s来实现的。Linux内核中的page管理同样也使用到了这样的链接结构。linux内核情景分析 这样描述道:linux内核作者将prev和next从具体的“宿主”数据结构中抽象成为一个结构体list_head,这样list_head就可以成为该“宿主”的“连接件”。(kernel:include/linux/list.h , include/linux/mm.h )
采用ngx_quque_t来构建双向链表,可以将链表的链接操作相关的数据结构抽象出来,这样有利于进行链表操作函数的编写。其次,用ngx_queue_t结构串接起来的链表可以是不同类型的数据类型(只要这个数据类型包含ngx_quque_t这个数据结构)。打个不恰当的比喻,不管什么样的物品(数据类型),只要物品上有个孔(ngx_quque_t)我们就能用线(ngx_queue_t构成的链)将这些物品串起来。再者,对于链表而言,进行排序,移动元素等操作只需要修改ngx_queue_t中的相关指针即可,所以也称Nginx的双向链表结构为轻量级链表。
2. ngx_queue_t源码
(源码主要注释来自github),为了在VC6.0下能够正常运行,该段源码的部分数据类型定义的参数已被我重新定义(源码已标注)
//ngx_queue.h #ifndef _NGX_QUEUE_H_INCLUDED_ #define _NGX_QUEUE_H_INCLUDED_ //add by ordeder #define ngx_int_t int #define u_char unsigned int //自定义offsetof //http://blog.csdn.net/ordeder/article/details/10226427 #define offsetof(struct_type, member) ((size_t) &((struct_type *) 0)->member) typedef struct ngx_queue_s ngx_queue_t; //end of "add by ordeder" //参考: //http://blog.csdn.net/livelylittlefish/article/details/6607324 struct ngx_queue_s { ngx_queue_t *prev; //前一个 ngx_queue_t *next; //下一个 }; //初始化队列 #define ngx_queue_init(q) \ (q)->prev = q; \ (q)->next = q //判断队列是否为空 #define ngx_queue_empty(h) \ (h == (h)->prev) //在头节点之后插入新节点 #define ngx_queue_insert_head(h, x) \ (x)->next = (h)->next; \ (x)->next->prev = x; \ (x)->prev = h; \ (h)->next = x #define ngx_queue_insert_after ngx_queue_insert_head //在尾节点之后插入新节点 #define ngx_queue_insert_tail(h, x) \ (x)->prev = (h)->prev; \ (x)->prev->next = x; \ (x)->next = h; \ (h)->prev = x //头节点 #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 #if (NGX_DEBUG) //删除节点 #define ngx_queue_remove(x) \ (x)->next->prev = (x)->prev; \ (x)->prev->next = (x)->next; \ (x)->prev = NULL; \ (x)->next = NULL #else #define ngx_queue_remove(x) \ (x)->next->prev = (x)->prev; \ (x)->prev->next = (x)->next #endif //分隔队列 #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; //链接队列 #define ngx_queue_add(h, n) \ (h)->prev->next = (n)->next; \ (n)->next->prev = (h)->prev; \ (h)->prev = (n)->prev; \ (h)->prev->next = h; //获取队列中节点数据, q是队列中的节点,type队列类型,link是队列类型中ngx_queue_t的元素名 #define ngx_queue_data(q, type, link) \ (type *) ((u_char *) q - offsetof(type, link)) //队列的中间节点 ngx_queue_t *ngx_queue_middle(ngx_queue_t *queue); void ngx_queue_sort(ngx_queue_t *queue, ngx_int_t (*cmp)(const ngx_queue_t *, const ngx_queue_t *)); #endif /* _NGX_QUEUE_H_INCLUDED_ */
3. VC6.0下的测试驱动
以下是一个测试,我将nginx中的关于ngx_queue_t相关源码作为一个.h头文件,在vc中定义了两个不同类型的结构体进行测试,测试思路为:定义两个不同类型的结构体book和journal,他们都包含ngx_queue_t这个结构。测试中将这两个不同类型的对象用一个ngx链串接起来,然后根据ISBN对链表中的对象进行排序。
//ngx_queue.c 测试用例 #include "ngx_queue.h" #include <stdio.h> /////////////////////一下两个函数来自 source code: ngx_quque.c 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; } } } /* the stable insertion sort */ 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); } } //以下代码为测试用例 struct Book_s{ ngx_queue_t qLink; int type; int ISBN; }; struct Journal_s{ ngx_queue_t qLink; int type; int ISBN; //前三个元素的定义顺序和book相同,为了ngx_queue_data()中统一使用Boot_t来获取元素指针 int price; //相比book,增多的一个元素,这里为了和book结构体不同而添加的 }; typedef struct Book_s Boot_t; typedef struct Journal_s Journal_t; #define N 3 ngx_int_t book_ISBN_cmp(const ngx_queue_t *a, const ngx_queue_t *b) { Boot_t* pBook_a = ngx_queue_data(a,Boot_t,qLink); Boot_t* pBook_b = ngx_queue_data(b,Boot_t,qLink); return pBook_a->ISBN > pBook_b->ISBN; } int main() { Boot_t book[N]; Journal_t journal[N]; int i; ngx_queue_t queueContainer; ngx_queue_init(&queueContainer); for (i=0;i<N;i++) { book[i].ISBN = i; book[i].type = 0; journal[i].ISBN = i+N; journal[i].type = 1; journal[i].price = 100 + i; ngx_queue_insert_head(&queueContainer,&book[i].qLink); ngx_queue_insert_tail(&queueContainer,&journal[i].qLink); } ngx_queue_t *q; Boot_t* pBook; Journal_t * pJournal; for (q = ngx_queue_head(&queueContainer); q != ngx_queue_sentinel(&queueContainer); q = ngx_queue_next(q)) { pBook = (Boot_t*) (ngx_queue_data(q,Boot_t,qLink)); if (pBook->type == 0) //Book { printf("book isbn:%d \n",pBook->ISBN); } else if(pBook->type == 1) //journal { pJournal = (Journal_t *) pBook; printf("journal isbn:%d price:%d\n",pJournal->ISBN,pJournal->price); } } //将queueContainer按照ISBN排序 ngx_queue_sort(&queueContainer,book_ISBN_cmp); printf("\nAfter sort by ISBN\n"); for (q = ngx_queue_head(&queueContainer); q != ngx_queue_sentinel(&queueContainer); q = ngx_queue_next(q)) { pBook = (Boot_t*) (ngx_queue_data(q,Boot_t,qLink)); if (pBook->type == 0) //Book { printf("book isbn:%d \n",pBook->ISBN); } else if(pBook->type == 1) //journal { pJournal = (Journal_t *) pBook; printf("journal isbn:%d price:%d\n",pJournal->ISBN,pJournal->price); } } return 0; }
4. 测试结果及其分析
4.1测试输出如下:
Content of queue as flows
book isbn:2
book isbn:1
book isbn:0
journal isbn:3 price:100
journal isbn:4 price:101
journal isbn:5 price:102
After sort by ISBN
book isbn:0
book isbn:1
book isbn:2
journal isbn:3 price:100
journal isbn:4 price:101
journal isbn:5 price:102
4.2 分析
下图给出了将book和journal插入链表后,排序前各个数据对象在链表中的数据关系。由于book和journal是数组,所以采用连续空间表示。存储空间中不同颜色的去域块代表不同的数据对象。从图可以看出,qLink数据构成了宿主数据的链接关系,真是堪比一条绳索,将各个数据对象链接起来。queueContainer作为链表的表头,不寄宿到数据对象,他是作为整个双链表的哨兵,标志处表头和表尾所在的位置。