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

目录
一、双向链表接口函数及相关宏定义分析
0、list_head 结构体
1、offsetof(TYPE, MEMBER) 宏
2、ontainer_of(ptr, type, member) 宏
3、LIST_HEAD_INIT 宏
4、LIST_HEAD 宏
5、INIT_LIST_HEAD 函数
6、LIST_HEAD 和 INIT_LIST_HEAD 的区别
7、list_add 函数
8、list_add_tail 函数
9、list_del函数
10. list_empty函数
11、list_entry 宏
12、list_first_entry 宏
13、list_for_each 宏函数
14、list_for_each_safe 宏函数
15、list_for_each_entry 宏函数
16、list_for_each_entry 宏函数的使用示例
17、list_for_each_entry_safe函数
18、list_for_each_entry_reverse 函数
19、其他
二、单向链表接口函数及相关宏定义
三、双向链表综合应用案例-增、减、删、清空操作
最近在学习链表数据结构,开始是想找个库来使用,后来发现linux内核的链表list.h本身就是一个特别好的库,本文着重的分析list.h文件中功能、重要接口,然后结合实际的应用程序来具体分析。
下面的条目都是最常用的 宏 和 函数,一些不常用的宏没有列出,有兴趣的可以直接查看源码。
一、双向链表接口函数及相关宏定义分析 0、list_head 结构体 结构体定义原型如下:

struct list_head { struct list_head *next, *prev; };

这是一个双链表结构,这个结构体定义的相当巧妙,里面并没有 数据元素,只有2个链表指针,分别指向前一个链表点地址和后一个链表点地址,之所以这么定义是为了通用,linux是提供了链表管理接口,并不提供具体的数据结构链表,我们在定义自己的链表的时候,增加一个struct list_head 指针就可以使用list.h提供的所有接口了。
这个双链表结构,进一步理解,是一个双向循环链表,或者说是双向环形链表,环形链表相比单向链表,优点是头尾相连,这一点对于遍历 整个链表的 代码实现是很重要也是很方便的,因为最后一个节点的next一定是指向 链表头 head的,而链表头head的prev一定是指向最后一个节点的。链表结构如下:
Linux|深入理解Linux内核之链表 list.h 功能实现原理、接口说明及示例代码
文章图片

从上图可知,使用list_head链表,是需要一个head 指针的,这个指针就相当于一根引线,head本身没有任何数据内容,只有两个方向指针prev和next,而自定义的数据结构中只要包含了list_head指针就可以使用 list提供的所有接口函数了,自定义链表结构如下:
typedef struct userType{ void *data; struct list_head list } USR_LIST_TYPE;


1、offsetof(TYPE, MEMBER) 宏 该宏的代码原型如下:
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)//其中 TYPE 为结构体类型,MEMBER为该结构体的 元素,

该宏的功能是获取 MEMBER在该结构体中的 偏移地址。举例来说:
struct test{ int a; int b; };

则执行offsetof(strtuct test, a) = 0; offsetof(struct test, b) = 4;
具体的解释,可以参考文章《container of 分析》
2、ontainer_of(ptr, type, member) 宏 该宏的代码原型如下:
#define container_of(ptr, type, member) ({\ const typeof(((type *)0)->member) * __mptr = (ptr); \ (type *)((char *)__mptr - offsetof(type, member)); })//其中 type 是结构体类型, member是结构体中的元素,ptr是指向memeber的指针,是个地址

