libuv系列--queue详解
一、目的
在以前的博文《RT-Thread系列--双链表分析》我们介绍了如何实现双链表，其实这种双链表结构在linux内核中用得比较多，但是考虑到版权问题，libuv通过宏实现了同样功能的双链表结构。本篇的目的就是帮助大家理解其实现原理，涉及到的知识点包括：指针、指针数组、左值
二、介绍
涉及的源文件为libuv/src/queue.h
typedef void *QUEUE[2];上面的代码片段通过typedef定义了一个新类型QUEUE指针数组类型，数组大小为2个void类型的指针。
我们可以声明一个QUEUE类型的变量
void *p[2];
QUEUE q = p;也可以声明一个QUEUE类型的指针
void *p[2];
QUEUE *q = &p;QUEUE类型里面的两个void *指针的作用是用于存储链表中的前一个元素和后一个元素的地址
在进一步介绍了QUEUE的相关接口细节之前我们先使用QUEUE构建一个双链表。
struct foo {
QUEUE q;
int val;
};
int main() {
QUEUE header;
QUEUE_INIT(&header);
for (int i = 0; i < 10; i++) {
struct foo *obj = calloc(1, sizeof(struct foo));
obj->val = i;
//QUEUE_INSERT_HEAD(&header, &obj->q);
QUEUE_INSERT_TAIL(&header, &obj->q);
}
struct foo *obj;
QUEUE *q;
QUEUE_FOREACH(q, &header) {
obj = QUEUE_DATA(q, struct foo, q);
printf("obj value: %d\n", obj->val);
}
return 0;
}在构建一个新的双链表时，我们需要将QUEUE作为一个变量放在自定义的结构体中，比如上面的foo结构体中的变量q，通过q就可以将struct foo A/B/C连接起来。
同时为了管理素双链表，我们还需要一个链表头，例如上面代码中的QUEUE header。
#define QUEUE_NEXT(q) (*(QUEUE **) &((*(q))[0]))
#define QUEUE_PREV(q) (*(QUEUE **) &((*(q))[1]))上面的两个宏一个是为了获取双链表q元素下一个元素的地址，一个是获取上一个元素的地址。注意QUEUE_NEXT中的q是QUEUE *类型的。
之所以这样复杂是为了类型一致和保持左值，我们下面好好解释一下
正常情况下我们如果要获取下一个元素的地址的话，可以直接q[0]就可以了，为什么此处如此复杂。
(*(q))是对QUEUE *类型的q解引用
((*(q))[0])是获取第一个指针
因为在类型Queue中[0][1]存放的是下一个元素的Queue类型的地址，所以我们需要对其进行类型强转（原本类型为void *）
QUEUE * ((*(q))[0])
但是这样类型强转之后是一个右值，无法对其赋值；如果只是进行取值操作是可以这样定义的。
举例说明
//①
int a = 10;
//②
(char)a = 2; //错误
//③
*((char *)&a) = 2; //正确在步骤②中我们是无法修改a的值等于2，但是③的方法却可以实现。
基于这样的原因，我们对
((*(q))[0])取地址，取地址后类型变成void **类型；然后我们再进行QUEUE **类型强制转换；然后再对其解引用（*）；
最终 QUEUE_NEXT(q)宏定义我们既可以用于取值操作，也可以用于赋值操作。
#define QUEUE_PREV_NEXT(q) (QUEUE_NEXT(QUEUE_PREV(q)))
#define QUEUE_NEXT_PREV(q) (QUEUE_PREV(QUEUE_NEXT(q)))链表初始化
#define QUEUE_INIT(q) \
do { \
QUEUE_NEXT(q) = (q); \
QUEUE_PREV(q) = (q); \
} \
while (0)将q的next/prev都指向自身，此时q是一个空链表，例如QUEUE_INIT(header)将header进行初始化。
判断链表是否为空
#define QUEUE_EMPTY(q) \
((const QUEUE *) (q) == (const QUEUE *) QUEUE_NEXT(q))获取链表的第一个元素（必须是非空链表）
#define QUEUE_HEAD(q) \
(QUEUE_NEXT(q))通过节点内QUEUE变量的地址获取的元素的首地址
/* Public macros. */
#define QUEUE_DATA(ptr, type, field) \
((type *) ((char *) (ptr) - offsetof(type, field)))在头部插入新元素
#define QUEUE_INSERT_HEAD(h, q) \
do { \
QUEUE_NEXT(q) = QUEUE_NEXT(h); \
QUEUE_PREV(q) = (h); \
QUEUE_NEXT_PREV(q) = (q); \
QUEUE_NEXT(h) = (q); \
} \
while (0)
在 尾部插入新元素
#define QUEUE_INSERT_TAIL(h, q) \
do { \
QUEUE_NEXT(q) = (h); \
QUEUE_PREV(q) = QUEUE_PREV(h); \
QUEUE_PREV_NEXT(q) = (q); \
QUEUE_PREV(h) = (q); \
} \
while (0)移除节点
#define QUEUE_REMOVE(q) \
do { \
QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q); \
QUEUE_NEXT_PREV(q) = QUEUE_PREV(q); \
} \
while (0)遍历链表
/* Important note: mutating the list while QUEUE_FOREACH is
* iterating over its elements results in undefined behavior.
*/
#define QUEUE_FOREACH(q, h) \
for ((q) = QUEUE_NEXT(h); (q) != (h); (q) = QUEUE_NEXT(q))上面的遍历过程中不能新增或者删除节点
链接拼接
#define QUEUE_ADD(h, n) \
do { \
QUEUE_PREV_NEXT(h) = QUEUE_NEXT(n); \
QUEUE_NEXT_PREV(n) = QUEUE_PREV(h); \
QUEUE_PREV(h) = QUEUE_PREV(n); \
QUEUE_PREV_NEXT(h) = (h); \
} \
while (0)将n链表中的元素拼接到h链表的尾部
分割链表
#define QUEUE_SPLIT(h, q, n) \
do { \
QUEUE_PREV(n) = QUEUE_PREV(h); \
QUEUE_PREV_NEXT(n) = (n); \
QUEUE_NEXT(n) = (q); \
QUEUE_PREV(h) = QUEUE_PREV(q); \
QUEUE_PREV_NEXT(h) = (h); \
QUEUE_PREV(q) = (n); \
} \
while (0)将h链表从q节点开始分割到链表n中
移动链表
#define QUEUE_MOVE(h, n) \
do { \
if (QUEUE_EMPTY(h)) \
QUEUE_INIT(n); \
else { \
QUEUE* q = QUEUE_HEAD(h); \
QUEUE_SPLIT(h, q, n); \
} \
} \
while (0)将链表中的节点移动到链表n中
三、实战
#include "queue.h"
#include <stdio.h>
#include <stdlib.h>
struct foo {
QUEUE q;
int val;
};
int main() {
QUEUE header;
QUEUE_INIT(&header);
for (int i = 0; i < 10; i++) {
struct foo *obj = calloc(1, sizeof(struct foo));
obj->val = i;
//QUEUE_INSERT_HEAD(&header, &obj->q);
QUEUE_INSERT_TAIL(&header, &obj->q);
}
struct foo *obj;
QUEUE *q;
QUEUE_FOREACH(q, &header) {
obj = QUEUE_DATA(q, struct foo, q);
printf("obj value: %d\n", obj->val);
}
QUEUE header2;
QUEUE_MOVE(&header, &header2);
while (!QUEUE_EMPTY(header2)) {
q = QUEUE_HEAD(&header2);
QUEUE_REMOVE(q);
obj = QUEUE_DATA(q, struct foo, q);
printf("remove: %d, add tail\n", obj->val);
QUEUE_INSERT_TAIL(&header, q);
}
QUEUE_MOVE(&header, &header2);
while (!QUEUE_EMPTY(header2)) {
q = QUEUE_HEAD(&header2);
QUEUE_REMOVE(q);
//安全遍历
obj = QUEUE_DATA(q, struct foo, q);
printf("free: %d\n", obj->val);
free(q);
}
return 0;
}以上，就是libuv queue的全部内容。