Linux内核链表实现过程(linux内核结构详解)

编辑：rootadmin

关于双链表实现，一般教科书上定义一个双向链表节点的方法如下：即一个链表节点包含：一个指向前向节点的指针、一个指向后续节点的指针，以及数据域共三部分。但查看linux内核代码中的list实现时，会发现其与教科书上的方法有很大的差别。来看看linux是如何实现双链表。双链表节点定义发现链表节点中根本就没有数据域，这样的链表有什么用？linux内核中定义这样的链表原因何在？这是因为linux中是通过独立定义一个链表结构，并在结构体中内嵌一个链表节点来实现链表结构的。这样有一个好处就是能达到链表与结构体分离的目的。如此一来，我们构建好一个链表后，其结构示意图如下：链表的定义及初始化宏定义：LIST_HEAD(name)宏用来定义一个链表头，并使他的两个指针都指向自己。我们可以在程序的变量声明处，直接调用LIST_HEAD(name)宏，来定义并初始化一个名为name的链表。也可以先声明一个链表，然后再使用INIT_LIST_HEAD来初始化这个链表。也即：是等价的。

插入操作删除操作删除链表节点的操作很简单，是通过将要删除的节点的前一个节点与后一个节点链接到一起。链表节点替换操作链表遍历操作（重点在这里）首先来看一个如何根据链表节点地址得到其所在结构体的地址。是一个带3个参数的宏，该宏的作用是获取链表节点(ptr)所在结构体的起始地址。有了这个宏，我们只要知道某一个链表节点指针，就可以通过该链表节点得到其所在结构体的指针，从而，我们遍历链表，也便可以达到遍历我们自己定义的结构体。第一个参数为一个地址，他是结构体链表节点元素的地址，第二个参数是结构体类型，第三个参数是链表节点元素在结构体中的名字。来仔细分析一下这个宏：最外面的一层括号可以去掉，这是为了防止宏扩展的，去掉如下：(type *) ((char *)(ptr)-(size_t)(&((type *)0)->member))现在就比较清楚了，首先(type *)是C强制转换操作，就是将后面的的数据转化成type结构的指针。而后面的操作可以再分解(char *)(ptr) - (size_t)(&((type *)0)->member) 这样就是一个减法的操作，前面是一个指针，我们传过去的结构体链表节点元素的指针，这里被转化成指向字符的。而后面是一个整形，可以再分解(size_t) (&((type *)0)->member)显然这个整形是一个指针转化的，而这个指针又可以再分解，&((type *)0)->member 可以看出这个指针是一个变量取地址得到的，这个变量又是什么呢((type *)0)->member 看起来有点奇怪，不过这个操作是整个宏中最精妙的，他将地址0转化成type类型，接下来又取得这个结构的member元素，member就是我们传进来的参数：元素在结构体中的命名。其实((type *)0)->member取的变量是内容是什么一点都不重要，重要的我们要取这个变量的地址。取完这个地址将它转换成size_t类型，这样这个数据就是((type *)0)->member相对与地址0的偏移。回到上面的那个减法，将结构体中链表节点元素的地址与他与结构体首地址的偏移相减，不就得到了结构体的地址了吗。)(&((type *)0)->member))) 最外面的一层括号可以去掉，这是为了防止宏扩展的，去掉如下：(type *) ((char *)(ptr)-(size_t)(&((type *)0)->member)) 现在就比较清楚了，首先(type *)是C强制转换操作，就是将后面的数据转化成type结构的指针。而后面的操作可以再分解(char *)(ptr) - (size_t)(&((type *)0)->member) 这样就是一个减法的操作，前面是一个指针，我们传过去的结构体元素的指针，这里被转化成指向字符的。而后面是一个长整形，可以再分解(size_t) (&((type *)0)->member) 显然这个长整形是一个指针转化的，而这个指针又可以再分解，&((type *)0)->member 可以看出这个指针是一个变量取地址得到的，这个变量又是什么呢?((type *)0)->member 起来有点奇怪，不过这个操作是整个宏中最精妙的，他将地址0转化成type类型，接下来又取得这个结构的member元素，member就是我们传进来的参数：元素在结构体中的命名。其实((type *)0)->member取的变量是内容是什么一点都不重要，重要的我们要取这个变量的地址。取完这个地址将它转换成size_t类型，这样这个数据就是((type *)0)->member相对与地址0的偏移。回到上面的那个减法，将结构体中元素的地址与他与结构体首地址的偏移相减，便得到了结构体的地址了。链表的遍历操作时通过一个宏来实现的：其中prefetch是用于性能优化，暂时不用去管它。从上述链表遍历宏可以看出，其只是一次获得了链表节点指针，在实际应用中，我们都需要获取链表节点所在结构体的数据项，因此，通常将list_for_each和list_entry一起使用。为此，linux的list实现提供了另外一个接口如下：有了这个接口，我们就可以通过链表结构来遍历我们实际的结构体数据域了。例如，我们定义了一个结构体如下：那么我们遍历链表的代码如下：此外Linux链表还提供了两个对应于基本遍历操作的"_safe"接口：list_for_each_safe(pos, n, head)、list_for_each_entry_safe(pos, n, head, member)，它们要求调用者另外提供一个与pos同类型的指针n，在for循环中暂存pos下一个节点的地址，避免因pos节点被释放而造成的断链。当然，linux链表不止提供上述接口，还有

推荐整理分享Linux内核链表实现过程(linux内核结构详解)，希望有所帮助，仅作参考，欢迎阅读内容。

文章相关热门搜索词:链表实现lru,linux内核实现,链表实现lru,链表实现lru,linux内核链表实现好处,linux内核数据结构,linux 链表,linux 链表,内容如对您有帮助，希望把文章链接给更多的朋友！

linux网络编程用到的网络函数详解用和使用示例一.概念介绍网络程序分为服务端程序和客户端程序。服务端即提供服务的一方，客户端为请求服务的一方。但实际情况是有些程序的客户端、服务器端

给定链表中间节点指针，删除中间节点的方法问题如下输入：链表a-b-c-d-e中指向节点c的指针输出：无返回值，但新链表变为a-b-d-e解答：想了好久没想出来，看了提示才知道解法的。这里用到了一

linux使用select实现精确定时器详解在编写程序时，我们经常会用到定时器。首先看看select函数原型如下：intselect(intnfds,fd_set*readfds,fd_set*writefds,fd_set*exceptfds,structtimeval*timeout);参数说明：sle