楓樹

作者：

Liam R. Howlett

概述

楓樹是一種 B-樹資料型別，經過最佳化，用於儲存非重疊範圍，包括大小為 1 的範圍。該樹設計簡單易用，不需要使用者編寫搜尋方法。它支援以快取高效的方式迭代遍歷一系列條目，並跳轉到上一個或下一個條目。該樹還可以設定為 RCU 安全操作模式，允許併發讀寫。寫入者必須在鎖上進行同步，該鎖可以是預設的自旋鎖，或者使用者可以將鎖設定為不同型別的外部鎖。

楓樹保持較小的記憶體佔用，旨在有效利用現代處理器快取。大多數使用者將能夠使用普通 API。對於更復雜的場景，存在高階 API。楓樹最重要的用途是跟蹤虛擬記憶體區域。

楓樹可以儲存介於0和ULONG_MAX之間的值。楓樹保留底部兩位設定為“10”且小於 4096（即 2、6、10 ... 4094）的值供內部使用。如果條目可能使用保留條目，使用者可以使用xa_mk_value()轉換條目，並透過呼叫xa_to_value()將其轉換回來。如果使用者需要使用保留值，則在使用高階 API時可以轉換該值，但會被普通 API 阻止。

楓樹還可以配置為支援搜尋給定大小（或更大）的間隙。

使用高階 API 也支援預分配節點。這對於那些在無法分配時必須保證在給定程式碼段內成功儲存操作的使用者很有用。節點的分配相對較小，大約 256 位元組。

普通 API

首先初始化一個楓樹，可以使用 DEFINE_MTREE() 用於靜態分配的楓樹，或者使用mt_init() 用於動態分配的楓樹。一個新初始化的楓樹在0到ULONG_MAX的範圍內包含一個NULL指標。目前支援兩種型別的楓樹：分配樹和普通樹。普通樹的內部節點具有更高的分支因子。分配樹的分支因子較低，但允許使用者從0向上或從ULONG_MAX向下搜尋給定大小或更大的間隙。透過在初始化樹時傳入MT_FLAGS_ALLOC_RANGE標誌，可以使用分配樹。

然後可以使用mtree_store()或mtree_store_range()設定條目。mtree_store()將用新條目覆蓋任何現有條目，成功時返回 0，否則返回錯誤程式碼。mtree_store_range()以相同方式工作但接受一個範圍。mtree_load()用於檢索在給定索引處儲存的條目。您可以使用mtree_erase()透過只知道該範圍內的一個值來擦除整個範圍，或者透過呼叫mtree_store()並將條目設定為 NULL 來部分擦除一個範圍或同時擦除多個範圍。

如果您只想在範圍（或索引）當前為NULL時儲存新條目，可以使用mtree_insert_range()或mtree_insert()，如果範圍不為空，它們將返回 -EEXIST。

您可以使用mt_find()從某個索引向上搜索條目。

您可以透過呼叫mt_for_each()遍歷範圍內的每個條目。您必須提供一個臨時變數來儲存遊標。如果要遍歷樹的每個元素，則可以使用0和ULONG_MAX作為範圍。如果呼叫者在遍歷期間將持有鎖，那麼值得檢視高階 API部分中的mas_for_each() API。

有時需要確保下一次對楓樹的儲存呼叫不會分配記憶體，請參閱高階 API以瞭解此用例。

您可以使用mtree_dup()複製整個楓樹。這比將所有元素逐個插入到新樹中更高效。

最後，您可以透過呼叫mtree_destroy()從楓樹中移除所有條目。如果楓樹條目是指標，您可能希望首先釋放這些條目。

分配節點

分配由內部樹程式碼處理。有關其他選項，請參閱高階節點分配。

鎖定

您不必擔心鎖定。有關其他選項，請參閱高階鎖定。

楓樹使用 RCU 和內部自旋鎖來同步訪問

獲取 RCU 讀鎖
內部獲取 ma_lock

如果您想利用內部鎖來保護儲存在楓樹中的資料結構，您可以在呼叫mtree_load()之前呼叫 mtree_lock()，然後在呼叫 mtree_unlock() 之前對找到的物件進行引用計數。這將防止在查詢物件和增加引用計數之間儲存操作從樹中移除該物件。您還可以使用 RCU 來避免解引用已釋放的記憶體，但這超出了本文件的範圍。

