<strong>qemu数据结构分析</strong>

qemu数据结构分析

这里主要分析queue.h头文件中包含的四种数据结构：1.单链表 2.双链表 3.简单队列 4.尾队列

一、单链表

1.1 应用场景

适用于数据量大的集合并且没有过多删除动作的场景，也适用做LIFO（后进先出）队列。

1.2 定义

/*
 * Singly-linked List definitions.
 */
#define QSLIST_HEAD(name, type)                                          \
struct name {                                                           \
        struct type *slh_first; /* first element */                     \
}

#define QSLIST_HEAD_INITIALIZER(head)                                    \
        { NULL }

#define QSLIST_ENTRY(type)                                               \
struct {                                                                \
        struct type *sle_next;  /* next element */                      \
}

1.3 元素插入

 

#define QSLIST_INSERT_AFTER(slistelm, elm, field) do {                   \
        (elm)->field.sle_next = (slistelm)->field.sle_next;             \
        (slistelm)->field.sle_next = (elm);                             \
} while (/*CONSTCOND*/0)

qemu代码中并没有使用该数据结构，这里简单分析一下该链表的元素插入方式。

插入流程比较简单，slistelm是待插入元素的前一个元素位置，elm是待插入元素，field是数据结构中的域名称，这里是next。

插入过程：1.将elm元素的next域的sle_next指向slistelm指向的下一个元素

2.将slistelm指向待插入元素elm

二、双向链表

2.1 应用场景

由于有前向指针，因此删除元素不需要遍历链表。新加入元素可以实现前插或后插。

2.2 定义

 

/*
 * List definitions.
 */
#define QLIST_HEAD(name, type)                                          \
struct name {                                                           \
        struct type *lh_first;  /* first element */                     \
}

#define QLIST_HEAD_INITIALIZER(head)                                    \
        { NULL }

#define QLIST_ENTRY(type)                                               \
struct {                                                                \
        struct type *le_next;   /* next element */                      \
        struct type **le_prev;  /* address of previous next element */  \
}

2.3 插入操作分析

#define QLIST_INSERT_AFTER(listelm, elm, field) do {                    \
        if (((elm)->field.le_next = (listelm)->field.le_next) != NULL)  \
                (listelm)->field.le_next->field.le_prev =               \
                    &(elm)->field.le_next;                              \
        (listelm)->field.le_next = (elm);                               \
        (elm)->field.le_prev = &(listelm)->field.le_next;               \
} while (/*CONSTCOND*/0)

插入过程：1. 首先待插入元素的le_next指针指向插入位置的下一个元素

2. 待插入位置的下一个元素的le_prev指向待插入元素的le_next指针。注意这里的le_prev是一个指向指针的指针，因此le_prev保存的是指针le_next的地址，而不是它的值。如果是值的话就变成指向自身了。

3. 前一个元素的le_next开始指向待插入元素

4. 最后待插入元素的le_prev指向其前一个元素的le_next指针。

2.4 在qemu中的应用

双向链表在qemu中有大量使用，如block设备链（block-backend.c）。

三、简单队列

3.1 定义

/*
 * Simple queue definitions.
 */
#define QSIMPLEQ_HEAD(name, type)                                       \
struct name {                                                           \
    struct type *sqh_first;    /* first element */                      \
    struct type **sqh_last;    /* addr of last next element */          \
}

#define QSIMPLEQ_HEAD_INITIALIZER(head)                                 \
    { NULL, &(head).sqh_first }

#define QSIMPLEQ_ENTRY(type)                                            \
struct {                                                                \
    struct type *sqe_next;    /* next element */                        \
}

2.3 元素插入

#define QSIMPLEQ_INSERT_AFTER(head, listelm, elm, field) do {           \
    if (((elm)->field.sqe_next = (listelm)->field.sqe_next) == NULL)    \
        (head)->sqh_last = &(elm)->field.sqe_next;                      \
    (listelm)->field.sqe_next = (elm);                                  \
} while (/*CONSTCOND*/0

简单队列的插入过程也比较简单

插入过程：1. 首先将待插入元素的sqe_next指针指向待插入位置的下一个元素

2. 最后将插入位置的前一个元素的sqe_next指针指向待插入元素

四、尾队列

4.1 应用场景

尾队列在链表头有一个头指针，在链表尾有一个尾指针。元素由前向指针和尾指针构成双向链表。可以在任意方向上进行遍历。

4.2 定义

/*
 * 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 */ \
}

4.3 插入过程

#define QTAILQ_INSERT_AFTER(head, listelm, elm, field) do {             \
        if (((elm)->field.tqe_next = (listelm)->field.tqe_next) != NULL)\
            (elm)->field.tqe_next->field.tqe_circ.tql_prev =            \
                &(elm)->field.tqe_circ;                                 \
        else                                                            \
            (head)->tqh_circ.tql_prev = &(elm)->field.tqe_circ;         \
        (listelm)->field.tqe_next = (elm);                              \
        (elm)->field.tqe_circ.tql_prev = &(listelm)->field.tqe_circ;    \
} while (/*CONSTCOND*/0)

尾队列结构由于头结点有一个tqh_circ指针始终指向尾结点，因此可以以O(1)的复杂度在尾部插入元素。同时能够以O(1)的复杂度在头部删除元素。

尾队列结构在中间的插入过程比较复杂。

插入过程：1.将待插入元素elm的tqe_next指针指向插入位置的下一个元素

2. 将插入位置下一个元素的tql_prev指针指向待插入元素的tqe_circ。这里和双向链表一样，tql_prev是一个指向指针的指针，保存的是前一个节点中tqe_circ指针的地址。

3. 第一，二步实际上完成了插入元素与插入位置下一个元素之间的连接，构成了一个循环。现在开始的是与插入位置前一个元素之间的连接。首先将插入位置前一个元素的tqe_next指向待插入元素elm。

4. 最后将待插入元素的tql_prev指向前一个元素。保存前一个元素tqe_circ指针的地址。

4.4 在qemu中的应用

尾队列的应用十分广泛，在内核，libevent中都能看到它的身影。主要得益于它O(1)复杂度的插入和删除操作以及可以双向遍历。

在qemu中，如memory_mapping使用的就是QTAIL_LIST(memory_mapping.c)。

五、总结

在qemu中主要使用双向链表和尾队列这两种数据结构。对于这两种数据结构的初始化，插入，添加，删除操作都使用宏定义做了封装。理解了这两种数据结构，可以更好的理解qemu相关模块的代码。