深入理解Linux内核之链表 list.h 功能实现原理、接口说明及示例代码 _链表

目录
一、双向链表接口函数及相关宏定义分析
0、结构体
1、(TYPE, ) 宏
2、(ptr, type, ) 宏
3、宏
4、宏
5、函数
6、和的区别
7、函数
8、函数
9、函数
10. 函数
11、宏
12、宏
13、宏函数
14、宏函数
15、宏函数
16、宏函数的使用示例
17、safe函数
18、函数
19、其他
二、单向链表接口函数及相关宏定义
三、双向链表综合应用案例-增、减、删、清空操作
最近在学习链表数据结构，开始是想找个库来使用，后来发现linux内核的链表list.h本身就是一个特别好的库，本文着重的分析list.h文件中功能、重要接口，然后结合实际的应用程序来具体分析。
下面的条目都是最常用的宏和函数，一些不常用的宏没有列出，有兴趣的可以直接查看源码。
一、双向链表接口函数及相关宏定义分析 0、结构体
结构体定义原型如下：
struct list_head {struct list_head *next, *prev;};
这是一个双链表结构，这个结构体定义的相当巧妙，里面并没有数据元素，只有2个链表指针，分别指向前一个链表点地址和后一个链表点地址，之所以这么定义是为了通用，linux是提供了链表管理接口，并不提供具体的数据结构链表，我们在定义自己的链表的时候，增加一个指针就可以使用list.h提供的所有接口了。
这个双链表结构，进一步理解，是一个双向循环链表，或者说是双向环形链表，环形链表相比单向链表，优点是头尾相连，这一点对于遍历整个链表的代码实现是很重要也是很方便的，因为最后一个节点的next一定是指向链表头 head的，而链表头head的prev一定是指向最后一个节点的。链表结构如下：
从上图可知，使用链表，是需要一个head 指针的，这个指针就相当于一根引线， head本身没有任何数据内容，只有两个方向指针prev和next，而自定义的数据结构中只要包含了指针就可以使用 list提供的所有接口函数了，自定义链表结构如下：
typedef struct userType{void *data;struct list_head list} USR_LIST_TYPE;
1、(TYPE, ) 宏
该宏的代码原型如下：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)//其中 TYPE 为结构体类型，MEMBER为该结构体的元素，
该宏的功能是获取在该结构体中的偏移地址。举例来说：
struct test{int a;int b;};
则执行 ( test, a) = 0; ( test, b) = 4;
具体的解释，可以参考文章《 of 分析》
2、(ptr, type, ) 宏
该宏的代码原型如下：
#define container_of(ptr, type, member) ({\const typeof(((type *)0)->member) * __mptr = (ptr); \(type *)((char *)__mptr - offsetof(type, member)); })//其中 type 是结构体类型，member是结构体中的元素， ptr是指向memeber的指针，是个地址
该宏的功能是：通过结构体类型type中的地址(ptr）获取这个结构体的入口地址。测试代码如下：
/** Get offset of a member variable.** @param[in] type the type of the struct this embedded in* @param[in] member the name of the variable within the struct.*/#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)/** Get the struct for this entry.** @para[in] ptrthe list head to take the element from.* @para[in] typethe type of the struct this is embedded in.* @para[in] member the name of the variable within the struct.*/#define container_of(ptr, type, member) ({\const typeof(((type *)0)->member) * __mptr = (ptr); \(type *)((char *)__mptr - offsetof(type, member)); })typedef struct {int data1;int data2;}TEST_TYPE;int main(int argc, char *argv[]) {TEST_TYPE tests = {1,2};int *ptr = &tests.data2;printf("data1 offset:%d\n", offsetof(TEST_TYPE, data1));printf("data2 offset:%d\n", offsetof(TEST_TYPE, data2));printf("ptr:%d\n", ptr);printf("tests addr:%d\n", container_of(ptr, TEST_TYPE, data2));return 0;}
运行结果如下：
data1 offset:0data2 offset:4ptr:6487556tests addr:6487552
结果验证了所属功能，data2的地址为 ptr也就是，而data2的偏移地址是4，所以结构体tests的地址是

文章插图
- 4 =
3、宏
宏原型如下：
#define LIST_HEAD_INIT(name） {&(name), &(name)}
先说功能：该宏的作用是初始化链表节点，将prev和next指针都指向结构体变量name本身。第一次看到这个宏的时候，我是有些蒙圈的，怎么还有这种操作？这是嘛意思？理解这个宏，我们要有这么几个前提：
① name 的类型一定是，所以name中自然是包含2个元素的，分别为*prev,和*next.这连个元素是指针，换言说就是“地址值”
② 我们对结构体变量进行赋值或者初始化的时候，可以逐个元素的赋值，也可以通过{ }，进行一次性赋值。
有了上面2个前提，我们对这个宏展开，功能如下：

LIST_HEAD_INIT(name) 替换成 {&(name), &(name)} 其实就是 将 name 本身的地址（&取地址符）分别赋值给 name的两个元素 struct list_head *prev和 *next

所以该宏是不能单独使用的，需要将结果返回给一个类型的变量。
4、宏
该宏的原型如下：
#define LIST_HEAD(name) \struct list_head name = LIST_HEAD_INIT(name)
通过前面的分析，可知该宏的功能：定义1个类型头指针，并且初始化。
5、函数
该函数原型如下：
static inline void INIT_LIST_HEAD(struct list_head *list){list->next = list;list->prev = list;}
该函数是一个内联函数，内联函数一般都是定义在头文件中的，调用内联函数时，相当于将内联函数嵌入到被调用函数中了，这样就节省了函数调用所需的栈空间，所以执行效率比较高，list.h中的所有接口函数都是内联函数。
该函数的功能：初始化链表头指针head，将其prev和next元素都指向list 本身。
6、和的区别
第一次接触这两者的时候，还有点蒙，怎么定义了两个一样功能的东西，后来一琢磨发现还真完全一样，区别是：
宏有2个动作：定义一个变量，然后初始化该变量。
只有1个动作：初始化已经定义过的变量。
所以在使用函数时，需要先定义好变量，然后再调用该函数，而则不用，一次就完成了，具体怎么使用，就看自己的习惯了。
7、函数
函数原型：

static inline void __list_add(struct list_head *new,struct list_head *prev,struct list_head *next){next->prev = new;new->next = next;new->prev = prev;prev->next = new;}/*** list_add - add a new entry* @new: new entry to be added* @head: list head to add it after---此处就是特制链表头 head** Insert a new entry after the specified head.* This is good for implementing stacks.*/static inline void list_add(struct list_head *new, struct list_head *head){__list_add(new, head, head->next);}

功能：将新链表节点指针 new 添加到节点 head之后，而且从双链表的设计架构上看，此处的head就是链表头，所以该功能是插入到链表头head之后。
8、函数
函数原型：

/*** list_add_tail - add a new entry* @new: new entry to be added* @head: list head to add it before---此处就是特指链表头 。** Insert a new entry before the specified head.* This is useful for implementing queues.*/static inline void list_add_tail(struct list_head *new, struct list_head *head){__list_add(new, head->prev, head);}

其中函数其实是插入功能，将节点new插入到 head之后。
功能：将 new节点插入到链表头head节点之前，源码的注释说的很清楚：在head之前插入一个新的节点，由于是双向循环链表，也就是一个环形链表，所以这里的 tail 十分形象，就是在链表的末尾处增加一个新的节点。
9、函数
函数原型：

/** 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;}static inline void list_del(struct list_head *entry){__list_del(entry->prev, entry->next);entry->next = LIST_POISON1;entry->prev = LIST_POISON2;}

功能：删除链表中的一个节点entry，链表节点的删除，其实是删除掉该节点在链表中的逻辑链接接关系，让该节点的前一个节点 next直接指向该节点的后一个节点，而后一个节点的 prev直接指向该节点的前一个节点。而对于被删除的这个节点指针，并没有进行进行物理删除，而是将其指向了所谓的毒指针，这样如果后面再使用这个节点，就可以认为这个节点指针是空的了。我们也可以对进行修改，方便我们的理解。修改如下：

static inline void list_del(dlist_t *node){dlist_t *prev = node->prev;dlist_t *next = node->next;prev->next = next;next->prev = prev;}

这个理解起来更容易，不过确实要承认，不如linux中的实现，更加稳定。
10. 函数
函数原型：

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

功能:判断该链表是否为空，这里判断的逻辑，一定是判断这个链表的头指针 head的next是否指向它自己，如果是，则说明为空，这里其实可以判断链表中任意一个节点是否为空。
11、宏
原型：

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

功能：获取链表中某个节点的地址，这里调用了宏函数，即通过结构体元素的地址计算出整个结构体的起始地址，这个函数很重要，主要用于链表的遍历，通过链表中某个节点的某个元素的地址，计算出这个节点的地址。
12、宏
原型：

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

功能：如字面意思，获取链表中第一个元素（节点）的地址，这里已经限定了，一定是链表的第一个节点的地址，注意，不是head的地址，链表的head中并不会有内容， head的下一个节点才是有效的数据节点，该函数也是获取第一个first节点的入口地址，但是ptr一般是head，因为使用的时候是ptr->next 。
13、宏函数
函数原型：

/*** 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; prefetch(pos->next), pos != (head); \pos = pos->next)

功能：正如注释里所说：（迭代、重复），从头遍历整个链表。这里特别注意，pos只是一个临时的变量，该宏函数一定是从链表的头部head 遍历整个链表，而定义为void (void *a (())) { }，这个太高级了，我们可以简单的想，一定是判断 pos不是 NULL ，只要是 pos->next为空，就说明到了链表的结尾了。对于一些工程案例中，没有使用，也是可以的，直接判断pos与head是否相等，因为该链表结构为双向循环的。所以如果自己写代码，不想实现，完全可以删掉，如下所示：
#define list_for_each(pos, head) \for (pos = (head)->next;pos != (head); pos = pos->next)
注：上面的代码中只有 for(xxx;xxx;xxx)，并没有执行的内容，所以真正用的时候，用的方式如下：
list_for_each(pos, head){/* 循环执行代码 */}
14、宏函数
原型：

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

