<a href="https://github.com/torvalds/linux/blob/master/include/linux/radix-tree.h">include/linux/radix-tree.h</a>
<a href="https://github.com/torvalds/linux/blob/master/lib/radix-tree.c">lib/radix-tree.c</a>
<code>+-----------+</code>
<code>| |</code>
<code>| " " |</code>
<code>+------+-----------+------+</code>
<code>| |</code>
<code>+----v------+ +-----v-----+</code>
<code>| | | |</code>
<code>| g | | c |</code>
<code>+-----------+ +-----------+</code>
<code>| o | | a |</code>
<code>|</code>
<code>+-----v-----+</code>
<code>| t |</code>
是以在這個例子中，我們可以看到一個有着兩個鍵 <code>go</code> 和 <code>cat</code> 的 <code>字典樹</code> 。壓縮的字典樹也叫做 <code>基數樹</code>，它和 <code>字典樹</code> 的不同之處在于，所有隻有一個子節點的中間節點都被删除。
<code>struct radix_tree_root {</code>
<code>unsigned int height;</code>
<code>gfp_t gfp_mask;</code>
<code>struct radix_tree_node __rcu *rnode;</code>
<code>};</code>
這個結構體描述了一個基數樹的根，它包含了3個域成員：
<code>height</code> - 樹的高度;
<code>gfp_mask</code> - 告知如何執行動态記憶體配置設定;
<code>rnode</code> - 孩子節點指針.
我們第一個要讨論的字段是 <code>gfp_mask</code> ：
底層核心的記憶體動态配置設定函數以一組标志作為 <code>gfp_mask</code> ，用于描述如何執行動态記憶體配置設定。這些控制配置設定程序的 <code>gfp_</code> 标志擁有以下值：( <code>gf_noio</code> 标志)意味着睡眠以及等待記憶體，( <code>__gfp_highmem</code> 标志)意味着高端記憶體能夠被使用，( <code>gfp_atomic</code> 标志)意味着配置設定程序擁有高優先級并不能睡眠等等。
<code>gfp_noio</code> - 睡眠等待記憶體
<code>__gfp_highmem</code> - 高端記憶體能夠被使用;
<code>gfp_atomic</code> - 配置設定程序擁有高優先級并且不能睡眠;
等等。
下一個字段是<code>rnode</code>：
<code>struct radix_tree_node {</code>
<code>unsigned int path;</code>
<code>unsigned int count;</code>
<code>union {</code>
<code>struct {</code>
<code>struct radix_tree_node *parent;</code>
<code>void *private_data;</code>
<code>struct rcu_head rcu_head;</code>
<code>/* for tree user */</code>
<code>struct list_head private_list;</code>
<code>void __rcu *slots[radix_tree_map_size];</code>
<code>unsigned long tags[radix_tree_max_tags][radix_tree_tag_longs];</code>
這個結構體包含的資訊有父節點中的偏移以及到底端(葉節點)的高度、子節點的個數以及用于通路和釋放節點的字段成員。這些字段成員描述如下：
<code>path</code> - 父節點中的偏移和到底端(葉節點)的高度
<code>count</code> - 子節點的個數;
<code>parent</code> - 父節點指針;
<code>private_data</code> - 由樹的使用者使用;
<code>rcu_head</code> - 用于釋放節點;
<code>private_list</code> - 由樹的使用者使用;
<code>radix_tree_node</code> 的最後兩個成員—— <code>tags</code> 和 <code>slots</code> 非常重要且令人關注。linux 核心基數樹的每個節點都包含了一組指針槽slots，槽裡存儲着指向資料的指針。在linux核心基數樹的實作中，空槽存儲的是 <code>null</code> 。linux核心中的基數樹也支援标簽tags，它與 <code>radix_tree_node</code> 結構體的 <code>tags</code> 字段相關聯。有了标簽，我們就可以對基數樹中存儲的記錄以單個比特位bit進行設定。
既然我們了解了基數樹的結構，那麼該是時候看一下它的api了。
<a></a>
我們從結構體的初始化開始。有兩種方法初始化一個新的基數樹。第一種是使用 <code>radix_tree</code> 宏：
<code>radix_tree(name, gfp_mask);</code>
正如你所看到的，我們傳遞了 <code>name</code> 參數，是以通過 <code>radix_tree</code> 宏，我們能夠定義和初始化基數樹為給定的名字。<code>radix_tree</code> 的實作很簡單：
<code>#define radix_tree(name, mask) \</code>
<code>struct radix_tree_root name = radix_tree_init(mask)</code>
<code></code>
<code>#define radix_tree_init(mask) { \</code>
<code>.height = 0, \</code>
<code>.gfp_mask = (mask), \</code>
<code>.rnode = null, \</code>
<code>}</code>
在 <code>radix_tree</code> 宏的開始，我們使用給定的名字定義 <code>radix_tree_root</code> 結構體執行個體，并使用給定的 mask 調用 <code>radix_tree_init</code> 宏。 而 <code>radix_tree_init</code> 宏則是使用預設值和給定的mask對 <code>radix_tree_root</code> 結構體進行了初始化。
第二種方法是手動定義<code>radix_tree_root</code>結構體，并且将它和mask傳給 <code>init_radix_tree</code> 宏：
<code>struct radix_tree_root my_radix_tree;</code>
<code>init_radix_tree(my_tree, gfp_mask_for_my_radix_tree);</code>
<code>init_radix_tree</code> 宏的定義如下:
<code>#define init_radix_tree(root, mask) \</code>
<code>do { \</code>
<code>(root)->height = 0; \</code>
<code>(root)->gfp_mask = (mask); \</code>
<code>(root)->rnode = null; \</code>
<code>} while (0)</code>
和<code>radix_tree_init</code>宏所做的初始化工作一樣，<code>init_radix_tree</code> 宏使用預設值和給定的 mask 完成初始化工作。
接下來是用于向基數樹插入和删除資料的兩個函數：
<code>radix_tree_insert</code>;
<code>radix_tree_delete</code>;
第一個函數 <code>radix_tree_insert</code> 需要3個參數：
基數樹的根;
索引鍵;
插入的資料;
<code>radix_tree_delete</code> 函數需要和 <code>radix_tree_insert</code> 一樣的一組參數，但是不需要傳入要删除的資料。
基數樹的搜尋以兩種方法實作：
<code>radix_tree_lookup</code>;
<code>radix_tree_gang_lookup</code>;
<code>radix_tree_lookup_slot</code>.
第一個函數<code>radix_tree_lookup</code>需要兩個參數：
這個函數嘗試在樹中查找給定的鍵，并傳回和該鍵相關聯的記錄。第二個函數 <code>radix_tree_gang_lookup</code> 有以下的函數簽名：
<code>unsigned int radix_tree_gang_lookup(struct radix_tree_root *root,</code>
<code>void **results,</code>
<code>unsigned long first_index,</code>
<code>unsigned int max_items);</code>
它傳回的是記錄的個數。 <code>results</code> 中的結果，按鍵排序，并從第一個索引開始。傳回的記錄個數将不會超過<code>max_items</code> 的值。
最後一個函數<code>radix_tree_lookup_slot</code>将會傳回包含資料的指針槽。
<a href="http://en.wikipedia.org/wiki/radix_tree">radix tree</a>
<a href="http://en.wikipedia.org/wiki/trie">trie</a>
本文來自雲栖社群合作夥伴“linux中國”
原文釋出時間為：2013-04-02.
![linux-svn解除安裝與安裝[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)