Linux内核中常用的数据结构和算法
Linux内核代码中广泛使用了数据结构和算法，其中最常用的两个是链表和红黑树。 链表 Linux内核代码大量使用了链表这种数据结构。链表是在解决数组不能动态扩展这个缺陷而产生的一种数据结构。链表所包含的元素可以动态创建并插入和删除。链表的每个元素都是离散存放的，因此不需要占用连续的内存。链表通常由若干节点组成，每个节点的结构都是一样的，由有效数据区和指针区两部分组成。有效数据区用来存储有效数据信息，而指针区用来指向链表的前继节点或者后继节点。因此，链表就是利用指针将各个节点串联起来的一种存储结构。 （1）单向链表 单向链表的指针区只包含一个指向下一个节点的指针，因此会形成一个单一方向的链表，如下代码所示。 struct list { int data; /*有效数据*/ struct list *next; /*指向下一个元素的指针*/ }; 登录后复制 如图所示，单向链表具有单向移动性，也就是只能访问当前的节点的后继节点，而无法访问当前节点的前继节点，因此在实际项目中运用得比较少。 单向链表示意图 （2）双向链表 如图所示，双向链表和单向链表的区别是指针区包含了两个指针，一个指向前继节点，另一个指向后继节点，如下代码所示。 struct list { int data; /*有效数据*/ struct list *next; /*指向下一个元素的指针*/ struct list *prev; /*指向上一个元素的指针*/ }; 登录后复制 双向链表示意图 （3）Linux内核链表实现 单向链表和双向链表在实际使用中有一些局限性，如数据区必须是固定数据，而实际需求是多种多样的。这种方法无法构建一套通用的链表，因为每个不同的数据区需要一套链表。为此，Linux内核把所有链表操作方法的共同部分提取出来，把不同的部分留给代码编程者自己去处理。Linux内核实现了一套纯链表的封装，链表节点数据结构只有指针区而没有数据区，另外还封装了各种操作函数，如创建节点函数、插入节点函数、删除节点函数、遍历节点函数等。 Linux内核链表使用struct list_head数据结构来描述。 <include> struct list_head { struct list_head *next, *prev;…