序章碎碎念

對(duì)于鏈表，大家應(yīng)該都不陌生。學(xué)過數(shù)據(jù)結(jié)構(gòu)的，都知道它作為鏈?zhǔn)絻?chǔ)存的基礎(chǔ)，重要性不言而喻。
由于本人自動(dòng)化專業(yè)，實(shí)際上不學(xué)數(shù)據(jù)結(jié)構(gòu)。在大四眾人考研的考研，找工作的找工作的情況下。本人在學(xué)校開始了蹭課之旅。在一場(chǎng)和大二學(xué)弟們同堂聽課的過程中，這里也第一次遇見本次的主題——鏈表。
早期學(xué)習(xí)鏈表的時(shí)候，實(shí)際上對(duì)malloc和free是幾乎沒有理解的。老師在講解的時(shí)候，就輕描淡寫的一帶而過，這里如果心里沒有對(duì)它有初步的認(rèn)識(shí)，很容易搞不清楚情況。

這里在序言中，我就簡(jiǎn)單的對(duì)基礎(chǔ)比較差的讀者介紹一下這兩位后續(xù)常用的東西——malloc和free。

// 這是包含我們需要使用的malloc和free函數(shù)的頭文件
#include <stdlib.h> // 這里是主角之一，malloc
// 首先，malloc本身不是單詞，是memory allocation縮寫
// 從功能上，malloc會(huì)在運(yùn)行時(shí)動(dòng)態(tài)申請(qǐng)內(nèi)存大小為size字節(jié)的內(nèi)存，然后返回給你這段內(nèi)存的首地址
// 額外要注意的是，malloc申請(qǐng)的內(nèi)存只能通過free釋放
// 如果申請(qǐng)失敗（內(nèi)存不足等）則返回NULL
void* malloc(size_t size) // 這里是另一位主角，free
// free比較簡(jiǎn)單，它會(huì)通過指針釋放掉之前申請(qǐng)的內(nèi)存
// 那么有問題，如果值傳入指針，free函數(shù)如何知道自己釋放多大內(nèi)存？
// 這個(gè)實(shí)際上在malloc的時(shí)候，會(huì)多申請(qǐng)一塊出來用于存放大小信息，一邊f(xié)ree的時(shí)候能夠訪問
// 有興趣的可以探究一下這個(gè)問題
void free(void* ptr)

數(shù)組	malloc+free
聲明時(shí)申請(qǐng)內(nèi)存，超過使用域則由系統(tǒng)自動(dòng)回收（主打一個(gè)省心）	自己申請(qǐng)，自己釋放（主打一個(gè)自由）
編譯初期固定大小（除c99標(biāo)準(zhǔn)下可變數(shù)組）	編譯過程中可以通過變量動(dòng)態(tài)申請(qǐng)大小
隨便申請(qǐng)釋放，無所畏懼	小內(nèi)存頻繁申請(qǐng)釋放會(huì)產(chǎn)生內(nèi)存碎片
不怕產(chǎn)生內(nèi)存泄漏	當(dāng)內(nèi)存未釋放，但是未有任何指針引用它的時(shí)候，會(huì)產(chǎn)生內(nèi)存泄漏
局部變量出作用域就被釋放，有時(shí)候會(huì)導(dǎo)致野指針	內(nèi)存申請(qǐng)后就算出函數(shù)也不會(huì)消失，必須等待你釋放

既然講到這里，其實(shí)基本認(rèn)為讀者已經(jīng)對(duì)指針有所了解了。如果再往下科普，這個(gè)話題就越說越跑偏了。
回到這個(gè)話題來，初學(xué)者的鏈表之旅會(huì)較為容易。更多的精力可能會(huì)放到研究鏈表如何增刪改查。學(xué)到的也是以簡(jiǎn)單的單向鏈表為主：

在學(xué)習(xí)的時(shí)候，咱們看到最多的鏈表也是形如下面的結(jié)構(gòu)體：

struct Node {int data;           // 數(shù)據(jù)struct Node* next;  // 指向下一個(gè)節(jié)點(diǎn)的指針
};

然后每次都是手?jǐn)]創(chuàng)建、銷毀、增刪改查。對(duì)于新手的我們來說，很難做到封裝成模塊使用。
于是乎，漫長(zhǎng)的時(shí)間里，我?guī)缀醵疾幌胗眠@玩意。手?jǐn)]一套太麻煩了。我開始尋找有無能復(fù)用的鏈表模塊。

從redis源碼里掏出來的adlist

某個(gè)偶然的機(jī)會(huì)，我從一篇文章里看到了C語言寫的數(shù)據(jù)庫(kù) redis 中的一個(gè)數(shù)據(jù)結(jié)構(gòu)。正式咱們后續(xù)要說的主角：adlist。我于是乎去翻閱源碼，抽絲剝繭。最終總結(jié)如下：

