链表

链表是linux内核中最简单，同时也是应用最广泛的数据结构。

内核中定义的是环形双向链表。

1.1 头文件简介

内核中关于链表定义的代码位于： include/linux/types.h

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

include/linux/list.h文件中对每个函数都有注释，我们将在1.3节中介绍常用的链表操作（增加，删除，遍历）的使用方法。

  • list_empty(head) - tests whether a list is empty
  • list_add(new_entry, head) - adds a new entry. Insert a new entry after the specified head.
  • list_del(entry) - deletes entry from list.
  • list_for_each(pos, head) - iterate over a list

1.2 链表结构的特点

在阅读list.h文件之前，有一点必须注意：linux内核中的链表使用方法和一般数据结构中定义的链表是有所不同的。

一般的双向链表一般是如下的结构，

  • 有个单独的头结点(head)
  • 每个节点(node)除了包含必要的数据之外，还有2个指针(pre,next)
  • pre指针指向前一个节点(node)，next指针指向后一个节点(node)
  • 头结点(head)的pre指针指向链表的最后一个节点
  • 最后一个节点的next指针指向头结点(head)

具体见下图：

传统的链表有个最大的缺点就是不好共通化，因为每个node中的data1，data2等等都是不确定的(无论是个数还是类型)。

linux中的链表巧妙的解决了这个问题，linux的链表不是将用户数据保存在链表节点中，而是将链表节点保存在用户数据中。

linux的链表节点只有2个指针(pre和next)，这样的话，链表的节点将独立于用户数据之外，便于实现链表的共同操作。

具体见下图：

linux链表中的最大问题是怎样通过链表的节点来取得用户数据？

和传统的链表不同，linux的链表节点(node)中没有包含用户的用户data1，data2等。

整个list.h文件中，我觉得最复杂的代码就是获取用户数据的宏定义

1
2
#define list_entry(ptr, type, member) \
    container_of(ptr, type, member)

1.3 使用接口

  • 向链表中增加结点

给链表增加一个结点：

1
list_add(struct list_head *new, struct list_head *head)

该函数向指定链表的head结点后插入new结点。

  • 从链表中删除一个结点

从链表中删除一个结点，调用list_del():

1
list_del(struct list_head *entry)

该函数从链表中删除entry元素。

  • 遍历链表

遍历链表最简单的方法就是使用list_for_each()宏，该宏使用两个list_head类型参数，第一个参数用来指向当前项，这是一个你必须要提供的临时变量，第二个参数是需要遍历的链表的以头结点形式存在的list_head。每次遍历中，第一个参数在链表中不断移动指向下一个元素，直到链表中的所有元素都被访问为止。用法如下：

1
2
3
4
struct list_head *p;
    list_for_each(p, fox_list) {
    /* p 指向链表中的元素 */
}

1.4 使用示例

构造了一个内核模块来实际使用一下内核中的链表。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#include <linux/kernel.h>
#include <linux/module.h>
#include <linux/slab.h>
#include <linux/list.h>

MODULE_LICENSE("GPL");
MODULE_AUTHOR("XIYOU");

#define N 10   //链表节点
struct numlist {
  int num;//数据
  struct list_head list;//指向双联表前后节点的指针
};

struct list_head listhead;//头节点

static int __init doublelist_init(void)
{
    struct numlist *listnode;//每次申请链表节点时所用的指针
    struct list_head *pos;
    struct numlist *p;
    int i;

    printk("doublelist is starting...\n");
    //初始化头节点
    INIT_LIST_HEAD(&listhead);

    //建立N个节点，依次加入到链表当中
    for (i = 0; i < N; i++) {
        listnode = (struct numlist *)kmalloc(sizeof(struct numlist), GFP_KERNEL); // kmalloc（）在内核空间申请内存，类似于malloc
        listnode->num = i+1;
        list_add_tail(&listnode->list, &listhead);
        printk("Node %d has added to the doublelist...\n", i+1);
    }

    //遍历链表
    i = 1;
    list_for_each(pos, &listhead) {
        p = list_entry(pos, struct numlist, list);
        printk("Node %d's data:%d\n", i, p->num);
        i++;
    }

    return 0;
}

static void __exit doublelist_exit(void)
{
    struct list_head *pos, *n;
    struct numlist *p;
    int i;

    //依次删除N个节点
    i = 1;
    list_for_each_safe(pos, n, &listhead) {  //为了安全删除节点而进行的遍历
        list_del(pos);//从双链表中删除当前节点
        p = list_entry(pos, struct numlist, list);//得到当前数据节点的首地址，即指针
        kfree(p);//释放该数据节点所占空间
        printk("Node %d has removed from the doublelist...\n", i++);
    }
    printk("doublelist is exiting..\n");
}

module_init(doublelist_init);
module_exit(doublelist_exit);

具体运行可参见linux kernel 模块化编程入门。

参考资料：

  1. cnblogs wang_yb
  2. republick.gitbooks.io
  3. List, HList, and Hash Table
  4. 《Linux内核设计与实现》第六章