Linux内核【链表】整理笔记

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

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

    在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)这样的函数供我们使用：

#define LIST_HEAD(name) \
    struct list_head name = LIST_HEAD_INIT(name)

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

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

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

struct list_head student_list；
INIT_LIST_HEAD (&student_list);

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

#define NAME_MAX_SIZE 32

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

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

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

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

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

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

   还有关于链表的分割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{}的指针类型，这一点需要时刻牢记在心。

    

关于链表我们更多时候是对其进行遍历的需求，上一篇博文里我们主要认识了一下和链表操作比较常用的几个内核API接口，其入参全都是清一色的struct list_head{}类型。至于链表的遍历，内核也有一组基本的接口(其实都是宏定义的)供开发者调用。

 
   首先是list_for_each(pos, head)，参数pos是需要开发者在外部提供的一个临时struct list_head{}类型的指针对象，类似于for循环的i、j、k之类的游标，head是我们要遍历的链表头。常见用法：

LIST_HEAD(student_list);
struct list_head *stu;
list_for_each(stu, &student_list){
    //在这个作用域里，指针stu依次指向student_list里的每一个struct list_head{}成员节点
}

   当然stu指向的是struct list_head{}类型的对象，我们一般是需要指向struct student{}的才对，此时list_entry(ptr, type, member)就出场了，它完全是container_of(ptr, type, member)的一个别名而已。container_of()就是根据type类型结构体中的member成员的指针ptr，反身找到该member所在结构体对象的type首地址。废话不多说，上图：

   此时的用法就变成下面这样子：

   注意结合上图，领会一下list_entry(ptr,type,member)三个参数之间的关系。这样如果每次要遍历链表时既要定义临时的struct list_head{}指针变量，又要定义目标结构体对象指针变量，总感觉些许不爽。好在Linux感知到了你的J点，于是乎：

list_for_each_entry(pos, head, member)

    横空出世。参数pos和member意义没有变，而head则指向我们要遍历的链表首地址，这样一来开发者不用再自己定义struct list_head{}类型临时指针变量，只要需要自己定义一个的目标数据结构的临时指针变量就可以了：

LIST_HEAD(student_list);
struct student *st;
list_for_each_entry(st, &student_list, stu_list){
    //Todo here … …
}

   此时指针变量st，就相当于for循环的游标变量i了。
   当然，内核能感知的远不止于此，还有一个名为list_for_each_entry_reverse(pos, head, member)的宏，用于对双向链表的逆向遍历，参数的意义和list_for_each_entry()完全一样，区别在它是对链表从尾部到首部进行依次遍历。该接口主要是为了提高链表的访问速度，考虑两种情况：

第一，如果你明确知道你要访问的节点会出现在链表靠后的位置；

第二，如果你需要用双向链表实现一个类似于“栈”的数据结构；

针对以上两种需求，相比于list_for_each_entry()，list_for_each_entry_reverse()的速度和效率明显优于前者。为了追求极致，内核开发者们就是这么任性，没办法。

上述两个接口在遍历链表时已经完全可以胜任，但还无法满足删除的需求，原因是…算了，都懒的说了，把那两个宏展开，在纸上画一下，如果要删除节点，会发生什么“神奇”的事情就一目了然了。那如果遍历链表过程中要删除节点，该怎么办？咱接着唠：

list_for_each_entry_safe(pos, n, head, member)

   如果你还没看过list.h文件，那么单从list_for_each_entry_safe(pos,n,head,member)的四个入参命名上，应该可以读懂它们的意思和用法了吧！如果你已经在纸上画过了，那么新增的n很明显应该是pos指针所指元素的下一个节点的地址，注意，pos和n都是目标结构体的类型，而非struct list_head{}类型，本例中它们都是struct student{}类型的指针，童鞋们可不要犯迷糊了。现在用法就更简单了：

LIST_HEAD(student_list);
struct student *st,*next;
list_for_each_entry_safe (st, next,&student_list, stu_list){
    //在这里可以对st所指向的节点做包括删除在内的任意操作
    //但千万别操作next，它是由list_for_each_entry_safe()进行维护的
}

   不用多想，肯定也存在一个名为list_for_each_entry_safe_reverse(pos, n, head, member)的宏。简单小节一下：
   1)、list_for_each_entry()和list_for_each_entry_reverse()，如果只需要对链表进行遍历，这两个接口效率要高一些；
   2)、list_for_each_entry_safe()和list_for_each_entry_safe_reverse()，如果遍历过程中有可能要对链表进行删除操作，用这两个；
   实际项目中，大家可以根据具体场景而考虑使用哪种方式。另外，关于链表遍历，内核还有其他一些列list_for_*相关的宏可供调用，这里就不一一阐述了，list.h源码里面无论是注释还是实现都相当明确。

   
   说了老半天，还是操练几把感受感受，模拟训练之“内核级精简版学生管理系统”：
   头文件student.h长相如下：

/*student.h*/
#ifndef __STUDENT_H_
#define __STUDENT_H_

#include <linux/list.h>
#define MAX_STRING_LEN 32
typedef struct student
{
        char m_name[MAX_STRING_LEN];
        char m_sex;
        int m_age;
        struct list_head m_list;  /*把我们的学生对象组织成双向链表，就靠该节点了*/
}Student;
#endif

 
   源文件student.c长相也不丑陋：

#include <linux/module.h>
#include <linux/kernel.h>
#include <linux/init.h>

#include "student.h"

MODULE_LICENSE("Dual BSD/GPL");
MODULE_AUTHOR("Koorey Wung");

static int dbg_flg = 0;

LIST_HEAD(g_student_list);

static int add_stu(char* name,char sex,int age)
{
        Student *stu,*cur_stu;

        list_for_each_entry(cur_stu,&g_student_list,m_list){ //仅遍历是否有同名学生，所以用该接口
                if(0 == strcmp(cur_stu->m_name,name))
                {
                        printk("Error:the name confict!\n");
                        return -1;
                }
        }

        stu = kmalloc(sizeof(Student), GFP_KERNEL);
        if(!stu)
        {
                printk("kmalloc mem error!\n");
                return -1;
        }

        memset(stu,0,sizeof(Student));
        strncpy(stu->m_name,name,strlen(name));
        stu->m_sex = sex;
        stu->m_age = age;
        INIT_LIST_HEAD(&stu->m_list);

        if(dbg_flg)
                printk("(Add)name:[%s],\tsex:[%c],\tage:[%d]\n",stu->m_name,stu->m_sex,stu->m_age);

     &nbs