枫树¶
- 作者：
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开始搜索的索引。随后用作迭代器。
__maxindex 的最大限制
描述
此迭代器跳过所有解析为 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 *startpID 指针。
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 *startpID 指针。
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。