功能：也是遍历链表函数，只不过如果我们在遍历的过程中涉及到节点的删除操作，则需要使用这个函数，从这个函数中也可以发现，有了一个中间节点 n 作为临时存储区，这也契合了函数名中 safe的含义，更加安全。
15、宏函数
原型：

/*** 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.//我们自己的链表 头 head* @member:	the name of the list_struct within the struct. // 链表结构体的 元素 ， 一般就是*那个struct list_head 的指针元素*/#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循环体的实现原理：
①

pos = list_entry((head)->next, typeof(*pos), member);其中：(head)->next:链表头head的next元素，指向了整个链表的 第一个含数据的有效 节点 。typeof(*pos): 获取 *pos 的数据类型 。这个一般是我们自定义的数据结构 。member： 我们自定义的数据结构 member元素 ， 一般就是那个 struct head_list 类型元素list_entry: 通过结构体中的 member 的地址计算出该链表节点的地址 。所以该条命令是：获取 链表节点地址 ， 然后赋值给 pos

②

pos->member != (head);//判断该节点 是否是 链表头节点head ， 这是遍历for循环中的条件判断部分，//由于链表是双链表循环结构，如果pos->member == head, 说明已经遍历到最//后,或者该链表为空

③

pos = list_entry(pos->member.next, typeof(*pos), member))这里的方式跟①中一样 ， 只不过取的 pos->member.next，也就是更新pos为当前节点的下一个节点 ， 到这里我们第一次感受到了struct list_head 数据结构的设计巧妙 ， 可以很方便（尽管理解起来难）的找到任意一个节点 。

