主要内容
- 链表
- 队列
- 映射
- 二叉树
1. 链表
- 单向链表、双向链表
- 环形链表
linux内核中的链表使用方法和一般数据结构中定义的链表是有所不同的。
传统链表：
传统双向链表.png
传统的链表有个最大的缺点就是不好共通化，因为每个node中的data1，data2等等都是不确定的(无论是个数还是类型)。
linux中的链表巧妙的解决了这个问题，linux的链表不是将用户数据保存在链表节点中，而是将链表节点保存在用户数据中。
linux的链表节点只有2个指针(pre和next)，这样的话，链表的节点将独立于用户数据之外，便于实现链表的共同操作。
Linux内核链表：
linux内核双向链表.png
最大的问题在于，怎样通过链表的节点来取得用户数据？
答案是通过container_of()宏
#define container_of(ptr, type, member) ({ \
const typeof(((type *)0)->member)*__mptr = (ptr); \
(type *)((char *)__mptr - offsetof(type, member)); })
- type一般是个结构体，也就是包含用户数据和链表节点的结构体。
- ptr是指向type中链表节点的指针
- member则是type中定义链表节点是用的名字
比如：
struct student
{
int id;
char* name;
struct list_head list;
};
- type是struct student
- ptr是指向stuct list的指针，也就是指向member类型的指针
- member就是 list
下面分析一下container_of宏:
// 步骤1：将数字0强制转型为type*，然后取得其中的member元素
((type *)0)->member // 相当于((struct student *)0)->list
// 步骤2：定义一个临时变量__mptr，并将其也指向ptr所指向的链表节点
const typeof(((type *)0)->member)*__mptr = (ptr);
// 步骤3：计算member字段距离type中第一个字段的距离，也就是type地址和member地址之间的差
// offset(type, member)也是一个宏，定义如下：
#define offsetof(TYPE, MEMBER) ((size_t) &((TYPE *)0)->MEMBER)
// 步骤4：将__mptr的地址 - type地址和member地址之间的差
// 其实也就是获取type的地址
步骤1，2，4比较容易理解，下面的图以sturct student为例进行说明步骤3：
- 首先需要知道 ((TYPE *)0) 表示将地址0转换为 TYPE 类型的地址
-
由于TYPE的地址是0，所以((TYPE *)0)->MEMBER 也就是 MEMBER的地址和TYPE地址的差，如下图所示：
理解步骤3.png
2. 队列
FIFO，没啥好说的
- 队列的size在初始化时，始终设定为2的n次方
- 使用队列之前将队列结构体中的锁(spinlock)释放
3. 映射
类似于python里的字典
散列表是一种映射，但自平衡二叉树搜索树也能实现存储数据，比如C++中map就是红黑树嘛，在最坏情况下能有更好的表现
Linux内核中的映射叫idr，目标时映射一个位于id标识数UID到一个指针
具体可见https://blog.csdn.net/orz415678659/article/details/8539794
4. 红黑树
5. 算法复杂度
大o符号代表上限（更差情况）
大θ符号代表最小上限
