深入理解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]	ptr 	the list head to take the element from.* @para[in]	type 	the 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:0
data2 offset:4
ptr:6487556
tests 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 =  (i + 1)*10;list_add_tail(&pmsg->list, &msg_head);}/* 根据list 遍历 整个链表，并打印信息 */list_for_each_entry(pmsg, &msg_head, list){printf("msg index:%d  data:%d\n", pmsg->index, pmsg->data);}return 0;
}

运行结果如下：

msg index:1  data:10
msg index:2  data:20
msg index:3  data:30
msg index:4  data:40
msg index:5  data:50
msg index:6  data:60
msg index:7  data:70
msg index:8  data:80
msg index:9  data:90
msg index:10  data: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]   queue   he head for your list.
* @param[in]   node    the type * to use as a loop cursor.
* @param[in]   type    the type of the struct this is embedded in.
* @param[in]   member  the 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]   queue   the head for your list.* @param[in]   tmp     the type * to use as a temp.* @param[in]   node    the type * to use as a loop cursor.* @param[in]   type    the type of the struct this is embedded in.* @param[in]   member  the 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]   name    the list to be initialized.*/
#define SLIST_HEAD_INIT(name) {0}/** Initialise the list.** @param[in]   name    the list to be initialized.*/
#define SLIST_HEAD(name) \slist_t name = SLIST_HEAD_INIT(name)/** Get the struct for this entry.* @param[in]   addr     the list head to take the element from.* @param[in]   type     the type of the struct this is embedded in.* @param[in]   member   the 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]   ptr     the list head to take the element from.
* @param[in]   type    the type of the struct this is embedded in.
* @param[in]   member  the 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]   queue    the 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 =  (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:%d  data:%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 = 55;break;}}//print all the listprintf("*** print the list ****************************\n");list_for_each_entry(pmsg, &msg_head, list){printf("msg index:%d  data:%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:%d  data:%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:%d  data:%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;
}

运行结果如下：

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