Linux基數(shù)樹（radix tree）是將指針與long整數(shù)鍵值相關(guān)聯(lián)的機制，它存儲有效率，并且可快速查詢，用于指針與整數(shù)值的映射（如：IDR機制）、內(nèi)存管理等。
IDR（ID Radix）機制是將對象的身份鑒別號整數(shù)值ID與對象指針建立關(guān)聯(lián)表，完成從ID與指針之間的相互轉(zhuǎn)換。IDR機制使用radix樹狀結(jié)構(gòu)作為由id進行索引獲取指針的稀疏數(shù)組，通過使用位圖可以快速分配新的ID，IDR機制避免了使用固定尺寸的數(shù)組存放指針。IDR機制的API函數(shù)在lib/idr.c中實現(xiàn)，這里不加分析。
Linux radix樹最廣泛的用途是用于內(nèi)存管理，結(jié)構(gòu)address_space通過radix樹跟蹤綁定到地址映射上的核心頁，該radix樹允許內(nèi)存管理代碼快速查找標識為dirty或writeback的頁。Linux radix樹的API函數(shù)在lib/radix-tree.c中實現(xiàn)。
（1）radix樹概述
radix樹是通用的字典類型數(shù)據(jù)結(jié)構(gòu)，radix樹又稱為PAT位樹（Patricia Trie or crit bit tree）。Linux內(nèi)核使用了數(shù)據(jù)類型unsigned long的固定長度輸入的版本。每級代表了輸入空間固定位數(shù)。
radix tree是一種多叉搜索樹，樹的葉子結(jié)點是實際的數(shù)據(jù)條目。每個結(jié)點有一個固定的、2^n指針指向子結(jié)點（每個指針稱為槽slot），并有一個指針指向父結(jié)點。
Linux內(nèi)核利用radix樹在文件內(nèi)偏移快速定位文件緩存頁，圖4是一個radix樹樣例，該radix樹的分叉為4(22)，樹高為4，樹的每個葉子結(jié)點用來快速定位8位文件內(nèi)偏移，可以定位4x4x4x4=256頁，如：圖中虛線對應(yīng)的兩個葉子結(jié)點的路徑組成值0x00000010和0x11111010，指向文件內(nèi)相應(yīng)偏移所對應(yīng)的緩存頁。 
圖4 一個四叉radix樹
Linux radix樹每個結(jié)點有64個slot，與數(shù)據(jù)類型long的位數(shù)相同，圖1顯示了一個有3級結(jié)點的radix樹，每個數(shù)據(jù)條目（item）可用3個6位的鍵值（key）進行索引，鍵值從左到右分別代表第1~3層結(jié)點位置。沒有孩子的結(jié)點在圖中不出現(xiàn)。因此，radix樹為稀疏樹提供了有效的存儲，代替固定尺寸數(shù)組提供了鍵值到指針的快速查找。 
圖1 一個3級結(jié)點的radix樹及其鍵值表示
（2）radix樹slot數(shù)
Linux內(nèi)核根用戶配置將樹的slot數(shù)定義為4或6，即每個結(jié)點有16或64個slot，如圖2所示，當(dāng)樹高為1時，64個slot對應(yīng)64個頁，當(dāng)樹高為2時，對應(yīng)64*64個頁。 
圖2 高為1和2、slot數(shù)為64的radix樹
Linux內(nèi)核radix樹的slot數(shù)定義如下（在lib/radix-tree.c中）：
#ifdef __KERNEL__
/*值為6時，表示每個結(jié)點有2^6＝64個slot，值為4時，表示有2^4=16個slot*/
#define RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
#else
#define RADIX_TREE_MAP_SHIFT 3 /* 用于更有強度的測試 */
#endif
/*表示1個葉子結(jié)點可映射的頁數(shù)，如：1<<6=64，表示可映射64個slot映射64頁*/
#define RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
#define RADIX_TREE_MAP_MASK (RADIX_TREE_MAP_SIZE-1)
/*定義slot數(shù)占用的long類型長度個數(shù)，每個slot用位圖1位進行標記，如：64個slot時，值為2*/
#define RADIX_TREE_TAG_LONGS \
((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) / BITS_PER_LONG)
（3）結(jié)點結(jié)構(gòu)
樹的根結(jié)點結(jié)構(gòu)radix_tree_root列出如下（在include/linux/radix-tree.h中）：
#define RADIX_TREE_MAX_TAGS 2 /*每個slot需要的最大標簽位數(shù)*/
/*根結(jié)點的標簽存放在gfp_mask中，通過__GFP_BITS_SHIFT移位得到 */
struct radix_tree_root {
unsigned int height; /* 從葉子向上計算的樹高度 */
gfp_t gfp_mask;
/*間接指針指向結(jié)點而非數(shù)據(jù)條目，通過設(shè)置root->rnode的低位表示是否是間指針*/
struct radix_tree_node *rnode;
#ifdef CONFIG_RADIX_TREE_CONCURRENT
struct radix_tree_context *context;
struct task_struct *owner;
#endif
};
結(jié)構(gòu)radix_tree_context列出如下：
struct radix_tree_context {
struct radix_tree_root *root;
#ifdef CONFIG_RADIX_TREE_CONCURRENT
spinlock_t *locked;
#endif
}
樹的結(jié)點結(jié)構(gòu)radix_tree_node列出如下（在lib/radix-tree.c中）：
struct radix_tree_node {
unsigned int height; /* 從葉子向上計算的樹高度 */
unsigned int count; /*非葉子結(jié)點含有一個count域，表示出現(xiàn)在該結(jié)點的孩子的數(shù)量*/
struct rcu_head rcu_head;
void *slots[RADIX_TREE_MAP_SIZE]; /*結(jié)點的slot指針*/
/* 結(jié)點標簽數(shù)組=每個slot需要的最大標簽位數(shù)*slot數(shù)所需的long類型變量數(shù) */
unsigned long tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};
Linux內(nèi)核radix樹高度是可變的，它依賴于存儲的索引鍵值。radix樹查詢必須知道樹高度，以便知道結(jié)點的slot是指向葉子結(jié)點的指針還是結(jié)點的其他層。Linux在結(jié)點結(jié)構(gòu)中有成員height存入樹高度信息。
Linux radix樹的獨特特征是標簽擴展。圖2顯示了有2個標簽，分別表示打開和關(guān)閉。這些標簽是結(jié)點結(jié)構(gòu)的成員tags，該標簽用一個位圖實現(xiàn)，在加鎖的情況下設(shè)置和清除。每個標簽基本上是一個在radix樹頂層上的位圖序號。標簽與群查詢一起用來在給定的范圍內(nèi)查找給定標簽集的頁。
標簽在每結(jié)點位圖中維護，在每個給定的級別上，可以判定下一個級別是否至少有一個標簽集。
圖2 帶有2位圖標簽指示的8位radix樹
在結(jié)點結(jié)構(gòu)radix_tree_node中，tags域是一個二維數(shù)組，每個slot用2位標識，這是一個典型的用空間換時間的應(yīng)用。tags域用于記錄該結(jié)點下面的子結(jié)點有沒有相應(yīng)的標志位。目前RADIX_TREE_MAX_TAGS為2，表示只記錄兩個標志，其中tags[0]為PAGE_CACHE_DIRTY，tags[1]為PAGE_CACHE_WRITEBACK。如果當(dāng)前節(jié)點的tags[0]值為1，那么它的子樹節(jié)點就存在PAGE_CACHE_DIRTY節(jié)點，否則這個子樹分枝就不存在著這樣的節(jié)點，就不必再查找這個子樹了。比如在查找PG_dirty的頁面時，就不需要遍歷整個樹，而可以跳過那些tags[0]為0值的子樹，這樣就提高了查找效率。
“加標簽查詢”是返回有指定標簽集radix樹條目的查詢，可以查詢設(shè)置了標簽的條目。加標簽查詢可以并行執(zhí)行，但它們需要通過設(shè)置或清除標簽從操作上互斥。
(4) 并行操作的優(yōu)化
Linux radix樹并行操作包括并行查詢和并行修改，其中，并行修改在標準內(nèi)核中未完沒有實現(xiàn)，需要通過打補丁獲得該功能。并行操作說明如下：
通過使用RCU，RCU Radix樹可以進行完全并發(fā)的查詢操作。RCU從根本上要求原子操作地移動指針從數(shù)據(jù)結(jié)構(gòu)的一個版本到新的版本，保持舊版本直到系統(tǒng)經(jīng)過靜止狀態(tài)。在靜止狀態(tài)點，舊版本數(shù)據(jù)結(jié)構(gòu)已沒有用戶，因此可以被安全釋放。
RCU radix樹的修改操作之間還需要串行化，但是查詢不再需要與修改操作串行化。
RCU可使RCU radix樹查詢完全并行化，但修改操作成了“瓶頸”。這可通過將全樹的鎖破碎成較小的鎖進行改善，再明顯的方法是對結(jié)點進行加鎖而非對整個樹加鎖。
radix樹修改操作可分為單向和雙向操作。單向操作僅執(zhí)行從根節(jié)點和葉子結(jié)點的單方向指針移動，它包括插入、更新和設(shè)置標簽操作。雙向操作較復(fù)雜，它需要在指針移到葉子后又回移，它包括刪除和清除標簽操作。
梯級加鎖（Ladder Locking）和鎖耦合（Lock-Coupling）技術(shù)常用于數(shù)據(jù)庫方面，允許單向遍歷結(jié)點加鎖的樹（雙向可能產(chǎn)生死鎖）。如果所有的修改者從樹頂?shù)綐涞走M行修改，并且修改的結(jié)點持有鎖，那么，向下遍歷時對孩子加鎖，在孩子被鎖住時再釋放該結(jié)點鎖。在這種情況下并發(fā)操作是可能的，因為只要根結(jié)點解鎖，另一個操作就可以自上向下進行。如果兩操作的路徑?jīng)]有相同操作結(jié)點，后一個操作可能在前一個操作完成之前完成。最壞的情況是流水線操作，但這還是比串行化操作好很多。
雙向操作包括刪除和清除標簽操作，分別說明如下：
1）清除標簽
在radix樹中清除一個標簽包括向下遍歷樹、查找定位條目和清除條目標簽的操作。只要孩子結(jié)點沒有打標簽的條目，就可以向上遍歷結(jié)點清除標簽。結(jié)束條件是：如果遍歷遇到一個結(jié)點，在清除一個標簽后，它還有一個或多個條目帶有標簽集，就可以結(jié)束向上遍歷。為了與向下遍歷期間有同樣的結(jié)束點，將終止條件改為：向上遍歷將在有比清除標簽數(shù)更多標簽的結(jié)點處結(jié)束。這樣，不論何時遇到這樣的結(jié)點，將作為上遍歷樹的結(jié)束點。
2）刪除元素
刪除元素在刪除無用結(jié)點時還需要刪除該條目的所有標簽。它的終止條件需要滿足這兩個方面。向上回退遍歷樹時需要滿足下面的條件：當(dāng)遇到一個非空結(jié)點且沒有無用的標簽時應(yīng)終止向上回退遍歷樹。
在向下遍歷樹時鑒別此點的條件是：當(dāng)遇到有超過2個孩子的結(jié)點、并且每個標簽來說結(jié)點有多于一個標簽條目被清除時，結(jié)束向上遍歷。該條件用來鑒別向上回退遍歷的終止點。
（5）radix樹API說明
聲明和初始化radix樹的方法列出如下：
#include <linux/radix-tree.h>
/* gfp_mask表示如何執(zhí)行內(nèi)存分配，如果操作（如：插入）以原子性上下文中執(zhí)行，其值為GFP_ATOMIC*/
RADIX_TREE(name, gfp_mask); /* 聲明和初始化名為name的樹*/
struct radix_tree_root my_tree;
INIT_RADIX_TREE(my_tree, gfp_mask);
插入條目的函數(shù)定義列出如下：
int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
函數(shù)radix_tree_insert插入條目item到樹root中，如果插入條目中內(nèi)存分配錯誤，將返回錯誤-ENOMEM。該函數(shù)不能覆蓋寫正存在的條目。如果索引鍵值index已存在于樹中，返回錯誤-EEXIST。插入操作成功是，返回0。
對于插入條目操作失敗將引起嚴重問題的場合，下面的一對函數(shù)可避免插入操作失?。?
int radix_tree_preload(gfp_t gfp_mask);
void radix_tree_preload_end(void);
函數(shù)radix_tree_preload嘗試用給定的gfp_mask分配足夠的內(nèi)存，保證下一個插入操作不會失敗。在調(diào)用插入操作函數(shù)之前調(diào)用此函數(shù)，分配的結(jié)構(gòu)將存放在每CPU變量中。函數(shù)radix_tree_preload操作成功后，將完畢內(nèi)核搶占。因此，在插入操作完成之后，用戶應(yīng)調(diào)用函數(shù)radix_tree_preload_end打開內(nèi)核搶占。
刪除條目的函數(shù)定義列出如下：
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
函數(shù)radix_tree_delete刪除與索引鍵值index相關(guān)的條目，如果刪除條目在樹中，返回該條目的指針，否則返回NULL。
用于查詢操作的函數(shù)定義列出如下：
/*在樹中查找指定鍵值的條目，查找成功，返回該條目的指針，否則，返回NULL*/
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index);
/*返回指向slot的指針，該slot含有指向查找到條目的指針*/
void **radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long index);
/*查詢返回max_items條目在results中。查詢時鍵值索引從first_index開始*/
radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items);
與標簽操作相關(guān)的函數(shù)說明列出如下：
/*將鍵值index對應(yīng)的條目設(shè)置標簽tag，返回值為設(shè)置標簽的條目*/
void *radix_tree_tag_set(struct radix_tree_root *root, unsigned long index, unsigned int tag);
/*從鍵值index對應(yīng)的條目清除標簽tag，返回值為清除標簽的條目*/
void *radix_tree_tag_clear(struct radix_tree_root *root, unsigned long index, unsigned int tag);
/*檢查鍵值index對應(yīng)的條目是否為標簽tag，如果鍵值不存在，返回0，如果鍵值存在，但標簽未設(shè)置，返回-1；如果鍵值存在，且標簽已設(shè)置，返回1*/
int radix_tree_tag_get(struct radix_tree_root *root, unsigned long index, unsigned int tag);
/*從first_index起查詢樹root中標簽值為tag的條目，在results中返回*/
unsigned int radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items, unsigned int tag);
/*如果樹root中有任何條目使用tag標簽，返回鍵值*/
int radix_tree_tagged(struct radix_tree_root *root, unsigned int tag);
（6）并行操作使用radix樹API的方法
查詢操作支持RCU無阻塞并行讀操作，因此，需要遵循RCU的用法加RCU讀鎖，還需要將rcu_dereference()用于獲得的slot，在寫（或更新）操作時，需要給新的slot使用rcu_assign_pointer()。查詢操作的使用方法列出如下：
struct page **slot, *page;
rcu_read_lock();
slot = radix_tree_lookup_slot(&mapping->page_tree, index);
page = rcu_dereference(*slot);
rcu_read_unlock();
Linux內(nèi)核的radix樹需要打補丁才支持并發(fā)修改。查詢僅有一個全局狀態(tài)：RCU靜止狀態(tài)，并發(fā)修改需要跟蹤持有什么鎖。鎖狀態(tài)對于操作來說必須是外部的，因此，我們需要實例化一個本地上下文跟蹤這些鎖。查詢修改slot的方法列出如下：
struct page **slot;
DEFINE_RADIX_TREE_CONTEXT(ctx,&mapping->page_tree);
radix_tree_lock(&ctx); /*鎖住了根結(jié)點*/
/* ctx.tree代替&mapping->page_tree作為根，可以傳遞上下文
slot = radix_tree_lookup_slot(tx.tree, index);
rcu_assign_pointer(*slot, new_page);
radix_tree_unlock(&ctx);
radix樹API函數(shù)radix_tree_lookup_slot含有鎖從樹頂向下移動機制，鎖移動的代碼部分列出如下：
void **radix_tree_lookup_slot(struct radix_tree *root, unsigned long index)
{
...
RADIX_TREE_CONTEXT(context, root); /*提供上下文和實際的root指針*、
...
do {
...
/* 從樹頂向下移動鎖*/
radix_ladder_lock(context, node);
...
} while (height > 0);
...
}
（7）radix樹API的實現(xiàn)
樹的操作通常包括查找、插入、刪除和樹調(diào)整，下面分別說明radix樹這些操作的實現(xiàn)。
radix樹通過索引鍵值進行查詢，如圖1所示，它按路徑組成索引鍵值，圖中3級結(jié)點對應(yīng)3段6位表示的索引值，圖中key對應(yīng)的葉子slot的索引鍵值為“2,63,1”。通過葉子slot的指針slot[1]就可得到所存儲的數(shù)據(jù)item。因此，查詢迭代時，需要將索引鍵值“2,63,1”移去高2層“2,63”，得到葉子slot的指針索引鍵值“1”。
圖1 一個3級結(jié)點的radix樹及其鍵值表示
函數(shù)radix_tree_lookup執(zhí)行查找操作，查找方法是：從葉子到樹頂，通過數(shù)組索引鍵值值查看數(shù)組元素的方法，一層層地查找slot。其列出如下（在lib/radix-tree.c中）：
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long index)
{
unsigned int height, shift;
struct radix_tree_node *node, **slot;
node = rcu_dereference(root->rnode); /*獲取根結(jié)點*/
if (node == NULL)
return NULL;
/*間接指針指向結(jié)點而非數(shù)據(jù)條目，通過設(shè)置root->rnode的低位表示是否是間指針。對于間接指針來說，樹高度值root->height大于0，但是RCU查找需要測試間接指針，因為root->height 值不可靠。這種問題僅的RCU下需要考慮*/
if (!radix_tree_is_indirect_ptr(node)) { /*非間接指針，說明只有根結(jié)點*/
if (index > 0)
return NULL;
return node;
}
/*獲取真正結(jié)點指針，因為根結(jié)點指針的第0位設(shè)置為1表示為間接指針。當(dāng)使用結(jié)點指針時，必須將第0位設(shè)置為0，因為地址以字對齊*/
node = radix_tree_indirect_to_ptr(node);
height = node->height;
if (index > radix_tree_maxindex(height)) /*索引鍵值不能超過最大索引值*/
return NULL;
/*每層索引偏移值為RADIX_TREE_MAP_SHIFT，葉子索引值偏移基數(shù)為（樹高-1）*每層索引偏移值*/
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
do { /*從葉子到樹頂，通過樹路徑組成的索引查找指定索引鍵值的slot*/
slot = (struct radix_tree_node **)(node->slots + ((index>>shift) & RADIX_TREE_MAP_MASK)); /*如：slots +1*/
node = rcu_dereference(*slot);
if (node == NULL)
return NULL;
shift -= RADIX_TREE_MAP_SHIFT; /*向上移一層，再迭代查找*/
height--;
} while (height > 0);
return node;
}
函數(shù)radix_tree_gang_lookup執(zhí)行多個索引鍵值的查找，其列出如下：
unsigned int radix_tree_gang_lookup(struct radix_tree_root *root, void **results, unsigned long first_index, unsigned int max_items)
{
unsigned long max_index;
struct radix_tree_node *node;
unsigned long cur_index = first_index;
unsigned int ret;
node = rcu_dereference(root->rnode);
if (!node)
return 0;
if (!radix_tree_is_indirect_ptr(node)) { /*如果為非間接指針，表示只有根節(jié)點*/
if (first_index > 0)
return 0;
results[0] = node;
return 1;
}
node = radix_tree_indirect_to_ptr(node); /*清除用于間接指針標識的第0位*/
max_index = radix_tree_maxindex(node->height); /*獲取樹的最大索引鍵值*/
ret = 0;
while (ret < max_items) { /* max_items為查找的最大條目數(shù)*/
unsigned int nr_found;
unsigned long next_index; /* 下一個搜索的索引鍵值*/
if (cur_index > max_index) /*已查詢完所需查詢的索引鍵值*/
break;
nr_found = __lookup(node, results + ret, cur_index,
max_items - ret, &next_index);
ret += nr_found;
if (next_index == 0)
break;
cur_index = next_index;
}
return ret;
}
static unsigned int
__lookup(struct radix_tree_node *slot, void **results, unsigned long index, unsigned int max_items, unsigned long *next_index)
{
unsigned int nr_found = 0;
unsigned int shift, height;
unsigned long i;
height = slot->height;
if (height == 0)
goto out;
/*所有葉子slot的索引鍵值基數(shù)偏移*/
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
/*從底層向樹頂層，
for ( ; height > 1; height--) { /*從葉子向樹頂查找*/
i = (index >> shift) & RADIX_TREE_MAP_MASK;
for (;;) { /*遍歷每一層的各個路徑，由樹頂?shù)疆?dāng)前層一條路徑組成索引鍵值*/
/*如果slot不為空，那么它掛有子結(jié)點，跳出本循環(huán)，進入子結(jié)點層進行本循環(huán)*/
if (slot->slots[i] != NULL)
break;
/*如果slot為空，就跳過slot對應(yīng)的所有索引鍵值*/
/*清除索引號低位.將索引號與該層slot的起始索引號對齊*/
index &= ~((1UL << shift) - 1);
/*跳過一個slot的索引鍵值數(shù)*/
index += 1UL << shift;
if (index == 0)
goto out; /* 32-bit wraparound */
i++; /*找到多個slot*/
if (i == RADIX_TREE_MAP_SIZE)
goto out;
}
shift -= RADIX_TREE_MAP_SHIFT; /*向上移一層，基數(shù)偏移減少*/
slot = rcu_dereference(slot->slots[i]);
if (slot == NULL)
goto out;
}
/* 返回找到的多個slot*/
for (i = index & RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++) {
struct radix_tree_node *node;
index++;
node = slot->slots[i];
if (node) {
results[nr_found++] = rcu_dereference(node);
if (nr_found == max_items)
goto out;
}
}
out:
*next_index = index;
return nr_found;
}
函數(shù)radix_tree_insert找到索引鍵值對應(yīng)的結(jié)點，將item加到該結(jié)點的slot指針上。其列出如下：
int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void *item)
{
struct radix_tree_node *node = NULL, *slot;
unsigned int height, shift;
int offset;
int error;
BUG_ON(radix_tree_is_indirect_ptr(item));
/* 如果樹的高度不夠，就擴展樹。函數(shù)radix_tree_maxindex計算樹高容納的最大索引*/
if (index > radix_tree_maxindex(root->height)) {
error = radix_tree_extend(root, index);
if (error)
return error;
}
slot = radix_tree_indirect_to_ptr(root->rnode);
height = root->height;
shift = (height-1) * RADIX_TREE_MAP_SHIFT; /*計算偏移基數(shù)*/
offset = 0;
while (height > 0) {
if (slot == NULL) { /*如果slot為空，則需要加入孩子結(jié)點*/
/* 分配slot */
if (!(slot = radix_tree_node_alloc(root)))
return -ENOMEM;
slot->height = height;
if (node) {/*添加slot*/
rcu_assign_pointer(node->slots[offset], slot);
node->count++;
} else
rcu_assign_pointer(root->rnode,radix_tree_ptr_to_indirect(slot));
}
/* 進入上一層*/
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
node = slot;
slot = node->slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
}
/*如果index對應(yīng)的slot已有映射頁面，返回-EEXIST*/
if (slot != NULL)
return -EEXIST;
if (node) {
node->count++; /*增加子結(jié)點的計數(shù)*/
rcu_assign_pointer(node->slots[offset], item);
BUG_ON(tag_get(node, 0, offset));
BUG_ON(tag_get(node, 1, offset));
} else { /*為頂層結(jié)點*/
rcu_assign_pointer(root->rnode, item);
BUG_ON(root_tag_get(root, 0));
BUG_ON(root_tag_get(root, 1));
}
return 0;
}
如果當(dāng)前樹高度不足以存放index，就需要擴展樹，擴展方法是在舊樹頂上加新的根結(jié)點，并將原根結(jié)點的tag信息移到新根結(jié)點的第1個slot。函數(shù)radix_tree_extend 列出如下：
static int radix_tree_extend(struct radix_tree_root *root, unsigned long index)
{
struct radix_tree_node *node;
unsigned int height;
int tag;
/* 計算擴展的深度*/
height = root->height + 1;
/*如果index超過樹高所容納的最大索引值，樹高遞增*/
while (index > radix_tree_maxindex(height))
height++;
/*到這里已計算好合適的高度height*/
if (root->rnode == NULL) { /*只有根結(jié)點，設(shè)置好樹高度就可返回*/
root->height = height;
goto out;
}
/*將當(dāng)前樹擴展到高度height*/
do {
unsigned int newheight;
if (!(node = radix_tree_node_alloc(root))) /*分配一個結(jié)點*/
return -ENOMEM;
/* 增加樹高，在樹頂點之上增加一個結(jié)點*/
node->slots[0] = radix_tree_indirect_to_ptr(root->rnode);
/*傳播tag信息到新根結(jié)點*/
/*以前的根結(jié)點現(xiàn)成為新頂結(jié)點的第1個插槽。 如果以前的根結(jié)點打上了tag，就將新增結(jié)點的第1個插槽對應(yīng)的子節(jié)點打上相應(yīng)的tag*/
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
if (root_tag_get(root, tag))
tag_set(node, tag, 0);
}
newheight = root->height+1;
node->height = newheight;
node->count = 1;
node = radix_tree_ptr_to_indirect(node);
rcu_assign_pointer(root->rnode, node);
root->height = newheight;
} while (height > root->height);
out:
return 0;
}
函數(shù)radix_tree_delete刪除index對應(yīng)的條目，并返回刪除條目的地址。其列出如下：
void *radix_tree_delete(struct radix_tree_root *root, unsigned long index)
{
/*數(shù)組path用于保存路徑上的結(jié)點及索引偏移值*/
struct radix_tree_path path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
struct radix_tree_node *slot = NULL;
struct radix_tree_node *to_free;
unsigned int height, shift;
int tag;
int offset;
height = root->height;
if (index > radix_tree_maxindex(height)) /*index不能超過樹的最大索引值*/
goto out;
slot = root->rnode;
if (height == 0) { /*只有根結(jié)點*/
root_tag_clear_all(root);
root->rnode = NULL;
goto out;
}
slot = radix_tree_indirect_to_ptr(slot);
shift = (height - 1) * RADIX_TREE_MAP_SHIFT;
pathp->node = NULL;
/*獲取刪除條目的路徑*/
/*將index從根到葉子的路徑所經(jīng)過的結(jié)點及相應(yīng)索引偏移值存放在數(shù)組pathp中*/
do {
if (slot == NULL)
goto out;
pathp++;
offset = (index >> shift) & RADIX_TREE_MAP_MASK;
pathp->offset = offset;
pathp->node = slot;
slot = slot->slots[offset];
shift -= RADIX_TREE_MAP_SHIFT;
height--;
} while (height > 0);
if (slot == NULL)
goto out;
/*清除與刪除條目相關(guān)的所有標簽*/
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++) {
if (tag_get(pathp->node, tag, pathp->offset))
radix_tree_tag_clear(root, index, tag);
}
to_free = NULL;
/*釋放不再需要的結(jié)點 */
while (pathp->node) { /*刪除
pathp->node->slots[pathp->offset] = NULL; /*清除slot*/
pathp->node->count--; /*孩子數(shù)量減1*/
/*調(diào)用RCU機制的函數(shù)call_rcu在最后一個引用結(jié)束時延遲釋放結(jié)點to_free */
if (to_free)
radix_tree_node_free(to_free);
if (pathp->node->count) { /*還有孩子存在*/
if (pathp->node == radix_tree_indirect_to_ptr(root->rnode)) /*為根結(jié)點的孩子*/
radix_tree_shrink(root); /*樹縮小*/
goto out;
}
/*釋放有0個slot的結(jié)點 */
to_free = pathp->node;
pathp--;
}
/*運行到這里，說明是根結(jié)點*/
root_tag_clear_all(root);
root->height = 0;
root->rnode = NULL;
if (to_free)
radix_tree_node_free(to_free);
out:
return slot;
}
函數(shù)radix_tree_shrink縮小樹的高度到最小。其列出如下：
static inline void radix_tree_shrink(struct radix_tree_root *root)
{
/* 嘗試縮小樹的高度*/
while (root->height > 0) {
struct radix_tree_node *to_free = root->rnode;
void *newptr;
BUG_ON(!radix_tree_is_indirect_ptr(to_free));
to_free = radix_tree_indirect_to_ptr(to_free);
/*候選結(jié)點多于一個孩子或孩子不在最左邊slot，不能縮小樹的高度，跳出循環(huán)*/
if (to_free->count != 1)
break;
if (!to_free->slots[0])
break;
/*不需要調(diào)用rcu_assign_pointer()，因為僅從樹的一部分到另一部分移動結(jié)點。如果釋放舊指針的引用to_free->slots[0]是安全的，那么釋放新指針的引用root->rnode也是安全的*/
newptr = to_free->slots[0];
if (root->height > 1)
newptr = radix_tree_ptr_to_indirect(newptr);
root->rnode = newptr;
root->height--;
/* 僅釋放0結(jié)點*/
tag_clear(to_free, 0, 0);
tag_clear(to_free, 1, 0);
to_free->slots[0] = NULL;
to_free->count = 0;
radix_tree_node_free(to_free);
}
}
