QEMU中的队列queue

include/qemu/queue.h中的注释如下。该文件通过宏定义的方式，定义了4种数据结构，以及相关的操作。
四种数据结构分别是：singly-linked list单向链表、list双向链表、simple queue简单队列、tail queue尾队列。

1
/*
2
 * This file defines four types of data structures: singly-linked lists,
3
 * lists, simple queues, and tail queues.
4
 *
5
 * A singly-linked list is headed by a single forward pointer. The
6
 * elements are singly linked for minimum space and pointer manipulation
7
 * overhead at the expense of O(n) removal for arbitrary elements. New
8
 * elements can be added to the list after an existing element or at the
9
 * head of the list.  Elements being removed from the head of the list
10
 * should use the explicit macro for this purpose for optimum
11
 * efficiency. A singly-linked list may only be traversed in the forward
12
 * direction.  Singly-linked lists are ideal for applications with large
13
 * datasets and few or no removals or for implementing a LIFO queue.
14
 *
15
 * A list is headed by a single forward pointer (or an array of forward
22 collapsed lines
16
 * pointers for a hash table header). The elements are doubly linked
17
 * so that an arbitrary element can be removed without a need to
18
 * traverse the list. New elements can be added to the list before
19
 * or after an existing element or at the head of the list. A list
20
 * may only be traversed in the forward direction.
21
 *
22
 * A simple queue is headed by a pair of pointers, one the head of the
23
 * list and the other to the tail of the list. The elements are singly
24
 * linked to save space, so elements can only be removed from the
25
 * head of the list. New elements can be added to the list after
26
 * an existing element, at the head of the list, or at the end of the
27
 * list. A simple queue may only be traversed in the forward direction.
28
 *
29
 * A tail queue is headed by a pair of pointers, one to the head of the
30
 * list and the other to the tail of the list. The elements are doubly
31
 * linked so that an arbitrary element can be removed without a need to
32
 * traverse the list. New elements can be added to the list before or
33
 * after an existing element, at the head of the list, or at the end of
34
 * the list. A tail queue may be traversed in either direction.
35
 *
36
 * For details on the use of these macros, see the queue(3) manual page.
37
 */

　　本文主要描述tail queue，并简单介绍其他三种数据结构。

`singly-linked list`单向链表

　　特点：

由元素组成，每个元素通过单个向前的指针连接。
在列表头部或某个元素之后添加元素效率较高。
移除元素通常需要O(n)时间，因为可能涉及遍历列表以找到元素。
在删除操作较少或数据以后进先出（LIFO）方式增长的场景中最为理想。

　　适用场景：

在数据集大且删除操作少的应用中非常有用。
适合堆栈实现，其中元素不断地被推入并从头部弹出。

`list`双向链表

　　特点：

元素是双向链接的，允许轻松移除任何元素而无需完全遍历。
只能向前遍历。
新元素可以在列表的头部或现有元素之前或之后添加。

　　适用场景：

适合频繁插入和从列表任何部分删除的应用。
在需要快速访问和修改数据且不希望遍历列表带来性能损失的场景中常用。

`simple queue`简单队列

　　特点：

由两个指针头部，一个指向列表的头部，另一个指向尾部。
元素单向链接，这意味着节省空间，但只允许从头部移除。
支持在列表的末尾或现有元素之后添加元素。

　　适用场景：

适合队列实现，其中元素在尾部入队，在头部出队（先进先出，FIFO）。
在主要是追加操作或元素按到达顺序处理的情况下非常有用。

`tail queue`尾队列

　　特点：

类似于简单队列，但元素是双向链接的。
允许移除任何元素而无需遍历整个列表。
元素可以在列表的头部或尾部添加或移除，列表可以向任一方向遍历。

　　适用场景：

在需要频繁在列表两端插入和删除的情况下非常灵活。
理想用于实现双端队列（deque），在两端高效添加或删除数据。

　　在QEMU中tail queue被大量使用。

`tail queue`数据结构形式

QTailQLink

