Maple Tree¶

作者:: Liam R. Howlett

概述¶

Maple Tree 是一种 B 树数据类型，它针对存储非重叠范围（包括大小为 1 的范围）进行了优化。该树被设计为易于使用，不需要用户编写的搜索方法。它支持遍历一系列条目，并以缓存高效的方式转到前一个或下一个条目。该树还可以置于 RCU 安全的操作模式，允许并发读写。写入器必须在锁上同步，可以是默认的自旋锁，也可以是用户将锁设置为不同类型的外部锁。

Maple Tree 维护着较小的内存占用，并且被设计为高效地使用现代处理器缓存。大多数用户都能够使用普通的 API。对于更复杂的场景，存在一个高级 API。Maple Tree 最重要的用途是跟踪虚拟内存区域。

Maple Tree 可以存储 0 到 ULONG_MAX 之间的值。Maple Tree 保留了最低两位设置为“10”且低于 4096 的值（即 2、6、10 .. 4094）供内部使用。如果条目可能使用保留条目，则用户可以使用 xa_mk_value() 转换条目，并通过调用 xa_to_value() 将它们转换回来。如果用户需要使用保留值，则用户可以在使用高级 API时转换该值，但会被普通 API 阻止。

Maple Tree 还可以配置为支持搜索给定大小（或更大）的间隙。

使用高级 API也支持预分配节点。这对于必须在给定代码段内保证成功存储操作而无法进行分配的用户很有用。节点的分配相对较小，约为 256 字节。

普通 API¶

首先初始化一个 Maple Tree，对于静态分配的 Maple Tree，使用 DEFINE_MTREE()，对于动态分配的 Maple Tree，使用mt_init()。一个新初始化的 Maple Tree 包含一个 NULL 指针，对应于 0 - ULONG_MAX 的范围。目前支持两种类型的 Maple Tree：分配树和常规树。常规树的内部节点的扇出更高。分配树的扇出较低，但允许用户从 0 向上或从 ULONG_MAX 向下搜索给定大小或更大的间隙。通过在初始化树时传入 MT_FLAGS_ALLOC_RANGE 标志，可以使用分配树。

然后，可以使用mtree_store() 或 mtree_store_range() 设置条目。mtree_store() 将使用新条目覆盖任何条目，并在成功时返回 0，否则返回错误代码。mtree_store_range() 的工作方式相同，但采用一个范围。mtree_load() 用于检索存储在给定索引处的条目。可以使用 mtree_erase() 通过仅知道该范围内的单个值来擦除整个范围，或者可以使用带有 NULL 条目的 mtree_store() 调用来部分擦除一个范围或多个范围。

如果只想在范围当前为 NULL 时才将新条目存储到范围（或索引），可以使用 mtree_insert_range() 或 mtree_insert()，如果范围不为空，则返回 -EEXIST。

可以使用 mt_find() 从索引向上搜索条目。

可以通过调用 mt_for_each() 遍历范围内的每个条目。您必须提供一个临时变量来存储游标。如果要遍历树的每个元素，则可以使用 0 和 ULONG_MAX 作为范围。如果调用者将在遍历期间保持锁，则值得查看高级 API 部分中的 mas_for_each() API。

有时，有必要确保下次调用存储到 Maple Tree 时不分配内存，请参阅高级 API以了解此用例。

可以使用 mtree_dup() 复制整个 Maple Tree。这比将所有元素逐个插入新树中更有效。

最后，可以通过调用 mtree_destroy() 从 Maple Tree 中删除所有条目。如果 Maple Tree 条目是指针，您可能希望先释放这些条目。

分配节点¶

分配由内部树代码处理。有关其他选项，请参阅高级分配节点。

锁定¶

您不必担心锁定。有关其他选项，请参阅高级锁定。

Maple Tree 使用 RCU 和内部自旋锁来同步访问

获取 RCU 读锁

mtree_load()
mt_find()
mt_for_each()
mt_next()
mt_prev()

在内部获取 ma_lock

mtree_store()
mtree_store_range()
mtree_insert()
mtree_insert_range()
mtree_erase()
mtree_dup()
mtree_destroy()
mt_set_in_rcu()
mt_clear_in_rcu()

如果想利用内部锁来保护存储在 Maple Tree 中的数据结构，可以在调用mtree_load()之前调用 mtree_lock()，然后在调用 mtree_unlock() 之前对找到的对象进行引用计数。这将防止在查找对象和递增 refcount 之间，存储操作从树中删除对象。您还可以使用 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() 将在第一次调用时查找 last 处或之下的第一个现有条目，并在每次后续调用时查找上一个条目。

如果用户需要在操作期间放弃锁，则必须使用 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() #define 完成，该宏将外部锁作为参数。

函数和结构¶

枫树标志

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 安全锁
MT_FLAGS_LOCK_BH - 获取 bh 安全锁
MT_FLAGS_LOCK_EXTERN - 不使用 mt_lock

MAPLE_HEIGHT_MAX 可以存储的最大高度

MTREE_INIT¶

