queue.h中是qemu使用到的一些基础的数据结构，比如QLIST，QSLIST，QSIMPLEQ，QTAILQ。

本文主要介绍QLIST的数据结构，其它几种数据结构与之类似。

需要注意entry是嵌入在其他结构体(elm)中使用，QLIST是elm的链表，不是entry的链表。

HEAD

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

lh_first表示list head first

head的静态初始化：

#define QLIST_HEAD_INITIALIZER(head)                                    \
        { NULL }

head的动态初始化：

#define QLIST_INIT(head) do {                                           \
        (head)->lh_first = NULL;                                        \
} while (/*CONSTCOND*/0)

ENTRY

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

le_next表示list entry next，le_prev表示list entry prev

注意le_prev，是两个星号，是为了删除elm时的*(elm)->field.le_prev /*等效于之前一个elm的le_next*/ = (elm)->field.le_next;，可以在之后的示意图中详细看看。

elm是包含entry的结构体，比如：

typedef struct elm {
    QLIST_ENTRY(type) field;
    // other fields
} elm;

在head后面插入一个elm：

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

在某个listelm前面或者后面插入elm：

#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)

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

删除elm：

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

遍历，safe模式的可以对本elm进行写操作，注意((next_var) = ((var)->field.le_next), 1)，让&&后面的条件始终未1，防止next_var为NULL时，少循环一次：

#define QLIST_FOREACH(var, head, field)                                 \
        for ((var) = ((head)->lh_first);                                \
                (var);                                                  \
                (var) = ((var)->field.le_next))

#define QLIST_FOREACH_SAFE(var, head, field, next_var)                  \
        for ((var) = ((head)->lh_first);                                \
                (var) && ((next_var) = ((var)->field.le_next), 1);      \
                (var) = (next_var))

其他操作：

#define QLIST_EMPTY(head)                ((head)->lh_first == NULL)
#define QLIST_FIRST(head)                ((head)->lh_first)
#define QLIST_NEXT(elm, field)           ((elm)->field.le_next)

示意图：

QSLIST是单向链表，QTAILQ的头多了一个指向末尾的指针，不再赘述。