　　文件include/qemu/queue.h中定义了tail queue最重要的数据结构QTailQLink，这是一个内部结构，被QTAILQ_HEAD和QTAILQ_ENTRY使用。主要目的在于尽可能不影响自定义数据结构的同时，将数据结构联系起来。

1
typedef struct QTailQLink {
2
    void *tql_next;
3
    struct QTailQLink *tql_prev;
4
} QTailQLink;

　　QTailQLink定义的tql_next类型为void *，其作用是指向当前节点后续的自定义数据结构节点，由于自定义数据结构类型不能确定，因此只能用void *定义。tql_prev则是指向当前节点的前一个QTailQLink节点。这两个变量的在后续QTAILQ_HEAD和QTAILQ_ENTRY中将体现出独特的作用。

QTAILQ_HEAD

　　QTAILQ_HEAD定义如下：

1
/*
2
 * Tail queue definitions.  The union acts as a poor man template, as if
3
 * it were QTailQLink<type>.
4
 */
5
#define QTAILQ_HEAD(name, type)                                         \
6
union name {                                                            \
7
        struct type *tqh_first;       /* first element */               \
8
        QTailQLink tqh_circ;          /* link for circular backwards list */ \
9
}
10
/*
11
 * union使两个变量共享同一个空间：tqh_first为一个指针，QTailQLink包含两个指针。
12
 * 因此，tqh_first和tqh_circ.tql_next储存在同一个位置。
13
 * 即tqh_circ.tql_next就是tqh_first。
14
 */

　　需要注意，QTAILQ_HEAD被定义为union结构体，也就是union结构体中所有的变量共享同一块内存空间。当我们QTailQLink展开后，tqh_first和QTailQLink.tql_next共享同一块内存，也就是两者实际上的值是相同的，只不过名字不同。

QTAILQ_ENTRY

　　同理，QTAILQ_ENTRY也是如此：

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

　　QTAILQ_HEAD和QTAILQ_ENTRY区别在与，QTAILQ_HEAD.tqh_first指向第一个自定义数据结构体，QTAILQ_HEAD本身是一个单独节点，不会存在于自定义数据结构中。而QTAILQ_ENTRY是定义在自定义数据结构体中的，作为自定义数据结构体的一部分。

`ModuleEntry`举例

　　为了直观的理解，以util/module.c中定义的ModuleEntry为例：

1
// A general element for tail queue, must contain QTAILQ_ENTRY, and the name for
2
// QTAILQ_ENTRY is arbitrary
3
// Example
4
typedef struct ModuleEntry
5
{
6
    void (*init)(void);            // data only for this struct
7
    QTAILQ_ENTRY(ModuleEntry) node;// use for queue
8
    module_init_type type;         // data only for this struct
9
} ModuleEntry;
10

11
typedef QTAILQ_HEAD(, ModuleEntry) ModuleTypeList;

　　ModuleEntry就是自定义数据结构体，其中包含QTAILQ_ENTRY定义的同时，还包含有其他变量，将其展开后代码如下：

1
typedef struct ModuleEntry
2
{
3
    void (*init)(void);
4
    union {
5
        struct ModuleEntry *tqe_next;
6
        struct QTailQLink {
7
            void *tql_next;
8
            struct QTailQLink *tql_prev;
9
        } tqe_circ;
10
    } node;
11
    module_init_type type;
12
} ModuleEntry;

　　根据在QTAILQ_ENTRY中的对union结构体的分析，我们可以得到

1
ModuleEntry entry;
2
/* 下面两者等价，指向ModuleEntry类型 */
3
(ModuleEntry *) entry.node.tqe_next
4
(ModuleEntry *) entry.node.tqe_circ.tql_next
5

6
/* 指向struct QTailQLink */
7
(struct QTailQLink *) entry.node.tqe_circ.tql_prev

　　而QTAILQ_HEAD则是单独定义的：

1
typedef QTAILQ_HEAD(, ModuleEntry) ModuleTypeList;
2
static ModuleTypeList dso_init_list;

　　同样将其展开，可以看到和ModuleEntry不同点在在于，其中不包含其他类型的数据。