#include <stdlib.h>
#include "adlist.h"/* Create a new list. The created list can be freed with* listRelease(), but private value of every node need to be freed* by the user before to call listRelease(), or by setting a free method using* listSetFreeMethod.** On error, NULL is returned. Otherwise the pointer to the new list. */
list *listCreate(void)
{struct list *list;if ((list = malloc(sizeof(*list))) == NULL)return NULL;list->head = list->tail = NULL;list->len = 0;list->dup = NULL;list->free = NULL;list->match = NULL;return list;
}/* Remove all the elements from the list without destroying the list itself. */
void listEmpty(list *list)
{unsigned long len;listNode *current, *next;current = list->head;len = list->len;while (len--){next = current->next;if (list->free)list->free(current->value);free(current);current = next;}list->head = list->tail = NULL;list->len = 0;
}/* Free the whole list.** This function can't fail. */
void listRelease(list *list)
{listEmpty(list);free(list);
}/* Add a new node to the list, to head, containing the specified 'value'* pointer as value.** On error, NULL is returned and no operation is performed (i.e. the* list remains unaltered).* On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeHead(list *list, void *value)
{listNode *node;if ((node = malloc(sizeof(*node))) == NULL)return NULL;node->value = value;if (list->len == 0){list->head = list->tail = node;node->prev = node->next = NULL;}else{node->prev = NULL;node->next = list->head;list->head->prev = node;list->head = node;}list->len++;return list;
}/* Add a new node to the list, to tail, containing the specified 'value'* pointer as value.** On error, NULL is returned and no operation is performed (i.e. the* list remains unaltered).* On success the 'list' pointer you pass to the function is returned. */
list *listAddNodeTail(list *list, void *value)
{listNode *node;if ((node = malloc(sizeof(*node))) == NULL)return NULL;node->value = value;if (list->len == 0){list->head = list->tail = node;node->prev = node->next = NULL;}else{node->prev = list->tail;node->next = NULL;list->tail->next = node;list->tail = node;}list->len++;return list;
}list *listInsertNode(list *list, listNode *old_node, void *value, int after)
{listNode *node;if ((node = malloc(sizeof(*node))) == NULL)return NULL;node->value = value;if (after){node->prev = old_node;node->next = old_node->next;if (list->tail == old_node){list->tail = node;}}else{node->next = old_node;node->prev = old_node->prev;if (list->head == old_node){list->head = node;}}if (node->prev != NULL){node->prev->next = node;}if (node->next != NULL){node->next->prev = node;}list->len++;return list;
}/* Remove the specified node from the specified list.* It's up to the caller to free the private value of the node.** This function can't fail. */
void listDelNode(list *list, listNode *node)
{if (node->prev)node->prev->next = node->next;elselist->head = node->next;if (node->next)node->next->prev = node->prev;elselist->tail = node->prev;if (list->free)list->free(node->value);free(node);list->len--;
}/* Returns a list iterator 'iter'. After the initialization every* call to listNext() will return the next element of the list.** This function can't fail. */
listIter *listGetIterator(list *list, int direction)
{listIter *iter;if ((iter = malloc(sizeof(*iter))) == NULL)return NULL;if (direction == AL_START_HEAD)iter->next = list->head;elseiter->next = list->tail;iter->direction = direction;return iter;
}/* Release the iterator memory */
void listReleaseIterator(listIter *iter)
{free(iter);
}/* Create an iterator in the list private iterator structure */
void listRewind(list *list, listIter *li)
{li->next = list->head;li->direction = AL_START_HEAD;
}void listRewindTail(list *list, listIter *li)
{li->next = list->tail;li->direction = AL_START_TAIL;
}/* Return the next element of an iterator.* It's valid to remove the currently returned element using* listDelNode(), but not to remove other elements.** The function returns a pointer to the next element of the list,* or NULL if there are no more elements, so the classical usage* pattern is:** iter = listGetIterator(list,<direction>);* while ((node = listNext(iter)) != NULL) {*     doSomethingWith(listNodeValue(node));* }** */
listNode *listNext(listIter *iter)
{listNode *current = iter->next;if (current != NULL){if (iter->direction == AL_START_HEAD)iter->next = current->next;elseiter->next = current->prev;}return current;
}/* Duplicate the whole list. On out of memory NULL is returned.* On success a copy of the original list is returned.** The 'Dup' method set with listSetDupMethod() function is used* to copy the node value. Otherwise the same pointer value of* the original node is used as value of the copied node.** The original list both on success or error is never modified. */
list *listDup(list *orig)
{list *copy;listIter iter;listNode *node;if ((copy = listCreate()) == NULL)return NULL;copy->dup = orig->dup;copy->free = orig->free;copy->match = orig->match;listRewind(orig, &iter);while ((node = listNext(&iter)) != NULL){void *value;if (copy->dup){value = copy->dup(node->value);if (value == NULL){listRelease(copy);return NULL;}}else{value = node->value;}if (listAddNodeTail(copy, value) == NULL){/* Free value if dup succeed but listAddNodeTail failed. */if (copy->free)copy->free(value);listRelease(copy);return NULL;}}return copy;
}/* Search the list for a node matching a given key.* The match is performed using the 'match' method* set with listSetMatchMethod(). If no 'match' method* is set, the 'value' pointer of every node is directly* compared with the 'key' pointer.** On success the first matching node pointer is returned* (search starts from head). If no matching node exists* NULL is returned. */
listNode *listSearchKey(list *list, void *key)
{listIter iter;listNode *node;listRewind(list, &iter);while ((node = listNext(&iter)) != NULL){if (list->match){if (list->match(node->value, key)){return node;}}else{if (key == node->value){return node;}}}return NULL;
}/* Return the element at the specified zero-based index* where 0 is the head, 1 is the element next to head* and so on. Negative integers are used in order to count* from the tail, -1 is the last element, -2 the penultimate* and so on. If the index is out of range NULL is returned. */
listNode *listIndex(list *list, long index)
{listNode *n;if (index < 0){index = (-index) - 1;n = list->tail;while (index-- && n)n = n->prev;}else{n = list->head;while (index-- && n)n = n->next;}return n;
}/* Rotate the list removing the tail node and inserting it to the head. */
void listRotateTailToHead(list *list)
{if (listLength(list) <= 1)return;/* Detach current tail */listNode *tail = list->tail;list->tail = tail->prev;list->tail->next = NULL;/* Move it as head */list->head->prev = tail;tail->prev = NULL;tail->next = list->head;list->head = tail;
}/* Rotate the list removing the head node and inserting it to the tail. */
void listRotateHeadToTail(list *list)
{if (listLength(list) <= 1)return;listNode *head = list->head;/* Detach current head */list->head = head->next;list->head->prev = NULL;/* Move it as tail */list->tail->next = head;head->next = NULL;head->prev = list->tail;list->tail = head;
}/* Add all the elements of the list 'o' at the end of the* list 'l'. The list 'other' remains empty but otherwise valid. */
void listJoin(list *l, list *o)
{if (o->len == 0)return;o->head->prev = l->tail;if (l->tail)l->tail->next = o->head;elsel->head = o->head;l->tail = o->tail;l->len += o->len;/* Setup other as an empty list. */o->head = o->tail = NULL;o->len = 0;
}

#ifndef __ADLIST_H__
#define __ADLIST_H__/* Node, List, and Iterator are the only data structures used currently. */typedef struct listNode
{struct listNode *prev;struct listNode *next;void *value;
} listNode;typedef struct listIter
{listNode *next;int direction;
} listIter;typedef struct list
{listNode *head;listNode *tail;void *(*dup)(void *ptr);void (*free)(void *ptr);int (*match)(void *ptr, void *key);unsigned long len;
} list;/* Functions implemented as macros */
#define listLength(l) ((l)->len)
#define listFirst(l) ((l)->head)
#define listLast(l) ((l)->tail)
#define listPrevNode(n) ((n)->prev)
#define listNextNode(n) ((n)->next)
#define listNodeValue(n) ((n)->value)#define listSetDupMethod(l, m) ((l)->dup = (m))
#define listSetFreeMethod(l, m) ((l)->free = (m))
#define listSetMatchMethod(l, m) ((l)->match = (m))#define listGetDupMethod(l) ((l)->dup)
#define listGetFreeMethod(l) ((l)->free)
#define listGetMatchMethod(l) ((l)->match)/* Prototypes */
list *listCreate(void);
void listRelease(list *list);
void listEmpty(list *list);
list *listAddNodeHead(list *list, void *value);
list *listAddNodeTail(list *list, void *value);
list *listInsertNode(list *list, listNode *old_node, void *value, int after);
void listDelNode(list *list, listNode *node);
listIter *listGetIterator(list *list, int direction);
listNode *listNext(listIter *iter);
void listReleaseIterator(listIter *iter);
list *listDup(list *orig);
listNode *listSearchKey(list *list, void *key);
listNode *listIndex(list *list, long index);
void listRewind(list *list, listIter *li);
void listRewindTail(list *list, listIter *li);
void listRotateTailToHead(list *list);
void listRotateHeadToTail(list *list);
void listJoin(list *l, list *o);/* Directions for iterators */
#define AL_START_HEAD 0
#define AL_START_TAIL 1#endif /* __ADLIST_H__ */

