第6章 内核数据结构

介绍几种Linux内核常用的内建数据结构，Linux内核实现了这些数据结构，提倡大家开发时重用，其中包括：

• 链表
• 队列
• 映射
• 二叉树

之后有介绍算法复杂度。

6.1 链表

       链表是Linux内核中
最简单、最普通的数据结构。存放可变数量元素（节点）的数据结构。

特点：

• 元素动态创建并插入列表，编译时无需知道元素个数。
• 不占用连续的内存空间

6.1.1 单向链表和双向链表

（1）单向链表：

1
2
3
4
5
6
1/* 链表中的一个元素 */

2struct list_element{

3   void *data;

4   struct list_element *next;

5}

6

（2）双向链表

1
2
3
4
5
6
7
1/* 链表中的一个元素 */

2struct list_element{

3   void *data;                  /* 有效数据 */

4   struct list_element *next;   /* 指向下一个元素的指针 */

5   struct list_element *prev;   /* 指向上一个元素的指针 */

6}

7

6.1.2 环形链表

末位元素又指向了链表的首元素，首尾相连，称为环形链表。
环形双向链表提供了最大的灵活性，Linux内核的标准链表就是采用环形双向链表形式实现的。

6.1.3 沿链表移动

        沿链表移动只能是线性的，先访问一个元素，沿该元素向后指针访问下一个元素，不断重复。

        如果需要随机访问数据，一般不使用链表。使用链表的理想情况是：需要遍历所有数据元素或需要动态加入或删除数据时。

        遍历一个链表，需要线性的从第一个元素访问到最后一个元素。

6.1.4 Linux内核中的实现

传统的链表，对于一个struct，在内部添加一个指向数据的next节点指针，才能串联在链表中。

Linux与众不同，不是将数据结构塞入链表，而是将链表节点塞入数据结构。

（1）链表数据结构

头文件<linux/list.h>

1
2
3
4
5
1struct list_head{

2   struct list_head *next;   /* 指向下一个元素的指针 */

3   struct list_head *prev;   /* 指向上一个元素的指针 */

4}

5

1
2
3
4
5
6
7
1struct fox{

2   unsigned long tail_length；

3   unsigned long weigth；

4   bool is_fantastic；

5   struct list_head list；

6}

7

（2）定义一个链表

（3）链表头

6.5.1 操作链表

内核提供了一组函数来操作链表，这些函数都要使用一个或多个list_head结构体指针做参数。函数是C语言以内联函数提供的，原型在文件<linux/linst.h>中。这些函数复杂度都是O(1)。

（1）向链表中加入一个节点

（2）从链表中删除一个节点

（3）移动和合并链表节点