libuv源码阅读(2)--queue.h
原创libuv源码阅读(2)--queue.h
原创
源码：
#ifndef QUEUE_H_
#define QUEUE_H_
#include <stddef.h>
typedef void *QUEUE[2];
/* Private macros. */
#define QUEUE_NEXT(q) (*(QUEUE **) &((*(q))[0]))
#define QUEUE_PREV(q) (*(QUEUE **) &((*(q))[1]))
#define QUEUE_PREV_NEXT(q) (QUEUE_NEXT(QUEUE_PREV(q)))
#define QUEUE_NEXT_PREV(q) (QUEUE_PREV(QUEUE_NEXT(q)))
/* Public macros. */
#define QUEUE_DATA(ptr, type, field) \
((type *) ((char *) (ptr) - offsetof(type, field)))
/* 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_EMPTY(q) \
((const QUEUE *) (q) == (const QUEUE *) QUEUE_NEXT(q))
#define QUEUE_HEAD(q) \
(QUEUE_NEXT(q))
#define QUEUE_INIT(q) \
do { \
QUEUE_NEXT(q) = (q); \
QUEUE_PREV(q) = (q); \
} \
while (0)
#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)
#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)
#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)
#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)
#endif /* QUEUE_H_ */这是一种双向队列的实现，假设现在有2个strcut BASE 和 A 要通过双向队列组织起来，BASE作为队列头结点的持有者，A作为队列元素插入：
struct BASE {
int a,
void* QUEUE[2];
}
struct A {
int c,
int d,
int e,
void* QUEUE[2];
}
struct BASE base;
struct A a;第一步需要初始化队列：
QUEUE_INIT(&(base.QUEUE))
QUEUE_INIT(&(a.QUEUE))我们传入的参数是指向queue字段地址的指针：
typedef void *QUEUE[2];
#define QUEUE_INIT(q) \
do { \
QUEUE_NEXT(q) = (q); \
QUEUE_PREV(q) = (q); \
} \
while (0)
#define QUEUE_NEXT(q) (*(QUEUE **) &((*(q))[0]))
#define QUEUE_PREV(q) (*(QUEUE **) &((*(q))[1]))
#define QUEUE_PREV_NEXT(q) (QUEUE_NEXT(QUEUE_PREV(q)))
#define QUEUE_NEXT_PREV(q) (QUEUE_PREV(QUEUE_NEXT(q)))我们把 QUEUE_NEXT展开来看 ( *(QUEUE **) &((*(q))[0]) ) 先看 (*(q)) 取得对q指针指向元素的引用,它是一个有2个void*指针元素的数组，然后 &((*(q))[0]) 取得数组第一个元素的地址；再来看类型： QUEUE * 是指向 queue 类型元素的指针，再加一个 *号 就是 QUEUE ** 一个指向 queue元素指针的指针 ，看下我们 &((*(q))[0]) 中 q的2个元素确实都是 指向queue类型元素的指针。类型相符，最后用一个 * 来对它们取引用作为左值来使用，那既可以对他们赋值也可以把它们当做 右值来使用。
queue[2] 中 第一个元素存下一个节点的地址，第二个元素存上一个节点的地址。
所以结论就是：QUEUE_NEXT(q) 取q指向元素的下个节点的引用；QUEUE_PREV(q) 取q指向元素的上个节点的引用；QUEUE_PREV_NEXT(q) 取q指向元素的上个节点的下个节点的引用(用于给它赋值); QUEUE_NEXT_PREV(q) 取q指向元素的下个节点的上个节点的引用(用于给它赋值);
逻辑上效果如图所示：
QUEUE_DATA: 取得包含queue队列节点的元素地址：
#define QUEUE_DATA(ptr, type, field) \
((type *) ((char *) (ptr) - offsetof(type, field)))以图中的节点a 为例子：ptr是 a.queue的地址，type 是 struct A，field是 queue；先看下 offsetof :
#define offsetof(st, m) ((size_t)&(((st *)0)->m))
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
offsetof通过把 0 强制转换为 目标type类型的地址我们成为指针 address(值为0) ，从而通过address->field得到目标字段的地址为 0+字段偏移量 == queue偏移量; 得到偏移量之后，我们再用 prt指向的待计算位置 (目标元素地址+queue偏移量) - (quque偏移量) == 目标元素地址了。
QUEUE_FOREACH：遍历队列直到回到 h 头节点
#define QUEUE_FOREACH(q, h) \
for ((q) = QUEUE_NEXT(h); (q) != (h); (q) = QUEUE_NEXT(q))QUEUE_EMPTY： q队列是否为空，判断它的next是不是就是它自己就可以了
#define QUEUE_EMPTY(q) \
((const QUEUE *) (q) == (const QUEUE *) QUEUE_NEXT(q))QUEUE_HEAD：取出哨兵head节点的下一个节点就是第一个元素节点了
#define QUEUE_HEAD(q) \
(QUEUE_NEXT(q))QUEUE_ADD： 把 n 队列的元素都接入到 h 队列的尾部：
分4步实现：
1. 把 h 的最后一个元素的下一个元素地址赋值为 n 的第一个元素地址；
2. 把 n 的第一个元素的前一个元素的地址赋值为 h 的最后一个元素地址；
3. 把 h 哨兵头部节点的上一个元素赋值为 n 的最后一个元素地址；
4. 把 h 的前一个元素(现在就是 n 的最后一个元素) 的下一个元素赋值为 h 头部节点的地址；
自此，接入操作完成。
#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)QUEUE_SPLIT：把 h 队列 从 节点 q 开始截断到尾部元素，并将截断出来的元素放入 队列 n 中：
分6步实现:
1. 把队列 n 头部节点的prev指向 h 的尾部的元素地址；
2. 把队列 n 的 prev（现在为h 的尾部元素）的next 指向 n 头部节点地址；
3. 把队列头部节点 n 的next 指向 q 节点地址；
4. 把队列头部节点 h 的 prev 指向 q 的prev；
5. 把队列头部节点 h 的prev (现在就是 q 的prev指向的元素) 的 next 指向 h 自己；
6. 最后把 q 的prev 指向新头部节点 n ；
至此，分离操作完成，可以通过 n 的使用新的队列了，原队列保留剩下的元素(可能为空)；
#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)QUEUE_MOVE：把 h 中的全部元素都转移到 n 中，是上述情况的一种特殊情况，h会变成空
#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)QUEUE_INSERT_HEAD：把 q 从 h 的头部插入：
1. q 的 next 指向 h 的next；
2. q 的 prev 指向 h;
3. q 的 next (现为 h 的 next 指向的元素) 的 prev 指向 q；
4. h 的 next 指向 q；
插入完毕。
#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)q从它所属的队列中摘除：很简单，q的next 和 prev 都重新指向自己就可以了。
#define QUEUE_REMOVE(q) \
do { \
QUEUE_PREV_NEXT(q) = QUEUE_NEXT(q); \
QUEUE_NEXT_PREV(q) = QUEUE_PREV(q); \
} \
while (0)
总结：双向队列的 动态操作(插入 删除 合并 分离) 等都是 O（1） 级别时间复杂度的操作，效率很高；所以libuv中对各类资源对象很多都是用双向队列来管理的；以后自己用C写项目可以直接引用这部分实现作为queue 队列实现的一种方案。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。
原创声明：本文系作者授权腾讯云开发者社区发表，未经许可，不得转载。
如有侵权，请联系 cloudcommunity@tencent.com 删除。