linux中的优先搜索树的实现

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 树，那么从待插节点最高位开始依次操作，根据结果来进行左右抉择，每从树根处开始和树中节点的相应位进行“mask=1UL(root-index_bits-1);while(mask)GET_INDEX(cur,r_index,h_index);if(r_index=radix_indexif(h_index heap_index|/破坏了父子约束，因此需要交换父子(h_index=heap_indexnode=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(indexelse/对应位为 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 性质就可以了，只需要从待删除节点往下沿着大孩子走一直到叶节点，然后再回溯回来即可，回溯过程中需要依次