链表
1、链表数据结构
#include <linux/list.h>
strcut list_head{struct list_head *next;struct list_head *prev;
}
从结构体成员指针找到结构体地址
#include <linux/stddef.h>
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE*)0)->MEMBER)
#define container_of(ptr, type, member) ({ \const typeof(((type *)0)->member) *__mptr = (ptr); \(type *) ((char *) __mptr -offsetof(type,member));})
使用container_of()宏，定义一个简单的函数返回包含list_head的父类结构体
#define list_entry(ptr, type, member) container_of(ptr, type, member)
2、链表初始化
INIT_LIST_HEAD(list_head)
3、链表操作
//向链表添加节点，从head节点后面添加
list_add(struct list_head *new, struct list_head *head)
//把节点添加到链表尾，在head节点前插入new节点
list_add_tail(struct list *new, struct list_head *head)//从链表删除节点，并不会释放entry或释放包含entry的数据结构体所占用的内存，仅将entry元素从链表移除
list_del(struct list_head *entry)
//从链表中删除节点并对其重新初始化
list_del_init(struct list_head *entry)//把节点从一个链表移到另一个链表，把list项从链表移除，然后加入另一个链表的head节点后面
list_move(struct list_head *list, struct list_head *head)
//把节点从一个链表移到另一个链表的末尾
list_move_tail(struct list_head *list, struct list_head *head)//检查链表是否为空
list_empty(struct list_head *head)//把两个未连接的链表合并在一起，将list指向的链表插入到指定链表的head元素后面
list_splice(struct list_head *list, struct list_head *head)
//把两个未连接的链表合并一起，并重新初始化原来的链表
list_splice_int(struct list_head *list, struct list_head *head)
4、遍历链表
//基本方法
struct list_head *p;
list_for_each(p, list) {command; //*p指向链表中的元素...
}//多数内核使用list_for_each_entry宏遍历链表，该宏也使用list_entry宏
list_for_each_entry(pos, head, member) //pos指向包含链表的结构体的指针
/*
struct sample {...struct list_head list;...
};
struct sample *p;
struct sample ins;//链表实例
list_for_each_entry(p, &ins, list) {//p指向包含链表的下一个结构体command;...
}
*///方向遍历链表
list_for_each_entry_reverse(pos, head, member)
//遍历的同时删除，在删除操作之前把删除现存储到next指针临时变量上
list_for_each_entry_safe(pos, next, head, member)
list_for_each_entry_safe_reverse(pos, next, head, member)
队列
#include <linux/kfifo.h>//创建队列
/*动态方法，两个函数*/
struct kfifo fifo;
/*成功返回0，失败返回负数错误码，size必须是2的幂*/
int kfifo_alloc(struct kfifo *fifo, unsigned int size, gfp_t gfp_mask);
/*该函数创建并初始化一个kfifo对象，使用buffer指向的size字节大小的内存,size必须是2的幂*/
void kfifo_init(struct kfifo *fifo, void *buffer, unsigned int size);
/*静态方法，该方法创建一个名称为name，大小为size的kfifo对象，size必须是2的幂*/
DECLARE_KFIFO(name, size);
INIT_KFIFO(name);//推入队列数据
/*该函数把from指针指向的len字节数据拷贝到fifo所指的队列中，成功返回推入数据的字节大小，否则返回负数错误码*/
unsigned int kfifo_in(struct kfifo *fifo, const void *from, unsigned int len);//摘取队列数据
/*该函数从fifo指向的队列中拷贝长度为len字节的数据到to所指的缓冲中，成功返回拷贝的数据长度，失败返回负数错误码，当数据被读取后，数据就不存在在队列之中*/
unsigned int kfifo_out(struct kfifo *fifo, void *to, unsigned int len);
/*该函数和kfifo_out类似，但是出口偏移量不增加，而且数据读取之后，数据仍存在队列之中，offset指向队列中的索引位置，如果为0，则读取队列头*/
unsigned int kfifo_out_peek(struct kfifo *fifo, void *to, unsigned int len，unsigned int offset);//获取队列长度
/*获取用于存储kfifo队列的空间总体大小*/
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);
/*判断队列是否未满或空，若为空或满，返回非0值，否则返回0*/
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);
/*撤销kfifo_alloc分配的队列，如果使用kfifo_init方法创建队列，则需要释放相关缓冲*/
void kfifo_free(struct kfifo *fifo);
映射
Linux内核提供简单、有效的映射数据结构，但是是一个非通用的映射，在内核中目的是：映射一个唯一的标识数（UID）到一个指针。
idr数据结构用于映射用户空间的UID，比如将inodify watch的描述符或者POSIX的定时器ID映射到内核相关联的数据结构上，如inodify_watch或者k_itimer结构体。
//初始化一个idr
/*建立一个idr，可以静态或动态分配一个idr数据结构，然后调用idr_init()*/
struct idr id_hub;
void idr_init(struct idr *idp);//分配一个新的UID
/*建立idr，就可以分配新的UID，第一步，分配新的UID，允许在必要时调整后备树的大小，第二步，真正请求新的UID*/
/*调整后备树大小，成功返回1，失败返回0*/
int idr_pre_get(struct idr *idp, gfp_t gfp_mask);
/*执行获取新的UID，并将其加到idr的方法是idr_get_new()，该方法使用idp所指向的idr分配一个新的UID，并且将其关联到指针ptr上，将新的UID存于id中，成功返回0，失败返回非零错误码，错误码-EAGAIN，需要再次调用idr_pre_get，如果idr已满，返回-ENOSPC*/
int idr_get_new(struct idr *idp, void *ptr, int *id);
/*
int id
do {if (!idr_pre_get(&idr_hub, GFP_KERNEL);return -ENOSPC;ret = idr_get_new(&idr_hub, ptr, &id);
} while(ret == -EAGAIN);
*//*是调用者可指定一个最小的UID返回值，保证新的UID在系统运行期间唯一*/
int idr_get_new_above(struct idr *idp, void *ptr, int starting_id, int *id);//查找UID
/*根据调用者寄语的UID，idr将返回对应的指针，失败返回空指针（如果调用idr_get_new或者idr_get_new_above将空指针映射给UID，那么idr_find成功时也返回NULL）*/
void *idr_find(struct idr *idp, int id);//删除UID
/*从idr中删除UID，成功则将id关联的指针一起从映射中删除*/
void idr_remove(struct idr *idp, int id);//撤销idr
/*该方法值释放idr中未使用的内存，并不释放当前分配给UID使用的任何内存*/
void idr_destroy(struct idr *idp);
/*内核代码不会撤销idr，除非关闭或者卸载，而且只有在没有其他用户（也就是没有更多的UID）时才能删除，可以调用idr_remove_all强制删除所有的UID*/
void idr_remove_all(struct idr *idp);