linux中的优先搜索树的实现.docx

linux中的优先搜索树的实现 prio treelinux中的优先搜索树的实现 prio tree linux中的优先搜索树的实现-prio_tree prio_tree在linux内核中被应用于反向内存映射，prio-tree是一棵查找树，它查找的是一个区间，为何将之组织成tree是一个数学问题，简单理解就是根节点包含了所有的区间，父节点代表的区间包含了子节点代表的区间，这里的包含不是现实意义的包含，而是heap/radix意义上的包含，只要满足heap的性质以及radix的性质即可，不过大多数情况下包含的意义就是现实意义的包含，Documentation中的prio_tree.txt中的图示可以看一下，4,3,7是5,2,7和6,1,7的父节点，父节点区间现实包含了两个子节点区间，而5,2,7是4,2,6和5,1,6的父节点，5,2,7就没有现实包含4,2,6，但是仍然是后者的父节点，因为它们满足了heap的性质，5,2,7的heap-index是7，大于4,2,6的heap-index。由于prio-tree首先要是一个heap(插入过程中详细说明)-处理父子关系，其次要是一个radix树-处理兄弟关系，父子间满足了heap之后还要在兄弟间满足radix性质，总之，prio-tree节点间的关系有两个层次的两种，第一层，父子关系，必须符合heap性质，第二层，兄弟关系，必须符合radix性质。以上简要介绍了prio-tree的性质，是所有实现的共性，linux内核的实现实现了自己的个性，如果看代码的话就会发现，linux引入了一些变量或者约束，使得prio-tree在性能，资源消耗以及代码可读性之间做出了一个完美的平衡，最值得推崇的就是linux的prio-tree中维护了一个图表，该图表约束了prio-tree的高度，该图表以一个数组实现，数组的内容其实就是该索引下最大的heap，每一个树节点都有一个index_bits字段，它表示了用index_bits个比特就能表达最大的heap，而此index_bits减1正是这么些比特在数组中的下标，图表如下:bit-used array-index max-heap 10 12 111 32 111 43 1111由上面的图表1可以推导出下面的等式，下面的等式优化了树的性能，促使了数的平衡，并且巧妙的处理了兄弟之间的关系，使之符合prio-tree的原始约束:bit-used+1=tree-height(等式1)根据上述等式，mask=1UL(root-index_bits-1);，这个mask代表了当前处理的层的最高位，它决定了待插入节点是插入左孩子还是插入右孩子。插入过程中，每下将一层，mask要右移一位，由于prio-tree是一棵二叉树，因此二进制的0和1就能决定左和右，这个性质和二叉radix查找树是一样的，一个二进制的数是由0和1组成的串，如果欲将之插入一棵radix树，那么从待插节点最高位开始依次操作，根据结果来进行左右抉择，每从树根处开始和树中节点的相应位进行&下降一层，比较位就右移一位，直到成功插入，这样就保证了树的radix性质，上述等式1其实并不是必不可少的，它的作用更大的意义是优化，包括代码紧凑度的优化以及时间空间的优化，没有它的话，代码不可能写成现在的prio_tree.c中如此紧凑又容易理解的形式，同时一棵树还会因为频繁的插入和删除而变得很高，这样对查找来讲是很不利的，正如宏黑树用颜色来约束平衡，AVL树用高度来约束平衡一样，prio-tree用上述等式1来约束平衡。既然用radix性质实现了一棵radix树，我们还可以用heap性质来构造一个heap，-tree了，而heap的本质上也是一棵二叉树，如果将二者合并的话，就是prio性质主要体现在父子上面，对兄弟之间并没有多大的约束，因此在prio-tree的插入过程中，基本分为三大块，第一大块是实现heap的性质，在此基础上，第二大快对待左右抉择的时候利用radix的性质以及radix的插入逻辑实现插入，两大块保证了prio-tree的性质，但是不能保证平衡性，由此在此两块的基础上尽量保证树的平衡，于是等式1起作用，以上的三块联动已经近乎完美了，但是理想情况往往不能尽满足现实需求，很多的节点都拥有相同的radix，那么根据heap的性质，它们最终将成为一个近似链表的东西，因此如果为了处理这些链表二增加树的高度(增加max-heap)，那么树看起来会很不平衡的，因此单独列出一个overflow-sub-tree来处理这种情况，加入这个性质之后，prio-tree实则成了一个集heap，radix树，链表于一身的集大成，最终的结果就是prio_tree.c中的prio_tree_insert函数的实现:insert:cur=root-prio_tree_node;mask=1UL(root-index_bits-1);while(mask)GET_INDEX(cur,r_index,h_index);if(r_index=radix_index&h_index=heap_index)return cur;if(h_index heap_index|/破坏了父子约束，因此需要交换父子(h_index=heap_index&r_index radix_index)struct prio_tree_node*tmp=node;node=prio_tree_replace(root,cur,node);cur=tmp;/需要插入的node现在已经成了被替换的node index=r_index;/交换所有的索引，heap索引和radix索引.if(size_flag)index=heap_index-radix_index;else index=radix_index;if(index&mask)/此处的if-else用于确定兄弟约束，对应位为1则往右走./右孩子为空的话直接插入右孩子的位置，返回else/否则返回右孩子cur=cur-right;else/对应位为0则往左走./左孩子为空的话直接插入左孩子的位置，返回else/否则返回左孩子cur=cur-left;mask=1;/进入下一层的radix抉择if(mask)/处理overflow树mask=1UL(root-index_bits-1);size_flag=1;由于heap和radix树的逻辑都是执行过程中体现的，并且都是确定的，只有那个图表1相关的代码是prio-tree独有的，因此在prio_tree_init中必然要进行相关的初始化，可以看出，prio_tree_init进行的仅仅是图表1相关的初始化，初始化完成以后，从图表1就可以推出等式1了，由此prio-tree的运行所需要的基础设施就全部到位了:void _init prio_tree_init(void)unsigned int i;for(i=0;i ARRAY_SIZE(index_bits_to_maxindex)-1;1;i+)index_bits_to_maxindexi=(1UL(i+1)-index_bits_to_maxindexARRAY_SIZE(index_bits_to_maxindex)-1=0UL;很多树节点的remove操作都很复杂，甚至比insert还要复杂，但是对于prio-tree来讲却是很简单的，因为prio-tree节点的heap特性，并且整个prio-tree首先肯定是一个heap，所谓的radix只是在对兄弟无约束的heap加上了兄弟间的约束而已，因此remove操作完全实际上就是一个heap调整的过程，调整完heap之后无需再关心树的radix性质，因为它只要首先是一个heap即可，在remove的每一步操作中，只要能保证树的heap性质就可以了，只需