16、宏函数的使用示例
前面讲解了宏函数功能（遍历查找）以及实现原理，但是怎么用，还是会有点抽象，下面我们来用代码举例：

typedef struct usrList{int index;int data;struct list_head list;} USR_LIST_TYPE;int main(int argc, char *argv[]) {USR_LIST_TYPE msg, *pmsg;LIST_HEAD(msg_head);int *ptr = &msg.data;int i;/* insert the 10 msgs */for(i = 0; i < 10; i++){pmsg = (USR_LIST_TYPE *)malloc(sizeof(USR_LIST_TYPE));pmsg->index = i + 1;pmsg->data =http://www.kingceram.com/post/(i + 1)*10;list_add_tail(&pmsg->list, &msg_head);}/* 根据list 遍历 整个链表 ， 并打印信息 */list_for_each_entry(pmsg, &msg_head, list){printf("msg index:%ddata:%d\n", pmsg->index, pmsg->data);}return 0;}

运行结果如下：

msg index:1data:10msg index:2data:20msg index:3data:30msg index:4data:40msg index:5data:50msg index:6data:60msg index:7data:70msg index:8data:80msg index:9data:90msg index:10data:100

17、safe函数
原型：

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

功能：的安全版，当遍历过程中涉及到删除节点的时候，使用该宏函数。
18、函数
原型：

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

功能：反向遍历整个链表。
19、其他
双向链表的其他接口参考源码list.h
二、单向链表接口函数及相关宏定义
通过对双向链表的学习，我们了解了链表的相关操作，双向链表功能比较全，但是也有一点点缺点，就是每个链表节点都包含2个方向指针，所以如果可以定义一种单向链表，对于内存来讲，不仅能够节省内存，而且对于一些简单的结构，遍历的效率也会更高, ，这里参考阿里云IOT- C SDK中单向链表的实现方式，就不一一的解释了，毕竟能够理解双向链表，再去看单向链表，就很简单了。该链表结构是单向不循环数据结构，如下图所示：
代码如下：

/* for single link list */typedef struct slist_s {struct slist_s *next;} slist_t;static inline void slist_add(slist_t *node, slist_t *head){node->next = head->next;head->next = node;}static inline void slist_add_tail(slist_t *node, slist_t *head){while (head->next) {head = head->next;}slist_add(node, head);}static inline void slist_del(slist_t *node, slist_t *head){while (head->next) {if (head->next == node) {head->next = node->next;break;}head = head->next;}}static inline int slist_empty(const slist_t *head){return !head->next;}static inline void slist_init(slist_t *head){head->next = 0;}/** Iterate over list of given type.** @param[in]queuehe head for your list.* @param[in]nodethe type * to use as a loop cursor.* @param[in]typethe type of the struct this is embedded in.* @param[in]memberthe name of the slist_t within the struct.*/#define slist_for_each_entry(queue, node, type, member)\for (node = container_of((queue)->next, type, member); \&node->member;\node = container_of(node->member.next, type, member))/** Iterate over list of given type safe against removal of list entry.** @param[in]queuethe head for your list.* @param[in]tmpthe type * to use as a temp.* @param[in]nodethe type * to use as a loop cursor.* @param[in]typethe type of the struct this is embedded in.* @param[in]memberthe name of the slist_t within the struct.*/#define slist_for_each_entry_safe(queue, tmp, node, type, member) \for (node = container_of((queue)->next, type, member),\tmp = (queue)->next ? (queue)->next->next : NULL;\&node->member;\node = container_of(tmp, type, member), tmp = tmp ? tmp->next : tmp)/** Initialise the list.** @param[in]namethe list to be initialized.*/#define SLIST_HEAD_INIT(name) {0}/** Initialise the list.** @param[in]namethe list to be initialized.*/#define SLIST_HEAD(name) \slist_t name = SLIST_HEAD_INIT(name)/** Get the struct for this entry.* @param[in]addrthe list head to take the element from.* @param[in]typethe type of the struct this is embedded in.* @param[in]memberthe name of the slist_t within the struct.*/#define slist_entry(addr, type, member) (\addr ? (type *)((long)addr - offsetof(type, member)) : (type *)addr \)/** Get the first element from a list.** @param[in]ptrthe list head to take the element from.* @param[in]typethe type of the struct this is embedded in.* @param[in]memberthe name of the slist_t within the struct.*/#define slist_first_entry(ptr, type, member) \slist_entry((ptr)->next, type, member)/** Get the list length.** @param[in]queuethe head for your list.*/static inline int slist_entry_number(slist_t *queue){int num;slist_t *cur = queue;for (num = 0; cur->next; cur = cur->next, num++);return num;}

三、双向链表综合应用案例-增、减、删、清空操作
示例代码如下：

typedef struct usrList{int index;int data;struct list_head list;} USR_LIST_TYPE;int main(int argc, char *argv[]) {USR_LIST_TYPE msg, *pmsg, *pos,*n;//struct list_head *pos, *n;//用于遍历 临时用LIST_HEAD(msg_head);int *ptr = &msg.data;int i;/* insert the 10 msgs 插入10个节点 */printf("*** now,we will insert 10 msgs into list ******\n");for(i = 0; i < 10; i++){pmsg = (USR_LIST_TYPE *)malloc(sizeof(USR_LIST_TYPE));pmsg->index = i + 1;pmsg->data =http://www.kingceram.com/post/(i + 1)*10;list_add_tail(&pmsg->list, &msg_head);}printf("*** print the list ****************************\n");list_for_each_entry(pmsg, &msg_head, list){printf("msg index:%ddata:%d\n", pmsg->index, pmsg->data);}/* modify the index:5 node,and data is 55， 修改某个节点*/printf("*** now,we will modify the index=5 msg ********\n");list_for_each_entry(pmsg, &msg_head, list){if(pmsg->index == 5){pmsg->data = http://www.kingceram.com/post/55;break;}}//print all the listprintf("*** print the list ****************************\n");list_for_each_entry(pmsg, &msg_head, list){printf("msg index:%ddata:%d\n", pmsg->index, pmsg->data);}//删除某个节点printf("*** now,we will delete the index=5 msg ********\n");list_for_each_entry_safe(pos,n, &msg_head, list){if(pos->index == 5){list_del(&(pos->list));free(pos);break;}}printf("*** print the list ****************************\n");list_for_each_entry(pmsg, &msg_head, list){printf("msg index:%ddata:%d\n", pmsg->index, pmsg->data);}/* 使用list_for_each_safe 进行删除节点操作list_for_each_safe(pos, n, &msg_head){pmsg = list_entry(pos, USR_LIST_TYPE, list);//获取节点指针if(pmsg->index == 5){list_del(pos);free(pmsg);//务必释放该节点所占的物理内存break;}}printf("*** print the list ****************************\n");list_for_each_entry(pmsg, &msg_head, list){printf("msg index:%ddata:%d\n", pmsg->index, pmsg->data);}*///删除全部节点printf("*** now,we will delete all msg ********\n");list_for_each_entry_safe(pos, n, &msg_head, list){list_del(&(pos->list));free(pos);}//判断链表是否为空if(list_empty(&msg_head))printf("the list is empty.\n");else printf("the list is not empty.\n");return 0;}

运行结果如下：
【深入理解Linux内核之链表 list.h 功能实现原理、接口说明及示例代码】

*** now,we will insert 10 msgs into list ********* print the list ****************************msg index:1data:10msg index:2data:20msg index:3data:30msg index:4data:40msg index:5data:50msg index:6data:60msg index:7data:70msg index:8data:80msg index:9data:90msg index:10data:100*** now,we will modify the index=5 msg *********** print the list ****************************msg index:1data:10msg index:2data:20msg index:3data:30msg index:4data:40msg index:5data:55msg index:6data:60msg index:7data:70msg index:8data:80msg index:9data:90msg index:10data:100*** now,we will delete the index=5 msg *********** print the list ****************************msg index:1data:10msg index:2data:20msg index:3data:30msg index:4data:40msg index:6data:60msg index:7data:70msg index:8data:80msg index:9data:90msg index:10data:100*** now,we will delete all msg ********Now,the list is empty.