資料結構中為了存儲和查找的友善，用各種樹結構來存儲檔案，本章就淺談一下各種樹的表示方法、特點及各自的用途，本章設計的樹結構包括：二叉查找樹（二叉排序樹）、平衡二叉樹（AVL樹）、紅黑樹、B-樹、B+樹、字典樹（trie樹）、字尾樹、廣義字尾樹。
1、二叉查找樹（二叉排序樹）
（圖a）
二叉查找樹是一種動态查找表（圖a），具有這些性質：
（1）若它的左子樹不為空，則左子樹上的所有節點的值都小于它的根節點的值； （2）若它的右子樹不為空，則右子樹上所有節點的值都大于它的根節點的值；
（3）其他的左右子樹也分别為二叉查找樹；
（4）二叉查找樹是動态查找表，在查找的過程中可見添加和删除相應的元素，在這些操作中需要保持二叉查找樹的以上性質。
2、平衡二叉樹（AVL樹）
（圖b）
含有相同節點的二叉查找樹可以有不同的形态，而二叉查找樹的平均查找長度與樹的深度有關，是以需要找出一個查找平均長度最小的一棵，那就是平衡二叉樹（圖b），具有以下性質：
（1）要麼是棵空樹，要麼其根節點左右子樹的深度之差的絕對值不超過1； （2）其左右子樹也都是平衡二叉樹；
（3）二叉樹節點的平衡因子定義為該節點的左子樹的深度減去右子樹的深度。則平衡二叉樹的所有節點的平衡因子隻可能是-1,0,1。
3、紅黑樹
（圖c）
紅黑樹是一種自平衡二叉樹，在平衡二叉樹的基礎上每個節點又增加了一個顔色的屬性，節點的顔色隻能是紅色或黑色。具有以下性質： （1）根節點隻能是黑色；
（2）紅黑樹中所有的葉子節點後面再接上左右兩個空節點，這樣可以保持算法的一緻性，而且所有的空節點都是黑色；
（3）其他的節點要麼是紅色，要麼是黑色，紅色節點的父節點和左右孩子節點都是黑色，及黑紅相間；
（4）在任何一棵子樹中，從根節點向下走到空節點的路徑上所經過的黑節點的數目相同，進而保證了是一個平衡二叉樹。
4、B-樹
（圖d）
B-樹是一種平衡多路查找樹，它在檔案系統中很有用。一棵m階B-樹（圖d為4階B-樹），具有下列性質： （1）樹中每個節點至多有m棵子樹；
（2）若根節點不是葉子節點，則至少有2棵子樹； （3）除根節點之外的所有非終端節點至少有
棵子樹；
（4）每個節點中的資訊結構為（A0,K1,A1,K2......Kn,An），其中n表示關鍵字個數，Ki為關鍵字，Ai為指針；
（5）所有的葉子節點都出現在同一層次上，且不帶任何資訊，也是為了保持算法的一緻性。
5、B+樹
（圖e）
B+數是B-樹的一種變形，它與B-樹的差别在于（圖e為3階B+樹）： （1）有n棵子樹的節點含有n個關鍵字；
（2）所有的葉子節點包含了全部關鍵字的資訊，及指向這些關鍵字記錄的指針，且葉子節點本身按關鍵字大小自小到大順序連結；
（3）所有非終端節點可以看成是索引部分，節點中僅含有其子樹（根節點）中最大（或最小）關鍵字，所有B+樹更像一個索引順序表；
（4）對B+樹進行查找運算，一是從最小關鍵字起進行順序查找，二是從根節點開始，進行随機查找。
6、字典樹（trie樹）
（圖f）
字典樹是一種以樹形結構儲存大量字元串。以便于字元串的統計和查找，經常被搜尋引擎系統用于文本詞頻統計。它的優點是：利用字元串的公共字首來節約存儲空間，最大限度地減少無謂的字元串比較，查詢效率比哈希表高。具有以下特點（圖f）：
（1）根節點為空； （2）除根節點外，每個節點包含一個字元； （3）從根節點到某一節點，路徑上經過的字元連接配接起來，為該節點對應的字元串。
（4）每個字元串在建立字典樹的過程中都要加上一個區分的結束符，避免某個短字元串正好是某個長字元串的字首而淹沒。
7、字尾樹
字尾樹則是一個字元串的所有字尾組成的字典樹。具體内容再前幾章已講過。
8、廣義字尾樹
廣義字尾樹是好幾個字元串的的所有字尾組成的字典樹，同樣每個字元串的所有字尾都具有一個相同的結束符，不同字元串的結束符不同，具體内容見前幾章。
Linux基數樹（radix
tree）是将指針與long整數鍵值相關聯的機制，它存儲有效率，并且可快速查詢，用于指針與整數值的映射（如：IDR機制）、記憶體管理等。
IDR（ID
Radix）機制是将對象的身份鑒别号整數值ID與對象指針建立關聯表，完成從ID與指針之間的互相轉換。IDR機制使用radix樹狀結構作為由id進行索引擷取指針的稀疏數組，通過使用位圖可以快速配置設定新的ID，IDR機制避免了使用固定尺寸的數組存放指針。IDR機制的API函數在lib/idr.c中實作，這裡不加分析。
Linux
radix樹最廣泛的用途是用于記憶體管理，結構address_space通過radix樹跟蹤綁定到位址映射上的核心頁，該radix樹允許記憶體管理代碼快速查找辨別為dirty或writeback的頁。Linux
radix樹的API函數在lib/radix-tree.c中實作。
（1）radix樹概述
radix樹是通用的字典類型資料結構，radix樹又稱為PAT位樹（Patricia Trie or crit bit
tree）。Linux核心使用了資料類型unsigned long的固定長度輸入的版本。每級代表了輸入空間固定位數。
radix
tree是一種多叉搜尋樹，樹的葉子結點是實際的資料條目。每個結點有一個固定的、2^n指針指向子結點（每個指針稱為槽slot），并有一個指針指向父結點。
Linux核心利用radix樹在檔案内偏移快速定位檔案緩存頁，圖4是一個radix樹樣例，該radix樹的分叉為4(22)，樹高為4，樹的每個葉子結點用來快速定位8位檔案内偏移，可以定位4x4x4x4=256頁，如：圖中虛線對應的兩個葉子結點的路徑組成值0x00000010和0x11111010，指向檔案内相應偏移所對應的緩存頁。
圖4
一個四叉radix樹
radix樹每個結點有64個slot，與資料類型long的位數相同，圖1顯示了一個有3級結點的radix樹，每個資料條目（item）可用3個6位的鍵值（key）進行索引，鍵值從左到右分别代表第1~3層結點位置。沒有孩子的結點在圖中不出現。是以，radix樹為稀疏樹提供了有效的存儲，代替固定尺寸數組提供了鍵值到指針的快速查找。
圖1
一個3級結點的radix樹及其鍵值表示
（2）radix樹slot數
Linux核心根使用者配置将樹的slot數定義為4或6，即每個結點有16或64個slot，如圖2所示，當樹高為1時，64個slot對應64個頁，當樹高為2時，對應64*64個頁。
圖2
高為1和2、slot數為64的radix樹
Linux核心radix樹的slot數定義如下（在lib/radix-tree.c中）：
#ifdef
__KERNEL__
/*值為6時，表示每個結點有2^6＝64個slot，值為4時，表示有2^4=16個slot*/
#define
RADIX_TREE_MAP_SHIFT (CONFIG_BASE_SMALL ? 4 : 6)
#else
RADIX_TREE_MAP_SHIFT 3 /* 用于更有強度的測試
*/
#endif
/*表示1個葉子結點可映射的頁數，如：1<<6=64，表示可映射64個slot映射64頁*/
RADIX_TREE_MAP_SIZE (1UL << RADIX_TREE_MAP_SHIFT)
RADIX_TREE_MAP_MASK
(RADIX_TREE_MAP_SIZE-1)
/*定義slot數占用的long類型長度個數，每個slot用位圖1位進行标記，如：64個slot時，值為2*/
RADIX_TREE_TAG_LONGS \
((RADIX_TREE_MAP_SIZE + BITS_PER_LONG - 1) /
BITS_PER_LONG)
（3）結點結構
樹的根結點結構radix_tree_root列出如下（在include/linux/radix-tree.h中）：
RADIX_TREE_MAX_TAGS 2 /*每個slot需要的最大标簽位數*/
/*根結點的标簽存放在gfp_mask中，通過__GFP_BITS_SHIFT移位得到 */
struct radix_tree_root
{
unsigned int height; /* 從葉子向上計算的樹高度
gfp_t gfp_mask;
/*間接指針指向結點而非資料條目，通過設定root->rnode的低位表示是否是間指針*/
struct
radix_tree_node *rnode;
CONFIG_RADIX_TREE_CONCURRENT
struct radix_tree_context
*context;
struct task_struct *owner;
};
結構radix_tree_context列出如下：
struct radix_tree_context
struct radix_tree_root *root;
spinlock_t
*locked;
}
樹的結點結構radix_tree_node列出如下（在lib/radix-tree.c中）：
struct radix_tree_node {
unsigned int height; /*
從葉子向上計算的樹高度 */
unsigned int count;
/*非葉子結點含有一個count域，表示出現在該結點的孩子的數量*/
struct rcu_head rcu_head;
void
*slots[RADIX_TREE_MAP_SIZE]; /*結點的slot指針*/
/*
結點标簽數組=每個slot需要的最大标簽位數*slot數所需的long類型變量數 */
unsigned long
tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
Linux核心radix樹高度是可變的，它依賴于存儲的索引鍵值。radix樹查詢必須知道樹高度，以便知道結點的slot是指向葉子結點的指針還是結點的其他層。Linux在結點結構中有成員height存入樹高度資訊。
radix樹的獨特特征是标簽擴充。圖2顯示了有2個标簽，分别表示打開和關閉。這些标簽是結點結構的成員tags，該标簽用一個位圖實作，在加鎖的情況下設定和清除。每個标簽基本上是一個在radix樹頂層上的位圖序号。标簽與群查詢一起用來在給定的範圍内查找給定标簽集的頁。
标簽在每結點位圖中維護，在每個給定的級别上，可以判定下一個級别是否至少有一個标簽集。
帶有2位圖示簽訓示的8位radix樹
在結點結構radix_tree_node中，tags域是一個二維數組，每個slot用2位辨別，這是一個典型的用空間換時間的應用。tags域用于記錄該結點下面的子結點有沒有相應的标志位。目前RADIX_TREE_MAX_TAGS為2，表示隻記錄兩個标志，其中tags[0]為PAGE_CACHE_DIRTY，tags[1]為PAGE_CACHE_WRITEBACK。如果目前節點的tags[0]值為1，那麼它的子樹節點就存在PAGE_CACHE_DIRTY節點，否則這個子樹分枝就不存在着這樣的節點，就不必再查找這個子樹了。比如在查找PG_dirty的頁面時，就不需要周遊整個樹，而可以跳過那些tags[0]為0值的子樹，這樣就提高了查找效率。
“加标簽查詢”是傳回有指定标簽集radix樹條目的查詢，可以查詢設定了标簽的條目。加标簽查詢可以并行執行，但它們需要通過設定或清除标簽從操作上互斥。
(4) 并行操作的優化
radix樹并行操作包括并行查詢和并行修改，其中，并行修改在标準核心中未完沒有實作，需要通過打更新檔獲得該功能。并行操作說明如下：
RCU并發查詢
通過使用RCU，RCU
Radix樹可以進行完全并發的查詢操作。RCU從根本上要求原子操作地移動指針從資料結構的一個版本到新的版本，保持舊版本直到系統經過靜止狀态。在靜止狀态點，舊版本資料結構已沒有使用者，是以可以被安全釋放。
RCU
radix樹的修改操作之間還需要串行化，但是查詢不再需要與修改操作串行化。
并發修改
RCU可使RCU
radix樹查詢完全并行化，但修改操作成了“瓶頸”。這可通過将全樹的鎖破碎成較小的鎖進行改善，再明顯的方法是對結點進行加鎖而非對整個樹加鎖。
radix樹修改操作可分為單向和雙向操作。單向操作僅執行從根節點和葉子結點的單方向指針移動，它包括插入、更新和設定标簽操作。雙向操作較複雜，它需要在指針移到葉子後又回移，它包括删除和清除标簽操作。
梯級加鎖（Ladder
Locking）和鎖耦合（Lock-Coupling）技術常用于資料庫方面，允許單向周遊結點加鎖的樹（雙向可能産生死鎖）。如果所有的修改者從樹頂到樹底進行修改，并且修改的結點持有鎖，那麼，向下周遊時對孩子加鎖，在孩子被鎖住時再釋放該結點鎖。在這種情況下并發操作是可能的，因為隻要根結點解鎖，另一個操作就可以自上向下進行。如果兩操作的路徑沒有相同操作結點，後一個操作可能在前一個操作完成之前完成。最壞的情況是流水線操作，但這還是比串行化操作好很多。
雙向操作包括删除和清除标簽操作，分别說明如下：
1）清除标簽
在radix樹中清除一個标簽包括向下周遊樹、查找定位條目和清除條目标簽的操作。隻要孩子結點沒有打标簽的條目，就可以向上周遊結點清除标簽。結束條件是：如果周遊遇到一個結點，在清除一個标簽後，它還有一個或多個條目帶有标簽集，就可以結束向上周遊。為了與向下周遊期間有同樣的結束點，将終止條件改為：向上周遊将在有比清除标簽數更多标簽的結點處結束。這樣，不論何時遇到這樣的結點，将作為上周遊樹的結束點。
2）删除元素
删除元素在删除無用結點時還需要删除該條目的所有标簽。它的終止條件需要滿足這兩個方面。向上回退周遊樹時需要滿足下面的條件：當遇到一個非空結點且沒有無用的标簽時應終止向上回退周遊樹。
在向下周遊樹時鑒别此點的條件是：當遇到有超過2個孩子的結點、并且每個标簽來說結點有多于一個标簽條目被清除時，結束向上周遊。該條件用來鑒别向上回退周遊的終止點。
（5）radix樹API說明
聲明和初始化radix樹
聲明和初始化radix樹的方法列出如下：
#include <linux/radix-tree.h>
/*
gfp_mask表示如何執行記憶體配置設定，如果操作（如：插入）以原子性上下文中執行，其值為GFP_ATOMIC*/
RADIX_TREE(name,
gfp_mask); /* 聲明和初始化名為name的樹*/
struct radix_tree_root my_tree;
INIT_RADIX_TREE(my_tree, gfp_mask);
插入條目
插入條目的函數定義列出如下：
int radix_tree_insert(struct radix_tree_root *root, unsigned long index, void
*item)
函數radix_tree_insert插入條目item到樹root中，如果插入條目中記憶體配置設定錯誤，将傳回錯誤-ENOMEM。該函數不能覆寫寫正存在的條目。如果索引鍵值index已存在于樹中，傳回錯誤-EEXIST。插入操作成功是，傳回0。
對于插入條目操作失敗将引起嚴重問題的場合，下面的一對函數可避免插入操作失敗：
int radix_tree_preload(gfp_t gfp_mask);
void
radix_tree_preload_end(void);
函數radix_tree_preload嘗試用給定的gfp_mask配置設定足夠的記憶體，保證下一個插入操作不會失敗。在調用插入操作函數之前調用此函數，配置設定的結構将存放在每CPU變量中。函數radix_tree_preload操作成功後，将完畢核心搶占。是以，在插入操作完成之後，使用者應調用函數radix_tree_preload_end打開核心搶占。
删除條目
删除條目的函數定義列出如下：
void *radix_tree_delete(struct radix_tree_root *root, unsigned long
index)
函數radix_tree_delete删除與索引鍵值index相關的條目，如果删除條目在樹中，傳回該條目的指針，否則傳回NULL。
查詢操作
用于查詢操作的函數定義列出如下：
/*在樹中查找指定鍵值的條目，查找成功，傳回該條目的指針，否則，傳回NULL*/
void *radix_tree_lookup(struct
radix_tree_root *root, unsigned long
index);
/*傳回指向slot的指針，該slot含有指向查找到條目的指針*/
**radix_tree_lookup_slot(struct radix_tree_root *root, unsigned long
/*查詢傳回max_items條目在results中。查詢時鍵值索引從first_index開始*/
radix_tree_gang_lookup(struct
radix_tree_root *root, void **results, unsigned long first_index, unsigned int
max_items);
标簽操作
與标簽操作相關的函數說明列出如下：
/*将鍵值index對應的條目設定标簽tag，傳回值為設定标簽的條目*/
void *radix_tree_tag_set(struct
radix_tree_root *root, unsigned long index, unsigned int
tag);
/*從鍵值index對應的條目清除标簽tag，傳回值為清除标簽的條目*/
*radix_tree_tag_clear(struct radix_tree_root *root, unsigned long index,
unsigned int
/*檢查鍵值index對應的條目是否為标簽tag，如果鍵值不存在，傳回0，如果鍵值存在，但标簽未設定，傳回-1；如果鍵值存在，且标簽已設定，傳回1*/
int
radix_tree_tag_get(struct radix_tree_root *root, unsigned long index, unsigned
int tag);
/*從first_index起查詢樹root中标簽值為tag的條目，在results中傳回*/
radix_tree_gang_lookup_tag(struct radix_tree_root *root, void **results,
unsigned long first_index, unsigned int max_items, unsigned int
/*如果樹root中有任何條目使用tag标簽，傳回鍵值*/
int radix_tree_tagged(struct
radix_tree_root *root, unsigned int tag);
（6）并行操作使用radix樹API的方法
查詢擷取slot操作
查詢操作支援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();
查詢修改slot操作
Linux核心的radix樹需要打更新檔才支援并發修改。查詢僅有一個全局狀态：RCU靜止狀态，并發修改需要跟蹤持有什麼鎖。鎖狀态對于操作來說必須是外部的，是以，我們需要執行個體化一個本地上下文跟蹤這些鎖。查詢修改slot的方法列出如下：
struct page
**slot;
DEFINE_RADIX_TREE_CONTEXT(ctx,&mapping->page_tree);
radix_tree_lock(&ctx);
/*鎖住了根結點*/
/* ctx.tree代替&mapping->page_tree作為根，可以傳遞上下文
radix_tree_lookup_slot(tx.tree, index);
rcu_assign_pointer(*slot,
new_page);
radix_tree_unlock(&ctx);
radix樹API函數radix_tree_lookup_slot含有鎖從樹頂向下移動機制，鎖移動的代碼部分列出如下：
void **radix_tree_lookup_slot(struct radix_tree *root, unsigned long
...
RADIX_TREE_CONTEXT(context, root); /*提供上下文和實際的root指針*、
...
do {
...
/*
從樹頂向下移動鎖*/
radix_ladder_lock(context, node);
} while (height > 0);
（7）radix樹API的實作
樹的操作通常包括查找、插入、删除和樹調整，下面分别說明radix樹這些操作的實作。
查找單個條目
radix樹通過索引鍵值進行查詢，如圖1所示，它按路徑組成索引鍵值，圖中3級結點對應3段6位表示的索引值，圖中key對應的葉子slot的索引鍵值為“2,63,1”。通過葉子slot的指針slot[1]就可得到所存儲的資料item。是以，查詢疊代時，需要将索引鍵值“2,63,1”移去高2層“2,63”，得到葉子slot的指針索引鍵值“1”。
函數radix_tree_lookup執行查找操作，查找方法是：從葉子到樹頂，通過數組索引鍵值值檢視數組元素的方法，一層層地查找slot。其列出如下（在lib/radix-tree.c中）：
void *radix_tree_lookup(struct radix_tree_root *root, unsigned long
unsigned int height,
shift;
struct radix_tree_node *node, **slot;
node = rcu_dereference(root->rnode);
/*擷取根結點*/
if (node ==
NULL)
return NULL;
/*間接指針指向結點而非資料條目，通過設定root->rnode的低位表示是否是間指針。對于間接指針來說，樹高度值root->height大于0，但是RCU查找需要測試間接指針，因為root->height
值不可靠。這種問題僅的RCU下需要考慮*/
if
(!radix_tree_is_indirect_ptr(node)) {
/*非間接指針，說明隻有根結點*/
if (index >
0)
return
NULL;
return
node;
}
/*擷取真正結點指針，因為根結點指針的第0位設定為1表示為間接指針。當使用結點指針時，必須将第0位設定為0，因為位址以字對齊*/
node = radix_tree_indirect_to_ptr(node);
height = node->height;
if (index
> radix_tree_maxindex(height))
/*索引鍵值不能超過最大索引值*/
/*每層索引偏移值為RADIX_TREE_MAP_SHIFT，葉子索引值偏移基數為（樹高-1）*每層索引偏移值*/
shift = (height-1) * RADIX_TREE_MAP_SHIFT;
/*從葉子到樹頂，通過樹路徑組成的索引查找指定索引鍵值的slot*/
slot = (struct radix_tree_node **)(node->slots + ((index>>shift) &
RADIX_TREE_MAP_MASK)); /*如：slots
+1*/
node =
if (node
== NULL)
return NULL;
shift -= RADIX_TREE_MAP_SHIFT;
/*向上移一層，再疊代查找*/
height--;
return node;
查找多個條目
函數radix_tree_gang_lookup執行多個索引鍵值的查找，其列出如下：
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);
(!node)
return 0;
if (!radix_tree_is_indirect_ptr(node)) {
/*如果為非間接指針，表示隻有根節點*/
if
(first_index >
0;
results[0] =
1;
radix_tree_indirect_to_ptr(node); /*清除用于間接指針辨別的第0位*/
max_index = radix_tree_maxindex(node->height);
/*擷取樹的最大索引鍵值*/
ret = 0;
while (ret < max_items)
{ /* max_items為查找的最大條目數*/
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 ==
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 =
unsigned int shift, height;
unsigned long i;
height = slot->height;
if (height
== 0)
goto
out;
/*所有葉子slot的索引鍵值基數偏移*/
shift =
(height-1) * RADIX_TREE_MAP_SHIFT;
/*從底層向樹頂層，
for ( ; height > 1; height--) {
/*從葉子向樹頂查找*/
i = (index >>
shift) & RADIX_TREE_MAP_MASK;
for (;;) {
/*周遊每一層的各個路徑，由樹頂到目前層一條路徑組成索引鍵值*/
/*如果slot不為空，那麼它挂有子結點，跳出本循環，進入子結點層進行本循環*/
if (slot->slots[i] !=
/*如果slot為空，就跳過slot對應的所有索引鍵值*/
/*清除索引号低位.将索引号與該層slot的起始索引号對齊*/
index &= ~((1UL << shift) -
1);
/*跳過一個slot的索引鍵值數*/
index += 1UL <<
if (index ==
goto out; /* 32-bit wraparound
i++;
/*找到多個slot*/
if (i ==
RADIX_TREE_MAP_SIZE)
goto out;
}
shift -= RADIX_TREE_MAP_SHIFT;
/*向上移一層，基數偏移減少*/
slot =
rcu_dereference(slot->slots[i]);
if
(slot == NULL)
/* 傳回找到的多個slot*/
for (i = index
& RADIX_TREE_MAP_MASK; i < RADIX_TREE_MAP_SIZE; i++)
struct radix_tree_node
index++;
node =
slot->slots[i];
if (node)
results[nr_found++] =
rcu_dereference(node);
if (nr_found ==
}
out:
*next_index =
index;
return nr_found;
函數radix_tree_insert找到索引鍵值對應的結點，将item加到該結點的slot指針上。其列出如下：
struct radix_tree_node *node = NULL,
*slot;
unsigned int height, shift;
int offset;
int error;
BUG_ON(radix_tree_is_indirect_ptr(item));
/*
如果樹的高度不夠，就擴充樹。函數radix_tree_maxindex計算樹高容納的最大索引*/
> radix_tree_maxindex(root->height))
error = radix_tree_extend(root,
if
(error)
return error;
slot = radix_tree_indirect_to_ptr(root->rnode);
height = root->height;
(height-1) * RADIX_TREE_MAP_SHIFT; /*計算偏移基數*/
offset = 0;
while (height >
0) {
if (slot == NULL) {
/*如果slot為空，則需要加入孩子結點*/
/* 配置設定slot
if
(!(slot =
radix_tree_node_alloc(root)))
return
-ENOMEM;
slot->height =
height;
(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 >>
node = slot;
slot =
node->slots[offset];
shift -=
RADIX_TREE_MAP_SHIFT;
/*如果index對應的slot已有映射頁面，傳回-EEXIST*/
if (slot !=
return -EEXIST;
if (node) {
/*增加子結點的計數*/
rcu_assign_pointer(node->slots[offset],
item);
BUG_ON(tag_get(node, 0,
offset));
BUG_ON(tag_get(node, 1,
} else {
/*為頂層結點*/
rcu_assign_pointer(root->rnode,
BUG_ON(root_tag_get(root,
0));
1));
return 0;
擴充樹的高度
如果目前樹高度不足以存放index，就需要擴充樹，擴充方法是在舊樹頂上加新的根結點，并将原根結點的tag資訊移到新根結點的第1個slot。函數radix_tree_extend
列出如下：
static int radix_tree_extend(struct radix_tree_root *root, unsigned
long index)
unsigned int height;
int
tag;
/* 計算擴充的深度*/
height =
root->height + 1;
/*如果index超過樹高所容納的最大索引值，樹高遞增*/
while (index >
radix_tree_maxindex(height))
height++;
/*到這裡已計算好合适的高度height*/
(root->rnode == NULL) {
/*隻有根結點，設定好樹高度就可傳回*/
root->height = height;
/*将目前樹擴充到高度height*/
do
unsigned int
newheight;
if (!(node =
/*配置設定一個結點*/
return -ENOMEM;
/*
增加樹高，在樹頂點之上增加一個結點*/
node->slots[0]
= radix_tree_indirect_to_ptr(root->rnode);
/*傳播tag資訊到新根結點*/
/*以前的根結點現成為新頂結點的第1個插槽。
如果以前的根結點打上了tag，就将新增結點的第1個插槽對應的子節點打上相應的tag*/
for (tag = 0; tag < RADIX_TREE_MAX_TAGS; tag++)
(root_tag_get(root,
tag))
tag_set(node, tag, 0);
}
newheight =
root->height+1;
node->height
= newheight;
node->count =
node =
radix_tree_ptr_to_indirect(node);
node);
root->height =
} while (height >
root->height);
out:
函數radix_tree_delete删除index對應的條目，并傳回删除條目的位址。其列出如下：
*radix_tree_delete(struct radix_tree_root *root, unsigned long
/*數組path用于儲存路徑上的結點及索引偏移值*/
struct radix_tree_path
path[RADIX_TREE_MAX_PATH + 1], *pathp = path;
radix_tree_node *slot = NULL;
*to_free;
int tag;
int offset;
/*index不能超過樹的最大索引值*/
goto out;
slot = root->rnode;
if (height ==
0) { /*隻有根結點*/
root_tag_clear_all(root);
root->rnode = NULL;
slot =
radix_tree_indirect_to_ptr(slot);
shift = (height - 1) *
pathp->node =
/*擷取删除條目的路徑*/
/*将index從根到葉子的路徑所經過的結點及相應索引偏移值存放在數組pathp中*/
if (slot ==
goto
pathp++;
offset = (index >>
pathp->offset = offset;
pathp->node = slot;
slot =
slot->slots[offset];
shift -=
if (slot ==
/*清除與删除條目相關的所有标簽*/
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;
/*釋放不再需要的結點
while (pathp->node) {
/*删除
pathp->node->slots[pathp->offset] = NULL;
/*清除slot*/
pathp->node->count--;
/*孩子數量減1*/
/*調用RCU機制的函數call_rcu在最後一個引用結束時延遲釋放結點to_free
(to_free)
radix_tree_node_free(to_free);
if (pathp->node->count) {
/*還有孩子存在*/
if
(pathp->node == radix_tree_indirect_to_ptr(root->rnode))
/*為根結點的孩子*/
radix_tree_shrink(root);
/*樹縮小*/
goto
/*釋放有0個slot的結點
to_free =
pathp->node;
pathp--;
/*運作到這裡，說明是根結點*/
root->height =
root->rnode = NULL;
return slot;
縮小樹的高度
函數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);
/*候選結點多于一個孩子或孩子不在最左邊slot，不能縮小樹的高度，跳出循環*/
if (to_free->count !=
1)
(!to_free->slots[0])
/*不需要調用rcu_assign_pointer()，因為僅從樹的一部分到另一部分移動結點。如果釋放舊指針的引用to_free->slots[0]是安全的，那麼釋放新指針的引用root->rnode也是安全的*/
newptr = to_free->slots[0];
(root->height >
newptr =
radix_tree_ptr_to_indirect(newptr);
root->rnode = newptr;
root->height--;
/*
僅釋放0結點*/
tag_clear(to_free, 0,
0);
tag_clear(to_free, 1,
to_free->slots[0] =
to_free->count =