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

1        0        1

2        1        11

3        2        111

4        3        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，本質上也是一棵二叉樹，如果将二者合并的話，就是prio-tree了，而heap的性質主要展現在父子上面，對兄弟之間并沒有多大的限制，是以在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; i++)

        index_bits_to_maxindex[i] = (1UL << (i + 1)) - 1;

    index_bits_to_maxindex[ARRAY_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性質就可以了，隻需要從待删除節點往下沿着大孩子走一直到葉節點，然後再回溯回來即可，回溯過程中需要依次的将目前節點和父節點進行對換，依次進行，最終就是待删除節點的大孩子替換了待删除節點，删除至此結束，至于忽略了radix性質是否會帶來樹的不平衡，答案是可能不會也可能會，但不甚會，如果在remove操作時加上樹的平衡性維護，那麼代碼将變得複雜，同時也會影響到效率。

 本文轉自 dog250 51CTO部落格，原文連結:http://blog.51cto.com/dog250/1271813