本文共 2176 字，大约阅读时间需要 7 分钟。

在Linux内核源码中，为了创建链表，其创建了list.h文件来创建链表。list.h的路径为/usr/src/kernels/include/linux。

list.h中有两个宏定义：

#define LIST_HEAD_INIT(name) {&(name),&（name）}#define LIST_HEAD(name) \struct list_head name=LSIT_HEAD_INIT(name)

其实写成一行就是：

struct list_head name={&(name),&(name)};

也就是表头的建立以及初始化。注意这里的struct_head结构体建立的不是单链表，而是双链表。在这贴出struct list_head的定义:

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

INIT_LIST_HEAD()函数的操作和这两个宏定义的操作是一样的。

_ _list_add()函数，这是把一个新的节点插入链表中。插入的过程如下图：

其他的插入函数都是调用该函数来完成。

_ _list_del()函数是用来删除链表中的一个节点。删除的方法很明了。

注意，这里虽然改变了前后节点指针指向的地址，但是中间的节点的指针指向的地址并没有改变，所以这个节点是可以用来做位置记录的。 其他的删除函数同样的是调用这个函数来完成。

list_replace()函数是用新的节点替换掉旧的节点。替换的顺序按图示：

这里被替换掉的节点的空间也没有被释放掉，它的指针指向的地址也没有改变，所以节点可以记录位置。

list_move()函数是把节点取出来，然后在插入到自己想移动的地方。它移动的过程是先用__list_del()函数把节点取出来，但不释放。然后在用list_add()把节点插入想去的地方。节点的插入有两种方法，一个是头插：list_add()，一个是尾插：list_add_tail()，所以调用函数的时候要看清。

__list_cut_position()函数是把原来的表分割成两个新表。截取出来的表构成新的循环链表。函数操作如图所示：

另外，__list_splice()函数的功能是将两个表整合到一起，成为一个链表。

关于链表的遍历，内核提供了list_for_each_entry()来遍历链表中的元素。

#define list_for_each_entry(pos, head, member)				\	for (pos = list_first_entry(head, typeof(*pos), member);	\	     &pos->member != (head);					\	     pos = list_next_entry(pos, member))#define list_first_entry(ptr, type, member) \	list_entry((ptr)->next, type, member)#define list_next_entry(pos, member) \	list_entry((pos)->member.next, typeof(*(pos)), member)#define list_entry(ptr, type, member) \	container_of(ptr, type, member)#define container_of(ptr, type, member) ({				\	void *__mptr = (void *)(ptr);					\	BUILD_BUG_ON_MSG(!__same_type(*(ptr), ((type *)0)->member) &&	\			 !__same_type(*(ptr), void),			\			 "pointer type mismatch in container_of()");	\	((type *)(__mptr - offsetof(type, member))); })#define offsetof(TYPE, MEMBER)	((size_t)&((TYPE *)0)->MEMBER)

来看一下container_of函数，container_of函数返回了一个地址，这里忽略BUILD_BUG_ON_MSG函数，通过offsetof函数的定义，可以知道该函数主要返回了结构体中成员变量的相对偏移量。随后，利用成员当前实际的地址减去偏移量，便可以获得当前结构体的地址。整个计算如下图所示：

|--------struct AAA--------|--- ptr - offsetof(TYPE, MEMBER)|                          | |  offsetof(TYPE, MEMBER)|              			   | ||--struct list_head *head--|--- ptr|                          ||--------------------------|

按照上述的计算过程，便可以对链表进行遍历了。

转载地址：http://opxii.baihongyu.com/