MTREE_INIT (name, __flags)

初始化枫树

参数

name: 枫树名称
__flags: 枫树标志

MTREE_INIT_EXT¶

MTREE_INIT_EXT (name, __flags, __lock)

使用外部锁初始化枫树。

参数

name: 树名称
__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)¶: 为不同的索引设置 Maple Tree 操作状态。

参数

struct ma_state *mas: 枫树操作状态。
unsigned long start: 枫树中范围的新起点。
unsigned long last: 枫树中范围的新终点。

描述

将操作状态移动到引用不同的范围。这将导致从顶部开始遍历；请参阅mas_next() 以移动到相邻的索引。

void mas_set(struct ma_state *mas, unsigned long index)¶: 为不同的索引设置 Maple Tree 操作状态。

参数

struct ma_state *mas: 枫树操作状态。
unsigned long index: Maple Tree 的新索引。

描述

将操作状态移动到引用不同的索引。这将导致从顶部开始遍历；请参阅mas_next() 以移动到相邻的索引。

void mt_init_flags(struct maple_tree *mt, unsigned int flags)¶: 使用标志初始化一个空的 Maple Tree。

参数

struct maple_tree *mt: Maple Tree
unsigned int flags: Maple Tree 的标志。

描述

如果您需要使用特殊标志（例如，分配树）初始化 Maple Tree，请使用此函数。

上下文

任何上下文。

void mt_init(struct maple_tree *mt)¶: 初始化一个空的 Maple Tree。

参数

struct maple_tree *mt: Maple Tree

描述

一个空的 Maple Tree。

上下文

任何上下文。

void mt_clear_in_rcu(struct maple_tree *mt)¶: 将树切换到非 RCU 模式。

参数

struct maple_tree *mt: Maple Tree

void mt_set_in_rcu(struct maple_tree *mt)¶: 将树切换到 RCU 安全模式。

参数

struct maple_tree *mt: Maple Tree

mt_for_each¶

mt_for_each (__tree, __entry, __index, __max)

从索引开始迭代每个条目，直到最大值。

参数

__tree: Maple Tree
__entry: 当前条目
__index: 开始搜索的索引。随后用作迭代器。
__max: index 的最大限制

描述

此迭代器跳过所有解析为 NULL 指针的条目，例如使用 XA_ZERO_ENTRY 保留的条目。

int mas_prealloc_calc(struct ma_state *mas, void *entry)¶: 计算给定存储操作所需的节点数

参数

struct ma_state *mas: maple 状态
void *entry: 要存储到树中的条目

返回

预分配所需的节点数。

void mas_wr_preallocate(struct ma_wr_state *wr_mas, void *entry)¶: 为存储操作预分配足够的节点

参数

struct ma_wr_state *wr_mas: maple 写状态
void *entry: 将要存储的条目

void *mas_insert(struct ma_state *mas, void *entry)¶: 插入值的内部调用

参数

struct ma_state *mas: maple 状态
void *entry: 要存储的条目

返回

NULL 或请求的索引处已存在的内容。需要检查 maple 状态是否存在错误情况。

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: maple 状态。
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: maple 状态。

描述

如果存在值，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: maple 编码节点
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)¶: 存储一个 entry。

参数

struct ma_state *mas: maple 状态。
void *entry: 要存储的条目。

描述

使用 mas->index 和 mas->last 设置 entry 的范围。

返回

mas->index 和 mas->last 之间的第一个条目或 NULL。

int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp)¶: 将值存储到树中。

参数

struct ma_state *mas: maple 状态
void *entry: 要存储的条目
gfp_t gfp: 必要时用于分配的 GFP_FLAGS。

返回

成功返回 0，请求无效返回 -EINVAL，内存无法分配返回 -ENOMEM。

void mas_store_prealloc(struct ma_state *mas, void *entry)¶: 使用在 maple 状态中预先分配的内存将值存储到树中。

参数

struct ma_state *mas: maple 状态
void *entry: 要存储的条目。

int mas_preallocate(struct ma_state *mas, void *entry, gfp_t gfp)¶: 为存储操作预分配足够的节点

参数

struct ma_state *mas: maple 状态
void *entry: 将要存储的条目
gfp_t gfp: 用于分配的 GFP_FLAGS。

返回

成功返回 0，内存无法分配返回 -ENOMEM。

void *mas_next(struct ma_state *mas, unsigned long max)¶: 获取下一个条目。

参数

struct ma_state *mas: maple 状态
unsigned long max: 要检查的最大索引。

描述

返回 mas->index 之后的下一个条目。必须持有 rcu_read_lock 或写锁。可以返回零条目。

返回

下一个条目或 NULL

void *mas_next_range(struct ma_state *mas, unsigned long max)¶: 将 maple 状态推进到下一个范围

参数

struct ma_state *mas: maple 状态
unsigned long max: 要检查的最大索引。

描述

将 mas->index 和 mas->last 设置为该范围。必须持有 rcu_read_lock 或写锁。可以返回零条目。

返回