高階 API

高階 API 提供了更大的靈活性和更好的效能，但代價是其介面可能更難使用且保護措施較少。在使用高階 API 時，您必須自行處理鎖定。您可以使用 ma_lock、RCU 或外部鎖進行保護。只要鎖定相容，您可以在同一個陣列上混合使用高階和普通操作。普通 API 是基於高階 API 實現的。

高階 API 基於 ma_state，這也是“mas”字首的來源。ma_state 結構體跟蹤樹操作，以便內部和外部樹使用者使用起來更方便。

初始化楓樹與普通 API中相同。請參見上文。

楓樹狀態分別在 mas->index 和 mas->last 中跟蹤範圍的開始和結束。

mas_walk()將遍歷樹到 mas->index 的位置，並根據條目的範圍設定 mas->index 和 mas->last。

您可以使用mas_store()設定條目。mas_store()將用新條目覆蓋任何現有條目，並返回第一個被覆蓋的現有條目。範圍作為楓樹狀態的成員傳入：index 和 last。

您可以使用mas_erase()透過將楓樹狀態的 index 和 last 設定為要擦除的所需範圍來擦除整個範圍。這將擦除在該範圍內找到的第一個範圍，將楓樹狀態的 index 和 last 設定為已擦除的範圍，並返回在該位置存在的條目。

您可以使用mas_for_each()遍歷範圍內的每個條目。如果要遍歷樹的每個元素，則可以使用0和ULONG_MAX作為範圍。如果需要定期釋放鎖，請參閱鎖定部分中的mas_pause()。

使用楓樹狀態允許mas_next()和mas_prev()像樹是連結串列一樣工作。儘管分支因子很高，但攤銷效能損失被快取最佳化所彌補。mas_next()將返回索引處條目之後的下一個條目。mas_prev()將返回索引處條目之前的上一個條目。

在第一次呼叫時，mas_find()將找到在索引處或之上的第一個條目，並在隨後的每次呼叫中找到下一個條目。

在第一次呼叫時，mas_find_rev()將找到在最後位置或之下的第一個條目，並在隨後的每次呼叫中找到上一個條目。

如果使用者在操作期間需要釋放鎖，則必須使用mas_pause()暫停楓樹狀態。

使用分配樹時提供了一些額外的介面。如果您希望在某個範圍內搜尋間隙，可以使用 mas_empty_area() 或 mas_empty_area_rev()。mas_empty_area() 從給定範圍的最低索引開始向上搜尋，直至範圍的最大值。mas_empty_area_rev() 從給定範圍的最高索引開始向下搜尋，直至範圍的下限。

高階節點分配

分配通常在樹內部處理，但是，如果需要在寫入發生之前進行分配，則呼叫 mas_expected_entries() 將分配插入給定數量範圍所需的最壞情況節點數。這也會導致樹進入批次插入模式。一旦插入完成，對楓樹狀態呼叫 mas_destroy() 將釋放未使用的分配。

高階鎖定

楓樹預設使用自旋鎖，但也可以使用外部鎖進行樹更新。要使用外部鎖，樹必須使用MT_FLAGS_LOCK_EXTERN flag進行初始化，這通常透過MTREE_INIT_EXT()宏定義完成，該宏定義將外部鎖作為引數。

函式和結構體

楓樹標誌

  • MT_FLAGS_ALLOC_RANGE - 跟蹤此樹中的間隙

  • MT_FLAGS_USE_RCU - 在 RCU 模式下操作

  • MT_FLAGS_HEIGHT_OFFSET - 標誌中樹高的位置

  • MT_FLAGS_HEIGHT_MASK - 楓樹高度值的掩碼

  • MT_FLAGS_LOCK_MASK - mt_lock 的使用方式

  • MT_FLAGS_LOCK_IRQ - 獲取 irq-safe

  • MT_FLAGS_LOCK_BH - 獲取 bh-safe

  • MT_FLAGS_LOCK_EXTERN - 不使用 mt_lock

MAPLE_HEIGHT_MAX 可儲存的最大高度

