在LVGL中難免需要用到鏈表：group中的對象需要用鏈表來存儲，這樣可以切換對象的焦點；再比如LVGL內(nèi)部的定時器，多個定時器也是用鏈表進(jìn)行存儲的。這篇文章就來分析一下LVGL中鏈表的源碼。

1 鏈表結(jié)構(gòu)體

對于鏈表來說，肯定有一個頭指針和一個尾指針，在LVGL中，鏈表的數(shù)據(jù)結(jié)構(gòu)如下：

/** 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 *的指針來保存某個數(shù)據(jù)的地址。

2 插入元素源碼分析

下面以向鏈表的尾部插入元素為例，來分析一下源碼：

2.1 初始化函數(shù)

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;
}

初始化函數(shù)就是初始化一下鏈表中單個node的大小，這里還將長度四字節(jié)對齊了。

2.2 插入元素

_lv_ll_ins_head用于在鏈表的最前面插入節(jié)點，而_lv_ll_ins_tail用于在鏈表的最后插入節(jié)點。它們的實現(xiàn)基本上一樣，這里以_lv_ll_ins_tail為例進(jìn)行分析。

#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大小的內(nèi)存，也就是剛剛我們設(shè)置的每個節(jié)點的大小，然后再加上兩個用于保存前一個元素和后一個元素的指針。

然后以node_set_prev函數(shù)為例，看下代碼做了什么事：

#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指針的位置，然后將這個指針指向的值賦值為參數(shù)中的prev指針。對于node_set_next來說，完成的操作類似，就是更改act中next指針的值。

對于這邊使用二維指針，把指針的地址取出來然后再給地址里指向的指針賦值，我覺得完全是多此一舉，只需要強(qiáng)制轉(zhuǎn)化act8的類型大小為指針的大小(prev元素的類型)即可，這樣不會覆蓋掉下一個元素的值。這里可能是為了處理更一般化的情況，比如prev不只是一個指針，可能是一個結(jié)構(gòu)體，結(jié)構(gòu)體里有更多信息，但也不保存結(jié)構(gòu)體的地址，而是保存結(jié)構(gòu)體數(shù)據(jù)，但這種想法似乎也沒有什么意義。

所以對于下面這兩行的代碼來說，就是把新創(chuàng)建節(jié)點的prev指向當(dāng)前鏈表的最后一個元素，將next指向NULL，這樣就在鏈表的最后插入了一個元素。

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

繼續(xù)分析代碼：

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結(jié)構(gòu)來說，我們知道前面只保存了單個元素的大小，還有頭尾指針。所以最開始先判斷當(dāng)前的鏈表的尾指針是否有值，若有，則將其next指向我們新創(chuàng)建的節(jié)點。然后將鏈表中的尾指針賦值為新節(jié)點的地址。如果鏈表的頭也為空的話，表示鏈表剛剛創(chuàng)建，該節(jié)點不僅是頭節(jié)點也是尾結(jié)點。

2.3 插入元素的用法

有了上面插入元素到鏈表尾部源碼的分析，我們來看看實際上是怎么使用_lv_ll_ins_tail函數(shù)的。

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

前面源碼中我們知道，插入的新元素的內(nèi)存是在_lv_ll_ins_tail中分配的，所以我們先插入，然后判斷如果這個內(nèi)存分配成功的話，我們就可以把插入到末尾的指針的值賦值為我們的節(jié)點next_node。

3 總結(jié)

實際上LVGL中鏈表的實現(xiàn)和我們預(yù)期的鏈表數(shù)據(jù)結(jié)構(gòu)差不多，唯一的不同是這里允許自定義每個節(jié)點的大小，然后直接在節(jié)點中保存數(shù)據(jù)，而不是保存指針，這也是一種思路吧。當(dāng)然，鏈表的操作不止在尾部插入元素，在lv_ll.c文件中還有獲取鏈表長度、刪除節(jié)點等函數(shù)，如果全部都分析一遍，篇幅就太長了，也是大家熟知的鏈表，故沒有多大的意義。這篇文章的目的就是了解一下LVGL中鏈表的數(shù)據(jù)結(jié)構(gòu)，然后以往尾部插入元素為例加深對LVGL中實現(xiàn)的鏈表的理解。