该宏的功能是:通过结构体类型type中memeber的地址(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:0 data2 offset:4 ptr:6487556 tests addr:6487552

结果验证了所属功能,data2的地址为 ptr也就是 6487556,而data2的偏移地址是4, 所以 结构体tests的地址是
6487556 - 4 = 6587552
3、LIST_HEAD_INIT 宏 宏原型如下:
#define LIST_HEAD_INIT(name) {&(name), &(name)}

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

所以该宏是不能单独使用的,需要将结果返回给一个 struct list_head 类型的变量。
4、LIST_HEAD 宏 该宏的原型如下:
#define LIST_HEAD(name) \ struct list_head name = LIST_HEAD_INIT(name)

通过 前面的分析,可知该宏的功能:定义1个struct list_head 类型头指针,并且初始化。
5、INIT_LIST_HEAD 函数 该函数原型如下:
static inline void INIT_LIST_HEAD(struct list_head *list) { list->next = list; list->prev = list; }

该函数是一个内联函数,内联函数一般都是定义在 头文件中的,调用内联函数时,相当于将内联函数嵌入到被调用函数中了,这样就节省了函数调用所需的栈空间,所以执行效率比较高,list.h中的所有接口函数都是内联函数。
该函数的功能:初始化 链表头指针head,将其prev和next元素都 指向list 本身。
6、LIST_HEAD 和 INIT_LIST_HEAD 的区别 第一次接触这两者的时候,还有点蒙,怎么定义了两个一样 功能的东西,后来一琢磨发现还真完全一样,区别是:
LIST_HEAD 宏 有2个动作:定义一个struct list_head 变量,然后初始化该变量。
INIT_LIST_HEAD 只有1个动作:初始化已经定义过的 变量。
所以在使用INIT_LIST_HEAD 函数时,需要先定义好变量,然后再调用该函数,而LIST_HEAD则不用,一次就 完成了,具体怎么使用,就看 自己的习惯了。
7、list_add 函数 函数原型:
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 函数 函数原型:
/** * 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); }

其中 __list_add函数其实是插入功能,将节点new插入到 head之后。
功能:将 new节点 插入到链表头head节点之前,源码的注释说的很清楚:在head之前 插入一个新的 节点,由于list_head是双向循环链表,也就是一个环形链表,所以这里的 tail 十分形象,就是在链表的 末尾处增加一个新的节点。
9、list_del函数 函数原型:
/* * 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直接指向 该节点的前一个节点。而对于被删除的这个节点指针,并没有进行进行物理删除,而是将其指向了所谓 的 毒指针,这样如果后面再使用这个节点,就可以认为这个节点指针是空的了。我们也可以对list_del进行修改,方便我们的理解。修改如下:
static inline void list_del(dlist_t *node) { dlist_t *prev = node->prev; dlist_t *next = node->next; prev->next = next; next->prev = prev; }

这个list_del理解起来更容易,不过确实要承认,不如linux中的实现,更加稳定。
10. list_empty函数 函数原型:
/** * 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 宏 原型:
/** * 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)

功能:获取链表中某个 节点的地址,这里调用了container_of 宏函数,即通过结构体元素 member的 地址计算出 整个结构体的起始地址,这个函数很重要,主要用于链表的遍历,通过链表中某个节点的某个元素的地址,计算出这个 节点的地址。
12、list_first_entry 宏 原型:
/** * 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 宏函数 函数 原型:
/** * 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)

功能:正如注释里所说:nterate(迭代、重复),从头遍历整个链表。这里特别注意,pos只是一个临时的变量,该宏函数 一定是从链表的头部head 遍历整个链表,而prefetch 定义为 static inline void prefetch(void *a __attribute__((unused))) { },这个太高级了,我们可以简单的想,一定是判断 pos不是 NULL,只要是 pos->next为空,就说明到了 链表的结尾了。对于一些 工程案例中,没有使用prefetch, 也是可以的,直接判断pos与head是否相等,因为该链表结构为双向循环的。所以如果自己写代码,不想实现prefetch,完全可以删掉, 如下所示:
#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 宏函数 原型:
/** * 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 宏函数 原型:
/** * 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))

功能: 通过给定类型(member) 遍历链表,通常用于遍历查找某个节点,这个给定类型member就是我们自定义的链表结构中的struct list_head 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、list_for_each_entry 宏函数的使用示例 前面讲解了list_for_each_entry 宏函数功能(遍历查找)以及实现原理,但是怎么用,还是会有点抽象,下面我们来用代码举例:
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 =https://www.it610.com/article/(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:10 msg index:2data:20 msg index:3data:30 msg index:4data:40 msg index:5data:50 msg index:6data:60 msg index:7data:70 msg index:8data:80 msg index:9data:90 msg index:10data:100

17、list_for_each_entry_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))

功能:list_for_each_entry的安全版,当遍历过程中涉及到 删除节点的时候,使用该宏函数。
18、list_for_each_entry_reverse 函数 原型:
/** * 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))

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

代码如下:
/* 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 =https://www.it610.com/article/(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 = https://www.it610.com/article/55; break; } } //print all the list 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 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; }

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


    推荐阅读