第6章 内核数据结构

Linux内核实现了常用的通用数据结构：

• 链表
• 队列
• 映射
• 二叉树
  内核开发者应尽可能使用这些数据结构，不要造轮子重复开发。

一、链表

链表数据结构：

//<linux/list.h>
struct list_head {
    struct list_head *next;
    struct list_head *prev;
};

因为C语言中，一个给定结构的变量偏移在编译时地址就被ABI固定下来了，所有使用宏container_of()可以从链表指针找到父结构中包含的任何变量：

#define container_of(ptr, type, member) ({\
    const typeof( ( (type *)0)->member ) *__mptr = (ptr); \
    (type *)( (char *)__mptr - offsetof(type,member) ); })

返回包含list_head的父类型结构体：

#define list_entry(ptr, type, member) container_of(ptr, type, member)

---

初始化链表：

INIT_LIST_HEAD(struct list_head*);

---

链表头：

static LIST_HEAD(struct list_head*)

---

增加链表节点：

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

---

删除链表节点：

list_del(struct list_head *entry)
list_del_init(struct list_head *entry)

---

遍历链表：

list_for_each(struct list_head *p, struct list_head *head) //p依次指向head为头节点的链表中的节点

list_for_each_entry(typeof(member) *f, struct list_head *head, member) //f依次指向head为头节点的链表中的节点的父结构中member成员

二、队列

Linux内核通用队列实现称为kfifo。

初始化队列：

int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask);
int kfifo_init(struct kfifo *fifo, void *bufffer, unsigned int size);

// size必须是2的幂

---

推入队列数据：

unsigned int kfifo_in(struct kfifo *fifo, const void *from, unsigned int len);

---

摘取队列数据：

unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len);
unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len, unsigned offset);  //只读取不从队列中删除数据

---

获取队列长度：

static inline unsigned int kfifo_size(struct kfifo *fifo); //队列空间总体大小
static inline unsigned int kfifo_len(struct kfifo *fifo); //已推入数据大小
static inline unsigned int kfifo_avail(struct kfifo *fifo); //队列中还有多少可用空间
static inline int kfifo_is_empty(struct kfifo *fifo); //队列是否空
static inline int kfifo_is_full(struct kfifo *fifo); //队列是否满

---

重置队列：

static inline void kfifo_reset(struct kfifo *fifo);

---

撤销队列：

void kfifo_free(struct kfifo *fifo);

三、映射

Linux内核提供了简单、有效的映射数据结构，目标是：映射一个唯一的标识数（UID）到一个指针。idr数据结构用于映射用户空间的UID。

初始化idr：

void  idr_init(struct idr *idp);

---

分配新的UID，分为两步：

• 1、告诉idr需要分配新的UID，允许其在必要时调整后备树的大小

int idr_pre_get(struct idr *idp, gfp_t gfp_mask);

• 2、获取新的UID，并且将其加到idr:

int idr_get_new(struct idr *idp, void *ptr, int *id);
int idr_get_new_above(struct idr *idp, void *ptr, int startint_id, int *id); //分配的UID必须大于或等于startint_id

---

查找UID:

void *idr_find(strcut idr *idp, int, id);

---

删除UID：

void idr_remove(struct idr *idp, int id);

---

撤销idr：

void idr_destroy(struct idr *idp); //只释放idr中未使用的内存，不释放当前分配给UID使用的任何内存
void idr_remove_all(struct idr *idp); //删除所有UID

四、二叉树

Linux实现的红黑树称为rbtree。