Linux内核【链表】整理笔记(1)

转自：http://blog.chinaunix.net/uid-23069658-id-4576255.html

我们都知道Linux内核里的双向链表和学校里教给我们的那种数据结构还是些不一样。Linux采用了一种更通用的设计，将链表以及其相关操作函数从数据本身进行剥离，这样我们在使用链表的时候就不用自己去实现诸如节点的插入、删除、遍历等操作了。当然，Linux也是从2.1.x内核开始才对链表进行了这样的统一，和我们目前看到的样子几乎差不多：

点击(此处)折叠或打开

1. struct list_head {
2.     struct list_head *next, *prev;
3. };

    在2.6.21里这个数据结构定义在include/liinux/list.h头文件里，但是在3.4.1内核里，以及后面要介绍的哈希链表的定义都放在include/linux/types.h头文件里。而本文将以3.4.1内核为例进行介绍，其实对链表来说内核的版本号几乎没什么影响，只要掌握了Linux设计链表的精髓，万变不离其宗。

   今天我们首先来聊聊链表。从上述定义代码我们可以看出，Linux内核的链表是双向链表，如果我们要将自己的数据结构以链表的形式进行组织，那么只要在我们自己的数据结构里，增加一个struct list_head{}类型的结构体成员对象就可以了，这样，我们就可以很方便地使用内核提供给我们的一组标准接口来对链表进行各种操作。
   如果我们需要定义一个链表，内核有LIST_HEAD(name)这样的函数供我们使用：

点击(此处)折叠或打开

1. #define LIST_HEAD(name) \
2.     struct list_head name = LIST_HEAD_INIT(name)

    
   其中#define LIST_HEAD_INIT(name) { &(name), &(name) }，其实这样的代码已经太简单不过了。如果我们要定义一个名为student_list的链表，直接LIST_HEAD(student_list)就可以了，展开后等价于下面的代码：

点击(此处)折叠或打开

1. struct list_head student_list= { &(student_list), &(student_list) };

    
   跟内核通知链类似，如果我们已经有了一个链表对象student_list，INIT_LIST_HEAD()接口可以对它初始化。所以，LIST_HEAD(student_list)代码和下面的代码是等价的：

点击(此处)折叠或打开

1. struct list_head student_list；
2. INIT_LIST_HEAD (&student_list);

    
   假如，我们现在要定义一个学生的结构体，并让其组织成链表的形式，可以这样做：

点击(此处)折叠或打开

1. #define NAME_MAX_SIZE 32
2. typedef struct student{
3.     char name[NAME_MAX_SIZE];    /*姓名*/
4.     unsigned char sex;              /*性别：m-男生；f-女生*/
5.     unsigned char age;              /*年龄*/
6.     struct list_head stu_list;  /*所有的学生最终通过这个结构串成链表*/
7. }Student;

   那么在写代码时，如果是通过kmalloc之类的函数动态创建节点，我们就可以用下面代码对链表节点进行初始化：

点击(此处)折叠或打开

1. Student *stu1;
2. stu1 = kmalloc(sizeof(*stu1), GFP_KERNEL);
3. strcpy(stu1->name,”xiaoming”);
4. stu1->sex = ‘m’;
5. stu1->age = 18;
6. INIT_LIST_HEAD(&stu1-> stu_list); /*和下面的用法注意区别*/

    如果是静态定义结构体变量的话就更简单了：

点击(此处)折叠或打开

1. Student stu2={
2.     .name={“xiaohong”},
3.     .sex=’f’,
4.     .age=18,
5.     .stu_list = LIST_HEAD_INIT(stu2.stu_list); /*和上面的用法注意区别*/
6. };

   有了数据节点，接下来就要对其进行操作了，内核提供了一组常用接口用于对双向链表操作，如下。

   还有关于链表的分割list_cut_position(*list,*head,*entry)以及合并list_splice(*list,*head)、list_splice_init (*list,*head)、list_splice_tail (*list,*head)、list_splice_tail_init (*list,*head)这几个API用法也都非常简单，对照内核源码的注释很轻松就可以上手了。

    通过上面的图我们可以看出来，在内核中当我们提及链表头的时候其实并没有牵扯到我们自己的结构体数据本身，链表头的next所指向的节点才是真正意义上的“链表头节点”，prev所指向的节点叫做“链表尾节点”。注意，不要把链表头和链表的头节点混为一谈。有了这个认识之后，我们就知道如果链表头的next和prev都指向链表头本身的话，那么这个链表其实就是空的，例如list_empty()或者list_empty_careful()所做的事情就是给定一个链表头，判断其是否为空，即是否包含任何有效的数据节点。同样地，如何判断链表是否只有一个节点呢？看看list_is_singular()的实现就豁然开朗了，真的是so easy。

   最后，将前面提及的API总结到下表2.1中，方便大家查阅。

    需要注意的是，上述所有链表操作函数的入参都是struct list_head{}的指针类型，这一点需要时刻牢记在心。

    未完，待续…