MTREE_INIT

MTREE_INIT (name, __flags)

初始化楓樹

引數

名稱

楓樹名稱

__flags

楓樹標誌

MTREE_INIT_EXT

MTREE_INIT_EXT (name, __flags, __lock)

使用外部鎖初始化楓樹。

引數

名稱

樹的名稱

__flags

楓樹標誌

__lock

外部鎖

bool mtree_empty(const struct maple_tree *mt)

判斷樹是否包含任何存在的條目。

引數

const struct maple_tree *mt

楓樹。

上下文

任何上下文。

返回

如果樹只包含 NULL 指標，則返回true。

void mas_reset(struct ma_state *mas)

重置楓樹操作狀態。

引數

struct ma_state *mas

楓樹操作狀態。

描述

重置 mas 的錯誤或遍歷狀態，以便將來對陣列的遍歷將從根開始。如果您已釋放鎖並希望重用 ma_state，請使用此函式。

上下文

任何上下文。

mas_for_each

mas_for_each (__mas, __entry, __max)

迭代遍歷楓樹的一個範圍。

引數

__mas

楓樹操作狀態 (maple_state)

__entry

從樹中檢索的條目

__max

從樹中檢索的最大索引

描述

返回時，mas->index 和 mas->last 將包含該條目的整個範圍。

注意

可能返回零條目。

mas_for_each_rev

mas_for_each_rev (__mas, __entry, __min)

反向迭代遍歷楓樹的一個範圍。

引數

__mas

楓樹操作狀態 (maple_state)

__entry

從樹中檢索的條目

__min

從樹中檢索的最小索引

描述

返回時，mas->index 和 mas->last 將包含該條目的整個範圍。

注意

可能返回零條目。

void __mas_set_range(struct ma_state *mas, unsigned long start, unsigned long last)

將楓樹操作狀態設定為當前位置的子範圍。

引數

struct ma_state *mas

楓樹操作狀態。

unsigned long start

楓樹中範圍的新起始。

unsigned long last

楓樹中範圍的新結束。

描述

將內部楓樹狀態值設定為子範圍。如果您不知道您在樹中的位置，請使用mas_set_range()。

void mas_set_range(struct ma_state *mas, unsigned long start, unsigned long last)

為不同的索引設定楓樹操作狀態。

引數

struct ma_state *mas

楓樹操作狀態。

unsigned long start

楓樹中範圍的新起始。

unsigned long last

楓樹中範圍的新結束。

描述

移動操作狀態以引用不同的範圍。這將產生從頂部開始遍歷的效果；請參閱mas_next()以移動到相鄰索引。

void mas_set(struct ma_state *mas, unsigned long index)

為不同的索引設定楓樹操作狀態。

引數

struct ma_state *mas

楓樹操作狀態。

unsigned long index

楓樹中的新索引。

描述

移動操作狀態以引用不同的索引。這將產生從頂部開始遍歷的效果；請參閱mas_next()以移動到相鄰索引。

void mt_init_flags(struct maple_tree *mt, unsigned int flags)

用標誌初始化一個空楓樹。

引數

struct maple_tree *mt

楓樹

unsigned int flags

楓樹標誌。

描述

如果您需要使用特殊標誌（例如，分配樹）初始化楓樹，請使用此函式。

上下文

任何上下文。

void mt_init(struct maple_tree *mt)

初始化一個空楓樹。

引數

struct maple_tree *mt

楓樹

描述

一個空楓樹。

上下文

任何上下文。

void mt_clear_in_rcu(struct maple_tree *mt)

將樹切換到非 RCU 模式。

引數

struct maple_tree *mt

楓樹

void mt_set_in_rcu(struct maple_tree *mt)

將樹切換到 RCU 安全模式。

引數

struct maple_tree *mt

楓樹

mt_for_each

mt_for_each (__tree, __entry, __index, __max)

從索引開始迭代每個條目，直到最大值。

引數

__tree

楓樹

__entry

當前條目

__index

開始搜尋的索引。隨後用作迭代器。

__max

index 的最大限制

描述

此迭代器跳過所有解析為 NULL 指標的條目，例如已透過 XA_ZERO_ENTRY 保留的條目。

