六、内核数据结构

6.1 链表

链表和静态数组的不同之处在于，他所包含的元素都是动态创建并插入链表的，在编译时不必知道具体需要创建多少个元素。链表中每个元素的创建时间各不相同，所以他们在内存中无须占用连续内存区。因为元素不连续存放，所以各个元素需要通过某种方式被连接在一起。

6.1.1 单向链表和双向链表

6.1.2 环形链表

6.1.3 沿链表移动

沿链表移动只能是线性移动。如果需要随机访问数据，一般不使用链表。使用链表存放数据的理想情况是：需要遍历所有数据或需要动态添加或删除数据。

6.1.4 链表在linux中的实现

linux内核中的链表不是将数据结构塞入链表，而是将链表节点塞入数据结构。

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

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

const typeof((type *)0)->member)* __mptr = （ptr); \

(type*)((char *)__mptr - offsetof(type,member));})

6.1.5 操作链表

1、增加一个节点

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

2.删除一个节点

list_del(struct list_head *entry);

3、移动合并链表节点

list_move（struct list_head *list，struct list_head *head)

6.6.1 遍历链表

list_for_each()宏

用法：list_for_each(p,list){
/*p指向链表中的元素*/

}

指向包含list_head结构体的指针

list_for_each(p,&fox_list){

f=list_entry(p,struct fox,list);/*f指向具体的entrity*/

}

list_for_each_entry(pos,head,member)

list_for_each_entry_reverse();

list_for_each_entry_safe(pos,next,head,member) 遍历的同时可以删除

6.2 队列

6.2.1 kfifo

linux的kfifo提供了两个主要操作：enqueue（入队列）和dequeue（出队列）。kfifo对象维护了两个偏移量：入口偏移和出口偏移。入口偏移是指下一次入队列时的位置，出口偏移是指下一次出队列时的位置。出口偏移总是小于入口偏移。当出口偏移等于入口偏移时，说明队列空了。当入口偏移等于队列长度时，说明队列重置前，不可再有新数据入队列。

6.2.2 创建队列

动态：int kfifo_alloc(struct kfifo *fifo,unsigned int size,gfp_t gfp_mask);创建并初始化一个大小为size的kfifo

静态：DECLARE_KFIFO(name,size)；INIT_KFIFO(name)；

6.2.3 推入队列数据

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

把from指针所指的len字节数据拷贝到fifo所指的队列中，如果成功，返回推入数据的字节大小。如果队列中的空闲字节小于len，则该函数最多可拷贝=剩余空间的长度，返回值可能小于len

6.2.4 摘取队列数据

unsigned int kfifo_out(struct kfifo *fifo，void *to,unsigned int len);

从fifo所指向的队列中拷贝出长度为len字节的数据，队列中数据如果总长度小于len，则拷贝小于len，返回小于len。数据被摘取后就不存在于队列中

只是看数据不删除数据：kfifo_out_peek()；

6.2.5 获取队列长度

kfifo_size()空间总体大小字节

kfifo_len()队列中已经推入的总数据长度

kfifo_avail()队列中还有多少可用空间

kfifo_is_empty()/kfifo_is_full()

6.2.6 重置和撤销队列

kfifo_reset（）；重置

kfifo_free()，撤销

6.2.7 队列使用举例

unsigned int i;

/* 将[0,32]压入到名为‘fifo’的kfifo中*/

for(i=0;i<32;i++)

　　kfifo_in(fifo,&i,sizeof(i));

while(kfifo_avail(fifo)){

　　unsigned int val;

　　int ret;

　　ret = kfifo_out(fifo,&val,sizeof(val));

　　if(ret!=sizeof(val))

　　　　return -EINVAL;

　　printk(KERN_INFO　＂%u\n",val);

}

6.3 映射

　　一个映射，也常称为关联数组，其实是一个由唯一键组成的集合，而每个键必然关联一个特定的值.映射至少支持3个操作：add(key,value),remove(key),value = lookup(key);

除了使用散列表外，映射也可以通过自平衡二叉搜索树存储数据。二叉树对比散列表的优势：1、二叉搜索树在最坏的情况下能有更好的表现（对数复杂性相比线性复杂性）；2、二叉搜索树同时满足顺须保证，较容易遍历；不需要散列函数，需要的键类型只要可以定义<=操作算子即可。

c++的STL容器std::map便是采用自平衡二叉搜索树实现的，它能提供按序遍历的能力。

linux提供了一个非通用的映射：映射一个唯一的标识数（UID）到一个指针。idr数据结构用于映射用户空间的UID。

6.3.1 初始化一个idr

struct idr id_huh;/*静态定义idr结构*/

idr_init(&id_huh);/*初始化idr结构*/

6.3.2 分配一个新的UID

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

int idr_get_new(struct idr *idp,void *ptr,int *id);

int idr_get_new_above(struct idr *idp,void *ptr,int starting_id,int *id);

6.3.3 查找UID

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

6.3.4 删除UID

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

6.3.5 撤销idr

void idr_destory(struct idr *idp);如果该方法成功，则只是释放idr中未使用的内存。它并不释放当前分配给UID使用的内存。可以调用idr_remove_all(struct idr *idp)方法删除所有UID，然后调用idr_destory()来使得idr占用的内存全部释放。

6.4 二叉树

6.4.1 二叉搜索树

1、根的左分支小于根节点值

2、右分支大于根节点值

3、所有的子树也都是二叉搜索树

在树种搜索一个给定值：算法对数的；遍历：线性的。

6.4.2 自平衡二叉搜索树

一个平衡二叉搜索树是一个所有叶子节点深度差不超过1的二叉搜索树。一个自平衡二叉搜索树是指其操作都试图维持平衡的二叉搜索树。

1、红黑树

2、rbtree

linux实现的红黑树成为rbtree

6.5 数据结构以及选择

1、如果对数据集合的主要操作是遍历，就使用链表

2、如果你的代码符合生产者/消费者模式，则使用队列

3、如果需要一个UID映射到一个对象，就使用映射

4、如果需要存储大量数据，并且检索迅速，使用红黑树

6.6 算法复杂度

6.6.1 算法 算法就是一系列的指令，它可能有一个或多个输入，最后产生一个结果或输出。

6.6.2 大O符号

6.6.3 大θ符号

6.6.4 时间复杂度