在原代碼的基礎(chǔ)上修改的不多，刪掉了一些依賴，替換成了malloc之類的。這部分大家可以自己復(fù)制到自己的adlist.c adlist.h文件中，然后引入到自己的工程里面，就能夠嘗試去使用了。
這里給出一個(gè)，本人自己寫的簡(jiǎn)單的使用例程：

#include "adlist.h"
#include <stdio.h>/*** @brief 簡(jiǎn)單的遍歷打印鏈表* * @param l 鏈表對(duì)象*/
void print_list(list *l)
{printf("list len: %d\n", listLength(l));listIter *iter = listGetIterator(l, AL_START_HEAD);  // 創(chuàng)建迭代器// 使用迭代器進(jìn)行迭代for (listNode *node = listNext(iter);node != NULL;node = listNext(iter)) {if (node != NULL) {printf("list value:%d\n", *(int *)listNodeValue(node));}}listReleaseIterator(iter); // 結(jié)束后銷毀迭代器
}int main(void)
{list *list1 = listCreate(); // 創(chuàng)建鏈表對(duì)象// 這里最好是malloc或者全局變量// 不然出函數(shù)就會(huì)被回收，導(dǎo)致鏈表保存的指針為野指針int value1 = 1; int value2 = 2;// 添加數(shù)據(jù)到鏈表尾部listAddNodeTail(list1, &value1); listAddNodeTail(list1, &value2);print_list(list1);return 0;
}

redis里面的adlist我認(rèn)為是功能最全，代碼可讀性最好的鏈表，使用起來也最友好的鏈表了。代碼不需要注釋也能明白它用法。所以這里也不多做筆墨去分析它了。

極致的精簡(jiǎn)的list.h

而后的時(shí)間，與朋友交流的時(shí)候發(fā)現(xiàn)，他們更多的使用linux內(nèi)核鏈表。

