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 */voidngx_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)
版权声明：本文为博主原创文章，未经博主允许不得转载。
以上就介绍了nginx高级数据结构源码分析（一）-----双向链表，包括了方面的内容，希望对php教程有兴趣的朋友有所帮助。