嵌入式C语言（十三）

Linux内核中常用的数据结构和算法

Linux内核代码中广泛使用了数据结构和算法，其中最常用的两个是链表和红黑树。

1 链表

Linux内核代码大量使用了链表这种数据结构。

链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。

链表所包含的元素可以动态创建并插入和删除。

链表的每个元素都是离散存放的，因此不需要占用连续的内存。

链表通常由若干节点组成，每个节点的结构都是一样的，由有效数据区和指针区两部分组成。

有效数据区用来存储有效数据信息，而指针区用来指向链表的前继节点或者后继节点。因此，链表就是利用指针将各个节点串联起来的一种存储结构。

（1）单向链表

单向链表的指针区只包含一个指向下一个节点的指针，因此会形成一个单一方向的链表，如下代码所示。

struct list {
int data;　 /*有效数据*/
struct list *next; /*指向下一个元素的指针*/
};

如图2.2所示，单向链表具有单向移动性，也就是只能访问当前的节点的后继节点，而无法访问当前节点的前继节点，因此在实际项目中运用得比较少。

（2）双向链表

如图2.3所示，双向链表和单向链表的区别是指针区包含了两个指针，一个指向前继节点，另一个指向后继节点，如下代码所示。

struct list {
int data;　 /*有效数据*/
struct list *next; /*指向下一个元素的指针*/
struct list *prev; /*指向上一个元素的指针*/
};

（3）Linux内核链表实现

单向链表和双向链表在实际使用中有一些局限性，如数据区必须是固定数据，而实际需求是多种多样的。

这种方法无法构建一套通用的链表，因为每个不同的数据区需要一套链表。

为此，Linux内核把所有链表操作方法的共同部分提取出来，把不同的部分留给代码编程者自己去处理。

Linux内核实现了一套纯链表的封装，链表节点数据结构只有指针区而没有数据区，另外还封装了各种操作函数，如创建节点函数、插入节点函数、删除节点函数、遍历节点函数等。

Linux内核链表使用struct list_head数据结构来描述。

<include/linux/types.h>
struct list_head {
struct list_head *next, *prev;
};

struct list_head数据结构不包含链表节点的数据区，通常是嵌入其他数据结构，如struct page数据结构中嵌入了一个lru链表节点，通常是把page数据结构挂入LRU链表。

<include/linux/mm_types.h>
struct page {
struct list_head lru;
...
}

链表头的初始化有两种方法，一种是静态初始化，另一种动态初始化。

把 next 和 prev指针都初始化并指向自己，这样便初始化了一个带头节点的空链表。

<include/linux/list.h>
/*静态初始化*/
#define LIST_HEAD_INIT(name) { &(name), &(name) }
#define LIST_HEAD(name) \
struct list_head name = LIST_HEAD_INIT(name)
/*动态初始化*/
static inline void INIT_LIST_HEAD(struct list_head *list)
{
list->next = list;
list->prev = list;
}

添加节点到一个链表中，内核提供了几个接口函数，如list_add()是把一个节点添加到表头，list_add_tail()是插入表尾。

<include/linux/list.h>