在LVGL中难免需要用到链表:group中的对象需要用链表来存储,这样可以切换对象的焦点;再比如LVGL内部的定时器,多个定时器也是用链表进行存储的。这篇文章就来分析一下LVGL中链表的源码。

1 链表结构体

对于链表来说,肯定有一个头指针和一个尾指针,在LVGL中,链表的数据结构如下:

/** Dummy type to make handling easier*/
typedef uint8_t lv_ll_node_t;

/** Description of a linked list*/
typedef struct {
    uint32_t n_size;
    lv_ll_node_t * head;
    lv_ll_node_t * tail;
} lv_ll_t;

可以看出头尾指针实际上是用一个uint8_t *的指针来保存某个数据的地址。

2 插入元素源码分析

下面以向链表的尾部插入元素为例,来分析一下源码:

2.1 初始化函数

void _lv_ll_init(lv_ll_t * ll_p, uint32_t node_size)
{
    ll_p->head = NULL;
    ll_p->tail = NULL;
    
    /*Round the size up to 4*/
    node_size = (node_size + 3) & (~0x3);

    ll_p->n_size = node_size;
}

初始化函数就是初始化一下链表中单个node的大小,这里还将长度四字节对齐了。

2.2 插入元素

_lv_ll_ins_head用于在链表的最前面插入节点,而_lv_ll_ins_tail用于在链表的最后插入节点。它们的实现基本上一样,这里以_lv_ll_ins_tail为例进行分析。

#define LL_NODE_META_SIZE (sizeof(lv_ll_node_t *) + sizeof(lv_ll_node_t *))

void * _lv_ll_ins_tail(lv_ll_t * ll_p)
{
    lv_ll_node_t * n_new;

    n_new = lv_mem_alloc(ll_p->n_size + LL_NODE_META_SIZE);

    if(n_new != NULL) {
        node_set_next(ll_p, n_new, NULL);       /*No next after the new tail*/
        node_set_prev(ll_p, n_new, ll_p->tail); /*The prev. before new is the old tail*/
        if(ll_p->tail != NULL) {                /*If there is old tail then the new comes after it*/
            node_set_next(ll_p, ll_p->tail, n_new);
        }

        ll_p->tail = n_new;      /*Set the new tail in the dsc.*/
        if(ll_p->head == NULL) { /*If there is no head (1. node) set the head too*/
            ll_p->head = n_new;
        }
    }

    return n_new;
}

首先就是分配一个大小为ll_p->n_size + LL_NODE_META_SIZE大小的内存,也就是刚刚我们设置的每个节点的大小,然后再加上两个用于保存前一个元素和后一个元素的指针。

然后以node_set_prev函数为例,看下代码做了什么事:

#define LL_PREV_P_OFFSET(ll_p) (ll_p->n_size)

static void node_set_prev(lv_ll_t * ll_p, lv_ll_node_t * act, lv_ll_node_t * prev)
{
    if(act == NULL) return; /*Can't set the prev node of `NULL`*/

    uint8_t * act8 = (uint8_t *)act;

    act8 += LL_PREV_P_OFFSET(ll_p);

    lv_ll_node_t ** act_node_p = (lv_ll_node_t **) act8;
    lv_ll_node_t ** prev_node_p = (lv_ll_node_t **) &prev;

    *act_node_p = *prev_node_p;
}

首先 act8 += LL_PREV_P_OFFSET(ll_p)实际上就是actprev指针的位置,然后将这个指针指向的值赋值为参数中的prev指针。对于node_set_next来说,完成的操作类似,就是更改actnext指针的值。

所以对于下面这两行的代码来说,就是把新创建节点的prev指向当前链表的最后一个元素,将next指向NULL,这样就在链表的最后插入了一个元素。

node_set_next(ll_p, n_new, NULL);
node_set_prev(ll_p, n_new, ll_p->tail); 

继续分析代码:

if(ll_p->tail != NULL) {                /*If there is old tail then the new comes after it*/
	node_set_next(ll_p, ll_p->tail, n_new);
}

ll_p->tail = n_new;      /*Set the new tail in the dsc.*/
if(ll_p->head == NULL) { /*If there is no head (1. node) set the head too*/
	ll_p->head = n_new;
}

这表示对于ll_p结构来说,我们知道前面只保存了单个元素的大小,还有头尾指针。所以最开始先判断当前的链表的尾指针是否有值,若有,则将其next指向我们新创建的节点。然后将链表中的尾指针赋值为新节点的地址。如果链表的头也为空的话,表示链表刚刚创建,该节点不仅是头节点也是尾结点。

2.3 插入元素的用法

有了上面插入元素到链表尾部源码的分析,我们来看看实际上是怎么使用_lv_ll_ins_tail函数的。

lv_obj_t ** next = _lv_ll_ins_tail(&ll);
LV_ASSERT_MALLOC(next);
*next = next_node;

前面源码中我们知道,插入的新元素的内存是在_lv_ll_ins_tail中分配的,所以我们先插入,然后判断如果这个内存分配成功的话,我们就可以把插入到末尾的指针的值赋值为我们的节点next_node

3 总结

实际上LVGL中链表的实现和我们预期的链表数据结构差不多,唯一的不同是这里允许自定义每个节点的大小,然后直接在节点中保存数据,而不是保存指针,这也是一种思路吧。当然,链表的操作不止在尾部插入元素,在lv_ll.c文件中还有获取链表长度、删除节点等函数,如果全部都分析一遍,篇幅就太长了,也是大家熟知的链表,故没有多大的意义。这篇文章的目的就是了解一下LVGL中链表的数据结构,然后以往尾部插入元素为例加深对LVGL中实现的链表的理解。

Logo

旨在为数千万中国开发者提供一个无缝且高效的云端环境,以支持学习、使用和贡献开源项目。

更多推荐