linux内核设计与实现pdf百度⽹盘_linux学习17，链表数据类型
介绍，内核是怎样设。。。
上⼀节较为详细的讨论了 linux 中的系统调⽤，接下来⼏节将学习 linux 内核中的基本数据结构的设计和实现。本节先来看看 linux 内核中的链表。linux教程第五版pdf下载
链表和数组有些相似
链表是基于 C语⾔指针的，看了我《C语⾔⼊门》系列⽂章的朋友应该记得这张图:
指针 p2 指向⼀块内存，可以通过 p2 修改该内存⾥保存的数值。链表其实也是类似的，只不过链表是⼀个挨⼀个“串起来”的：
这种形式的数据结构和静态数组有些相似，不过链表包含的元素都是动态创建插⼊的，编译的时候并不需要知道要创建多少元素，⽽且链表的每个元素创建时间可能差异⽐较⼤，所以各个链表元素在内存中往往也不是连续的。
也正是因为链表的各个元素在内存中不像数组元素那样连续，所以链表才需要额外的“连接⽅式”将这些元素连接起来，指针正是⼀种⾮常合适的“连接⽅式”。
使⽤C语⾔定义链表
如果使⽤基本数据类型定义链表，例如：
int* a;int* b;int* c;a = b;b = c;
这样的确定义了⼀个链表，但是却没有任何意义，因为它真的只是⼀个链表，⽆法存储任何额外的信息。所以，链表⼀般都是⽤复合数据类型定义，常⽤的是结构体数据类型，这样⼀来，⼀个基本的链表可以如下定义：
struct node{ void* data; struct node* next;};
这样就很好⽤了，next 成员负责连接下⼀个(数据结构⼀模⼀样的)节点，data 成员则负责存储数据，如果 data 成员不⽅便存储所有数据，还可以随时增加数据成员。这样的数据结构简图如下：
在某些链表中，每个节点还可以指向前⼀个节点：
struct node{ void* data; struct node* prev; struct node* next;};
它的数据结构简图如下：
因为这种链表可以同时向前和向后连接，所有常被称作“双向链表”。
上⾯介绍的两种链表，两端的节点常常是指向 NULL 的，表⽰链表的起点和终点。但是有的链表两端节点并不指向 NULL，⽽是分别指向⾸尾，这样就形成了“环形链表”，请看下图：
linux 内核常使⽤的标准链表就是环形双向链表，这主要是因为环形双向链表有最⼤的灵活性。
访问链表元素
访问数组元素时既可以线性访问，也可以随机访问。这是因为数组的各个元素在内存中是紧密排列的，只需知道其中⼀个元素的地址，其他元素的地址都可以简单的推算出来。
⽽链表的各个元素在内存中并不连续，所以只能通过 next 或者 prev 指针线性访问。例如先访问节点 1，然后利⽤节点 1 的next 指针访问节点 2，再利⽤节点 2 的next 指针访问节点 3。
当然了，访问链表也可以从任意指定的节点开始。如果链表是环形链表，则从任意⼀个节点都能够遍历所有链表元素。如果是双向链表，则从某个节点出发，既可以向前访问，也可以向后访问。
这是⼀种最简单的沿着链表访问元素的⽅法，也是最适合访问链表的⽅法。如果需要随机访问数据，则就不应该使⽤链表的数据类型了。链表最适合使⽤在需要遍历所有元素，以及需要动态插⼊删除数据的场景。
linux 内核中的链表的设计和实现
⼀般情况下，定义链表时都是通过在数据内部添加 prev 和 next 指针实现的，请看：
struct fox{ int tail_len; int weight; struct fox* prev; struct fox* next;};
上⾯的 C语⾔代码使⽤ prev 和 next 指针定义了⼀个双向链表，然后⼜插⼊了尾巴长度和体重两个成员，⽤于描述 fox(狐狸) ，这就相当于“把数据结构”塞⼊链表。
linux 内核使⽤链表的⽅式与众不同，它不是将数据结构塞⼊链表，⽽是把链表塞⼊数据结构。linux 内核的链表相关C语⾔代码在 中声明：
struct list_head { struct list_head *next, *prev;};
可以看出，这是相当简单的双向链表，next 指针指向下⼀个节点，prev 指向前⼀个。list_head 并没有存储其他数据的地⽅，那怎样使⽤呢？按照上⾯的说法，linux 内核“将链表塞⼊数据结构”，请看C语⾔代码：
struct fox{ int tail_len; int weight; struct list_head list;};
这样链表就能存储其他数据了，访问下⼀个节点可以使⽤ fox 中的 ，访问前⼀个节点可以使⽤ list.prev。为了操作更⽅便，linux 内核还定义了⼀些链表操作函数，例如 list_add() 可以⽅便的将新节点加⼊链表，INIT_LIST_HEAD() 初始化链表等待：
不过 linux 内核提供的这些⽅法接收的参数都是 struct list_head 型的，⽽链表中的 next、prev 只是我
们想使⽤的结构体中的成员⽽已，要是只知道 next、prev 的地址，怎样访问结构体的其他成员呢？这就要借助于 container_of() 宏了，它的 C 语⾔代码如下，请看：
#define container_of(ptr, type, member) ({  const typeof( ((type *)0)->member ) *__mptr = (ptr);  (type *)( (char *)__mptr - offsetof(type,member) );})
通过 container_of 宏，linux 内核可以很⽅便的访问结构体的其他成员。这是因为在 C语⾔中，给定结构体中的变量偏移在编译时地址就被 ABI 固定下来了。
下⾯分析⼀下 container_of 宏，以 struct fox 为例：
struct fox{ int tail_len; int weight; struct list_head list;};struct fox f;
已知 list 的地址，如何求 f 的地址呢？其实很简单，将 list 的地址减去 list 在 struct fox 中的偏移就可以了。
container_of 宏就是这样的思路：
const typeof( ((type *)0)->member ) *__mptr = (ptr);
这⼀句定义了⼀个和 member 同类型的指针 __mptr，并将 ptr 的地址传递给它。
(type *)( (char *)__mptr - offsetof(type,member) );})
这⼀句的⽬的就是将 __mptr 减去 member 在 type 中的偏移，执⾏完毕之后就得到了 f 的地址，这时再访问其他成员就不难了。
offsetof 的宏定义如下，也是⾮常简单的：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
到这⾥，我们就清楚了linux 内核常⽤的标准链表的定义和基本使⽤⽅法。事实上，linux 内核还定义了⼀些其他⽐较⽅便操作链表的宏和⽅法，限于篇幅，下⼀节再说了。
欢迎在评论区⼀起讨论，质疑。⽂章都是⼿打原创(本⽂部分参考linux内核原理和设计)，每天最浅显
的介绍C语⾔、linux等嵌⼊式开发，喜欢我的⽂章就关注⼀波吧，可以看到最新更新和之前的⽂章哦。

版权声明：本站内容均来自互联网，仅供演示用，请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系QQ:729038198，我们将在24小时内删除。