Linux内核核心数据结构：链表、红黑树与KFIFO实现

Linux内核中的核心数据结构实现与应用1. 链表数据结构实现1.1 基础链表类型链表是Linux内核中最基础的数据结构之一主要用于解决数组不能动态扩展的问题。链表元素可以动态创建、插入和删除且不需要占用连续内存空间。典型的链表节点包含两部分有效数据区存储实际数据信息指针区连接前后节点的指针1.1.1 单向链表实现单向链表是最简单的链表形式每个节点只包含指向下一个节点的指针struct list { int data; /* 有效数据 */ struct list *next; /* 指向下一个元素的指针 */ };单向链表的局限性在于只能单向遍历无法访问前驱节点因此在内核中使用较少。1.1.2 双向链表实现双向链表通过增加前驱指针解决了单向链表的限制struct list { int data; /* 有效数据 */ struct list *next; /* 指向下一个元素的指针 */ struct list *prev; /* 指向上一个元素的指针 */ };1.2 Linux内核链表实现传统链表实现存在数据区固定、无法通用的问题。Linux内核采用创新的设计思路struct list_head { struct list_head *next, *prev; };这个设计特点包括纯指针结构不包含数据区通过嵌入到其他数据结构中实现通用性提供完整的操作函数集1.2.1 链表初始化内核提供两种初始化方式静态初始化#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; }1.2.2 链表操作API内核提供丰富的链表操作接口节点插入void list_add(struct list_head *new, struct list_head *head); // 头插法 void list_add_tail(struct list_head *new, struct list_head *head); // 尾插法链表遍历#define list_for_each(pos, head) \ for (pos (head)-next; pos ! (head); pos pos-next)获取宿主结构#define list_entry(ptr, type, member) \ container_of(ptr, type, member)container_of宏的实现原理#define container_of(ptr, type, member) ({ \ const typeof( ((type *)0)-member ) *__mptr (ptr); \ (type *)( (char *)__mptr - offsetof(type,member) );})2. 红黑树实现与应用2.1 红黑树特性红黑树是Linux内核中用于高效搜索的重要数据结构具有以下特性每个节点为红色或黑色叶节点都是黑色红色节点的子节点必须为黑色从任一节点到其叶节点的路径包含相同数量的黑色节点这些特性保证了红黑树的最坏情况操作时间复杂度为O(log n)。2.2 内核中的红黑树实现内核中的红黑树节点定义struct rb_node { unsigned long __rb_parent_color; struct rb_node *rb_right; struct rb_node *rb_left; } __attribute__((aligned(sizeof(long))));2.2.1 红黑树操作示例查找节点实现struct mytype *my_search(struct rb_root *root, int new) { struct rb_node *node root-rb_node; while (node) { struct mytype *data container_of(node, struct mytype, node); if (data-key new) node node-rb_left; else if (data-key new) node node-rb_right; else return data; } return NULL; }插入节点实现int my_insert(struct rb_root *root, struct mytype *data) { struct rb_node **new (root-rb_node), *parent NULL; while (*new) { struct mytype *this container_of(*new, struct mytype, node); parent *new; if (this-key >int kfifo_alloc(fifo, size, gfp_mask);静态分配#define DEFINE_KFIFO(fifo, type, size) #define INIT_KFIFO(fifo)3.2.2 数据操作数据写入int kfifo_in(fifo, buf, n);数据读取#define kfifo_out(fifo, buf, n)3.2.3 状态查询#define kfifo_size(fifo) /* 缓冲区总大小 */ #define kfifo_len(fifo) /* 已用大小 */ #define kfifo_is_empty(fifo) #define kfifo_is_full(fifo)3.2.4 用户空间交互#define kfifo_from_user(fifo, from, len, copied) #define kfifo_to_user(fifo, to, len, copied)这些接口结合了copy_to_user/copy_from_user和KFIFO机制为驱动开发提供了便利。