Linux中國

Linux 內核里的數據結構——基數樹

正如你所知道的,Linux內核提供了許多不同的庫和函數,它們實現了不同的數據結構和演算法。在這部分,我們將研究其中一種數據結構—— 基數樹 Radix tree 。在 Linux 內核中,有兩個文件與基數樹的實現和API相關:

讓我們先說說什麼是 基數樹 吧。基數樹是一種 壓縮的字典樹 compressed trie ,而字典樹是實現了關聯數組介面並允許以 鍵值對 方式存儲值的一種數據結構。這裡的鍵通常是字元串,但可以使用任意數據類型。字典樹因為它的節點而與 n叉樹 不同。字典樹的節點不存儲鍵,而是存儲單個字元的標籤。與一個給定節點關聯的鍵可以通過從根遍歷到該節點獲得。舉個例子:

               +-----------+
               |           |
               |    " "    |
               |           |
        +------+-----------+------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    g      |            |     c     |
   |           |            |           |
   +-----------+            +-----------+
        |                         |
        |                         |
   +----v------+            +-----v-----+
   |           |            |           |
   |    o      |            |     a     |
   |           |            |           |
   +-----------+            +-----------+
                                  |
                                  |
                            +-----v-----+
                            |           |
                            |     t     |
                            |           |
                            +-----------+

因此在這個例子中,我們可以看到一個有著兩個鍵 gocat字典樹 。壓縮的字典樹也叫做 基數樹 ,它和 字典樹 的不同之處在於,所有隻有一個子節點的中間節點都被刪除。

Linux 內核中的基數樹是把值映射到整形鍵的一種數據結構。include/linux/radix-tree.h文件中的以下結構體描述了基數樹:

struct radix_tree_root {
         unsigned int            height;
         gfp_t                   gfp_mask;
         struct radix_tree_node  __rcu *rnode;
};

這個結構體描述了一個基數樹的根,它包含了3個域成員:

  • height - 樹的高度;
  • gfp_mask - 告知如何執行動態內存分配;
  • rnode - 孩子節點指針.

我們第一個要討論的欄位是 gfp_mask

底層內核的內存動態分配函數以一組標誌作為 gfp_mask ,用於描述如何執行動態內存分配。這些控制分配進程的 GFP_ 標誌擁有以下值:( GF_NOIO 標誌)意味著睡眠以及等待內存,( __GFP_HIGHMEM 標誌)意味著高端內存能夠被使用,( GFP_ATOMIC 標誌)意味著分配進程擁有高優先順序並不能睡眠等等。

  • GFP_NOIO - 睡眠等待內存
  • __GFP_HIGHMEM - 高端內存能夠被使用;
  • GFP_ATOMIC - 分配進程擁有高優先順序並且不能睡眠;

等等。

下一個欄位是rnode

struct radix_tree_node {
        unsigned int    path;
        unsigned int    count;
        union {
                struct {
                        struct radix_tree_node *parent;
                        void *private_data;
                };
                struct rcu_head rcu_head;
        };
        /* For tree user */
        struct list_head private_list;
        void __rcu      *slots[RADIX_TREE_MAP_SIZE];
        unsigned long   tags[RADIX_TREE_MAX_TAGS][RADIX_TREE_TAG_LONGS];
};

這個結構體包含的信息有父節點中的偏移以及到底端(葉節點)的高度、子節點的個數以及用於訪問和釋放節點的欄位成員。這些欄位成員描述如下:

  • path - 父節點中的偏移和到底端(葉節點)的高度
  • count - 子節點的個數;
  • parent - 父節點指針;
  • private_data - 由樹的用戶使用;
  • rcu_head - 用於釋放節點;
  • private_list - 由樹的用戶使用;

radix_tree_node 的最後兩個成員—— tagsslots 非常重要且令人關注。Linux 內核基數樹的每個節點都包含了一組 指針槽 slots ,槽里存儲著指向數據的指針。在Linux內核基數樹的實現中,空槽存儲的是 NULL 。Linux內核中的基數樹也支持 標籤 tags ,它與 radix_tree_node 結構體的 tags 欄位相關聯。有了標籤,我們就可以對基數樹中存儲的記錄以單個 比特位 bit 進行設置。

既然我們了解了基數樹的結構,那麼該是時候看一下它的API了。

Linux內核基數樹API

我們從結構體的初始化開始。有兩種方法初始化一個新的基數樹。第一種是使用 RADIX_TREE 宏:

RADIX_TREE(name, gfp_mask);

正如你所看到的,我們傳遞了 name 參數,所以通過 RADIX_TREE 宏,我們能夠定義和初始化基數樹為給定的名字。RADIX_TREE 的實現很簡單:

#define RADIX_TREE(name, mask) 
         struct radix_tree_root name = RADIX_TREE_INIT(mask)

#define RADIX_TREE_INIT(mask)   { 
        .height = 0,              
        .gfp_mask = (mask),       
        .rnode = NULL,            
}

RADIX_TREE 宏的開始,我們使用給定的名字定義 radix_tree_root 結構體實例,並使用給定的 mask 調用 RADIX_TREE_INIT 宏。 而 RADIX_TREE_INIT 宏則是使用默認值和給定的mask對 radix_tree_root 結構體進行了初始化。

第二種方法是手動定義radix_tree_root結構體,並且將它和mask傳給 INIT_RADIX_TREE 宏:

struct radix_tree_root my_radix_tree;
INIT_RADIX_TREE(my_tree, gfp_mask_for_my_radix_tree);

INIT_RADIX_TREE 宏的定義如下:

#define INIT_RADIX_TREE(root, mask)  
do {                                 
        (root)->height = 0;          
        (root)->gfp_mask = (mask);   
        (root)->rnode = NULL;        
} while (0)

RADIX_TREE_INIT宏所做的初始化工作一樣,INIT_RADIX_TREE 宏使用默認值和給定的 mask 完成初始化工作。

接下來是用於向基數樹插入和刪除數據的兩個函數:

  • radix_tree_insert;
  • radix_tree_delete;

第一個函數 radix_tree_insert 需要3個參數:

  • 基數樹的根;
  • 索引鍵;
  • 插入的數據;

radix_tree_delete 函數需要和 radix_tree_insert 一樣的一組參數,但是不需要傳入要刪除的數據。

基數樹的搜索以兩種方法實現:

  • radix_tree_lookup;
  • radix_tree_gang_lookup;
  • radix_tree_lookup_slot.

第一個函數radix_tree_lookup需要兩個參數:

  • 基數樹的根;
  • 索引鍵;

這個函數嘗試在樹中查找給定的鍵,並返回和該鍵相關聯的記錄。第二個函數 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);

它返回的是記錄的個數。 results 中的結果,按鍵排序,並從第一個索引開始。返回的記錄個數將不會超過 max_items 的值。

最後一個函數radix_tree_lookup_slot將會返回包含數據的指針槽。

鏈接

via: https://github.com/0xAX/linux-insides/blob/master/DataStructures/radix-tree.md

作者:[0xAX] 譯者:cposture 校對:Mr小眼兒

本文由 LCTT 原創翻譯,Linux中國 榮譽推出


本文轉載來自 Linux 中國: https://github.com/Linux-CN/archive

對這篇文章感覺如何?

太棒了
0
不錯
0
愛死了
0
不太好
0
感覺很糟
0
雨落清風。心向陽

    You may also like

    Leave a reply

    您的電子郵箱地址不會被公開。 必填項已用 * 標註

    此站點使用Akismet來減少垃圾評論。了解我們如何處理您的評論數據

    More in:Linux中國