#ifndef __LIST_H__
#define __LIST_H__#ifndef offsetof
#define offsetof(type,member) __builtin_offsetof(type,member)
#endifstruct list_head {struct list_head *next, *prev;
};typedef struct list_head list_t;/*** container_of - cast a member of a structure out to the containing structure* @ptr:    the pointer to the member.* @type:   the type of the container struct this is embedded in.* @member: the name of the member within the struct.**/#ifndef container_of
#define container_of(ptr, type, member) ({          \const typeof( ((type *)0)->member ) *__mptr = (ptr);    \(type *)( (char *)__mptr - offsetof(type,member) );})
#endif/** Simple doubly linked list implementation.** Some of the internal functions ("__xxx") are useful when* manipulating whole lists rather than single entries, as* sometimes we already know the next/prev entries and we can* generate better code by using them directly rather than* using the generic single-entry routines.*/
//static define
#define LIST_HEAD_INIT(name) { &(name), &(name) }#define LIST_HEAD(name) \struct list_head name = LIST_HEAD_INIT(name)//動(dòng)態(tài)初始化
static inline void INIT_LIST_HEAD(struct list_head *list)
{list->next = list;list->prev = list;
}/** Insert a new_node entry between two known consecutive entries.** This is only for internal list manipulation where we know* the prev/next entries already!*/
static inline void __list_add(struct list_head *new_node,struct list_head *prev,struct list_head *next)
{next->prev = new_node;new_node->next = next;new_node->prev = prev;prev->next = new_node;
}/*** list_add - add a new_node entry* @new_node: new_node entry to be added* @head: list head to add it after** Insert a new_node entry after the specified head.* This is good for implementing stacks.*/
static inline void list_add(struct list_head *new_node, struct list_head *head)
{__list_add(new_node, head, head->next);
}/*** list_add_tail - add a new_node entry* @new_node: new_node entry to be added* @head: list head to add it before** Insert a new_node entry before the specified head.* This is useful for implementing queues.*/
static inline void list_add_tail(struct list_head *new_node, struct list_head *head)
{__list_add(new_node, head->prev, head);
}/** Delete a list entry by making the prev/next entries* point to each other.** This is only for internal list manipulation where we know* the prev/next entries already!*/
static inline void __list_del(struct list_head *prev, struct list_head *next)
{next->prev = prev;prev->next = next;
}/*** list_del - deletes entry from list.* @entry: the element to delete from the list.* Note: list_empty() on entry does not return true after this, the entry is* in an undefined state.*/
static inline void __list_del_entry(struct list_head *entry)
{__list_del(entry->prev, entry->next);
}static inline void list_del(struct list_head *entry)
{__list_del(entry->prev, entry->next);//entry->next = LIST_POISON1;//entry->prev = LIST_POISON2;
}/*** list_replace - replace old entry by new_node one* @old : the element to be replaced* @new_node : the new_node element to insert** If @old was empty, it will be overwritten.*/
static inline void list_replace(struct list_head *old,struct list_head *new_node)
{new_node->next = old->next;new_node->next->prev = new_node;new_node->prev = old->prev;new_node->prev->next = new_node;
}static inline void list_replace_init(struct list_head *old,struct list_head *new_node)
{list_replace(old, new_node);INIT_LIST_HEAD(old);
}/*** list_del_init - deletes entry from list and reinitialize it.* @entry: the element to delete from the list.*/
static inline void list_del_init(struct list_head *entry)
{__list_del_entry(entry);INIT_LIST_HEAD(entry);
}/*** list_move - delete from one list and add as another's head* @list: the entry to move* @head: the head that will precede our entry*/
static inline void list_move(struct list_head *list, struct list_head *head)
{__list_del_entry(list);list_add(list, head);
}/*** list_move_tail - delete from one list and add as another's tail* @list: the entry to move* @head: the head that will follow our entry*/
static inline void list_move_tail(struct list_head *list,struct list_head *head)
{__list_del_entry(list);list_add_tail(list, head);
}/*** list_is_last - tests whether @list is the last entry in list @head* @list: the entry to test* @head: the head of the list*/
static inline int list_is_last(const struct list_head *list,const struct list_head *head)
{return list->next == head;
}/*** list_empty - tests whether a list is empty* @head: the list to test.*/
static inline int list_empty(const struct list_head *head)
{return head->next == head;
}/*** list_empty_careful - tests whether a list is empty and not being modified* @head: the list to test** Description:* tests whether a list is empty _and_ checks that no other CPU might be* in the process of modifying either member (next or prev)** NOTE: using list_empty_careful() without synchronization* can only be safe if the only activity that can happen* to the list entry is list_del_init(). Eg. it cannot be used* if another CPU could re-list_add() it.*/
static inline int list_empty_careful(const struct list_head *head)
{struct list_head *next = head->next;return (next == head) && (next == head->prev);
}/*** list_rotate_left - rotate the list to the left* @head: the head of the list*/
static inline void list_rotate_left(struct list_head *head)
{struct list_head *first;if (!list_empty(head)) {first = head->next;list_move_tail(first, head);}
}/*** list_is_singular - tests whether a list has just one entry.* @head: the list to test.*/
static inline int list_is_singular(const struct list_head *head)
{return !list_empty(head) && (head->next == head->prev);
}static inline void __list_cut_position(struct list_head *list,struct list_head *head, struct list_head *entry)
{struct list_head *new_node_first = entry->next;list->next = head->next;list->next->prev = list;list->prev = entry;entry->next = list;head->next = new_node_first;new_node_first->prev = head;
}/*** list_cut_position - cut a list into two* @list: a new_node list to add all removed entries* @head: a list with entries* @entry: an entry within head, could be the head itself*  and if so we won't cut the list** This helper moves the initial part of @head, up to and* including @entry, from @head to @list. You should* pass on @entry an element you know is on @head. @list* should be an empty list or a list you do not care about* losing its data.**/
static inline void list_cut_position(struct list_head *list,struct list_head *head, struct list_head *entry)
{if (list_empty(head)) {return;}if (list_is_singular(head) &&(head->next != entry && head != entry)) {return;}if (entry == head) {INIT_LIST_HEAD(list);} else {__list_cut_position(list, head, entry);}
}static inline void __list_splice(const struct list_head *list,struct list_head *prev,struct list_head *next)
{struct list_head *first = list->next;struct list_head *last = list->prev;first->prev = prev;prev->next = first;last->next = next;next->prev = last;
}/*** list_splice - join two lists, this is designed for stacks* @list: the new_node list to add.* @head: the place to add it in the first list.*/
static inline void list_splice(const struct list_head *list,struct list_head *head)
{if (!list_empty(list)) {__list_splice(list, head, head->next);}
}/*** list_splice_tail - join two lists, each list being a queue* @list: the new_node list to add.* @head: the place to add it in the first list.*/
static inline void list_splice_tail(struct list_head *list,struct list_head *head)
{if (!list_empty(list)) {__list_splice(list, head->prev, head);}
}/*** list_splice_init - join two lists and reinitialise the emptied list.* @list: the new_node list to add.* @head: the place to add it in the first list.** The list at @list is reinitialised*/
static inline void list_splice_init(struct list_head *list,struct list_head *head)
{if (!list_empty(list)) {__list_splice(list, head, head->next);INIT_LIST_HEAD(list);}
}/*** list_splice_tail_init - join two lists and reinitialise the emptied list* @list: the new_node list to add.* @head: the place to add it in the first list.** Each of the lists is a queue.* The list at @list is reinitialised*/
static inline void list_splice_tail_init(struct list_head *list,struct list_head *head)
{if (!list_empty(list)) {__list_splice(list, head->prev, head);INIT_LIST_HEAD(list);}
}/*** list_entry - get the struct for this entry* @ptr:    the &struct list_head pointer.* @type:   the type of the struct this is embedded in.* @member: the name of the list_struct within the struct.*/
#define list_entry(ptr, type, member) \container_of(ptr, type, member)/*** list_first_entry - get the first element from a list* @ptr:    the list head to take the element from.* @type:   the type of the struct this is embedded in.* @member: the name of the list_struct within the struct.** Note, that list is expected to be not empty.*/
#define list_first_entry(ptr, type, member) \list_entry((ptr)->next, type, member)/*** list_for_each    -   iterate over a list* @pos:    the &struct list_head to use as a loop cursor.* @head:   the head for your list.*/
#define list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)/*** __list_for_each  -   iterate over a list* @pos:    the &struct list_head to use as a loop cursor.* @head:   the head for your list.** This variant doesn't differ from list_for_each() any more.* We don't do prefetching in either case.*/
#define __list_for_each(pos, head) \for (pos = (head)->next; pos != (head); pos = pos->next)/*** list_for_each_prev   -   iterate over a list backwards* @pos:    the &struct list_head to use as a loop cursor.* @head:   the head for your list.*/
#define list_for_each_prev(pos, head) \for (pos = (head)->prev; pos != (head); pos = pos->prev)/*** list_for_each_safe - iterate over a list safe against removal of list entry* @pos:    the &struct list_head to use as a loop cursor.* @n:      another &struct list_head to use as temporary storage* @head:   the head for your list.*/
#define list_for_each_safe(pos, n, head) \for (pos = (head)->next, n = pos->next; pos != (head); \pos = n, n = pos->next)/*** list_for_each_prev_safe - iterate over a list backwards safe against removal of list entry* @pos:    the &struct list_head to use as a loop cursor.* @n:      another &struct list_head to use as temporary storage* @head:   the head for your list.*/
#define list_for_each_prev_safe(pos, n, head) \for (pos = (head)->prev, n = pos->prev; \pos != (head); \pos = n, n = pos->prev)/*** list_for_each_entry  -   iterate over list of given type* @pos:    the type * to use as a loop cursor.* @head:   the head for your list.* @member: the name of the list_struct within the struct.*/
#define list_for_each_entry(pos, head, member)              \for (pos = list_entry((head)->next, typeof(*pos), member);  \&pos->member != (head);    \pos = list_entry(pos->member.next, typeof(*pos), member))/*** list_for_each_entry_reverse - iterate backwards over list of given type.* @pos:    the type * to use as a loop cursor.* @head:   the head for your list.* @member: the name of the list_struct within the struct.*/
#define list_for_each_entry_reverse(pos, head, member)          \for (pos = list_entry((head)->prev, typeof(*pos), member);  \&pos->member != (head);    \pos = list_entry(pos->member.prev, typeof(*pos), member))/*** list_prepare_entry - prepare a pos entry for use in list_for_each_entry_continue()* @pos:    the type * to use as a start point* @head:   the head of the list* @member: the name of the list_struct within the struct.** Prepares a pos entry for use as a start point in list_for_each_entry_continue().*/
#define list_prepare_entry(pos, head, member) \((pos) ? : list_entry(head, typeof(*pos), member))/*** list_for_each_entry_continue - continue iteration over list of given type* @pos:    the type * to use as a loop cursor.* @head:   the head for your list.* @member: the name of the list_struct within the struct.** Continue to iterate over list of given type, continuing after* the current position.*/
#define list_for_each_entry_continue(pos, head, member)         \for (pos = list_entry(pos->member.next, typeof(*pos), member);  \&pos->member != (head);    \pos = list_entry(pos->member.next, typeof(*pos), member))/*** list_for_each_entry_continue_reverse - iterate backwards from the given point* @pos:    the type * to use as a loop cursor.* @head:   the head for your list.* @member: the name of the list_struct within the struct.** Start to iterate over list of given type backwards, continuing after* the current position.*/
#define list_for_each_entry_continue_reverse(pos, head, member)     \for (pos = list_entry(pos->member.prev, typeof(*pos), member);  \&pos->member != (head);    \pos = list_entry(pos->member.prev, typeof(*pos), member))/*** list_for_each_entry_from - iterate over list of given type from the current point* @pos:    the type * to use as a loop cursor.* @head:   the head for your list.* @member: the name of the list_struct within the struct.** Iterate over list of given type, continuing from current position.*/
#define list_for_each_entry_from(pos, head, member)             \for (; &pos->member != (head);  \pos = list_entry(pos->member.next, typeof(*pos), member))/*** list_for_each_entry_safe - iterate over list of given type safe against removal of list entry* @pos:    the type * to use as a loop cursor.* @n:      another type * to use as temporary storage* @head:   the head for your list.* @member: the name of the list_struct within the struct.*/
#define list_for_each_entry_safe(pos, n, head, member)          \for (pos = list_entry((head)->next, typeof(*pos), member),  \n = list_entry(pos->member.next, typeof(*pos), member); \&pos->member != (head);                    \pos = n, n = list_entry(n->member.next, typeof(*n), member))/*** list_for_each_entry_safe_continue - continue list iteration safe against removal* @pos:    the type * to use as a loop cursor.* @n:      another type * to use as temporary storage* @head:   the head for your list.* @member: the name of the list_struct within the struct.** Iterate over list of given type, continuing after current point,* safe against removal of list entry.*/
#define list_for_each_entry_safe_continue(pos, n, head, member)         \for (pos = list_entry(pos->member.next, typeof(*pos), member),      \n = list_entry(pos->member.next, typeof(*pos), member);     \&pos->member != (head);                        \pos = n, n = list_entry(n->member.next, typeof(*n), member))/*** list_for_each_entry_safe_from - iterate over list from current point safe against removal* @pos:    the type * to use as a loop cursor.* @n:      another type * to use as temporary storage* @head:   the head for your list.* @member: the name of the list_struct within the struct.** Iterate over list of given type from current point, safe against* removal of list entry.*/
#define list_for_each_entry_safe_from(pos, n, head, member)             \for (n = list_entry(pos->member.next, typeof(*pos), member);        \&pos->member != (head);                        \pos = n, n = list_entry(n->member.next, typeof(*n), member))/*** list_for_each_entry_safe_reverse - iterate backwards over list safe against removal* @pos:    the type * to use as a loop cursor.* @n:      another type * to use as temporary storage* @head:   the head for your list.* @member: the name of the list_struct within the struct.** Iterate backwards over list of given type, safe against removal* of list entry.*/
#define list_for_each_entry_safe_reverse(pos, n, head, member)      \for (pos = list_entry((head)->prev, typeof(*pos), member),  \n = list_entry(pos->member.prev, typeof(*pos), member); \&pos->member != (head);                    \pos = n, n = list_entry(n->member.prev, typeof(*n), member))/*** list_safe_reset_next - reset a stale list_for_each_entry_safe loop* @pos:    the loop cursor used in the list_for_each_entry_safe loop* @n:      temporary storage used in list_for_each_entry_safe* @member: the name of the list_struct within the struct.** list_safe_reset_next is not safe to use in general if the list may be* modified concurrently (eg. the lock is dropped in the loop body). An* exception to this is if the cursor element (pos) is pinned in the list,* and list_safe_reset_next is called after re-taking the lock and before* completing the current iteration of the loop body.*/
#define list_safe_reset_next(pos, n, member)                \n = list_entry(pos->member.next, typeof(*pos), member)#endif /* __LIST_H__*/

