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。
