复杂度

调用 DropArena::box_into_inner() 或 DropBox::into_inner() 是 O(1) 并且具有非常小的常数（除非 T 的大小很大 - 那么 T 的复制占主导地位）。相应的 drop 函数也是 O(1) + 调用 Drop::drop 所需的时间，并且具有小的常数。

分配也非常快。分配有三种可能的路径。首先，区域中有之前分配过的空闲空间。在这种情况下，分配是 O(1) 并且常数很小。其次，区域预分配的容量足够大，可以容纳一个额外的元素。在这种情况下，分配也是 O(1) 并且常数很小。第三，区域真正用完了空间（这是最不常见的情况，即使我们只进行分配而不释放）。在这种情况下，我们必须使用系统分配器来分配更多空间。我们遵循与 typed_arena 相同的指南，进行一次足够容纳更多 T 的分配（实际上，我们使用 typed_arena 实现 DropArena）。

递归拥有数据结构

我们可以使用我们的区域编写一些基本拥有数据结构，如下所示。下面的列表实现受到了 使用完全过多的链表学习 Rust 的启发。

use drop_arena::{DropArena, DropBox};
struct Node<'arena, T> {
    item: T,
    rest: Link<'arena, T>,
}

type Link<'arena, T> = Option<DropBox<'arena, Node<'arena, T>>>;

struct List<'arena, T> {
    arena: &'arena DropArena<'arena, Node<'arena, T>>,
    ptr: Link<'arena, T>,
}

impl<'arena, T> Drop for List<'arena, T> {
    fn drop(&mut self) {
        while let Some(mut nxt) = self.ptr.take() {
            self.ptr = nxt.rest.take();
            self.arena.drop_box(nxt);
        }
    }
}

impl<'d, T> List<'d, T> {
    fn push(&mut self, val: T) {
        self.ptr = Some(self.arena.alloc(Node {
            item: val,
            rest: self.ptr.take(),
        }))
    }

    fn pop(&mut self) -> Option<T> {
        let first = self.ptr.take()?;
        let node = self.arena.box_into_inner(first);
        self.ptr = node.rest;
        Some(node.item)
    }

    fn new(arena: &'d DropArena<'d, Node<'d, T>>) -> Self {
        Self { arena, ptr: None }
    }
}


let arena = DropArena::new();
let mut list = List::new(&arena);

for i in 0..100 {
    list.push(i);
}

for i in (0..100).rev() {
    assert_eq!(list.pop().unwrap(), i);
}

改进领域

这个分配器适用于零大小类型，但在这种情况下效率不高。我计划在将来使用条件类型来解决这个问题。问题是，保持空闲块列表需要指针。然而，在理论上，当我们处理 ZST 时，我们可以选择根本不使用空闲列表。我想要单独使用 CondType 为 ZST 实现一个特殊的区域，但这个包仍然有限。为了使其可在这里使用，我们需要解决 这个问题。

需要进行更多的测试以确保 DropArena 是安全的。我使用 Miri 进行了一些基本的实验，但需要彻底的模糊测试。此代码使用了相当多的 unsafe，这意味着有大量可能出现严重错误的机会。我认为我已经捕捉到了大多数错误，但也不排除我遗漏了某些错误。

确保 DropBox<T> 实现了所有 Box<T> 的特性似乎是可取的。

维护

这是我第一个开源项目，所以我可能没有时间来正确维护它。话虽如此，我会尽我最大的努力，时间允许的话，特别是对于严重的错误。请耐心等待。

许可：MIT