linux 内核常用数据结构及算法——list（循环双向链表）

秒速五厘米 2022-08-14 00:51 411阅读 0赞

在linux内核中，应用到链表的地方非常多，所以在内核代码中，专门有一个list.h文件，定义了常用的链表操作，由于该文件的长度太长，这里就不将整个文件都粘出来了，如果没有下载代码，可以在如下网址阅读http://lxr.linux.no/linux+v3.17.3/include/linux/list.h

list.h中，定义了一个链表结点结构体list\_head，

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

在程序中，需要将list\_head作为结构体的指针，然后通过这个指针连接前驱、后继，比如以下的代码：

struct cat{
    	int color;
    	int weight;
    	int age;
    	struct list_head catList;
    };

通过结构体的catList成员可以将多个对象连入链表

### 主要的函数 ###

**INIT\_LIST\_HEAD**   初始化链表头

**list\_add(struct list\_head \*new, struct list\_head \*head)**加入一个新的结点

**list\_add\_tail(struct list\_head \*new, struct list\_head \*head)**在链表的尾部加入新的结点

**list\_del(struct list\_head \*entry)**删除一个结点，删除结点后，还要将其后继设为LIST\_POISON1、前驱设为LIST\_POISON2，目的是以防程序仍然按照错误的地址访问链表

**list\_replace(struct list\_head \*old,  
struct list\_head \*new)**用新的结点替换旧的结点

**list\_replace\_init(struct list\_head \*old,  
struct list\_head \*new)**用新的结点替换旧的结点，然后将旧的结点初始化为另一个链表头

**list\_del\_init(struct list\_head \*entry)**将一个结点从链表上删除，然后将其初始化为另一个

**list\_move(struct list\_head \*list, struct list\_head \*head)**将结点从一个位置换到另一个位置（移动到head之后）

**list\_move\_tail(struct list\_head \*list,  
 struct list\_head \*head)**将结点移动链表尾部（移动到head之前）

**list\_is\_last(const struct list\_head \*list,  
const struct list\_head \*head)**判断一个结点是否为链表的尾部

**list\_empty(const struct list\_head \*head)**判空（只有head）

**list\_empty\_careful(const struct list\_head \*head)**判空，会检查其他cpu有无正在修改该结点

**list\_is\_singular(const struct list\_head \*head)** 判断链表中是否只有head一个结点

**list\_cut\_position(struct list\_head \*list,  
struct list\_head \*head, struct list\_head \*entry)**将一个链表拆成两个，其中，list为新产生链表的头，entry为head链表上的一个结点。拆分后的head到entry之间的部分，被从原有链表中移除，放到新链表list中。

![Center][]

拆分前

![Center 1][]

拆分后

**list\_splice(const struct list\_head \*list,  
struct list\_head \*head)**将链表list合并到结点head之后（list中不包括list结点的所有结点加入head之后）

**static inline void list\_splice\_tail(struct list\_head \*list,  
struct list\_head \*head)**将链表list合并到结点head之前（list中不包括list结点的所有结点加入head之前）

**list\_splice\_init(struct list\_head \*list,  
   struct list\_head \*head)**将链表list合并到结点head之后（list中不包括list结点的所有结点加入head之后），之后重新初始化list结点

**list\_splice\_tail\_init(struct list\_head \*list,  
struct list\_head \*head)**将链表list合并到结点head之前（list中不包括list结点的所有结点加入head之前），之后重新初始化list结点

### 宏函数 ###

#define list_entry(ptr, type, member) \
    	container_of(ptr, type, member)

通过链表的指针，获得结构体的地址，实际上是由container\_of宏实现的，可以参考上一篇博客

#define list_first_entry(ptr, type, member) \
    	list_entry((ptr)->next, type, member)

获得ptr指针后第一个链表结点对应的结构体地址

#define list_for_each(pos, head) \
    	for (pos = (head)->next; prefetch(pos->next), pos != (head); \
            	pos = pos->next)

