qemu QLIST数据结构

简介: queue.h中是qemu使用到的一些基础的数据结构,比如QLIST,QSLIST,QSIMPLEQ,QTAILQ。 本文主要介绍QLIST的数据结构,其它几种数据结构与之类似。

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的头多了一个指向末尾的指针,不再赘述。


目录
相关文章
|
缓存 Linux 开发工具
CentOS 7- 配置阿里镜像源
阿里镜像官方地址http://mirrors.aliyun.com/ 1、点击官方提供的相应系统的帮助 :2、查看不同版本的系统操作: 下载源1、安装wget yum install -y wget2、下载CentOS 7的repo文件wget -O /etc/yum.
254877 0
|
XML 存储 数据安全/隐私保护
使用virsh migrate进行虚拟机迁移
使用virsh migrate进行虚拟机迁移
557 0
|
网络协议
DHCP服务详解
DHCP服务详解
837 0
|
11月前
|
算法 大数据 Python
局部异常因子(LOF)
局部异常因子(LOF)
|
JSON C语言 数据格式
使用cJSON库实现JSON与C结构体的互转
在实际应用中,我们经常需要将JSON格式的数据与C语言中的结构体进行相互转换。cJSON是一个非常便捷的C语言JSON解析库,它可以帮助我们在C语言中轻松地处理JSON数据。本文将介绍如何使用cJSON库来实现JSON数据与C结构体的互转。
1102 2
|
架构师 Unix Linux
内存泄露专题(4)mtrace内存追踪
内存泄露专题(4)mtrace内存追踪
421 0
【Linux C 几种锁的性能对比】 1.读写锁 2.互斥锁 3.自旋锁 4.信号量 5.rcu
【Linux C 几种锁的性能对比】 1.读写锁 2.互斥锁 3.自旋锁 4.信号量 5.rcu
|
测试技术 网络安全 虚拟化
libvirt虚拟机热迁移
验证不同迁移特性下的热迁移效率。
3225 0
|
C++ 计算机视觉
实用分享-Dependencies(DLL解析工具)
实用分享-Dependencies(DLL解析工具)
3761 0
|
存储 监控 安全
【KVM虚拟化】· virsh文件管理
【KVM虚拟化】· virsh文件管理
1002 0