Tail Queue in QEMU
A tail queue is headed by a pair of pointers:
- One to the head of the list and,
- The other to the tail of the list.
The elements are doubly linked so that an arbitrary element can be removed without a need to traverse the list. New elements can be added to the list before or after an existing element, at the head of the list, or at the end of the list. A tail queue may be traversed in either direction.
为什么叫尾队列呢？ 尾队列本质上就是具有尾指针的双链表。它相对于双链表的优势也非常明显：能够快速执行尾插入、尾删除操作。循环队列本质上就是首尾相连的尾队列。它的优势就是能够从任意 element 开始遍历整个队列。
In QEMU, QTAILQ is a combination of
- a singly-linked forwards list, it is not circular.
- and another singly-linked list which goes backwards and is circular.
Because the backwards list points inside the node, accessing the previous element needs to go two steps back and one forwards.
QEMU 里 QTAIL 里的元素应该是同一个类型的（至少 QTAILQ_ENTRY 在里面的 field name 应该是一样的）。
每一个想要使用 QTail 的结构体 <Type>，都需要在结构体定义中包含一个 QTAILQ_ENTRY<Type> 类型的属性，属性名字无所谓。就像这样（属性名字为 node）：
struct QemuInputHandlerState {
//...
QTAILQ_ENTRY(QemuInputHandlerState) node;
};
struct QTailQLink QEMU
这个 patch 引入了 QTailQLink 这个结构体：https://lore.kernel.org/all/20181219151917.3874-30-pbonzini@redhat.com/
Why next is pointing to void, rather than user-defined Type?
Because when we defining this structure, we don't know what exactly Type it is (Type1? Type2? Type3?), so we use the void*.
Why next and prev are not pointing to the same type, one is void* the other is QTailQLink*?
需要说明的是，glibc 里的 TAILQ 也是这么实现的，其 prev 也是一个指针的指针（我们这里指向的是 QTailQLink，其本身也是一个指针，所以本质是一样的）。
glibc/misc/sys/queue.h at master · zerovm/glibc
关于原因（OpenBSD 也是这么实现 TAILQ 这个数据结构的），这里解释了：c - Why the tail queue in the OpenBSD <sys/queue.h> uses the pointer to pointer? - Stack Overflow
OpenBSD 里 TAILQ 的定义：queue(3) - OpenBSD manual pages
原因是为了代码实现的通用简洁性，即不需要因为一个 node 是 first node 就作特殊的处理。
Note：请不要混淆 head 和 first node，它们是两个不同的类型，一个是 QTAILQ_HEAD 另一个是用户定义的类型，head 的 tqh_first 属性指向 node。
这种设计的好处是：A node can always be removed with:
// 如果我们只剩一个 node，那么就是把 head 置为 NULL，如果还有很多 node，那就是让上一个 node 的 next 指向自己的 next
// 也就是把自己跳过
*(node->tqe_prev) = node->tqe_next;
// 如果只剩一个 node，那么 if 为 false，不执行
// 否则，那么让 next 的 prev 指向我们的 prev，也就是跳过我们
if(node->tqe_next) tqe_next->tqe_prev = tqe_prev;
even when 这个 Queue 里只剩一个元素，也就是我们只有 head 和 first node 了。而且大家都是这么实现的。
The first node's tqe_prev points to this head pointer. 这是因为 head->tqe_prev 其实指向 head_prev->tqe_next，也就是自己。总之不用深究，就是为了代码实现的简洁性考虑。
typedef struct QTailQLink {
// 指向的是下一个 <Type> 地址
void *tql_next;
struct QTailQLink *tql_prev;
} QTailQLink;
QTAILQ_HEAD() / QTAILQ_ENTRY() QEMU
注意这两个都是 Union：
- 要么是直接指向用户定义的类型
<Type>，遍历的时候就是用的这个属性进行遍历的。 - 要么就是指向一个
QTailQLinktqe_circ。
第一个是指针，第二个是有两个指针的变量，所以看起来不管是 QTAILQ_HEAD 里的 tqh_first 还是 QTAILQ_ENTRY 里的 tqe_next，它们都是和 tql_next 共享的是 union 里同一片内存区域（第一片），我们可以将其称为 next 区域。而 tql_prev 则单独占用一片内存区域，我们可以称其为 prev 区域。由此是不是可以得出，一个 entry 要么只包含指向 next 的信息（只是 next 区域有值，prev 区域值为 NULL），要么同时有指向 next 和 prev 的信息（两个区域都有值）。
注意，tail 的 next 是 NULL 而不是 head，这用来表示它是一个 tail entry，和其他普通的 entry 作区分。 这也是这个链表里面唯一为空的指针。
所以说这个 QTAILQ_HEAD / QTAILQ_ENTRY 的内存大小其实就是 QTailQLink 的大小。
两者并无多大区别，只不过第一个指向 Type 的属性的名字不一样，一个是 tqh_first，一个是 tqe_next。
#define QTAILQ_HEAD(name, type) \
union name { \
struct type *tqh_first; /* first element */ \
// 指向尾节点的 QTailQLink，注意不等于指向尾节点哦
QTailQLink tqh_circ; /* link for circular backwards list */ \
}
// 注意 tqe_next 和 tql_next 的区别
#define QTAILQ_ENTRY(type) \
union { \
struct type *tqe_next; /* next element */ \
QTailQLink tqe_circ; /* link for circular backwards list */ \
}
QTAILQ_INSERT_HEAD() QEMU
field 是一个 QTAILQ_ENTRY(<UserDefinedType>) 类型的指针；
elm 是一个 <UserDefinedType> 类型的指针；
head 是一个 QTAILQ_HEAD(, <UserDefinedType>) 类型的指针。
如果这个链表不是空的：
如果这个链表是空的：
#define QTAILQ_INSERT_HEAD(head, elm, field) do { \
if (((elm)->field.tqe_next = (head)->tqh_first) != NULL) \
(head)->tqh_first->field.tqe_circ.tql_prev = \
&(elm)->field.tqe_circ; \
else \
(head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
(head)->tqh_first = (elm); \
(elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ; \
} while (/*CONSTCOND*/0)
QTAILQ_INSERT_TAIL() QEMU
head 是一个 QTAILQ_HEAD(, <UserDefinedType>) 类型的指针。
elm 是一个 <UserDefinedType> 类型的指针；
field 是变量名字，表示 QTAILQ_ENTRY(<UserDefinedType>) 在 <UserDefinedType> 中的名字；
一共要做四步，对应下面的四行代码：
- 要添加的这个新的 entry 的 next 指向 NULL，表示我们不用这个 field。
- 要添加的这个新的 entry 的 prev 指向 head 的 prev（是
QTailQLink类型的）。 - head 的 prev 的 next 指向这个新 entry，这里的指针是
<Type>类型的。 - head 的 prev 指向这个 entry，毕竟我们已经是新的尾 entry 了。这里的指针是
QTailQLink类型的。
#define QTAILQ_INSERT_TAIL(head, elm, field) do { \
(elm)->field.tqe_next = NULL; \
(elm)->field.tqe_circ.tql_prev = (head)->tqh_circ.tql_prev; \
(head)->tqh_circ.tql_prev->tql_next = (elm); \
(head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ; \
} while (0)
QTAILQ_REMOVE() QEMU
#define QTAILQ_REMOVE(head, elm, field) do { \
if (((elm)->field.tqe_next) != NULL) \
(elm)->field.tqe_next->field.tqe_circ.tql_prev = \
(elm)->field.tqe_circ.tql_prev; \
else \
(head)->tqh_circ.tql_prev = (elm)->field.tqe_circ.tql_prev; \
(elm)->field.tqe_circ.tql_prev->tql_next = (elm)->field.tqe_next; \
(elm)->field.tqe_circ.tql_prev = NULL; \
(elm)->field.tqe_circ.tql_next = NULL; \
(elm)->field.tqe_next = NULL; \
} while (/*CONSTCOND*/0)
Tail queue access methods / QTAILQ_EMPTY() / QTAILQ_FIRST() / QTAILQ_NEXT() / QTAILQ_IN_USE() / QTAILQ_LINK_PREV() / QTAILQ_LAST() / QTAILQ_PREV() / field_at_offset() / QTAILQ_RAW_FIRST() / QTAILQ_RAW_TQH_CIRC() / QTAILQ_RAW_NEXT() / QTAILQ_RAW_TQE_CIRC() QEMU
// 一个 tail queue 是不是空的由 tqh_first 是不是空决定，make sense
#define QTAILQ_EMPTY(head) ((head)->tqh_first == NULL)
// 同理，first 也是。make sense
#define QTAILQ_FIRST(head) ((head)->tqh_first)
// next 就直接 tqe_next 指向的下一个 Type 元素值就可以了，因为不管是 union
// 的哪一种，这个内存总是会存在的，而且都表示 next <Type>
#define QTAILQ_NEXT(elm, field) ((elm)->field.tqe_next)
// 表示 union 里的 prev 区域是有值的，也就是用来表示 prev 的。
#define QTAILQ_IN_USE(elm, field) ((elm)->field.tqe_circ.tql_prev != NULL)
// 给定一个 link，得到这个 link 的 prev.prev 的 link
// 然后根据这个 link 得到 next <Type>
// 类型转换为 <QTailQLink> -> <Type>
#define QTAILQ_LINK_PREV(link) \
((link).tql_prev->tql_prev->tql_next)
// 因为我们是一个循环链表，所以 head 的上一个就是 last
// 我们通过这种方式得到 last
// 类型转换为 <QTAILQ_HEAD> -> <Type>
#define QTAILQ_LAST(head) \
((typeof((head)->tqh_first)) QTAILQ_LINK_PREV((head)->tqh_circ))
// 通过一个 <Type> 找到 prev <Type>，类型转化为
// <Type> -> <Type>
#define QTAILQ_PREV(elm, field) \
((typeof((elm)->field.tqe_next)) QTAILQ_LINK_PREV((elm)->field.tqe_circ))
// 将 base + offset 处的内存转为 type 类型的指针。
#define field_at_offset(base, offset, type) \
((type *) (((char *) (base)) + (offset)))
// 如前所述，head 和 entry 都是 QTAILQ_HEAD 和 QTAILQ_ENTRY 类型的
// 这两个都是 union，没有类型名，有两个内存区域（我们之前已经提到了）
// 因此我们可以用 void* 来指向它，也可以用 QTailQLink* 来指向它（因为这个 union
// 里占用内存最大的元素就是 QTailQLink 类型的）
// 把 head 转成 void*
#define QTAILQ_RAW_FIRST(head) \
field_at_offset(head, 0, void *)
// 把 head 转成 QTailQLink*
#define QTAILQ_RAW_TQH_CIRC(head) \
field_at_offset(head, 0, QTailQLink)
// 把 entry 转成 void*
#define QTAILQ_RAW_NEXT(elm, entry) \
field_at_offset(elm, entry, void *)
// 把 entry 转成 QTailQLink*
#define QTAILQ_RAW_TQE_CIRC(elm, entry) \
field_at_offset(elm, entry, QTailQLink)
Tail queue traverse functions
QTAILQ_FOREACH() / QTAILQ_FOREACH_SAFE() QEMU
QTAILQ_FOREACH_SAFE() 相比于 QTAILQ_FOREACH() 多了一个参数，这个参数表示我们可以同时有两个指针，分别指向当前遍历到
的 entry 和这个 entry 的下一个 entry，而不是只能是一个 entry。
// var 是一个指向自定义数据结构 Type 的指针，表示遍历过程中当前正在遍历到的元素
// head 表示的是整个 QTailQ 链表的链表头
// field 表示属性在 Type 中的名字
#define QTAILQ_FOREACH(var, head, field) \
for ((var) = ((head)->tqh_first); \
(var); \
(var) = ((var)->field.tqe_next))
// 如果不理解，可以参考逗号表达式^
// 这里终止条件写的很别扭，其实就是为了在终止条件判断的时候插入一个计算
// 同时不要让计算结果影响到终止条件的判断（因为我们用逗号表达式永远返回 1 也就是 true）
// 因为 for 循环是在终止条件这里暂停的，所以此时 next_var 已经更新了和 var 不一样了。
#define QTAILQ_FOREACH_SAFE(var, head, field, next_var) \
for ((var) = ((head)->tqh_first); \
(var) && ((next_var) = ((var)->field.tqe_next), 1); \
(var) = (next_var))
展开了其实就是一个 for 循环：
for (var = head->tqh_first; var; var = var->field.tqe_next)
初始化为 head->tqh_first，可以理解。
终止条件为 var 为 NULL，也可以理解。``
遍历的 next 是通过 var->field.tqe_next 来遍历的。
所以我们可以看到，遍历并没有用到 QTailQLink 结构体，而是用了同一个 Union 当中的 tqe_next 属性。
同时也可以注意到，tqe_next 基本上永远是有值的。
QTAILQ_HEAD_INITIALIZER() QEMU
初始化 head 的 next 部分指向 NULL，prev 部分指向自己。
#define QTAILQ_HEAD_INITIALIZER(head) \
{ .tqh_circ = { NULL, &(head).tqh_circ } }
求物之妙，如系风捕景，能使是物了然于心者，千万人而不一遇也。