深入浅出Linux之内核数据结构
1. container
container是linux很重要的一个概念。有了container方法，才能实现对对象的封装。
分析一下container方法。
======================================================================
#define container_of(ptr, type, member) ({ \
const typeof( ((type *)0)->member ) *__mptr = (ptr); \
(type *)( (char *)__mptr - offsetof(type,member) );})
这个方法巧妙的实现了通过结构的一个成员找到整个结构的地址。有了container方法，list才
成为了一个通用的数据结构，通过container方法，还可以实现内核的封装，程序之间不暴露
内部的数据。
2. 双向链表list
List定义在/include/linux目录下。首先看看list的结构定义：
struct list_head {
struct list_head *next, *prev;
};
List是双向链表的一个抽象，list库提供了list_entry，使用了container方法，通过container 可以从list找到整个数据对象，这样list就成为了一种通用的数据结构。
======================================================================
#define list_entry(ptr, type, member) \
container_of(ptr, type, member)
内核定义了很多对list结构操作的内联函数和宏，计有：
- LIST_HEAD：定义并初始化一个list链表
- list_add_tail：加一个成员到链表尾
list_del：删除一个list成员
- list_empty：检查链表是否为空
- list_for_each：遍历链表。得到链表指针。
- list_for_each_safe：遍历链表。和list_for_each区别是可以删除遍历的成员
- list_for_each_entry：遍历链表，通过container方法返回结构指针。
3. hash list
Hash list和双向链表list很相似，它适用于hash表。看一下hash list的head定义：
struct hlist_head {
struct hlist_node *first;
};
和通常的list比较，hlist头只有一个指针，这样就节省了一个指针的内存。如果hash表非常
庞大，那么每个hash 表头节省一个指针，整个hash表节省的内存就很可观了。这就是内核
中专门定义hash list的原因。
Hash list库提供的函数和list很相似，计有：
l HLIST_HEAD：定义并初始化一个hash list链表头
l hlist_add_head：加一个成员到hash链表头
l hlist_del：删除一个hash list成员
l hlist_empty：检查hash 链表是否为空
l hlist_for_each：遍历hash 链表。
l hlist_for_each_safe：遍历链表。和hlist_for_each区别是可以删除遍历的成员
l hlist_for_each_entry：遍历hash 链表，通过container方法返回结构指针
4. 单向链表
内核中，没有提供单向链表的定义。但实际上，有多处使用了单向链表的概念。
======================================================================
for (i = 0, p -= n; i < n; i++, p++, index++) {
struct probe **s = &domain->probes[index % 255];
while (*s && (*s)->range < range)
s = &(*s)->next;
p->next = *s;
*s = p;
}
上面的例子是加入一个新的字符设备到系统的表里面。在系统的字符设备表里，
probe结构其实就是单向链表。这种结构在内核中应用很广泛。
5. red-black tree
红黑树位于/lib/rbtree.c文件。红黑树是一种自平衡的二叉树。实际上，红黑树可以看做是折半查找。我们知道，排序的快速做法是取队列的中间值比较，然后在剩下的队列中再次取中间值比较，迭代进行直到找到最合适的位置。红黑树实际就是实现了这种算法。
那么红黑树里面的“红黑”代表什么意思？红黑的颜色处理是避免树的不平衡。举个例子，如果1，2，3，4，5五个数字依次插入一颗红黑树，那么五个值都落在了树的右侧，如果6再插入这颗红黑树，那么需要比较五次。“红黑规则”就要将树旋转，树的根部要落在3这个节点，只需要比较两次，这样就避免了树的不平衡导致的问题。
内核中的io调度算法和内存管理中都使用了红黑树。红黑树有很多介绍的文章，读者可以结合代码分析一下。
6. radix tree
内核提供了一个基树库，代码在/lib/radix-tree.c文件。基树是一种空间换时间的数据结构，
通过空间的冗余减少了时间上的消耗。用一张图来分析：
图中显示，元素空间总共为256，但元素个数不固定。那么如果用数组存储，好处是插入查找只用一次操作，但是存储空间需要256，这是不可思议的。如果用链表存储，存储空间节省了，但是极限情况下查找操作次数等于元素的个数。而采用一颗高度为2的基树，第一级最多16个冗余结构，代表元素前四位的索引。第二级代表元素后四位的索引。那么只要两级查找就可以找到特定的元素，而且只有少量的冗余数据。图中假设只有一个元素10001000，那么只有树的第一级有元素，而且树的第二级只有1000这个节点有子节点，其它节点都不必分配空间。这样既可以快速定位查找，也减少了冗余数据。
基树很适合存储稀疏的数据，内核中文件的页cache就采用了基树。关于基树的文章很多，读者可以结合代码分析一下。