typed-generational-arena

一种安全的区域分配器，通过使用代数类型安全索引支持删除操作，从而避免ABA问题。从 generational-arena 分支。

灵感来自 Catherine West在2018年RustConf的闭幕演讲，其中在游戏编程的实体-组件-系统上下文中提出了这些想法。

是什么？为什么？

想象一下，你正在处理一个图，并希望一次添加和删除单个节点，或者你正在编写一个游戏，其世界由许多相互引用的对象组成，这些对象的生存期取决于用户输入。在这些情况下，匹配Rust的拥有权和生存期规则可能变得复杂。

对于结构体，使用共享所有权与内部可变性（即 Rc<RefCell<T>> 或 Arc<Mutex<T>>）或借用引用（即 &'a T 或 &'a mut T）是没有意义的。循环规则排除了引用计数类型，而所需的共享可变性规则排除了借用。

在这些情况下，人们可能会倾向于将对象存储在 Vec<T> 中，并通过它们的索引相互引用。不再需要借用检查或所有权问题！通常，这种解决方案足够好。

然而，现在我们无法删除不再需要的 Vec<T> 中的单个项目，因为我们最终会

• 弄乱被删除元素之后每个元素的索引，或者

• 遭受 ABA 问题。进一步阐述，如果我们试图用 Vec<Option<T>> 替换 Vec<T>，并通过将其设置为 None 来删除一个元素，那么我们就会创建以下有缺陷的序列的可能性

  • obj1 在索引 i 处引用 obj2

  • 有人从索引 i 处删除了 obj2，将该元素设置为 None

  • 第三件事在索引 i 处分配了 obj3，因为该索引处的元素是 None，因此可用于分配

  • obj1 尝试在索引 i 处获取 obj2，但错误地得到了 obj3，而实际上获取应该失败。

通过向集合引入单调递增的生成器计数器，将集合中的每个元素与其插入时的生成器相关联，并通过使用在元素插入时索引和生成器的时间对从集合中获取元素，然后我们可以解决上述 ABA 问题。在索引集合时，如果索引对的生成器与该索引处的元素生成器不匹配，则操作失败。

功能

• 零 unsafe
• 经过良好测试，包括快速检查
• no_std 兼容性
• 所有你期望的特质实现：IntoIterator，FromIterator，Extend 等...

用法

首先，将 typed-generational-arena 添加到你的 Cargo.toml

[dependencies]
typed-generational-arena = "0.2"

然后，导入 crate 并使用 typed_generational_arena::Arena 类型的一个变体！在这些示例中，我们使用 typed_generational_arena::StandardArena，但你可以使用最适合你目的的索引和生成器 ID 的任何组合。

extern crate typed_generational_arena;
use typed_generational_arena::StandardArena;

let mut arena = StandardArena::new();

// Insert some elements into the arena.
let rza = arena.insert("Robert Fitzgerald Diggs");
let gza = arena.insert("Gary Grice");
let bill = arena.insert("Bill Gates");

// Inserted elements can be accessed infallibly via indexing (and missing
// entries will panic).
assert_eq!(arena[rza], "Robert Fitzgerald Diggs");

// Alternatively, the `get` and `get_mut` methods provide fallible lookup.
if let Some(genius) = arena.get(gza) {
    println!("The gza gza genius: {}", genius);
}
if let Some(val) = arena.get_mut(bill) {
    *val = "Bill Gates doesn't belong in this set...";
}

// We can remove elements.
arena.remove(bill);

// Insert a new one.
let murray = arena.insert("Bill Murray");

// The arena does not contain `bill` anymore, but it does contain `murray`, even
// though they are almost certainly at the same index within the arena in
// practice. Ambiguities are resolved with an associated generation tag.
assert!(!arena.contains(bill));
assert!(arena.contains(murray));

// Iterate over everything inside the arena.
for (idx, value) in &arena {
    println!("{:?} is at {:?}", value, idx);
}

no_std

为了启用 no_std 兼容性，禁用默认启用的 "std" 特性。这目前需要 nightly Rust 和 feature(alloc) 以获取对 Vec 的访问。

[dependencies]
typed-generational-arena = { version = "0.2", default-features = false }

[dependencies]
typed-generational-arena = { version = "0.2", features = ["serde"] }