1
typedef union ModuleTypeList
2
{
3
    struct ModuleEntry *tqh_first;
4
    struct QTailQLink {
5
        void *tql_next;
6
        struct QTailQLink *tql_prev;
7
    } tqh_circ;
8
} ModuleTypeList;

　　在实际使用时，如下图组织数据：ModuleTypeList定义头节点，ModuleEntry定义中间节点，双向队列由头节点和 node 之间的指针来维护。

　　需要注意的是，所有next指针（tql_next、tqe_next）指向的都是自定义数据结构，而所有的prev指针（tql_prev）指向的都是struct QTailQLink（即tqh_circ，tqe_circ）。这意味着，如果我们想要访问cur节点的前一个节点，需要从tql_prev->tql_prev->tql_next来访问。

其他API

head初始化

　　有两种方式实现：QTAILQ_HEAD_INITIALIZER和QTAILQ_INIT。

　　QTAILQ_HEAD_INITIALIZER 实际上是宏定义的结构体赋值文本，不算是函数接口（api）。
QTAILQ_INIT是宏定义的函数体，算是函数接口（api）。

　　因此，函数调用时使用QTAILQ_INIT，而定义struct时需要初始化head，则使用QTAILQ_HEAD_INITIALIZER。

1
/* */
2
#define QTAILQ_HEAD_INITIALIZER(head)                                   \
3
        { .tqh_circ = { NULL, &(head).tqh_circ } }
4
/*
5
 * HEAD初始化时，头尾是同一个节点（本HEAD节点）
6
 * 和后续的 QTAILQ_INIT(head)作用相同，但用途不同。
7
 * QTAILQ_HEAD_INITIALIZER 是宏定义，用于自定义struct初始化head时使用。
8
 * QTAILQ_INIT 是函数，在函数中调用实现head初始化。
9
 */
10

11
/* QTAILQ_HEAD_INITIALIZER */
12
static QemuOptsList qemu_source_opts = {
13
    .name = "source",
14
    .implied_opt_name = "file",
15
    .head = QTAILQ_HEAD_INITIALIZER(qemu_source_opts.head),
35 collapsed lines
16
    .desc = {
17
        { }
18
    },
19
};
20

21
/*
22
 * Tail queue functions.
23
 */
24
#define QTAILQ_INIT(head) do {                                          \
25
        (head)->tqh_first = NULL;                                       \
26
        (head)->tqh_circ.tql_prev = &(head)->tqh_circ;                  \
27
} while (/*CONSTCOND*/0)
28
// 初始化队列时，由于只有一个HEAD节点，因此HEAD的prev指向自身，next（即first元素）指向空
29
// 否则HEAD的prev指向的就是尾元素
30

31
/* QTAILQ_INIT */
32
static ModuleTypeList init_type_list[MODULE_INIT_MAX];
33
static ModuleTypeList dso_init_list;
34
static void init_lists(void)
35
{
36
    static int inited;
37
    int i;
38

39
    if (inited) {
40
        return;
41
    }
42

43
    for (i = 0; i < MODULE_INIT_MAX; i++) {
44
        QTAILQ_INIT(&init_type_list[i]);
45
    }
46

47
    QTAILQ_INIT(&dso_init_list);
48

49
    inited = 1;
50
}

头部和尾部插入

　　由于是宏定义实现的接口，我们预先不知道自定义的数据结构的名称，以及其中的strutc QTailQLink名称，因此需要传入这两个参数，elm和field。例如，ModuleEntry对应于elm，ModuleEntry中的node对应于field。

1
/*
2
 * Tail queue functions.
3
 */
4
#define QTAILQ_INSERT_HEAD(head, elm, field) do {                       \
5
        if (((elm)->field.tqe_next = (head)->tqh_first) != NULL)        \
6
            (head)->tqh_first->field.tqe_circ.tql_prev =                \
7
                &(elm)->field.tqe_circ;                                 \
8
        else                                                            \
