ng_queue_t是nginx提供的一个顺序容器，它以双向链表的方式将数据组织在一起。
链表作为顺序容器的优势在于，它可以高效的执行插入、删除、合并等操作，在移动链表中的元素时只需要修改指针的指向，因此，它很适合频繁修改容器的场合。
相对于其他顺序容器，它的优势有以下三点：
（1） 实现了排序功能，采用额是插入排序，虽然不太适合超大规模数据的排序，但是简单实用。
（2） 它非常轻量级，不负责链表元素所占内存的分配。ngx_queue_t只是把这些分配号内存的元素用双向链表链接起来
（3） 支持两个链表的合并。
Nginx在设计这个双向链表时，由于容器与元素共用了ngx_queue_t结构体，为了避免此结构体成员的意义混乱，Nginx封装了链表容器与元素的所有方法。
ngx_queue_t的头文件：
typedef struct ngx_queue_s ngx_queue_t;
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的下一个元素
(q)->next
#define ngx_queue_prev(q) \返回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
(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;
#define ngx_queue_data(q, type, link) \返回q所属结构体地址
(type *) ((u_char *) q - offsetof(type, link))
ngx_queue_t的实现文件中只有两个方法：一个是返回链表中的中心元素，还有一个是对链表排序。
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)) { //next每走一步都要判断一下的
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); //分别保存q的前后节点
next = ngx_queue_next(q);
ngx_queue_remove(q);
do {
if (cmp(prev, q) <= 0) { //若prev小于，这个循环结束
break;
}
prev = ngx_queue_prev(prev);//否则跟前面一个元素比
} while (prev != ngx_queue_sentinel(queue));//这个为结束条件，prev为链表结构体结束
ngx_queue_insert_after(prev, q);//插入q
}
}
版权声明：本文为博主原创文章，未经博主允许不得转载。
以上就介绍了nginx高级数据结构源码分析（一）-----双向链表，包括了方面的内容，希望对PHP教程有兴趣的朋友有所帮助。
