ngx_queue_t 이중 연결 리스트

ngx_queue_t 이중 연결 목록

구조

<code><span>typedef</span><span>struct</span> ngx_queue_s ngx_queue_t;
<span>typedef</span><span>struct</span> ngx_queue_s {
    ngx_queue_t *prev;
    ngx_queue_t *next;
};</code>

전체 연결 목록의 구조는 다음과 같습니다. 시작과 센티널로 사용되는 빈 헤드가 있습니다. 연결된 목록(Used 탐색 시)을 탐색하고 다음 방법을 사용하여 이 헤드의 후속 위치에 노드를 추가합니다.

---

컨테이너가 제공하는 메서드

方法名	参数含义	执行意义
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所在的结构体变量之后

---

정렬 테스트

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

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

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

<span>int</span> main(){
    ngx_queue_t queueContainer;         <span>//Create a ngx_queue_t variable</span>
    ngx_queue_init(&queueContainer);    <span>//Initialize the variable</span><span>int</span> i = <span>0</span>;
    TestNode node[<span>5</span>];
    <span>for</span>(;i<<span>5</span>;++i)
        node[i].num = i;

    <span>//可以考虑一下插入后的顺序</span>
    ngx_queue_insert_tail(&queueContainer,&node[<span>0</span>].qEle);
    ngx_queue_insert_head(&queueContainer,&node[<span>1</span>].qEle);
    ngx_queue_insert_tail(&queueContainer,&node[<span>2</span>].qEle);
    ngx_queue_insert_after(&queueContainer,&node[<span>3</span>].qEle);
    ngx_queue_insert_tail(&queueContainer,&node[<span>4</span>].qEle);

    <span>//Pirnt queue</span>
    printQueue(&queueContainer);

    <span>//Sort</span>
    ngx_queue_sort(&queueContainer,compTestNode);

    <span>//Print queue after sort</span>
    printQueue(&queueContainer);

    <span>return</span><span>0</span>;
}</code>

참고:

사용된 "ngx_queue.h" 헤더 파일은 Nginx 소스 코드에서 복사하여 수정했습니다. 꽤 간단하므로 생략하겠습니다. 업로드하세요.

---

저작권: 고통은 마음속에 있습니다.

위 내용은 관련 내용을 포함하여 ngx_queue_t 이중 연결 목록을 소개한 내용이므로 PHP 튜토리얼에 관심이 있는 친구들에게 도움이 되기를 바랍니다.