LVGL双向链表学习笔记

1、LVGL链表数据类型分析

对于LVGL双向链表的使用，我们需要关注lv_ll.h和lv_ll.c两个文件，其中lv_ll.h里面包含了链表结构类型定义，以及相关API的声明，首先介绍链表的结构类，如下图所示：

一开始看到这个类型声明我是懵的，怎么链表的一个结点的类型是uint8_t,那是不是LVGL这个双向链表只能用于uint8_t类型的数据？可是转念一想LVGL内部的定时器、任务都是基于这个双向链表实现的，肯定有我没有理解到的地方，uint8_t是啥，不就是一个字节吗？在计算机内存中的基本单位，也是硬件所能访问的最小单位，这里我们可以联想到任何数据类型都可以字节进行访问，那么怎么访问呢？答案：指针。可以看出链表类型中头尾指针都是lv_ll_node_t *也就是uint8_t *，这样就可以通过head和tail对任意类型的结点进行访问。

2、LVGL链表实现原理

上一节已经对LVGL双向链表的数据类型进行分析，接下来开始分析其实现原理。

2.1、双向链表初始化

双向链表初始化_lv_ll_init()函数，其定义如下：

该函数主要用于初始化一个双向链表，并通过传入参数lv_ll_ *ll_p返回已经初始化的双向链表句柄，这里要重点关注第二个参数node_size，顾名思义该参数表示的是结点所占字节的大小，但要特别说明一下这个node_size表示的只是结点的数据域大小，并没有包含next、prv指针域，这一点在后面分析结点插入时会详细说明。在函数内部对node_size进行了8字节或4字节的内存对齐，具体是8字节对齐还是4字节对齐跟具体的系统位数相关了（比如WIN32就是4字节，WIN64就是8字节）。

2.2、插入结点

通过分析LVGL插入一个结点我们才能真正理解其双向链表的实现原理以及巧妙之处，这里以尾插法的实现进行分析，即_lv_ll_ins_tail()函数，其定义如下图所示：

① 创建一个新的结点
使用lv_mem_alloc()进行动态申请，注意这里申请的内存大小是ll_p->n
_size + LL_NODE_META_SIZE，其中ll_p->n_size就是之前在初始化时传入的node_size，那么我们来看看LL_NODE_META_SIZE是多大，转到定义可以看到：

哈哈，果然是两个指针的大小，如果熟悉双向链表马上就可以推测出这两个指针对应的就是next、prev指针，那么我们可以得到下面的结点内存模型：

还有个问题就是为什么可以确定prev在前，next在后呢？答案可以在下面这两个宏定义中找到：

其中LL_PREV_P_OFFSET表示prev指针相对域结点首地址的偏移，同理LL_NEXT_P_OFFSET表示的是next指针相对于结点首地址的偏移。通过这个偏移地址应该可以很清楚的看出prev在next前面的位置吧。
然后我们可以得到如下的双向链表模型：

② 设置新结点的next
使用node_set_next()函数设置结点的next，因为尾插法，所以新结点的next为空，这里重点分析node_set_next()函数的实现，其定义如下所示：

可以看出该函数内部都是指针的操作，对于指针操作来说，使用内存变化来理解是最好不过了，该函数的内存变化过程如下：

最终内存0x00000024的值为NULL，这也符合我们的预期：尾插法新结点的next为NULL。这里也值得思考一下：为什么设置next指针为什么需要如此复杂？因为LVGL双向链表的结点数据域是由外部决定的，我们只能通过地址这个信息来访问，同样的结点类型为uint8_t，我们也是只能通过地址信息来进行访问，不通过结构体成员的方式来访问数据域、prev指针以及next指针。同时函数内部中出现了两个二级指针，他们的作用就是用来访问地址，如果我们直接对传入act、next这两个一级指针进行操作，只能改这两个指针变量保存的地址值，并不能对传入地址进行访问，所以需要借助二级指针来对传入地址进行访问。
③ 设置新结点的prev
使用node_set_prev()函数设置结点的next，同样这里重点分析node_set_prev()函数的实现，其定义如下所示:

可以看出node_set_prev()和node_set_next()内部实现几乎是一模一样的只是act8获取的prev指针的偏移，就这个差异。其内存变化如下：

最终内存0x00000040（n_new的prev指针）的值为0x00000008（n_prev）。
④ 设置链表尾结点的next
⑤ 更新链尾为新结点
实际上LVGL实现原理的核心就是对node_set_next()和node_set_prev两个函数的理解，掌握了这两个函数的实现剩下的就是对双向链表的理解了，相信学习过数据结构理解双向链表应该是小菜一碟了吧。所以剩下的头插法、删除结点这些就不再赘述。

3、LVGL链表应用实例

点击查看代码

#define STD_NAME_LEN_MAX  15

//学生信息类型
typedef struct StudentInfo StudentInfo_t;
struct StudentInfo
{
    char name[STD_NAME_LEN_MAX];
    int age;
    int sex;
};

//学生信息表
StudentInfo_t std_table[] = {
    {"ZhangSan",  23,  1},
    {"LiSi",  25,  0},
    {"WangWu",  26,  1},
};

void lv_ll_test(void)
{
    StudentInfo_t* std;
    lv_ll_t std_ll;

    _lv_ll_init(&std_ll, sizeof(StudentInfo_t)); // 初始化std_ll链表

    /* 遍历学生信息表，将学生信息添加到std_ll中 */
    for (int i = 0; i < (sizeof(std_table) / sizeof(std_table[0])); i++) 
    {
        std = (StudentInfo_t*)_lv_ll_ins_tail(&std_ll);
        lv_snprintf(std->name, sizeof(std->name), std_table[i].name);
        std->age = std_table[i].age;
        std->sex = std_table[i].sex;
    }

    /* 遍历std_ll，验证学生信息是否正确添加到std_ll中 */
    std = (StudentInfo_t*)_lv_ll_get_head(&std_ll);
    while (std)
    {
        printf("name:%s  age:%d  sex:%d \n", std->name, std->age, std->sex);
        std = (StudentInfo_t*)_lv_ll_get_next(&std_ll, std);
    }

}