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>