ngx_queue_t doubly linked list-PHP Tutorial-php.cn

ngx_queue_t doubly linked list

WBOY

Release： 2016-08-08 09:20:19

Original

1196 people have browsed it

ngx_queue_t Doubly linked list

structure

<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>

Copy after login

The structure of the entire linked list is: there is an empty head, which is used as the start and sentinel of the linked list (used during traversal), and then uses the following method to follow up on this head Position plus node.

Methods provided by the container

Parameters of the parameter

Method name	Parameter meaning	Execution meaning
ngx_queue_init(h)	h is the pointer of ngx_queue_t	chain Table container initialization, empty linked list
ngx_queue_empty(h)	Same as above	Check whether the linked list is empty
nxg_queue_insert_head(h,x)	hSame as above, x is the ngx_queue_t pointer to be inserted	Head insertion method
nxg_queue_insert_head(h,x )	Same as above	Tail insertion method
ngx_queue_head(h)	Same as above	Return to the back pointer
ngx_queue_tail(h)	Same as above	Return to the tail pointer
ngx_queue_sentinel(h)	Same as above	Return the structure pointer
ngx_queue_remove(x)	Same as above	Remove the -> There are two parts: q (excluding q) and q->tail. The pointer of the latter part is stored on n
ngx_queue_add(h,n)	h and n are both doubly linked list container pointers	merge the linked lists. n is followed by h
ngx_queue_middle(h)	Same as above	Returns the pointer of the N/2+1th element
ngx_queue_sort(h,compfunc)	cmpfunc is the comparison method of elements	Use Insert sort CPMFUNC prototype: ngx_int_t (cpmfunc) (const ngx_queue_ta, const ngx_queue_t*b)
	The method name of the element in the two -way linked list

Execution meaning

ngx_queue_prev(q)ngx_queue_data(q,type,member) ngx_queue_insert(q,x)

<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>

Copy after login

For the "ngx_queue.h" header file used, I copied it from the Nginx source code and modified it. It's quite simple, so I won't upload it.

ngx_queue_next(q)	q is a pointer to a member of a structure variable ngx_queue_t in the linked list	Returns the next element
Same as above	Return the previous element
q Same as above, type is the structure type, member is the name of ngx_queue_t in the structure	Returns the first address of the structure variable where the q variable is located
q and x are both ngx_queue_t member pointers of a certain structure variable	Insert the structure variable where x is after the structure variable where q is
Test sort	Note:

The above introduces the ngx_queue_t doubly linked list, including the relevant content. I hope it will be helpful to friends who are interested in PHP tutorials.