临沂做网站的,2022年新闻热点事件,tk域名注册官网,seo服务外包报价极致的链表的使用 序章碎碎念从redis源码里掏出来的adlist极致的精简的list.hlvgl对链表的巧思lv_ll尾记 序章碎碎念
对于链表#xff0c;大家应该都不陌生。学过数据结构的#xff0c;都知道它作为链式储存的基础#xff0c;重要性不言而喻。 由于本人自动化专业#xff… 极致的链表的使用 序章碎碎念从redis源码里掏出来的adlist极致的精简的list.hlvgl对链表的巧思lv_ll尾记 序章碎碎念
对于链表大家应该都不陌生。学过数据结构的都知道它作为链式储存的基础重要性不言而喻。 由于本人自动化专业实际上不学数据结构。在大四众人考研的考研找工作的找工作的情况下。本人在学校开始了蹭课之旅。在一场和大二学弟们同堂听课的过程中这里也第一次遇见本次的主题——链表。 早期学习链表的时候实际上对malloc和free是几乎没有理解的。老师在讲解的时候就轻描淡写的一带而过这里如果心里没有对它有初步的认识很容易搞不清楚情况。
这里在序言中我就简单的对基础比较差的读者介绍一下这两位后续常用的东西——malloc和free。
// 这是包含我们需要使用的malloc和free函数的头文件
#include stdlib.h // 这里是主角之一malloc
// 首先malloc本身不是单词是memory allocation缩写
// 从功能上malloc会在运行时动态申请内存大小为size字节的内存然后返回给你这段内存的首地址
// 额外要注意的是malloc申请的内存只能通过free释放
// 如果申请失败内存不足等则返回NULL
void* malloc(size_t size) // 这里是另一位主角free
// free比较简单它会通过指针释放掉之前申请的内存
// 那么有问题如果值传入指针free函数如何知道自己释放多大内存
// 这个实际上在malloc的时候会多申请一块出来用于存放大小信息一边free的时候能够访问
// 有兴趣的可以探究一下这个问题
void free(void* ptr)
数组mallocfree声明时申请内存超过使用域则由系统自动回收主打一个省心自己申请自己释放主打一个自由编译初期固定大小除c99标准下可变数组编译过程中可以通过变量动态申请大小随便申请释放无所畏惧小内存频繁申请释放会产生内存碎片不怕产生内存泄漏当内存未释放但是未有任何指针引用它的时候会产生内存泄漏局部变量出作用域就被释放有时候会导致野指针内存申请后就算出函数也不会消失必须等待你释放
既然讲到这里其实基本认为读者已经对指针有所了解了。如果再往下科普这个话题就越说越跑偏了。 回到这个话题来初学者的链表之旅会较为容易。更多的精力可能会放到研究链表如何增删改查。学到的也是以简单的单向链表为主 在学习的时候咱们看到最多的链表也是形如下面的结构体
struct Node {int data; // 数据struct Node* next; // 指向下一个节点的指针
};然后每次都是手撸创建、销毁、增删改查。对于新手的我们来说很难做到封装成模块使用。 于是乎漫长的时间里我几乎都不想用这玩意。手撸一套太麻烦了。我开始寻找有无能复用的链表模块。
从redis源码里掏出来的adlist
某个偶然的机会我从一篇文章里看到了C语言写的数据库 redis 中的一个数据结构。正式咱们后续要说的主角adlist。我于是乎去翻阅源码抽丝剥茧。最终总结如下
#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 cant 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.* Its up to the caller to free the private value of the node.** This function cant 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 cant 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.* Its 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__ */在原代码的基础上修改的不多删掉了一些依赖替换成了malloc之类的。这部分大家可以自己复制到自己的adlist.c adlist.h文件中然后引入到自己的工程里面就能够尝试去使用了。 这里给出一个本人自己写的简单的使用例程
#include adlist.h
#include stdio.h/*** brief 简单的遍历打印链表* * param l 链表对象*/
void print_list(list *l)
{printf(list len: %d\n, listLength(l));listIter *iter listGetIterator(l, AL_START_HEAD); // 创建迭代器// 使用迭代器进行迭代for (listNode *node listNext(iter);node ! NULL;node listNext(iter)) {if (node ! NULL) {printf(list value:%d\n, *(int *)listNodeValue(node));}}listReleaseIterator(iter); // 结束后销毁迭代器
}int main(void)
{list *list1 listCreate(); // 创建链表对象// 这里最好是malloc或者全局变量// 不然出函数就会被回收导致链表保存的指针为野指针int value1 1; int value2 2;// 添加数据到链表尾部listAddNodeTail(list1, value1); listAddNodeTail(list1, value2);print_list(list1);return 0;
}redis里面的adlist我认为是功能最全代码可读性最好的链表使用起来也最友好的链表了。代码不需要注释也能明白它用法。所以这里也不多做笔墨去分析它了。
极致的精简的list.h
而后的时间与朋友交流的时候发现他们更多的使用linux内核链表。
#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)//动态初始化
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 anothers 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 anothers 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 wont 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 doesnt differ from list_for_each() any more.* We dont 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__*/
这个链表更加极致整体就只有一个头文件。代码不是宏就是内联函数。理论上不使用它它开销是0。这样的做法导致它的开销极低但是它使用起来不是很方便。代码的可读性也比较差。但是效率就很高
#include list.h
#include stdio.h
#include stdlib.h
#include string.htypedef 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); // 从链表中删除节点free(entry);}
}
如果说adlist的做法是认为万物都可以看成指针包到adlist的void *value;中去。那么list.h的做法则是讲自己打包包到任何的数据类型里面去。遍历链表后可以通过它的container_of找到每个包含了链表节点的结构体的头。从而实现链表的功能。它本身还不涉及任何内存分配和释放也不依赖任何头文件。真的做到了0依赖0动态内存分配。对于这种特别底层的东西做到这样的程度是尤为厉害的。这也使得我不得不“捏着鼻子”用。
lvgl对链表的巧思lv_ll
终于到了咱们的主角lvgl的源码 这次我们先从我写的例子入手再看源码。逐步分析它
#include lv_ll.h#include stdio.hint main()
{// 链表头的创建lv_ll_t list;// 初始化并设置了链表的value的大小lv_ll_init(list, sizeof(int));// 插入链表的时候顺带申请了空间一次mallocint* a (int*)lv_ll_ins_tail(list);int* b (int*)lv_ll_ins_tail(list);// 设置数据*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;
}
根着我的注释大家应该了解了如何使用链表去存储变量。 咱们把adlist list 和 lv_ll拉到一起做个对比
对比内容adlistlistlv_ll链表本身创建时分配内存外部传入用静态动态用户选择创建时分配链表数据用户创建传入指针用户创建和链表一起创建
实际上list所有内容都是由外部传入它本身是仅仅关注链表的操作内容。这种方式优点就在于无论使用静态数组还是动态malloc内存都是可以用户自定义的。
在adlist的时候 链表的内存使用了malloc。不用再用户端角度考虑传入了但是void* value还是需要传入。如果这里是局部变量的指针就会导致出现野指针的危险使用时应当注意。
lv_ll则非同寻常的做法在初始化的时候会固定好你每个节点的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;这里链表头里面有保存每个节点的大小倒是不惊讶。但是这个uint8_t *类型的头尾节点着实和我们之前接触到的链表有所不同。我们继续看看它初始化在做什么
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;
}从初始化开始我们来对比一下三者不同的点 list的结构 无论是头还是节点都只用同一个数据结构list_t。遍历的时候判断结尾也是判断下一个是否等于头是双向循环链表
adlist则是有它专属的头list和节点listNode两种对象 节点本质上是双向链表遍历到next为NULL的时候结束遍历 从初始化上来看我们的主角应该也是adlist这样的所以初始化是NULL。计算node_size 这里是根据架构进行字节对齐不足32bit或者64bit的算32bit或64bit。这样不会出现内存对齐的意外。 接下来看看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;
}这里就是一个技巧点。之前说了lvgl的链表不仅仅将链表使用malloc申请好了也将你value使用malloc申请好了。这里的节点数据结构实际上是隐藏的本质上是一个uint8_t的next一个uint8_t类型的prev。所以这里malloc的大小是之前设置好的vlaue的size大小加上元节点大小。
#define LL_NODE_META_SIZE (sizeof(lv_ll_node_t *) sizeof(lv_ll_node_t *))这里一大块数据被分成了数据区域和next和prev指针三个结构体元素且不用结构体。这里实际上没解决一个问题。为啥用uint8_t类型去指向下一个或者上一个节点内存的区域而不是void。这个比较好理解首先要了解的是不同类型的指针本质都是一个指针大小的vlaue不过里面存放的位置不同罢了。如果value相同指向同一片内存。类型不同会导致偏移一个单位后的偏移字节不相同。比如针对uint32_t类型1则会偏移四个字节而uint8_t 1则会偏移一个字节。所以这里在设计的时候不会对这个指针取值所以uint8_t设计是为了方便做偏移计算。 很明显一开始声明的n_new是lv_ll_node_t 。但是返回值确实void类型的其中涉及一个隐式类型转换。也就是说用户拿到手里还是void*类型。
那实际上lvgl的链表本质上和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; /*Cant 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*/}/*Its 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 its 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; /*Cant 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; /*Cant 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
尾记
大家喜欢哪一种链表呢还是说大家有更方便的链表评论区欢迎您的讨论