int mas_prealloc_calc(struct ma_wr_state *wr_mas, void *entry)

計算給定儲存操作所需的節點數

引數

struct ma_wr_state *wr_mas

楓樹寫入狀態

void *entry

要儲存到樹中的條目

返回

預分配所需的節點數。

void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *entry)

為儲存操作預分配足夠的節點

引數

struct ma_wr_state *wr_mas

楓樹寫入狀態

void *entry

將要儲存的條目

void *mas_insert(struct ma_state *mas, void *entry)

插入值的內部呼叫

引數

struct ma_state *mas

楓樹狀態

void *entry

要儲存的條目

返回

NULL或如果請求的索引處已存在內容，則為該內容。需要檢查楓樹狀態是否存在錯誤條件。

int mas_alloc_cyclic(struct ma_state *mas, unsigned long *startp, void *entry, unsigned long range_lo, unsigned long range_hi, unsigned long *next, gfp_t gfp)

查詢儲存條目位置的內部呼叫

引數

struct ma_state *mas

楓樹狀態。

unsigned long *startp

ID 指標。

void *entry

要儲存的條目。

unsigned long range_lo

搜尋範圍的下限。

unsigned long range_hi

搜尋範圍的上限。

unsigned long *next

指向下一個要分配的 ID 的指標。

gfp_t gfp

用於分配的 GFP_FLAGS。

返回

如果分配成功且未迴繞則為 0，如果分配成功且迴繞則為 1，如果沒有空閒條目則為 -EBUSY。

void *mas_walk(struct ma_state *mas)

在樹中搜索 mas->index。

引數

struct ma_state *mas

楓樹狀態。

描述

如果存在值，mas->index 和 mas->last 將設定為該範圍。如果 mas->status 為 ma_none，則重置為 ma_start。

返回

該位置的條目或NULL。

void __rcu **mte_dead_walk(struct maple_enode **enode, unsigned char offset)

遍歷一個死樹直到葉子前

引數

struct maple_enode **enode

楓樹編碼節點

unsigned char offset

起始偏移量

注意

這隻能在 RCU 回撥上下文中使用。

void mt_free_walk(struct rcu_head *head)

在 RCU 回撥上下文中遍歷並釋放樹

引數

struct rcu_head *head

節點中的 RCU 頭。

注意

這隻能在 RCU 回撥上下文中使用。

void *mas_store(struct ma_state *mas, void *entry)

儲存一個條目。

引數

struct ma_state *mas

楓樹狀態。

void *entry

要儲存的條目。

描述

mas->index 和 mas->last 用於設定條目的範圍。

返回

mas->index 和 mas->last 之間的第一個條目或NULL。

int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)

將值儲存到樹中。

引數

struct ma_state *mas

楓樹狀態

void *entry

要儲存的條目

gfp_t gfp

必要時用於分配的 GFP_FLAGS。

返回

成功時返回 0，無效請求時返回 -EINVAL，如果無法分配記憶體則返回 -ENOMEM。

void mas_store_prealloc(struct ma_state *mas, void *entry)

使用楓樹狀態中預分配的記憶體將值儲存到樹中。

引數

struct ma_state *mas

楓樹狀態

void *entry

要儲存的條目。

int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)

為儲存操作預分配足夠的節點

引數

struct ma_state *mas

楓樹狀態

void *entry

將要儲存的條目

gfp_t gfp

用於分配的 GFP_FLAGS。

返回

成功時返回 0，如果無法分配記憶體則返回 -ENOMEM。

void *mas_next(struct ma_state *mas, unsigned long max)

獲取下一個條目。

引數

struct ma_state *mas

楓樹狀態

unsigned long max

要檢查的最大索引。

描述

返回mas->index之後的下一個條目。必須持有 rcu_read_lock 或寫鎖。可以返回零條目。

返回

下一個條目或NULL

void *mas_next_range(struct ma_state *mas, unsigned long max)

將楓樹狀態推進到下一個範圍

引數

struct ma_state *mas

楓樹狀態

unsigned long max

要檢查的最大索引。

描述

將mas->index和mas->last設定為該範圍。必須持有 rcu_read_lock 或寫鎖。可以返回零條目。

