Qemu 的这个队列实现是如何工作的？

Question

我正在尝试了解 Qemu 的队列宏：https://github.com/qemu/qemu/blob/stable-4.2/include/qemu/queue.h

以下结构有什么作用？

typedef struct QTailQLink {
    void *tql_next;
    struct QTailQLink *tql_prev;
} QTailQLink;

/*
 * Tail queue definitions.  The union acts as a poor man template, as if
 * it were QTailQLink<type>.
 */
#define QTAILQ_HEAD(name, type)                                         \
union name {                                                            \
        struct type *tqh_first;       /* first element */               \
        QTailQLink tqh_circ;          /* link for circular backwards list */ \
}

ps: 我找到了 https://medium.com/@chenfelix/tail-queue-1b23232e4f49 但它已经过时了，现在看起来不像 Qemu 的源代码。

好吧，队列是一种按顺序存储一些元素的结构，您可以在它们之上添加：

a queue is a collection of entities that are maintained in a sequence and can be modified by the addition of entities at one end of the sequence and the removal of entities from the other end of the sequence. Wikipedia

为这个队列设置一个头是有意义的，所以我猜这就是 QTAILQ_HEAD 所做的。您可以持有指向第一个元素的指针。我想知道为什么不指向最后一个也。不管怎样，你可以通过遍历队列元素找到最后一个。

对我来说没有意义的是QTailQLink tqh_circ;。这是一些递归的东西，但我不明白为什么它在头部。

此外，为什么存在这样的东西：QSLIST_INSERT_AFTER、QSLIST_INSERT_HEAD？在队列中，根据定义，您只能在 tips 处 insert/remove。这些宏使您可以在任意点插入。

Answer 1

1、这段代码暗示QTailQLink是一个doubly linked list。因此，我们不一定需要保存尾部——我们总能从头部遍历找到它。

    typedef struct QTailQLink {
        void *tql_next;
        struct QTailQLink *tql_prev;
    } QTailQLink;

QTAILQ_HEAD的含义如果你看一下它在"queue.h"中的配套宏，可能会更清楚一些：

 /*
  * Tail queue definitions.  The union acts as a poor man template, as if
  * it were QTailQLink<type>.
  */
 #define QTAILQ_HEAD(name, type)                                         \
 union name {                                                            \
     struct type *tqh_first;       /* first element */               \
     QTailQLink tqh_circ;          /* link for circular backwards list */ \
 }

 #define QTAILQ_HEAD_INITIALIZER(head)                                   \
     { .tqh_circ = { NULL, &(head).tqh_circ } }

 #define QTAILQ_ENTRY(type)                                              \
 union {                                                                 \
     struct type *tqe_next;        /* next element */                \
     QTailQLink tqe_circ;          /* link for circular backwards list */ \
 }

...和...

/*
 * Tail queue functions.
 */
#define QTAILQ_INIT(head)
#define QTAILQ_INSERT_HEAD(head, elm, field)
#define QTAILQ_INSERT_TAIL(head, elm, field)
#define QTAILQ_INSERT_AFTER(head, listelm, elm, field)
#define QTAILQ_INSERT_BEFORE(listelm, elm, field)
#define QTAILQ_REMOVE(head, elm, field)
...
/*
 * Tail queue access methods.
 */
#define QTAILQ_EMPTY(head) 
#define QTAILQ_FIRST(head)  
#define QTAILQ_NEXT(elm, field)  
...

换句话说，它只是简单地定义并实现了一堆带有链表的标准队列操作。

Answer 2

header 文件顶部的注释定义了该数据结构的属性：

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

为什么是这个数据结构，为什么是这些操作？因为它是一组有用的事情，并且比简单的“你所能做的就是在尾部添加并在头部起飞”提供更多的灵活性queue。

header 还指出，这些宏是从 BSD 中的宏借用（并重命名）的；您可能想阅读 the FreeBSD manpage on them 以获得更详细的信息。

更一般地说，除了教育目的，几乎没有人真正需要研究这些宏的内部结构。如果您只是在编写 QEMU 代码，那么您应该能够使用此 header 提供的宏来执行诸如“遍历此 queue”之类的操作，而不必关心它们是如何在内部实现的。

如果您确实想研究宏是如何实现的，有几个巧妙的技巧可能会让您感到困惑：

(1) 联合的使用——QTAILQ_HEAD() 和 QTAILQ_ENTRY() 都定义了联合，使得一些字段相互重叠，并且相同可以通过两种方式访问指针。例如，在 QTAILQ_HEAD 中，tqh_circ.tql_next 指针与 qth_first 指针相同——但一个是 'void *'，另一个是 'struct type *'，所以使用哪一个取决于宏在对指针进行赋值时是否想要有效地提供某种类型安全。

(2) 一个数据项可以同时出现在多个 queue 上。这是通过让数据项的结构在其定义中有多个 QTAILQ_ENTRY() 来完成的。这意味着 queue 实现需要小心区分“这是一个指向数据项的指针”和“这是一个指向嵌入在数据项中的 QTailQLink 的指针”——一个数据项结构可以有多个 QTailQLinks , 对于不同的列表，它可能在。

(3) 在每个数据项（此处为 QTailQLink）中使用的头部中重复使用相同的数据类型对于避免特殊情况“这是列表中的第一项”很有用各种 add/remove/etc 操作。这就是为什么它不只是对空 queue.

使用“prev pointer is NULL”

（header 还定义了一个“简单的 queue”，它基于单链表并避免了这些巧妙的技巧；它不太灵活，在某些情况下效率较低。）

如果你想进一步调查，我的建议是画出一些图表，说明数据结构到底是什么样子，包括当你有一个 queue 时，哪些指针字段指向哪些其他地方，比如说, 其中有 3 个条目。

Qemu 的这个队列实现是如何工作的？

How does this queue implementation of Qemu work?

c

computer-science

singly-linked-list

qemu