怎么运用linux内核函数提供的双向循环链表

在linux内核中，有大量的数据结构需要用到双循环链表，例如进程、文件、模块、页面等。若采用双循环链表的传统实现方式，需要为这些数据结构维护各自的链表，并且为每个链表都要设计插入、删除等 *** 作函数。因为用来维持链表的next和prev指针指向对应类型的对象，因此一种数据结构的链表 *** 作函数不能用于 *** 作其它数据结构的链表。

我来回答吧 不过有点复杂 我尽量解释清楚 一个问题一个问题来吧！1，ptr指针是链表的头指针，2，INIT_LIST_HEAD(ptr) 是一个宏，具体的实现参见list.h 是将ptr里的 prev和next两个指针指向自己，这样就完成了初始化。3，list_for_each(*p1，*p2) 从名字上来看就知道是遍历一个链表，p1是循环遍历过程中使用的循环变量而p2是遍历链表使用的开始点和结束点。4，第四个问题是最关键也是最难以理解的问题了。首先，我们要明白在内核中为了最大可能的通用性，内核中设计的链表和我们平常使用的链表的最大区别是内核中的链表除了prev和next之外不包含任何数据，所以在使用链表的时候，我们将struct list_head 嵌入到具体使用的带链表的数据结构中，像进程表等，内核中很多结构体都使用这种方式。例如，struct temp { int a,struct list_head list} tmp这个时候通过链表头ptr，我们可以遍历到一个链表的任何一个位置，但是，我们只知道结构体tmp中list的位置，那么如何 *** 作这个链表中的数据呢，这个时候就要通过list_for_entry来获得包含list对应的tmp结构的地址。在这个例子中将list的地址减掉int a所占的空间，就能得到tmp的地址。为此专门设计了一个宏，list_entry（p，exp，list）来进行这个计算。其实list_entry等价于container_of(ptr,type, member)这个宏，宏的实现是const typeof( ((type *)0)->member ) *__mptr = (ptr)\(type *)( (char *)__mptr-offsetof(type,member) )})，下面解释一下这个实现，首先解释一下 offsetof这个宏，它的实现是#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)，意思是TYPE是个struct类型，而MEMBER是这个struct中的一个成员. 因为这个struct的基地址为0, 所以MEMBER的地址就是这个成员相对于struct头地址的偏移量。回到container_of的实现上来，首先声明一个和member是相同类型的指针常量*__mptr,并初始化为ptr，再将这个值强转成char*类型再减去ptr这个指针所指向的成员在整个struct的偏移量，这样就得到了这个struct的入口地址。所以list_entry这个宏返回的是p这个链表指针对应的链表节点的结构体的入口地址。至于为什么不能用&exp，你的问题里没有上下文无法判断。比较复杂，希望你能看懂

int main()

{

Link head//链表(不带头节点)

int n

printf("输入链表的长度n: ")

scanf("%d",&n)

printf("连续输入%d个数据(以空格隔开): ",n)

head=CreateLink(n)

printf("\n原本链表的节点是: ")

DispLink(head)

LinkSort(head)

printf("\n从大到小排序之后: ")

DispLink(head)

printf("\n")

return 0

}

链表的具体存储表示为：

① 用一组任意的存储单元来存放线性表的结点（这组存储单元既可以是连续的，也可以是不连续的）

② 链表中结点的逻辑次序和物理次序不一定相同。为了能正确表示结点间的逻辑关系，在存储每个结点值的同时，还必须存储指示其后继结点的地址（或位置）信息（称为指针（pointer）或链(link)）

链式存储是最常用的存储方式之一，它不仅可用来表示线性表，而且可用来表示各种非线性的数据结构。

以上内容参考：百度百科-单链表

---