返回

下一個條目或NULL

void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max)

獲取楓樹中的下一個值

引數

struct maple_tree *mt

楓樹

unsigned long index

起始索引

unsigned long max

要檢查的最大索引

描述

內部獲取 RCU 讀鎖以保護搜尋，這在釋放 RCU 讀鎖後不保護返回的指標。另請參閱：楓樹

返回

高於index的條目，如果未找到則為NULL。

void *mas_prev(struct ma_state *mas, unsigned long min)

獲取上一個條目

引數

struct ma_state *mas

楓樹狀態

unsigned long min

要檢查的最小值。

描述

必須持有 rcu_read_lock 或寫鎖。如果狀態為 ma_none，將重置 mas 為 ma_start。將在不可搜尋的節點處停止。

返回

上一個值或NULL。

void *mas_prev_range(struct ma_state *mas, unsigned long min)

推進到上一個範圍

引數

struct ma_state *mas

楓樹狀態

unsigned long min

要檢查的最小值。

描述

將mas->index和mas->last設定為該範圍。必須持有 rcu_read_lock 或寫鎖。如果節點為 ma_none，將重置 mas 為 ma_start。將在不可搜尋的節點處停止。

返回

上一個值或NULL。

void *mt_prev(struct maple_tree *mt, unsigned long index, unsigned long min)

獲取楓樹中的上一個值

引數

struct maple_tree *mt

楓樹

unsigned long index

起始索引

unsigned long min

要檢查的最小索引

描述

內部獲取 RCU 讀鎖以保護搜尋，這在釋放 RCU 讀鎖後不保護返回的指標。另請參閱：楓樹

返回

index之前的條目，如果未找到則為NULL。

void mas_pause(struct ma_state *mas)

暫停 mas_find/mas_for_each 以釋放鎖。

引數

struct ma_state *mas

要暫停的楓樹狀態

描述

有些使用者需要在遍歷過程中暫停並釋放他們持有的鎖，以便讓步給更高優先順序的執行緒或對條目執行操作。這些使用者應該在釋放鎖之前呼叫此函式。它將mas重置為適合使用者重新獲取鎖後迴圈的下一次迭代。如果在遍歷過程中找到的大多數條目都需要您呼叫mas_pause()，則mt_for_each()迭代器可能更合適。

bool mas_find_setup(struct ma_state *mas, unsigned long max, void **entry)

設定 mas_find*() 的內部函式。

引數

struct ma_state *mas

楓樹狀態

unsigned long max

最大索引

void **entry

指向條目的指標

返回

如果條目是答案則為 True，否則為 False。

void *mas_find(struct ma_state *mas, unsigned long max)

在第一次呼叫時，查詢 mas->index 處或之後的條目，直到max。否則，查詢 mas->index 之後的條目。

引數

struct ma_state *mas

楓樹狀態

unsigned long max

要檢查的最大值。

描述

必須持有 rcu_read_lock 或寫鎖。如果存在條目，則相應更新 last 和 index。可能將mas->status設定為 ma_overflow。

返回

條目或NULL。

void *mas_find_range(struct ma_state *mas, unsigned long max)

在第一次呼叫時，查詢 mas->index 處或之後的條目，直到max。否則，前進到 mas->index 的下一個槽位。

引數

struct ma_state *mas

楓樹狀態

unsigned long max

要檢查的最大值。

描述

必須持有 rcu_read_lock 或寫鎖。如果存在條目，則相應更新 last 和 index。可能將mas->status設定為 ma_overflow。

返回

條目或NULL。

bool mas_find_rev_setup(struct ma_state *mas, unsigned long min, void **entry)

設定 mas_find_*_rev() 的內部函式

引數

struct ma_state *mas

楓樹狀態

unsigned long min

最小索引

void **entry

指向條目的指標

返回

如果條目是答案則為 True，否則為 False。

void *mas_find_rev(struct ma_state *mas, unsigned long min)

在第一次呼叫時，查詢 mas->index 處或之下的第一個非空條目，直到min。否則查詢 mas->index 之下的第一個非空條目，直到min。

引數

struct ma_state *mas

楓樹狀態

unsigned long min

要檢查的最小值。