从head结点处开始，向后遍历整个链表，pos作为遍历的游标（链表结点list\_head的指针），作为后续操作的参数，通常需要与list\_entry协同使用，获得遍历链表上所有的结构体地址，典型的用法如下：

list_for_each (tmp, &cam_list) {
    		cpia = list_entry(tmp, struct cam_data, cam_data_list);
                     ......
            }

#define list_for_each_prev(pos, head) \
    	for (pos = (head)->prev; prefetch(pos->prev), pos != (head); \
            	pos = pos->prev)

从head结点处开始，向前遍历整个链表

#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的安全版本，多了一个临时变量n，用来存储链表结点的下一个结点，可以防止另一个cpu同时操作链表造成的断链问题。通常配合删除链表中的结点时使用，比如：

list_for_each_safe (list, next, &bus_info_head ) {
    		bus_info = list_entry (list, struct bus_info, bus_info_list);
    		kfree (bus_info);
    	}

#define list_for_each_prev_safe(pos, n, head) \
    	for (pos = (head)->prev, n = pos->prev; \
    	     prefetch(pos->prev), pos != (head); \
    	     pos = n, n = pos->prev)

list\_for\_each\_prev的安全版本

#define list_for_each_entry(pos, head, member)				\
    	for (pos = list_entry((head)->next, typeof(*pos), member);	\
    	     prefetch(pos->member.next), &pos->member != (head); 	\
    	     pos = list_entry(pos->member.next, typeof(*pos), member))

member参数为list\_head在数据结构中的名字。功能与list\_for\_each相似，只是pos游标为结构体的指针而不是list\_head的指针

#define list_for_each_entry_reverse(pos, head, member)			\
    	for (pos = list_entry((head)->prev, typeof(*pos), member);	\
    	     prefetch(pos->member.prev), &pos->member != (head); 	\
    	     pos = list_entry(pos->member.prev, typeof(*pos), member))

member参数为list\_head在数据结构中的名字。功能与list\_for\_each\_prev相似，只是pos游标为结构体的指针而不是list\_head的指针

#define list_for_each_entry_continue(pos, head, member) 		\
    	for (pos = list_entry(pos->member.next, typeof(*pos), member);	\
    	     prefetch(pos->member.next), &pos->member != (head);	\
    	     pos = list_entry(pos->member.next, typeof(*pos), member))

继续遍历链表，其中pos为结构体的指针。与list\_for\_each\_entry相比，不同的是，这里的pos需要有初值，即从pos结构体所在的list\_head指针开始向后遍历链表，直到list\_head指针与head相同

#define list_for_each_entry_continue_reverse(pos, head, member)		\
    	for (pos = list_entry(pos->member.prev, typeof(*pos), member);	\
    	     prefetch(pos->member.prev), &pos->member != (head);	\
    	     pos = list_entry(pos->member.prev, typeof(*pos), member))

从pos结构体所在的list\_head指针开始向前遍历链表，直到list\_head指针与head相同

#define list_for_each_entry_from(pos, head, member) 			\
    	for (; prefetch(pos->member.next), &pos->member != (head);	\
    	     pos = list_entry(pos->member.next, typeof(*pos), member))

从指针pos对应的结构体开始向后遍历链表，直到链表结点的指针与head相同。它与list\_for\_each\_entry\_continue不同之处就在于，进入list\_for\_each\_entry\_continue循环，第一次pos的值为pos初值对应的下一个结构体，而该函数第一次循环，pos值就是pos的初值

#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函数的安全版本

#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\_continue的安全版本

#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\_from的安全版本

#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\_for\_each\_entry\_reverse的安全版本

[Center]: /images/20220810/c70af914c9244fa98afd4c29b4902e6d.png
[Center 1]: /images/20220810/37f20acb1b3a4c8facd5682bbc531655.png