1.基本数据结构
struct ngx_queue_s {
ngx_queue_t *prev;
ngx_queue_t *next;
};
结构成员:
ngx_queue_t *prev;前驱指针
ngx_queue_t *next;后继指针
2.操作函数–头结点
2.1基本函数
define ngx_queue_init(q) \
(q)->prev = q; \
(q)->next = q
#define ngx_queue_empty(h) \
(h == (h)->prev)
#define ngx_queue_sentinel(h) \
(h)
#define ngx_queue_head(h) \
(h)->next
#define ngx_queue_last(h) \
(h)->prev
1.初始化头结点 将两个指针指向自身
2.检测前驱结点
3返回头结点（哨兵：）
4.头结点和尾结点
2.2添加和删除
#define ngx_queue_insert_head(h, x)
#define ngx_queue_insert_head(h, x)
(x)->next = (h)->next; \
(x)->next->prev = x; \
(x)->prev = h; \
(h)->next = x
采用一个哨兵的方法
h作为一个哨兵，x成为一个头结点
#define ngx_queue_insert_tail(h, x)
#define ngx_queue_insert_tail(h, x) \
(x)->prev = (h)->prev; \
(x)->prev->next = x; \
(x)->next = h; \
(h)->prev = x
删除
#define ngx_queue_remove(x)
(x)->next->prev = (x)->prev; \
(x)->prev->next = (x)->next; \
(x)->prev = NULL; \
(x)->next = NULL
3.合并和分离
#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;
1.分裂队列 h是头 q是分裂节点的界限 n为分裂完的新节点
2.合并队列 n本身的节点会抛弃
3.操作函数–数据节点
数据节点本质上与头节点并无区别，所以很多操作代码是相同的数据节点本质上与头节点并无区别，所以很多操作代码是相同的
添加和删除
#define ngx_queue_remove(x) \
(x)->next->prev = (x)->prev; \
(x)->prev->next = (x)->next
#define ngx_queue_insert_after ngx_queue_insert_head
注意：
函数宏ngx_queue_remove（）可以“删除” 当前节点，实际上它只是调整了节点的指针，
把节点从队列里摘除，并没有真正从内存里删除数据：
寻找：
#define ngx_queue_next(q) \
(q)->next
#define ngx_queue_prev(q) \
(q)->prev
ngx_queue_t *
ngx_queue_middle(ngx_queue_t *queue)
ngx_queue_middle(ngx_queue_t *queue)
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 <stdio.h> #include <stdlib.h>
#include <string.h>
#include <stddef.h>
#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;
}
输出
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 举报，一经查实，本站将立刻删除。
文章由极客之音整理，本文链接：https://www.bmabk.com/index.php/post/129632.html