描述

必須持有 rcu_read_lock 或寫鎖。如果存在條目，則相應更新 last 和 index。可能將mas->status設定為 ma_underflow。

返回

條目或NULL。

void *mas_find_range_rev(struct ma_state *mas, unsigned long min)

在第一次呼叫時，查詢 mas->index 處或之下的第一個非空條目，直到min。否則，前進到 mas->index 之前的上一個槽位，直到min。

引數

struct ma_state *mas

楓樹狀態

unsigned long min

要檢查的最小值。

描述

必須持有 rcu_read_lock 或寫鎖。如果存在條目，則相應更新 last 和 index。可能將mas->status設定為 ma_underflow。

返回

條目或NULL。

void *mas_erase(struct ma_state *mas)

查詢索引所在的範圍並擦除整個範圍。

引數

struct ma_state *mas

楓樹狀態

描述

必須持有寫鎖。搜尋mas->index，將mas->index和mas->last設定為該範圍並擦除該範圍。

返回

被擦除的條目或NULL，mas->index和mas->last已更新。

bool mas_nomem(struct ma_state *mas, gfp_t gfp)

檢查是否存在分配錯誤，並在必要時執行分配。如果存在已分配記憶體，則釋放它們。

引數

struct ma_state *mas

楓樹狀態

gfp_t gfp

用於分配的 GFP_FLAGS

返回

分配時為 true，否則為 false。

void *mtree_load(struct maple_tree *mt, unsigned long index)

從楓樹載入一個儲存的值

引數

struct maple_tree *mt

楓樹

unsigned long index

要載入的索引

返回

條目或NULL

int mtree_store_range(struct maple_tree *mt, unsigned long index, unsigned long last, void *entry, gfp_t gfp)

在給定範圍儲存一個條目。

引數

struct maple_tree *mt

楓樹

unsigned long index

範圍的開始

unsigned long last

範圍的結束

void *entry

要儲存的條目

gfp_t gfp

用於分配的 GFP_FLAGS

返回

成功時返回 0，無效請求時返回 -EINVAL，如果無法分配記憶體則返回 -ENOMEM。

int mtree_store(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp)

在給定索引處儲存一個條目。

引數

struct maple_tree *mt

楓樹

unsigned long index

儲存值的索引

void *entry

要儲存的條目

gfp_t gfp

用於分配的 GFP_FLAGS

返回

成功時返回 0，無效請求時返回 -EINVAL，如果無法分配記憶體則返回 -ENOMEM。

int mtree_insert_range(struct maple_tree *mt, unsigned long first, unsigned long last, void *entry, gfp_t gfp)

如果在給定範圍內沒有值，則插入一個條目。

引數

struct maple_tree *mt

楓樹

unsigned long first

範圍的開始

unsigned long last

範圍的結束

void *entry

要儲存的條目

gfp_t gfp

用於分配的 GFP_FLAGS。

返回

成功時返回 0，如果範圍已被佔用則返回 -EEXISTS，無效請求時返回 -EINVAL，如果無法分配記憶體則返回 -ENOMEM。

int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp)

如果在給定索引處沒有值，則插入一個條目。

引數

struct maple_tree *mt

楓樹

unsigned long index

儲存值的索引

void *entry

要儲存的條目

gfp_t gfp

用於分配的 GFP_FLAGS。

返回

成功時返回 0，如果範圍已被佔用則返回 -EEXISTS，無效請求時返回 -EINVAL，如果無法分配記憶體則返回 -ENOMEM。

int mtree_alloc_cyclic(struct maple_tree *mt, unsigned long *startp, void *entry, unsigned long range_lo, unsigned long range_hi, unsigned long *next, gfp_t gfp)

在樹中找到儲存此條目的位置。

引數

struct maple_tree *mt

楓樹。

unsigned long *startp

ID 指標。

void *entry

要儲存的條目。

unsigned long range_lo

搜尋範圍的下限。

unsigned long range_hi

搜尋範圍的上限。

unsigned long *next

指向下一個要分配的 ID 的指標。

gfp_t gfp

用於分配的 GFP_FLAGS。

描述

在next之後，在mt中找到一個空條目，將新索引儲存到id指標中，在該索引處儲存條目，然後更新next。

