Toolshed

此 crate 包含一个 Arena 分配器，以及一些可以与它一起使用的常用数据结构。

对于那些需要创建递归嵌套的 enum 树并且发现自己总是在 Box 中放置一切的痛苦时刻。

特性

• 分页 Arena：在堆上内部预分配 64KiB 页面，并允许 Copy 类型放置在该堆上。

• CopyCell：与 std::cell::Cell 几乎相同，但要求内部类型实现 Copy，并且它本身也实现了 Copy。

• List、Map 和 Set：您的基本数据结构，在 Arena 上分配，并使用通过 CopyCell 的内部可变性。永远不用担心再次共享指针！

• BloomMap 和 BloomSet：特殊变体的 Map 和 Set，具有非常简单但非常快的 bloom 过滤器。如果一个映射/集合经常查询它不包含的键/元素，则 bloom 过滤器检查将减少执行完整树查找的需要，从而大大提高性能。与常规的 Map 或 Set 相比，开销也极小。

• 所有数据结构都实现了预期的特性，例如 Debug 或 PartialEq。

• 可选的 serde Serialize 支持在特性标志之后。

示例

extern crate toolshed;

use toolshed::Arena;
use toolshed::map::Map;

// Only `Copy` types can be allocated on the `Arena`!
#[derive(Debug, PartialEq, Clone, Copy)]
enum Foo<'arena> {
    Integer(u64),

    // Recursive enum without `Box`es!
    Nested(&'arena Foo<'arena>),
}

fn main() {
    // Create a new arena
    let arena = Arena::new();

    // We allocate first instance of `Foo` in the arena.
    //
    // Please note that the `alloc` method returns a `&mut` reference.
    // Since we want to share our references around, we are going to
    // dereference and re-reference them to immutable ones with `&*`.
    let child: &Foo = &*arena.alloc(Foo::Integer(42));

    // Next instance of `Foo` will contain the child reference.
    let parent: &Foo = &*arena.alloc(Foo::Nested(child));

    // Empty map does not allocate
    let map = Map::new();

    // Inserting stuff in the map requires a reference to the `Arena`.
    // The reference can be shared, since `Arena` uses interior mutability.
    map.insert(&arena, "child", child);

    // We can put our `map` on the arena as well. Once again we use the `&*`
    // operation to change the reference to be immutable, just to demonstrate
    // that our `Map` implementation is perfectly happy with internal mutability.
    let map: &Map<&str, &Foo> = &*arena.alloc(map);

    // Each insert allocates a small chunk of data on the arena. Since arena is
    // preallocated on the heap, these inserts are very, very fast.
    //
    // We only have a non-mutable reference to `map` now, however `Map` is also
    // using interior mutability on references to allow exactly this kind of
    // behavior in a safe manner.
    map.insert(&arena, "parent", parent);

    assert_eq!(map.get("child"), Some(&Foo::Integer(42)));
    assert_eq!(map.get("parent"), Some(&Foo::Nested(&Foo::Integer(42))));
    assert_eq!(map.get("heh"), None);
}

基准测试

这里是对不同集合进行的一个非常偏颇的基准测试

running 8 tests
test bloom_set_create  ... bench:          49 ns/iter (+/- 0)
test bloom_set_read    ... bench:         181 ns/iter (+/- 10)
test fxhash_set_create ... bench:          86 ns/iter (+/- 1)
test fxhash_set_read   ... bench:         312 ns/iter (+/- 4)
test hash_set_create   ... bench:         152 ns/iter (+/- 94)
test hash_set_read     ... bench:       1,105 ns/iter (+/- 1)
test set_create        ... bench:          37 ns/iter (+/- 0)
test set_read          ... bench:         440 ns/iter (+/- 1)

• set 和 bloom_set 是此 crate 中 Set 和 BloomSet 的基准测试。
• hash_set 是默认的 stdlib HashSet。
• fxhash_set 是一个使用 fxhash crate 哈希的 HashSet。

许可证

此软件包根据 MIT 许可证和 Apache 许可证（版本 2.0）的条款进行分发。选择最适合您的那个。

有关详细信息，请参阅 LICENSE-APACHE 和 LICENSE-MIT。