這個(gè)鏈表更加極致，整體就只有一個(gè)頭文件。代碼不是宏就是內(nèi)聯(lián)函數(shù)。理論上不使用它，它開銷是0。這樣的做法導(dǎo)致它的開銷極低，但是它使用起來不是很方便。代碼的可讀性也比較差。但是效率就很高

#include "list.h"
#include <stdio.h>
#include <stdlib.h>
#include <string.h>typedef struct _student_t {char name[20];int age;list_t list;
} student_t;void student_reg(list_t* student_list, const char *name, int age)
{student_t *student = (student_t *)malloc(sizeof(student_t));student->age = age;strncpy(student->name, name, sizeof(student->name));list_add_tail(&student->list, student_list);
}void main(void)
{list_t student_list = LIST_HEAD_INIT(student_list);student_reg(&student_list, "Alice", 20);student_reg(&student_list, "Bob", 22);student_t *entry, *_entry;list_for_each_entry(entry, &student_list, list) {printf("Name: %s, Age: %d\n", entry->name, entry->age);}list_for_each_entry_safe(entry, _entry, &student_list, list) {list_del(&entry->list); // 從鏈表中刪除節(jié)點(diǎn)free(entry);}
}

如果說adlist的做法，是認(rèn)為萬物都可以看成指針，包到adlist的void *value;中去。那么，list.h的做法則是講自己打包，包到任何的數(shù)據(jù)類型里面去。遍歷鏈表后，可以通過它的container_of找到每個(gè)包含了鏈表節(jié)點(diǎn)的結(jié)構(gòu)體的頭。從而實(shí)現(xiàn)鏈表的功能。它本身還不涉及任何內(nèi)存分配和釋放，也不依賴任何頭文件。真的做到了0依賴，0動(dòng)態(tài)內(nèi)存分配。對(duì)于這種特別底層的東西做到這樣的程度是尤為厲害的。這也使得我不得不“捏著鼻子”用。

lvgl對(duì)鏈表的巧思lv_ll

終于到了咱們的主角，lvgl的源碼
這次我們先從我寫的例子入手，再看源碼。逐步分析它：

#include "lv_ll.h"#include <stdio.h>int main()
{// 鏈表頭的創(chuàng)建lv_ll_t list;// 初始化，并設(shè)置了鏈表的value的大小lv_ll_init(&list, sizeof(int));// 插入鏈表的時(shí)候順帶申請(qǐng)了空間（一次malloc）int* a = (int*)lv_ll_ins_tail(&list);int* b = (int*)lv_ll_ins_tail(&list);// 設(shè)置數(shù)據(jù)*a = 1;*b = 2;// 開始遍歷鏈表嗎，并打印值for (int* list_node  = (int*)lv_ll_get_head(&list); list_node != NULL; list_node = lv_ll_get_next(&list, list_node)){printf("num:%d\n", *list_node);}return 0;
}

根著我的注釋，大家應(yīng)該了解了如何使用鏈表去存儲(chǔ)變量。
咱們把a(bǔ)dlist list 和 lv_ll拉到一起，做個(gè)對(duì)比

對(duì)比內(nèi)容	adlist	list	lv_ll
鏈表本身	創(chuàng)建時(shí)分配內(nèi)存	外部傳入（用靜態(tài)動(dòng)態(tài)用戶選擇）	創(chuàng)建時(shí)分配
鏈表數(shù)據(jù)	用戶創(chuàng)建傳入指針	用戶創(chuàng)建	和鏈表一起創(chuàng)建

實(shí)際上list所有內(nèi)容都是由外部傳入，它本身是僅僅關(guān)注鏈表的操作內(nèi)容。這種方式優(yōu)點(diǎn)就在于無論使用靜態(tài)（數(shù)組）還是動(dòng)態(tài)（malloc）內(nèi)存都是可以用戶自定義的。

在adlist的時(shí)候， 鏈表的內(nèi)存使用了malloc。不用再用戶端角度考慮傳入了，但是void* value還是需要傳入。如果這里是局部變量的指針就會(huì)導(dǎo)致出現(xiàn)野指針的危險(xiǎn)，使用時(shí)應(yīng)當(dāng)注意。

lv_ll則非同尋常的做法，在初始化的時(shí)候會(huì)固定好你每個(gè)節(jié)點(diǎn)的value大小。讓我們來看看它鏈表頭是啥樣的：

/** 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;

這里鏈表頭里面有保存每個(gè)節(jié)點(diǎn)的大小倒是不驚訝。但是這個(gè)uint8_t *類型的頭尾節(jié)點(diǎn)著實(shí)和我們之前接觸到的鏈表有所不同。我們繼續(xù)看看它初始化在做什么：

void lv_ll_init(lv_ll_t *ll_p, uint32_t node_size)
{ll_p->head = NULL;ll_p->tail = NULL;
#ifdef LV_ARCH_64/*Round the size up to 8*/node_size = (node_size + 7) & (~0x7);
#else/*Round the size up to 4*/node_size = (node_size + 3) & (~0x3);
#endifll_p->n_size = node_size;
}

