intrusive_splay_tree

一个侵入式、无分配的splay树实现。

Splay树是自我调整的，这意味着对元素的操作（例如，执行find或insert）会以某种方式重新平衡树，使得该元素成为根。这意味着只要在此期间没有对其他元素进行操作，对该元素后续的操作都是O(1)。

实现和目标

• 侵入式：子树指针的空间存储在元素类型内部。在非侵入式中，我们会有一个包含子树指针的节点类型，它包含指向元素或我们将元素移动到节点中的指针。侵入式设计颠倒了这种关系，使得元素在自身内部持有子树指针。

• 无分配和移动：侵入式设计使得这个实现能够完全避免分配和移动内存中的元素。由于子树指针的空间已经存在于元素中，因此不需要分配，只需少量指针写入。因此，这个实现可以在没有访问分配器的受限环境中使用（例如，某些嵌入式设备或信号处理器中），以及那些无法在内存中移动的类型（例如，pthread_mutex_t）。

• 小的代码大小：这个实现旨在小型代码大小，并使用内部特例对象以避免由单态化引起的代码膨胀。这个实现适用于针对WebAssembly，因为代码是通过网络下载的，代码膨胀会延迟网页加载。

• 节点没有父指针：侵入式节点只有两个字大小：左子树和右子树指针。没有父指针，这将需要额外的字开销。为了达到这个目标，实现使用了splay树的"自顶向下"变体。

限制

• 树中的元素必须具有相同的生命周期。这意味着您必须使用类似于bumpalo的crate进行分配，或者使用静态数据等。

• 侵入式集合中的元素本质上是共享的。 它们总是可能被它们所在的集合别名。反过来，特定的侵入式集合只对元素有一个共享引用，因为元素可以同时存在于多个侵入式集合中。因此，您无法从侵入式伸展树中获得对元素的唯一可变引用。为了解决这个问题，您可能需要大量使用内部可变性，例如通过利用 Cell、RefCell 和 Mutex。

示例

此示例定义了一个 Monster 类型，其中其实例存在于两个侵入式树中：一个按名称对怪物进行排序，另一个按健康值排序。

use intrusive_splay_tree::{impl_intrusive_node, SplayTree};

use std::cmp::Ordering;
use std::marker::PhantomData;

// We have a monster type, and we want to query monsters by both name and
// health.
#[derive(Debug)]
struct Monster<'a> {
    name: String,
    health: u64,

    // An intrusive node so we can put monsters in a tree to query by name.
    by_name_node: intrusive_splay_tree::Node<'a>,

    // Another intrusive node so we can put monsters in a second tree (at
    // the same time!) and query them by health.
    by_health_node: intrusive_splay_tree::Node<'a>,
}

// Define a type for trees where monsters are ordered by name.
struct MonstersByName;

// Implement `IntrusiveNode` for the `MonstersByName` tree, where the
// element type is `Monster` and the field in `Monster` that has this tree's
// intrusive node is `by_name`.
impl_intrusive_node! {
    impl<'a> IntrusiveNode<'a> for MonstersByName
    where
        type Elem = Monster<'a>,
        node = by_name_node;
}

// Define how to order `Monster`s within the `MonstersByName` tree by
// implementing `TreeOrd`.
impl<'a> intrusive_splay_tree::TreeOrd<'a, MonstersByName> for Monster<'a> {
    fn tree_cmp(&self, rhs: &Monster<'a>) -> Ordering {
        self.name.cmp(&rhs.name)
    }
}

// And do all the same things for trees where monsters are ordered by health...
struct MonstersByHealth;
impl_intrusive_node! {
    impl<'a> IntrusiveNode<'a> for MonstersByHealth
    where
        type Elem = Monster<'a>,
        node = by_health_node;
}
impl<'a> intrusive_splay_tree::TreeOrd<'a, MonstersByHealth> for Monster<'a> {
    fn tree_cmp(&self, rhs: &Monster<'a>) -> Ordering {
        self.health.cmp(&rhs.health)
    }
}

// We can also implement `TreeOrd` for other types, so that we can query the
// tree by these types. For example, we want to query the `MonstersByHealth`
// tree by some `u64` health value, and we want to query the `MonstersByName`
// tree by some `&str` name value.

impl<'a> intrusive_splay_tree::TreeOrd<'a, MonstersByHealth> for u64 {
    fn tree_cmp(&self, rhs: &Monster<'a>) -> Ordering {
        self.cmp(&rhs.health)
    }
}

impl<'a> intrusive_splay_tree::TreeOrd<'a, MonstersByName> for str {
    fn tree_cmp(&self, rhs: &Monster<'a>) -> Ordering {
        self.cmp(&rhs.name)
    }
}

impl<'a> Monster<'a> {
    /// The `Monster` constructor allocates `Monster`s in a bump arena, and
    /// inserts the new `Monster` in both trees.
    pub fn new(
        arena: &'a bumpalo::Bump,
        name: String,
        health: u64,
        by_name_tree: &mut SplayTree<'a, MonstersByName>,
        by_health_tree: &mut SplayTree<'a, MonstersByHealth>
    ) -> &'a Monster<'a> {
        let monster = arena.alloc(Monster {
            name,
            health,
            by_name_node: Default::default(),
            by_health_node: Default::default(),
        });

        by_name_tree.insert(monster);
        by_health_tree.insert(monster);

        monster
    }
}

fn main() {
    // The arena that the monsters will live within.
    let mut arena = bumpalo::Bump::new();

    // The splay trees ordered by name and health respectively.
    let mut by_name_tree = SplayTree::default();
    let mut by_health_tree = SplayTree::default();

    // Now let's create some monsters, inserting them into the trees!

    Monster::new(
        &arena,
        "Frankenstein's Monster".into(),
        99,
        &mut by_name_tree,
        &mut by_health_tree,
    );

    Monster::new(
        &arena,
        "Godzilla".into(),
        2000,
        &mut by_name_tree,
        &mut by_health_tree,
    );

    Monster::new(
        &arena,
        "Vegeta".into(),
        9001,
        &mut by_name_tree,
        &mut by_health_tree,
    );

    // Query the `MonstersByName` tree by a name.

    let godzilla = by_name_tree.find("Godzilla").unwrap();
    assert_eq!(godzilla.name, "Godzilla");

    assert!(by_name_tree.find("Gill-Man").is_none());

    // Query the `MonstersByHealth` tree by a health.

    let vegeta = by_health_tree.find(&9001).unwrap();
    assert_eq!(vegeta.name, "Vegeta");

    assert!(by_health_tree.find(&0).is_none());
}

许可证：MPL-2.0