9
            (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ;         \
10
        (head)->tqh_first = (elm);                                      \
11
        (elm)->field.tqe_circ.tql_prev = &(head)->tqh_circ;             \
12
} while (/*CONSTCOND*/0)
13
// 向头节点插入时，先判断HEAD后有没有其他元素，并将当前元素elm的next指针指向HEAD后的元素
14
// 如果有其他元素，则将HEAD的后续元素的prev指针指向当前元素elm
15
// 如果没有其他元素，则将HEAD的prev指针指向当前元素elm。
49 collapsed lines
16
// 然后将HEAD的first指向elm，因为first其实就是HEAD的next
17
// 最后将elm的prev指向head。
18

19
// 需要注意：HEAD中的tqe_circ、elm中的field（即QTAILQ_ENTRY）的tqe_circ
20
// 才是整个链条中的“节点”，
21
// elm中，field就是QTAILQ_ENTRY，用来标识节点，因此elm不仅有“节点”，还有其他的数据
22
// 而在HEAD中，HEAD就是QTAILQ_HEAD，和QTAILQ_ENTRY同属基本的queue数据结构，
23
// 因此，在整个链条中，QTAILQ_HEAD和QTAILQ_ENTRY作为队列中的节点，其中的指针
24
// prev和next链接每个节点。
25

26
// 在实现中很有意思的一点，next指针的类型是type *，而pre的指针类型是QTailQLink *
27
// 因此，在访问next中的“节点”时，需要访问next.field.tqe_circ，而pre直接就访问
28
// pre.tqe_circ
29

30
#define QTAILQ_INSERT_TAIL(head, elm, field) do {                       \
31
        (elm)->field.tqe_next = NULL;                                   \
32
        (elm)->field.tqe_circ.tql_prev = (head)->tqh_circ.tql_prev;     \
33
        (head)->tqh_circ.tql_prev->tql_next = (elm);                    \
34
        (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ;             \
35
} while (/*CONSTCOND*/0)
36

37
#define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do {             \
38
        if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
39
            (elm)->field.tqe_next->field.tqe_circ.tql_prev =            \
40
                &(elm)->field.tqe_circ;                                 \
41
        else                                                            \
42
            (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ;         \
43
        (listelm)->field.tqe_next = (elm);                              \
44
        (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ;    \
45
} while (/*CONSTCOND*/0)
46

47
#define QTAILQ_INSERT_BEFORE(listelm, elm, field) do {                       \
48
        (elm)->field.tqe_circ.tql_prev = (listelm)->field.tqe_circ.tql_prev; \
49
        (elm)->field.tqe_next = (listelm);                                   \
50
        (listelm)->field.tqe_circ.tql_prev->tql_next = (elm);                \
51
        (listelm)->field.tqe_circ.tql_prev = &(elm)->field.tqe_circ;         \
52
} while (/*CONSTCOND*/0)
53

54
#define QTAILQ_REMOVE(head, elm, field) do {                            \
55
        if (((elm)->field.tqe_next) != NULL)                            \
56
            (elm)->field.tqe_next->field.tqe_circ.tql_prev =            \
57
                (elm)->field.tqe_circ.tql_prev;                         \
58
        else                                                            \
59
            (head)->tqh_circ.tql_prev = (elm)->field.tqe_circ.tql_prev; \
60
        (elm)->field.tqe_circ.tql_prev->tql_next = (elm)->field.tqe_next; \
61
        (elm)->field.tqe_circ.tql_prev = NULL;                          \
62
        (elm)->field.tqe_circ.tql_next = NULL;                          \
63
        (elm)->field.tqe_next = NULL;                                   \
64
} while (/*CONSTCOND*/0)

　　除了上述Tail queue functions，文件中还定义了一些访问方法，不在此处展示，当明白数据组织后，再去看源码将很容易。

　　‍

QEMU中的队列queue

​singly-linked list​单向链表

​list​双向链表

​simple queue​简单队列

​tail queue​尾队列

tail queue​数据结构形式

QTailQLink

QTAILQ_HEAD

QTAILQ_ENTRY

​ModuleEntry​举例

其他API

head初始化

头部和尾部插入

`singly-linked list`单向链表

`list`双向链表

`simple queue`简单队列

`tail queue`尾队列

`tail queue`数据结构形式

`ModuleEntry`举例