Linux内核之常用数据结构分析

要深入学习Linux内核相关知识，还需要了解一些内核中常用的数据结构和算法。其中最常用的两个就是链表和红黑树。

1、链表：

在Linux内核中，大量使用了链表这一数据结构。链表结构可以解决数据不能动态扩展的缺陷。链表由于每个元素都是离散存放的，所以不需要占用连续的内存，因而可以动态创建并插入和删除。链表通常由两部分构成，一部分是指针区域，另一部分是有效数据区域，其中，有效数据区域用来存放有效的数据信息，链表区域则用来存放指向链表的前继节点或者后继节点的指针。链表是使用指针将各节点串联起来的一种存储结构。常见的链表可以分为单向链表和双向链表：

a、单向链表：

单链表的指针域只包含一个指向下一个节点的指针，因此形成的是一个单一方向的链表，其代码如下：

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

由于单链表只包含一个指针域，因此具有单向移动性，只能访问当前节点的后继节点，而无法访问当前节点的前继节点，因此在实际项目中应用较少。

b、双向链表：

与单向链表不同的是，双向链表的指针域包含了两个指针，一个指向前继节点，另一个指向后继节点，其代码如下：

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

双向链表可以进行双向移动，既可以访问当前节点的前继节点，也可以访问当前节点的后继节点。

2、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>

void list_add(struct list_head *new, struct list_head *head)
list_add_tail(struct list_head *new, struct list_head *head)

3、红黑树：

红黑树（Red Black Tree）被广泛应用在内核的内存管理和进程调度中，用于将排序的元素组织到树中。
红黑树是具有以下特征的二叉树（每个节点或红或黑）：

• 每个叶节点是黑色的。
• 如果结点都是红色，那么两个子结点都是黑色。
• 从一个内部结点到叶结点的简单路径上，对所有叶节点来说，黑色结点的数目都是相同的。

红黑树的一个优点是，所有重要的操作（例如插入、删除、搜索）都可以在O(log n)时间内完成，n为树中元素的数目。