從初始化開始我們來對(duì)比一下三者不同的點(diǎn)：
list的結(jié)構(gòu)， 無論是頭還是節(jié)點(diǎn)，都只用同一個(gè)數(shù)據(jù)結(jié)構(gòu)list_t。遍歷的時(shí)候判斷結(jié)尾也是判斷下一個(gè)是否等于頭，是雙向循環(huán)鏈表：

adlist則是有它專屬的頭list，和節(jié)點(diǎn)listNode兩種對(duì)象
節(jié)點(diǎn)本質(zhì)上是雙向鏈表，遍歷到next為NULL的時(shí)候結(jié)束遍歷

從初始化上來看，我們的主角應(yīng)該也是adlist這樣的，所以初始化是NULL。計(jì)算node_size 這里是根據(jù)架構(gòu)進(jìn)行字節(jié)對(duì)齊（不足32bit或者64bit的算32bit或64bit）。這樣不會(huì)出現(xiàn)內(nèi)存對(duì)齊的意外。
接下來看看lv_ll_ins_tail的源碼：

/*** Add a new tail to a linked list* @param ll_p pointer to linked list* @return pointer to the new tail*/
void *lv_ll_ins_tail(lv_ll_t *ll_p)
{lv_ll_node_t *n_new;n_new = malloc(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;
}

這里就是一個(gè)技巧點(diǎn)。之前說了lvgl的鏈表不僅僅將鏈表使用malloc申請(qǐng)好了，也將你value使用malloc申請(qǐng)好了。這里的節(jié)點(diǎn)數(shù)據(jù)結(jié)構(gòu)實(shí)際上是隱藏的，本質(zhì)上是一個(gè)uint8_t的next一個(gè)uint8_t類型的prev。所以這里malloc的大小是之前設(shè)置好的vlaue的size大小加上"元節(jié)點(diǎn)"大小。

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

這里一大塊數(shù)據(jù)被分成了數(shù)據(jù)區(qū)域和next和prev指針，三個(gè)結(jié)構(gòu)體元素，且不用結(jié)構(gòu)體。這里實(shí)際上沒解決一個(gè)問題。為啥用uint8_t類型去指向下一個(gè)或者上一個(gè)節(jié)點(diǎn)內(nèi)存的區(qū)域，而不是void。這個(gè)比較好理解，首先要了解的是，不同類型的指針本質(zhì)都是一個(gè)指針大小的vlaue，不過里面存放的位置不同罷了。如果value相同（指向同一片內(nèi)存）。類型不同會(huì)導(dǎo)致偏移一個(gè)單位后的偏移字節(jié)不相同。比如，針對(duì)uint32_t類型+1則會(huì)偏移四個(gè)字節(jié)，而uint8_t +1則會(huì)偏移一個(gè)字節(jié)。所以，這里在設(shè)計(jì)的時(shí)候不會(huì)對(duì)這個(gè)指針取值，所以u(píng)int8_t設(shè)計(jì)是為了方便做偏移計(jì)算。
很明顯一開始聲明的n_new是lv_ll_node_t 。但是返回值確實(shí)void類型的，其中涉及一個(gè)隱式類型轉(zhuǎn)換。也就是說用戶拿到手里還是void*類型。

那實(shí)際上lvgl的鏈表本質(zhì)上和adlist很相似。不過加入了自己的一些小特色。

文章尾部附上lvgl中的lv_ll源碼（魔改后無其它依賴）

/*** @file lv_ll.c* Handle linked lists.* The nodes are dynamically allocated by the 'lv_mem' module,*//**********************      INCLUDES*********************/
#include "lv_ll.h"
#include <stdlib.h>/**********************      DEFINES*********************/
#define LL_NODE_META_SIZE (sizeof(lv_ll_node_t *) + sizeof(lv_ll_node_t *))
#define LL_PREV_P_OFFSET(ll_p) (ll_p->n_size)
#define LL_NEXT_P_OFFSET(ll_p) (ll_p->n_size + sizeof(lv_ll_node_t *))/***********************      TYPEDEFS**********************//***********************  STATIC PROTOTYPES**********************/
static void node_set_prev(lv_ll_t *ll_p, lv_ll_node_t *act, lv_ll_node_t *prev);
static void node_set_next(lv_ll_t *ll_p, lv_ll_node_t *act, lv_ll_node_t *next);/***********************  STATIC VARIABLES**********************//***********************      MACROS**********************//***********************   GLOBAL FUNCTIONS**********************//*** Initialize linked list* @param ll_p pointer to lv_ll_t variable* @param node_size the size of 1 node in bytes*/
void lv_ll_init(lv_ll_t *ll_p, uint32_t node_size)
{ll_p->head = NULL;ll_p->tail = NULL;
#ifdef LV_ARCH_64/*Round the size up to 8*/node_size = (node_size + 7) & (~0x7);
#else/*Round the size up to 4*/node_size = (node_size + 3) & (~0x3);
#endifll_p->n_size = node_size;
}/*** Add a new head to a linked list* @param ll_p pointer to linked list* @return pointer to the new head*/
void *lv_ll_ins_head(lv_ll_t *ll_p)
{lv_ll_node_t *n_new;n_new = malloc(ll_p->n_size + LL_NODE_META_SIZE);if (n_new != NULL) {node_set_prev(ll_p, n_new, NULL);       /*No prev. before the new head*/node_set_next(ll_p, n_new, ll_p->head); /*After new comes the old head*/if (ll_p->head != NULL) { /*If there is old head then before it goes the new*/node_set_prev(ll_p, ll_p->head, n_new);}ll_p->head = n_new;      /*Set the new head in the dsc.*/if (ll_p->tail == NULL) { /*If there is no tail (1. node) set the tail too*/ll_p->tail = n_new;}}return n_new;
}/*** Insert a new node in front of the n_act node* @param ll_p pointer to linked list* @param n_act pointer a node* @return pointer to the new node*/
void *lv_ll_ins_prev(lv_ll_t *ll_p, void *n_act)
{lv_ll_node_t *n_new;if (NULL == ll_p || NULL == n_act) {return NULL;}if (lv_ll_get_head(ll_p) == n_act) {n_new = lv_ll_ins_head(ll_p);if (n_new == NULL) {return NULL;}} else {n_new = malloc(ll_p->n_size + LL_NODE_META_SIZE);if (n_new == NULL) {return NULL;}lv_ll_node_t *n_prev;n_prev = lv_ll_get_prev(ll_p, n_act);node_set_next(ll_p, n_prev, n_new);node_set_prev(ll_p, n_new, n_prev);node_set_prev(ll_p, n_act, n_new);node_set_next(ll_p, n_new, n_act);}return n_new;
}/*** Add a new tail to a linked list* @param ll_p pointer to linked list* @return pointer to the new tail*/
void *lv_ll_ins_tail(lv_ll_t *ll_p)
{lv_ll_node_t *n_new;n_new = malloc(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;
}/*** Remove the node 'node_p' from 'll_p' linked list.* It does not free the memory of node.* @param ll_p pointer to the linked list of 'node_p'* @param node_p pointer to node in 'll_p' linked list*/
void lv_ll_remove(lv_ll_t *ll_p, void *node_p)
{if (ll_p == NULL) {return;}if (lv_ll_get_head(ll_p) == node_p) {/*The new head will be the node after 'n_act'*/ll_p->head = lv_ll_get_next(ll_p, node_p);if (ll_p->head == NULL) {ll_p->tail = NULL;} else {node_set_prev(ll_p, ll_p->head, NULL);}} else if (lv_ll_get_tail(ll_p) == node_p) {/*The new tail will be the node before 'n_act'*/ll_p->tail = lv_ll_get_prev(ll_p, node_p);if (ll_p->tail == NULL) {ll_p->head = NULL;} else {node_set_next(ll_p, ll_p->tail, NULL);}} else {lv_ll_node_t *n_prev = lv_ll_get_prev(ll_p, node_p);lv_ll_node_t *n_next = lv_ll_get_next(ll_p, node_p);node_set_next(ll_p, n_prev, n_next);node_set_prev(ll_p, n_next, n_prev);}
}/*** Remove and free all elements from a linked list. The list remain valid but become empty.* @param ll_p pointer to linked list*/
void lv_ll_clear(lv_ll_t *ll_p)
{void *i;void *i_next;i      = lv_ll_get_head(ll_p);i_next = NULL;while (i != NULL) {i_next = lv_ll_get_next(ll_p, i);lv_ll_remove(ll_p, i);free(i);i = i_next;}
}/*** Move a node to a new linked list* @param ll_ori_p pointer to the original (old) linked list* @param ll_new_p pointer to the new linked list* @param node pointer to a node* @param head true: be the head in the new list*             false be the tail in the new list*/
void lv_ll_chg_list(lv_ll_t *ll_ori_p, lv_ll_t *ll_new_p, void *node, bool head)
{lv_ll_remove(ll_ori_p, node);if (head) {/*Set node as head*/node_set_prev(ll_new_p, node, NULL);node_set_next(ll_new_p, node, ll_new_p->head);if (ll_new_p->head != NULL) { /*If there is old head then before it goes the new*/node_set_prev(ll_new_p, ll_new_p->head, node);}ll_new_p->head = node;       /*Set the new head in the dsc.*/if (ll_new_p->tail == NULL) { /*If there is no tail (first node) set the tail too*/ll_new_p->tail = node;}} else {/*Set node as tail*/node_set_prev(ll_new_p, node, ll_new_p->tail);node_set_next(ll_new_p, node, NULL);if (ll_new_p->tail != NULL) { /*If there is old tail then after it goes the new*/node_set_next(ll_new_p, ll_new_p->tail, node);}ll_new_p->tail = node;       /*Set the new tail in the dsc.*/if (ll_new_p->head == NULL) { /*If there is no head (first node) set the head too*/ll_new_p->head = node;}}
}/*** Return with head node of the linked list* @param ll_p pointer to linked list* @return pointer to the head of 'll_p'*/
void *lv_ll_get_head(const lv_ll_t *ll_p)
{if (ll_p == NULL) {return NULL;}return ll_p->head;
}/*** Return with tail node of the linked list* @param ll_p pointer to linked list* @return pointer to the tail of 'll_p'*/
void *lv_ll_get_tail(const lv_ll_t *ll_p)
{if (ll_p == NULL) {return NULL;}return ll_p->tail;
}/*** Return with the pointer of the next node after 'n_act'* @param ll_p pointer to linked list* @param n_act pointer a node* @return pointer to the next node*/
void *lv_ll_get_next(const lv_ll_t *ll_p, const void *n_act)
{/*Pointer to the next node is stored in the end of this node.*Go there and return the address found there*/const lv_ll_node_t *n_act_d = n_act;n_act_d += LL_NEXT_P_OFFSET(ll_p);return *((lv_ll_node_t **)n_act_d);
}/*** Return with the pointer of the previous node before 'n_act'* @param ll_p pointer to linked list* @param n_act pointer a node* @return pointer to the previous node*/
void *lv_ll_get_prev(const lv_ll_t *ll_p, const void *n_act)
{/*Pointer to the prev. node is stored in the end of this node.*Go there and return the address found there*/const lv_ll_node_t *n_act_d = n_act;n_act_d += LL_PREV_P_OFFSET(ll_p);return *((lv_ll_node_t **)n_act_d);
}/*** Return the length of the linked list.* @param ll_p pointer to linked list* @return length of the linked list*/
uint32_t lv_ll_get_len(const lv_ll_t *ll_p)
{uint32_t len = 0;void *node;for (node = lv_ll_get_head(ll_p); node != NULL; node = lv_ll_get_next(ll_p, node)) {len++;}return len;
}/*** Move a node before an other node in the same linked list* @param ll_p pointer to a linked list* @param n_act pointer to node to move* @param n_after pointer to a node which should be after `n_act`*/
void lv_ll_move_before(lv_ll_t *ll_p, void *n_act, void *n_after)
{if (n_act == n_after) {return;    /*Can't move before itself*/}void *n_before;if (n_after != NULL) {n_before = lv_ll_get_prev(ll_p, n_after);} else {n_before = lv_ll_get_tail(ll_p);    /*if `n_after` is NULL `n_act` should be the new tail*/}if (n_act == n_before) {return;    /*Already before `n_after`*/}/*It's much easier to remove from the list and add again*/lv_ll_remove(ll_p, n_act);/*Add again by setting the prev. and next nodes*/node_set_next(ll_p, n_before, n_act);node_set_prev(ll_p, n_act, n_before);node_set_prev(ll_p, n_after, n_act);node_set_next(ll_p, n_act, n_after);/*If `n_act` was moved before NULL then it become the new tail*/if (n_after == NULL) {ll_p->tail = n_act;}/*If `n_act` was moved before `NULL` then it's the new head*/if (n_before == NULL) {ll_p->head = n_act;}
}/*** Check if a linked list is empty* @param ll_p pointer to a linked list* @return true: the linked list is empty; false: not empty*/
bool lv_ll_is_empty(lv_ll_t *ll_p)
{if (ll_p == NULL) {return true;}if (ll_p->head == NULL && ll_p->tail == NULL) {return true;}return false;
}/***********************   STATIC FUNCTIONS**********************//*** Set the previous node pointer of a node* @param ll_p pointer to linked list* @param act pointer to a node which prev. node pointer should be set* @param prev pointer to a node which should be the previous node before 'act'*/
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;
}/*** Set the 'next node pointer' of a node* @param ll_p pointer to linked list* @param act pointer to a node which next node pointer should be set* @param next pointer to a node which should be the next node before 'act'*/
static void node_set_next(lv_ll_t *ll_p, lv_ll_node_t *act, lv_ll_node_t *next)
{if (act == NULL) {return;    /*Can't set the next node of `NULL`*/}uint8_t *act8 = (uint8_t *)act;act8 += LL_NEXT_P_OFFSET(ll_p);lv_ll_node_t **act_node_p = (lv_ll_node_t **) act8;lv_ll_node_t **next_node_p = (lv_ll_node_t **) &next;*act_node_p = *next_node_p;
}

/*** @file lv_ll.h* Handle linked lists. The nodes are dynamically allocated by the 'lv_mem' module.*/#ifndef LV_LL_H
#define LV_LL_H#ifdef __cplusplus
extern "C" {
#endif/**********************      INCLUDES*********************/
#include <stdint.h>
#include <stddef.h>
#include <stdbool.h>/**********************      DEFINES*********************//***********************      TYPEDEFS**********************//** 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;/*********************** GLOBAL PROTOTYPES**********************//*** Initialize linked list* @param ll_p pointer to lv_ll_t variable* @param node_size the size of 1 node in bytes*/
void lv_ll_init(lv_ll_t * ll_p, uint32_t node_size);/*** Add a new head to a linked list* @param ll_p pointer to linked list* @return pointer to the new head*/
void * lv_ll_ins_head(lv_ll_t * ll_p);/*** Insert a new node in front of the n_act node* @param ll_p pointer to linked list* @param n_act pointer a node* @return pointer to the new node*/
void * lv_ll_ins_prev(lv_ll_t * ll_p, void * n_act);/*** Add a new tail to a linked list* @param ll_p pointer to linked list* @return pointer to the new tail*/
void * lv_ll_ins_tail(lv_ll_t * ll_p);/*** Remove the node 'node_p' from 'll_p' linked list.* It does not free the memory of node.* @param ll_p pointer to the linked list of 'node_p'* @param node_p pointer to node in 'll_p' linked list*/
void lv_ll_remove(lv_ll_t * ll_p, void * node_p);/*** Remove and free all elements from a linked list. The list remain valid but become empty.* @param ll_p pointer to linked list*/
void lv_ll_clear(lv_ll_t * ll_p);/*** Move a node to a new linked list* @param ll_ori_p pointer to the original (old) linked list* @param ll_new_p pointer to the new linked list* @param node pointer to a node* @param head true: be the head in the new list*             false be the tail in the new list*/
void lv_ll_chg_list(lv_ll_t * ll_ori_p, lv_ll_t * ll_new_p, void * node, bool head);/*** Return with head node of the linked list* @param ll_p pointer to linked list* @return pointer to the head of 'll_p'*/
void * lv_ll_get_head(const lv_ll_t * ll_p);/*** Return with tail node of the linked list* @param ll_p pointer to linked list* @return pointer to the tail of 'll_p'*/
void * lv_ll_get_tail(const lv_ll_t * ll_p);/*** Return with the pointer of the next node after 'n_act'* @param ll_p pointer to linked list* @param n_act pointer a node* @return pointer to the next node*/
void * lv_ll_get_next(const lv_ll_t * ll_p, const void * n_act);/*** Return with the pointer of the previous node after 'n_act'* @param ll_p pointer to linked list* @param n_act pointer a node* @return pointer to the previous node*/
void * lv_ll_get_prev(const lv_ll_t * ll_p, const void * n_act);/*** Return the length of the linked list.* @param ll_p pointer to linked list* @return length of the linked list*/
uint32_t lv_ll_get_len(const lv_ll_t * ll_p);/*** TODO* @param ll_p* @param n1_p* @param n2_p
void lv_ll_swap(lv_ll_t * ll_p, void * n1_p, void * n2_p);*//*** Move a node before an other node in the same linked list* @param ll_p pointer to a linked list* @param n_act pointer to node to move* @param n_after pointer to a node which should be after `n_act`*/
void lv_ll_move_before(lv_ll_t * ll_p, void * n_act, void * n_after);/*** Check if a linked list is empty* @param ll_p pointer to a linked list* @return true: the linked list is empty; false: not empty*/
bool lv_ll_is_empty(lv_ll_t * ll_p);/***********************      MACROS**********************/#define lv_LL_READ(list, i) for(i = lv_ll_get_head(list); i != NULL; i = lv_ll_get_next(list, i))#define lv_LL_READ_BACK(list, i) for(i = lv_ll_get_tail(list); i != NULL; i = lv_ll_get_prev(list, i))#ifdef __cplusplus
} /*extern "C"*/
#endif#endif

尾記

大家喜歡哪一種鏈表呢？還是說大家有更方便的鏈表？評(píng)論區(qū)歡迎您的討論