下一个条目或 NULL

void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max)¶: 获取 maple 树中的下一个值

参数

struct maple_tree *mt: maple 树
unsigned long index: 起始索引
unsigned long max: 要检查的最大索引

描述

在内部获取 RCU 读锁以保护搜索，但这并不能保护在释放 RCU 读锁后返回的指针。另请参阅：Maple 树

返回

高于 index 的条目，如果找不到则返回 NULL。

void *mas_prev(struct ma_state *mas, unsigned long min)¶: 获取上一个条目

参数

struct ma_state *mas: maple 状态
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: maple 状态
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)¶: 获取 maple 树中的上一个值

参数

struct maple_tree *mt: maple 树
unsigned long index: 起始索引
unsigned long min: 要检查的最小索引

描述

在内部获取 RCU 读锁以保护搜索，但这并不能保护在释放 RCU 读锁后返回的指针。另请参阅：Maple 树

返回

index 之前的条目，如果找不到则返回 NULL。

void mas_pause(struct ma_state *mas)¶: 暂停 mas_find/mas_for_each 以释放锁。

参数

struct ma_state *mas: 要暂停的 maple 状态

描述

有些用户需要暂停遍历并释放他们持有的锁，以便让步给更高优先级的线程或对条目执行操作。这些用户应该在释放锁之前调用此函数。它会重置 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: maple 状态
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: maple 状态
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: maple 状态
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: maple 状态
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: maple 状态
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: maple 状态
unsigned long min: 要检查的最小值。

描述

必须持有 rcu_read_lock 或写锁。如果存在条目，则会相应地更新 last 和 index。可能会将 mas->status 设置为 ma_underflow。

返回

该条目或 NULL。

void *mas_erase(struct ma_state *mas)¶: 查找 index 所在的范围并擦除整个范围。

参数

struct ma_state *mas: maple 状态

描述

必须持有写锁。搜索 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: maple 状态
gfp_t gfp: 用于分配的 GFP_FLAGS

返回

分配时为 true，否则为 false。

void *mtree_load(struct maple_tree *mt, unsigned long index)¶: 加载存储在枫树中的值

参数

struct maple_tree *mt: maple 树
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: maple 树
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: maple 树
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: maple 树
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: maple 树
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_FLAGS_ALLOC_RANGE 标志初始化 mt。

上下文

任何上下文。获取并释放 mt.lock。如果 gfp 标志允许，则可能会休眠。

返回

如果分配成功且没有回绕则为 0，如果分配在回绕后成功则为 1，如果无法分配内存则为 -ENOMEM，如果无法使用 mt 则为 -EINVAL，或者如果不存在空闲条目则为 -EBUSY。

void *mtree_erase(struct maple_tree *mt, unsigned long index)¶: 查找索引并擦除整个范围。

参数

struct maple_tree *mt: maple 树
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）前序遍历的方式复制一个 maple 树。它使用 memcpy() 复制源树中的节点，并在非叶子节点中分配新的子节点。新节点与源节点完全相同，除了其中存储的所有地址。它比遍历源树中的所有元素并将它们逐个插入到新树中要快。用户需要确保源树和新树的属性相同，并且新树需要是一个空树，否则将返回 -EINVAL。

返回

成功时为 0，如果无法分配内存则为 -ENOMEM，如果两棵树的属性不同或新树不是空树则为 -EINVAL。

void __mt_destroy(struct maple_tree *mt)¶: 遍历并释放一个已锁定的 maple 树的所有节点。

参数

struct maple_tree *mt: maple 树

注意

不处理锁定。

void mtree_destroy(struct maple_tree *mt)¶: 销毁一个 maple 树

参数

struct maple_tree *mt: maple 树

描述

释放树使用的所有资源。处理锁定。

void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max)¶: 从起始位置开始搜索，直到找到一个条目。

参数

struct maple_tree *mt: maple 树
unsigned long *index: 包含搜索起始位置的指针
unsigned long max: 搜索范围的最大值

描述

在内部获取 RCU 读锁以保护搜索，但这并不能保护在释放 RCU 读锁后返回的指针。另请参阅：Maple 树

如果找到一个条目，index 将被更新为指向下一个可能的条目，无论找到的条目是占用单个索引还是一个索引范围。

返回

index 处或之后的条目，或 NULL

void *mt_find_after(struct maple_tree *mt, unsigned long *index, unsigned long max)¶: 从起始位置开始搜索，直到找到一个条目。

参数

struct maple_tree *mt: maple 树
unsigned long *index: 包含搜索起始位置的指针
unsigned long max: 要检查的最大值

描述

与 mt_find() 相同，只是在搜索之前检查 index 是否为 0。如果 index == 0，则中止搜索。这涵盖了迭代器循环中 index 绕回到 0 的情况。

返回

index 处或之后的条目，或 NULL

Linux 内核

目录

本页

Maple Tree¶

概述¶

普通 API¶

分配节点¶

锁定¶

高级 API¶

高级分配节点¶

高级锁定¶

函数和结构¶