nginx源码分析--双端列表

#define ngx_queue_remove(x)                                                   \
    (x)->next->prev = (x)->prev;                                              \
    (x)->prev->next = (x)->next
 
#define ngx_queue_insert_after   ngx_queue_insert_head

注意：

#define ngx_queue_next(q)                                                     \
    (q)->next
 
 
#define ngx_queue_prev(q)                                                     \
    (q)->prev
 

gx_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;
        }
    }
}

void 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);
    }
}

4 test

引出一个知识：

双端队列是在两端都可以插入或删除元素的数据结构，在Nginx里它被实现为双向循环链表ngx_queue_t，类似标准容器std : : list。

借用Boost程序库的概念，前面的ngx_array_t和ngx_list_t属于非侵入式容器,元素无须改动即可加入容器，而 ngx_queue_t 则不同，它是侵入式容器，必须把 ngx_queue_t作为元素的一个成员，然后才能放入队列，与boost.intrusive库很接近。

struct Xinfo
{
int x=0;
ngx_queue_t queue;
}

例子

#include                                                                        #include 
#include 
#include 
#include "ngx_queue.h"
 
//数据定义 节点必须有ngx_queue_t
typedef struct student
{
    int id; 
    int age;
    int weight;
    ngx_queue_t qnode;
}student;
//排序比较函数
ngx_int_t stu_cmp(const ngx_queue_t *n1, const ngx_queue_t *n2)
{
    //拿到数据
    struct student *s1 = ngx_queue_data(n1, student, qnode);
    struct student *s2 = ngx_queue_data(n2, student, qnode);
 
    return s1->id - s2->id;
}
//遍历
void stu_foreach(const ngx_queue_t *queue)
{
    ngx_queue_t *q = ngx_queue_head(queue);
 
    struct student *s = ngx_queue_data(q, student, qnode);
    if (q == ngx_queue_last(queue)) {
        return;
    }   
    printf("id = %d\n",s->id);
 
    for (q = ngx_queue_next(q); q != ngx_queue_sentinel(queue); q = ngx_queue_next(q)) {
        s = ngx_queue_data(q, student, qnode);
        printf("id = %d\n",s->id);
    }
}
 
int main(int argc,char *argv[])
{
    //初始化队列
    ngx_queue_t *q = (ngx_queue_t *)calloc(1,sizeof(ngx_queue_t));
    ngx_queue_init(q);
	//初始化数据
    struct student st1 = {1,11,111};
    struct student st2 = {2,12,112};
    struct student st3 = {3,13,113};
    struct student st4 = {4,14,114};
    struct student st5 = {5,15,115};
	//头插法 将qnode插入
    ngx_queue_insert_head(q,&st2.qnode);
    ngx_queue_insert_head(q,&st4.qnode);
    ngx_queue_insert_head(q,&st1.qnode);
    ngx_queue_insert_head(q,&st5.qnode);
    ngx_queue_insert_head(q,&st3.qnode);
    //排序
	printf("================sort=============\n");
    stu_foreach(q);
    printf("\n");
    ngx_queue_sort(q,stu_cmp);
    stu_foreach(q);
	//找中间值
    printf("================middle=============\n");
    ngx_queue_t *mid =  ngx_queue_middle(q);
    student *s = ngx_queue_data(mid, student, qnode);
    printf("id:%d\n",s->id);
	//分裂
    printf("================split=============\n");
    ngx_queue_t *n = (ngx_queue_t *)calloc(1,sizeof(ngx_queue_t));
    ngx_queue_init(n);
    ngx_queue_split(q,mid,n);
    printf("=old queue=\n");
    stu_foreach(q);
    printf("=new queue=\n");
    stu_foreach(n);
	//合并
    printf("================add=============\n");
    ngx_queue_add(q,n);
    stu_foreach(q);
    
    free(n);
    free(q);
    
    return 0;
}