Linux内核链表

最近在看Linux内核的代码，第一个想了解的是Linux内部所使用的数据结构：链表。

事实上Linux 内核使用的链表是双向循环链表.跟普通的链表一样，它的每个节点包含两个域：数据域和指针域，其中数据域很明确，就是用户自己的数据，没啥好说的，具体得看用户想通过链表组织什么数据。指针域是一个结构体如下：

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

View Code

从上面可以看出，这个链表是一个双向的链表，因为它的指针域包含了两个指针，一个指向前一个节点的指针域，另一个指向后一个节点的指针域。这就跟普通的链表有了很大的区别了，一般普通的链表的指针域是直接指向了另一个节点的数据域，当我们通过指针域得到到节点的地址后就可以直接获得数据。但是问题就是一旦一个链表的节点被创建以后，它的数据域就固定了，这样当下一个用户也想使用这个链表的时候就必须重新定义节点数据域，这样就使得链表的通用性下降了。Linux内核的链表为了让链表更加通用，就采用了如下的方式定义链表：让节点的指针域指向另一个节点的指针域，数据域可以让用户自行定义。如下面的定义：

struct student
{
    char name[10];
    int english;
    int math;
    int chinese;
    struct list_head list;
};

View Code

在上面的定义中，数据域是学生的数据，指针域是一个结构体，它们分别指向下一个和上一个节点的指针域。在这里，数据域可以由用户自行定义，只需要将指针域加入即可。
但是这样一来如果用户要使用链表来获得节点的数据就没有普通用户那么方便了。因为指针域指向的并非是另一个节点的数据域。不过不用担心，内核提供了函数让我们能通过指针域获得数据。下面介绍内核提供的常用的操作链表的函数：

　　INIT_LIST_HEAD():创建链表；

　　void list_add();在链表头插入一个节点

　　list_add_tail()；在链表尾插入一个节点

　　list_add_tail()；删除节点

　　list_entry()；取出节点

　　list_for_each();遍历链表

上面只是给出了操作函数的名称，并不是具体的函数头。可以在内核代码中查找到具体的函数定义和实现。这些函数都定义在include/linux/list.h 中

Linux 内核链表