LVGL源码分析(1):lv_ll链表的实现
在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)
实际上就是act
中prev
指针的位置,然后将这个指针指向的值赋值为参数中的prev
指针。对于node_set_next
来说,完成的操作类似,就是更改act
中next
指针的值。
所以对于下面这两行的代码来说,就是把新创建节点的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中实现的链表的理解。
更多推荐
所有评论(0)