mt必須使用 MT_FLAGS_ALLOC_RANGE 標誌進行初始化。

上下文

任何上下文。獲取並釋放 mt.lock。如果 gfp 標誌允許，可能會休眠。

返回

如果分配成功且未迴繞則為 0，如果分配成功且迴繞則為 1，如果無法分配記憶體則為 -ENOMEM，如果無法使用mt則為 -EINVAL，如果沒有空閒條目則為 -EBUSY。

void *mtree_erase(struct maple_tree *mt, unsigned long index)

查詢一個索引並擦除整個範圍。

引數

struct maple_tree *mt

楓樹

unsigned long index

要擦除的索引

描述

擦除與遍歷到條目然後將 NULL 儲存到整個範圍相同。實際上，它是使用高階 API 以這種方式實現的。

返回

儲存在index處的條目或NULL

int __mt_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)

複製整個楓樹

引數

struct maple_tree *mt

源楓樹

struct maple_tree *new

新楓樹

gfp_t gfp

用於分配的 GFP_FLAGS

描述

此函式透過深度優先搜尋（DFS）預序遍歷來複制一個楓樹。它使用 memcpy() 來複制源樹中的節點，並在非葉節點中分配新的子節點。新節點與源節點完全相同，除了其中儲存的所有地址。這比遍歷源樹中的所有元素並將其逐個插入到新樹中要快。使用者需要確保源樹和新樹的屬性相同，並且新樹必須是一個空樹，否則將返回 -EINVAL。請注意，使用者需要手動鎖定源樹和新樹。

返回

成功時返回 0，如果無法分配記憶體則返回 -ENOMEM，如果兩棵樹的屬性不同或新樹不是空樹則返回 -EINVAL。

int mtree_dup(struct maple_tree *mt, struct maple_tree *new, gfp_t gfp)

複製整個楓樹

引數

struct maple_tree *mt

源楓樹

struct maple_tree *new

新楓樹

gfp_t gfp

用於分配的 GFP_FLAGS

描述

此函式透過深度優先搜尋（DFS）預序遍歷來複制一個楓樹。它使用 memcpy() 來複制源樹中的節點，並在非葉節點中分配新的子節點。新節點與源節點完全相同，除了其中儲存的所有地址。這比遍歷源樹中的所有元素並將其逐個插入到新樹中要快。使用者需要確保源樹和新樹的屬性相同，並且新樹必須是一個空樹，否則將返回 -EINVAL。

返回

成功時返回 0，如果無法分配記憶體則返回 -ENOMEM，如果兩棵樹的屬性不同或新樹不是空樹則返回 -EINVAL。

void __mt_destroy(struct maple_tree *mt)

遍歷並釋放一個已鎖定楓樹的所有節點。

引數

struct maple_tree *mt

楓樹

注意

不處理鎖定。

void mtree_destroy(struct maple_tree *mt)

銷燬一個楓樹

引數

struct maple_tree *mt

楓樹

描述

釋放該樹使用的所有資源。處理鎖定。

void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max)

從起始位置開始搜尋，直到找到一個條目。

引數

struct maple_tree *mt

楓樹

unsigned long *index

指標，包含搜尋的起始位置。

unsigned long max

搜尋範圍的最大值

描述

內部獲取 RCU 讀鎖以保護搜尋，這在釋放 RCU 讀鎖後不保護返回的指標。另請參閱：楓樹

如果找到一個條目，index 將更新指向下一個可能的條目，無論找到的條目是佔用單個索引還是一個索引範圍。

返回

位於 index 處或其後的條目，或 NULL。

void *mt_find_after(struct maple_tree *mt, unsigned long *index, unsigned long max)

從起始位置開始搜尋，直到找到一個條目。

引數

struct maple_tree *mt

楓樹

unsigned long *index

指標，包含搜尋的起始位置。

unsigned long max

要檢查的最大值

描述

與 mt_find() 相同，但它在搜尋前會檢查 index 是否為 0。如果 index == 0，則中止搜尋。這涵蓋了迭代器迴圈中 index 繞回 0 的情況。

返回

位於 index 處或其後的條目，或 NULL。