欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  后端开发

ngx_queue_t双向链表

程序员文章站 2022-04-25 11:11:42
...
ngx_queue_t 双向链表

结构

typedefstruct ngx_queue_s ngx_queue_t;
typedefstruct ngx_queue_s {
    ngx_queue_t *prev;
    ngx_queue_t *next;
};

整个链表的结构就是:有一个空的头,这个头用作链表的起始和哨兵(遍历时用到),接着用下面的方法向这个头的后续位置加节点。


容器提供的方法

方法名 参数含义 执行意义
ngx_queue_init(h) h是ngx_queue_t的指针 链表容器初始化,空链表
ngx_queue_empty(h) 同上 检查链表是否为空
nxg_queue_insert_head(h,x) h同上,x为待插入ngx_queue_t指针 头插法
nxg_queue_insert_head(h,x) 同上 尾插法
ngx_queue_head(h) 同上 返回头指针
ngx_queue_tail(h) 同上 返回尾指针
ngx_queue_sentinel(h) 同上 返回结构体指针
ngx_queue_remove(x) 同上 移除x元素
ngx_queue_split(h,q,n) 同上 将链表分为h->q(不包括q)和q->tail两部分,后一部分的指针存放在n上
ngx_queue_add(h,n) h和n都是双向链表容器指针 合并链表,将n接在h之后
ngx_queue_middle(h) 同上 返回第N/2+1个元素的指针
ngx_queue_sort(h,compfunc) cmpfunc是元素的比较方法 使用**插入排序**cpmfunc原型:ngx_int_t (*cpmfunc)(const ngx_queue_t *a,const ngx_queue_t *b)

双向链表中元素的方法

方法名 参数含义 执行意义
ngx_queue_next(q) q为链表中某个结构体变量ngx_queue_t成员的指针 返回下一个元素
ngx_queue_prev(q) 同上 返回上一个元素
ngx_queue_data(q,type,member) q同上,type是该结构体类型,member是ngx_queue_t在该结构体中的名称 返回q变量所在结构体变量的首地址
ngx_queue_insert(q,x) q、x都是某个结构体变量的中ngx_queue_t成员指针 将x所在的结构体变量插入到q所在的结构体变量之后

测试sort

#include #include "./ngx_queue.h"//元素所在结构体typedefstruct _TestNode{
    u_char *str;
    ngx_queue_t qEle;   //包含ngx_queue_t组成双向链表int num;
}TestNode;

//设置的比较函数
ngx_int_t compTestNode(const ngx_queue_t *a,const ngx_queue_t *b){
    TestNode *aNode = ngx_queue_data(a, TestNode, qEle);
    TestNode *bNode = ngx_queue_data(b, TestNode, qEle);
    return aNode->num > bNode->num;
}

//按顺序打印链表内容void printQueue(ngx_queue_t *head){
    ngx_queue_t *pNode = NULL;
    for(pNode = ngx_queue_head(head);\
        pNode != ngx_queue_sentinel(head);\
        pNode = ngx_queue_next(pNode)){
        TestNode *node = ngx_queue_data(pNode,TestNode,qEle);
        printf("%d ",node->num);
    }
    printf("\n");
}

int main(){
    ngx_queue_t queueContainer;         //Create a ngx_queue_t variable
    ngx_queue_init(&queueContainer);    //Initialize the variableint i = 0;
    TestNode node[5];
    for(;i5