三、映射
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
四、hlist
hlist_head 和 hlist_node 是位于linux内核中的数据结构，其设计初衷主要是为了减少Hash表的内存消耗。
struct hlist_head { struct hlist_node *first; }; struct hlist_node { struct hlist_node *next, **pprev; };
其内存结构如下：
hlist_head 结构体仅仅有一个first指针，hlist_node 结构体有两个指针，next 和 ppre。其中next指针指向下一个hlist_node,如果该节点为最后一个一个节点，那么next指向NULL。
这样设计的原因在于：通常我们在使用Hash表是为实现快速查找，那么Hash表通常会维护一张相对较大的数组，否则的会带来较大的冲突，而一张较大的数组必然会带来较大的内存消耗。我们知道通常一个Hash表中每一个dentry(每一个具体数元素)会使用两个指针，有其中一个指向尾节点，而我们知道在Hash表中的list通常是非常短（如果过长，说明冲突过多），那么显然这个指向尾节点的指向我们就不那么的必要，Hash表中的每一个denry只用保存一个指针。这样的设计显然会造成链表中节点数据结构不一致，如果hlist_node采用的next和pre指针，那么对于第一个节点和其他节点操作必然会使不一致。hlist_node巧妙地将pprev指向上一个节点的next指针的地址，由于hlist_head和hlist_node指向的下一个节点的指针类型相同，这样就解决了通用性。
常用接口
（1）hlist_head 和 hlist_node初始化
#define HLIST_HEAD_INIT { .first = NULL } #define HLIST_HEAD(name) struct hlist_head name = { .first = NULL } #define INIT_HLIST_HEAD(ptr) ((ptr)->first = NULL) static inline void INIT_HLIST_NODE(struct hlist_node *h) { h->next = NULL; h->pprev = NULL; }
（2）添加节点
static inline void hlist_add_head(struct hlist_node *n, struct hlist_head *h) { struct hlist_node *first = h->first; n->next = first; if (first) first->pprev = &n->next; h->first = n; n->pprev = &h->first; }
（3）删除节点
static inline void __hlist_del(struct hlist_node *n) { struct hlist_node *next = n->next; struct hlist_node **pprev = n->pprev; *pprev = next; if (next) next->pprev = pprev; } static inline void hlist_del(struct hlist_node *n) { __hlist_del(n); n->next = LIST_POISON1; n->pprev = LIST_POISON2; }
（4）遍历节点
#define hlist_for_each_entry(pos, head, member) \ for (pos = hlist_entry_safe((head)->first, typeof(*(pos)), member);\ pos; \ pos = hlist_entry_safe((pos)->member.next, typeof(*(pos)), member))
五、二叉树
叉树是一种重要的数据结构，与数组、向量、链表都是一种顺序容器，它们提供了按位置访问数据的手段。但是有一个缺点，它们都是按照位置来确定数据，想要通过值来获取数据，只能通过遍历的方式。而二叉树在很大程度上解决了这个缺点，二叉树是按值来保存元素，也按值来访问元素。
二叉树由一个个节点组成，一个节点最多只能有两个子节点，从根节点开始左右扩散，分左子节点和右子节点，向下一直分支。
许多实际问题抽象出来的数据结构往往是二叉树的形式，即使是一般的树也能简单地转换为二叉树，而且二叉树的存储结构及其算法都较为简单，因此二叉树显得特别重要。二叉树是递归定义的。
(1)完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子节点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
(2)满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
(3)平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
5.1二叉树的遍历
对于二叉树来讲最主要、最基本的运算是遍历。
从二叉树的递归定义可知，一棵非空的二叉树由根结点及左、右子树这三个基本部分组成。因此，在任一给定结点上，可以按某种次序执行三个操作：
- 访问结点本身(N)，
- 遍历该结点的左子树(L)，
- 遍历该结点的右子树(R)。
遍历方法普遍有以下几种：
先序遍历（NLR）、中序遍历（LNR），后序遍历（LRN）和层次遍历。
遍历节点顺序：
- 先序遍历（NLR）：根、左子树、右子树
- 中序遍历（LNR）：左子树、根、右子树
- 后序遍历（LRN）：左子树、右子树、根
- 层次遍历：按照从上到下、从左到右的次序进行遍历
5.2二叉树的代码的实现
<?php class Node{ public $value; public $left; public $right; } //先序遍历 根节点 ---> 左子树 ---> 右子树 function preorder($root){ $stack=array(); array_push($stack,$root); while(!empty($stack)){ $center_node=array_pop($stack); echo $center_node->value.' ';//先输出根节点 if($center_node->right!=null){ array_push($stack,$center_node->right);//压入左子树 } if($center_node->left!=null){ array_push($stack,$center_node->left); } } } //中序遍历，左子树---> 根节点 ---> 右子树 function inorder($root){ $stack = array(); $center_node = $root; while (!empty($stack) || $center_node != null) { while ($center_node != null) { array_push($stack, $center_node); $center_node = $center_node->left; } $center_node = array_pop($stack); echo $center_node->value . " "; $center_node = $center_node->right; } } //后序遍历，左子树 ---> 右子树 ---> 根节点 function tailorder($root){ $stack=array(); $outstack=array(); array_push($stack,$root); while(!empty($stack)){ $center_node=array_pop($stack); array_push($outstack,$center_node);//最先压入根节点，最后输出 if($center_node->left!=null){ array_push($stack,$center_node->left); } if($center_node->right!=null){ array_push($stack,$center_node->right); } } while(!empty($outstack)){ $center_node=array_pop($outstack); echo $center_node->value.' '; } } $a=new Node(); $b=new Node(); $c=new Node(); $d=new Node(); $e=new Node(); $f=new Node(); $a->value='A'; $b->value='B'; $c->value='C'; $d->value='D'; $e->value='E'; $f->value='F'; $a->left=$b; $a->right=$c; $b->left=$d; $c->left=$e; $c->right=$f; preorder($a);//A B D C E F echo '<hr/>'; inorder($a);//D B A E C F echo '<hr/>'; tailorder($a);//D B E F C A
5.3二叉树的作用
二叉树常被用于实现二叉查找树和二叉堆。在计算机科学中，二叉树是每个结点最多有两个子树的树结构。通常子树被称作“左子树”和“右子树”。
根据不同的用途可分为：
1、完全二叉树——若设二叉树的高度为h，除第 h 层外，其它各层 (1～h-1) 的结点数都达到最大个数，第h层有叶子结点，并且叶子结点都是从左到右依次排布，这就是完全二叉树。
2、满二叉树——除了叶结点外每一个结点都有左右子叶且叶子结点都处在最底层的二叉树。
3、平衡二叉树——平衡二叉树又被称为AVL树（区别于AVL算法），它是一棵二叉排序树，且具有以下性质：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。
六、Introducing maple trees
maple tree（取这个名字可能是借用了枫叶的形状，意指能走向多个方向）与 rbtrees 有根本性的差异。它们属于 B-tree 类型(https://en.wikipedia.org/wiki/B-tree)，也就是说它们的每个节点可以包含两个以上的元素，leaf node（叶子节点）中最多包含 16 个元素，而 internal node（内部节点）中最多包含 10 个元素。使用 B-trees 也会导致很少需要创建新的 node，因为 node 可能包含一些空余空间，可以随着时间的推移而填充利用起来，这就不需要额外进行分配了。每个 node 最多需要 256 字节，这是常用的 cache line size 的整数倍。node 中增加的元素数量以及 cache-aligned size 就意味着在遍历树时会减少 cache-miss。
maple tree 对搜索过程也有改进，同样是来自于 B-tree 结构特点。在 B-tree 中，每个 node 都有一些 key 键值，名为 "pivot"，它会将 node 分隔成 subtree（子树）。在某个 key 之前的 subtree 只会包含小于等于 key 的数据，而这个 key 之后的子树只包含大于 key 的值（并且小于下一个 key 值）。
当然，maple tree 的设计中也是按照 lockless 方式的要求来的，使用 read-copy-update (RCU) 方式。maple tree 是一个通用结构，可以用在内核的不同子系统中。第一个用到 maple tree 的地方就是用来替换 VMA 管理中用到的 rbtree 和双向链表。作者之一 Liam Howlett 在一篇博客中解释了设计由来(https://blogs.oracle.com/linux/the-maple-tree)。
Maple tree 提供了两组 API：一个是简单 API ，一个是高级 API。简单 API 使用 mtree_前缀来标记相关功能，主结构 struct maple_tree 定义如下：
struct maple_tree { spinlock_t ma_lock; unsigned int ma_flags; void __rcu *ma_root; };
需要静态初始化（static initialize）的话，可以使用 DEFINE_MTREE(name) 和 MTREE_INIT(name，flags)，后者会的 flags 目前只定义了两个 bit 选项，其中 MAPLE_ALLOC_RANGE 表示该树将被用于分配 range，并且需要把多个分配区域之间的空间（gap）管理起来；MAPLE_USE_RCU 会激活 RCU mode，用在多个 reader 的场景下。mtree_init() API 也使用相同的 flags，不过是用在动态初始化（dynamic initialization）场景：
void mtree_init(struct maple_tree *mt, unsigned int ma_flags);
开发者可以用这个函数来 free 整个 tree：
void mtree_destroy(struct maple_tree *mt);
可以用三个函数来给树增加条目：mtree_insert()、mtree_insert_range()和 mtree_store_range()。前两个函数只有在条目不存在的情况下才会添加，而第三个函数可以对现有的条目进行覆盖。它们的定义如下：
int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp); int mtree_insert_range(struct maple_tree *mt, unsigned long first, unsigned long last, void *entry, gfp_t gfp); int mtree_store_range(struct maple_tree *mt, unsigned long first, unsigned long last, void *entry, gfp_t gfp);
mtree_insert()的参数 mt 是指向 tree 的指针，index 就是 entry index，entry 是指向一个条目的的指针，有必要的话可以利用 gfp 来指定新增 tree node 的内存分配参数（memory allocation flag）。mtree_insert_range() 会利用给出的 entry 数据来插入从 first 到 last 的一个 range 范围。这些函数成功时返回 0，否则返回负值，如果返回-EEXIST 就表示 key 已经存在。mtree_store_range()与 mtree_insert_range()接受的参数相同，不同的是，它会替换相应 key 的任何现有条目。
有两个函数可以用来从 tree 中获取一个条目或删除一个条目：
void *mtree_load(struct maple_tree *mt, unsigned long index); void *mtree_erase(struct maple_tree *mt, unsigned long index);
要读取一个条目的话，可以使用 mtree_load()，它的参数是一个指向 tree 的指针 mt ，以及所要读取的数据的键值 index。该函数会返回一个指向该条目的指针，如果在 tree 中没有找到键值，则返回 NULL。mtree_erase() 也是同样的语法，用于从 tree 中删除一个 entry。它会从 tree 中删除给定的 key，并返回相关的 entry，如果没有找到，则返回 NULL。
简单的 API 不止上面这些，还有比如 mtree_alloc_range() 可以用来从 key space 中分配一个 range。而高级 API (用 mas_ 前缀标记出来了) 则额外增加了遍历整个 tree 的迭代函数，以及使用 state variable 来访问后一个或者前一个元素。通过这种细粒度的操作，开发者就可以根据需要来恢复中断了的搜索。还有供开发人员找到空闲区域或者对 tree 进行复制操作的 API。
6.1Replacing the VMA rbtree (and more)
patch set 中不仅仅是引入了 maple tree。着重需要指出的是，这组 patch set 中有很大一部分是增加修改测试代码，考虑到这个改动会带来的巨大影响，以及新的数据结构在未来的重要性，这些测试代码是非常值得鼓励的。
这组 patch set 中有 70 个 patch 将 VMA 的所有操作中的 rbtree 操作换成了 maple tree，其中一个 patch 彻底在 VMA 中禁用了 rbtree。patch set 中另一部分代码移除了 VMA 里的双向链表。这个改动需要修改内核中所有直接地使用了 VMA 链表的代码：体系架构相关代码，core dump 代码，program 加载代码，一些设备驱动程序等，当然还有 memory-management 代码。patch set 里还删除了 VMA cache（用来跟踪每个进程最近访问过的 VMA，从而加快 lookup 速度），这是因为使用 maple tree 实现后速度更快，不再需要 VMA cache 了。
Patch set 的第一封邮件中还包括了一些性能数据 ，不过结果有些难以理解。一些 microbenchmark 的结果说明性能提升了，而其他一些（数量较少）则说明性能下降了。编译内核的时间与 5.10 内核本身相类似，只是多执行了几条指令（可能与添加的代码有关）。Howlett 希望大家给些建议如何对这些结果进行更深入的分析。
6.2Current status and next steps
目前 Maple tree 还处于 RFC 阶段，有一些缺点。比如说，目前的实现不支持 32 位系统或 non-MMU 的平台。不过，这些代码已经可以实际用起来了，内核开发者们可以研究一下，从而决定是否符合他们期望的方向（因为这组 patch set 并没有去掉 mmap_lock ）。这个 patch set 太大了，可能需要不少时间才能完成 review。
6.3Splay Tree
Splay Tree(伸展树)是Binary Search Tree(二叉搜索树)， Daniel Sleator和Robert E.Tarjan发明。但此操作可能会花费O(n)时间，但m次操作的最坏情况为O(m*log2(n))。
Splay Tree是在节点访问后，此节点将成为该树的根。如此节点位置深，则根到该节点路径上会有很多较深节点。旋转后，这些节点的深度会减少。
查找频率高的item经常在靠近树根的位置。每次查找后，对树进行重构，把item挪倒离树根近地方。Splay tree是自调整形式的二叉查找树，会沿着某个节点到树根间的路径，通过一系列旋转把此节点搬移到树根。
RtlSplay 主要例程，完成节点到Splay树根的操作。
RtlDelete 删除节点，重新平衡。
RtlIsRoot 节点是否是Splay树根。
RtlRealPredecessor 返回节点的pre节点。
RtlInsertAsLeftChild
下面贴以下Win2k源码中的RtlSplay代码：
PRTL_SPLAY_LINKS RtlSplay( IN PRTL_SPLAY_LINKS Links ) { PRTL_SPLAY_LINKS L; PRTL_SPLAY_LINKS P; PRTL_SPLAY_LINKS G; // while links is not the root we need to keep rotating it toward // the root L = Links; while (!RtlIsRoot(L)) { P = RtlParent(L); G = RtlParent(P); if (RtlIsLeftChild(L)) { if (RtlIsRoot(P)) { /* we have the following case P L / \ / \ L c ==> a P / \ / \ a b b c */ // Connect P & b // P->LeftChild = L->RightChild; if (P->LeftChild != NULL) {P->LeftChild->Parent = P;} // Connect L & P L->RightChild = P; P->Parent = L; // Make L the root L->Parent = L; } else if (RtlIsLeftChild(P)) { /* we have the following case | | G L / \ / \ P d ==> a P / \ / \ L c b G / \ / \ a b c d */ // Connect P & b P->LeftChild = L->RightChild; if (P->LeftChild != NULL) {P->LeftChild->Parent = P;} // Connect G & c G->LeftChild = P->RightChild; if (G->LeftChild != NULL) {G->LeftChild->Parent = G;} // Connect L & Great GrandParent if (RtlIsRoot(G)) { L->Parent = L; } else { L->Parent = G->Parent; *(ParentsChildPointerAddress(G)) = L; } // Connect L & P L->RightChild = P; P->Parent = L; // // Connect P & G // P->RightChild = G; G->Parent = P; } else { // RtlIsRightChild(Parent) /* we have the following case | | G L / \ / \ a P G P / \ / \ / \ L d ==> a b c d / \ b c */ // // Connect G & b // G->RightChild = L->LeftChild; if (G->RightChild != NULL) {G->RightChild->Parent = G;} // // Connect P & c // P->LeftChild = L->RightChild; if (P->LeftChild != NULL) {P->LeftChild->Parent = P;} // // Connect L & Great GrandParent // if (RtlIsRoot(G)) { L->Parent = L; } else { L->Parent = G->Parent; *(ParentsChildPointerAddress(G)) = L; } // // Connect L & G // L->LeftChild = G; G->Parent = L; // // Connect L & P // L->RightChild = P; P->Parent = L; } } else { // RtlIsRightChild(L) if (RtlIsRoot(P)) { /* we have the following case P L / \ / \ a L P c / \ / \ b c ==> a b */ // // Connect P & b // P->RightChild = L->LeftChild; if (P->RightChild != NULL) {P->RightChild->Parent = P;} // // Connect P & L // L->LeftChild = P; P->Parent = L; // // Make L the root // L->Parent = L; } else if (RtlIsRightChild(P)) { /* we have the following case | | G L / \ / \ a P P d / \ / \ b L G c / \ / \ c d ==> a b */ // // Connect G & b // G->RightChild = P->LeftChild; if (G->RightChild != NULL) {G->RightChild->Parent = G;} // // Connect P & c // P->RightChild = L->LeftChild; if (P->RightChild != NULL) {P->RightChild->Parent = P;} // // Connect L & Great GrandParent // if (RtlIsRoot(G)) { L->Parent = L; } else { L->Parent = G->Parent; *(ParentsChildPointerAddress(G)) = L; } // // Connect L & P // L->LeftChild = P; P->Parent = L; // // Connect P & G // P->LeftChild = G; G->Parent = P; } else { // RtlIsLeftChild(P) /* we have the following case | | G L / \ / \ P d P G / \ / \ / \ a L ==> a b c d / \ b c */ // // Connect P & b // P->RightChild = L->LeftChild; if (P->RightChild != NULL) {P->RightChild->Parent = P;} // // Connect G & c // G->LeftChild = L->RightChild; if (G->LeftChild != NULL) {G->LeftChild->Parent = G;} // // Connect L & Great GrandParent // if (RtlIsRoot(G)) { L->Parent = L; } else { L->Parent = G->Parent; *(ParentsChildPointerAddress(G)) = L; } // // Connect L & P // L->LeftChild = P; P->Parent = L; // // Connect L & G // L->RightChild = G; G->Parent = L; } } } return L; }
精选文章推荐阅读：
