示例

考虑以下四个结构体，它们实现了 Variant 以定义四种不同的自引用集合。请注意，这些定义既表达性强又简洁，从而导致了高效的实现。

use orx_selfref_col::*;

#[derive(Clone, Copy)]
struct SinglyListVariant;

impl<'a, T: 'a> Variant<'a, T> for SinglyListVariant {
    type Storage = NodeDataLazyClose<T>; // lazy close
    type MemoryReclaim = MemoryReclaimOnThreshold<2>; // closed nodes will be reclaimed when utilization drops below 75%
    type Prev = NodeRefNone; // previous nodes are not stored
    type Next = NodeRefSingle<'a, Self, T>; // there is only one next node, if any
    type Ends = NodeRefSingle<'a, Self, T>; // there is only one end, namely the front of the list
}

#[derive(Clone, Copy)]
struct DoublyListVariant;

impl<'a, T: 'a> Variant<'a, T> for DoublyListVariant {
    type Storage = NodeDataLazyClose<T>; // lazy close
    type MemoryReclaim = MemoryReclaimOnThreshold<3>; // closed nodes will be reclaimed when utilization drops below 87.5%
    type Prev = NodeRefSingle<'a, Self, T>; // there is only one previous node, if any
    type Next = NodeRefSingle<'a, Self, T>; // there is only one next node, if any
    type Ends = NodeRefsArray<'a, 2, Self, T>; // there are two ends, namely the front and back of the list
}

#[derive(Clone, Copy)]
struct BinaryTreeVariant;

impl<'a, T: 'a> Variant<'a, T> for BinaryTreeVariant {
    type Storage = NodeDataLazyClose<T>; // lazy close
    type MemoryReclaim = MemoryReclaimOnThreshold<1>; // closed nodes will be reclaimed when utilization drops below 50%
    type Prev = NodeRefSingle<'a, Self, T>; // there is only one previous node, namely parent node, if any
    type Next = NodeRefsArray<'a, 2, Self, T>; // there are 0, 1 or 2 next or children nodes
    type Ends = NodeRefSingle<'a, Self, T>; // there is only one end, namely the root of the tree
}

#[derive(Clone, Copy)]
struct DynamicTreeVariant;

impl<'a, T: 'a> Variant<'a, T> for DynamicTreeVariant {
    type Storage = NodeDataLazyClose<T>; // lazy close
    type MemoryReclaim = MemoryReclaimNever; // closed nodes will be left as holes
    type Prev = NodeRefSingle<'a, Self, T>; // there is only one previous node, namely parent node, if any
    type Next = NodeRefsVec<'a, Self, T>; // there might be any number of next nodes, namely children nodes
    type Ends = NodeRefSingle<'a, Self, T>; // there is only one end, namely the root of the tree
}

NodeIndex

NodeIndex 属于高效和安全的交集。

NodeIndex 是一个包含对集合中元素引用的结构体。它提供对元素的常数时间访问。此外，节点索引可以独立于集合存储在别处。

从这种意义上说，NodeIndex 对 SelfRefCol 的引用类似于 usize 对标准 Vec 的引用。

然而，它特别强调安全性和正确性。以下无效的用法在 NodeIndex 和 SelfRefCol 中不可能发生。

不能在错误的 SelfRefCol 上使用 NodeIndex

这个问题可以用 usize 观察，但不能用 NodeIndex 观察。

use orx_selfref_col::*;

let mut col1 = SelfRefCol::<Var, _>::new();
let a = col1.mutate_take('a', |x, a| x.push_get_ref(a).index(&x));

let col2 = SelfRefCol::<Var, _>::new();

assert!(!a.is_valid_for_collection(&col2)); // we cannot dereference 'a' with 'col2'!

在对应的元素被删除后不能使用 NodeIndex

这个问题可以用 usize 观察，但不能用 NodeIndex 观察。

let mut col = SelfRefCol::<Var, _>::new();
let [a, b, c, d, e, f, g] = col
    .mutate_take(['a', 'b', 'c', 'd', 'e', 'f', 'g'], |x, values| {
        values.map(|val| x.push_get_ref(val).index(&x))
    });

let removed_b = col.mutate_take(b, |x, b| b.as_ref(&x).close_node_take_data(&x)); // does not trigger reclaim yet

assert!(!b.is_valid_for_collection(&col)); // we cannot dereference 'b' as it is removed.

在元素重组后不能使用 NodeIndex

这是特定于具有懒节点关闭的 SelfRefCol 的，仅在 MemoryReclaimOnThreshold 策略使用时发生。对于 MemoryReclaimNever 策略，这种情况不会发生。

一旦节点利用率下降到一定的值，集合将重新组织其元素并回收已关闭节点的内存。这使先前创建的所有索引无效，从而防止任何错误的访问。

这类似于在索引指向第3个元素时移除向量的第一个元素。移除后，向量的元素被重新组织，而我们的索引现在指向了一个错误的元素。《NodeIndex》不允许这种访问。

let mut col = SelfRefCol::<Var, _>::new();
let [a, b, c] = col.mutate_take(['a', 'b', 'c'], |x, values| {
    values.map(|val| x.push_get_ref(val).index(&x))
});

let removed_b = col.mutate_take(b, |x, b| b.as_ref(&x).close_node_take_data(&x)); // triggers reclaim, elements reorganized

assert!(!a.is_valid_for_collection(&col)); // all prior indices are invalidated!
assert!(!b.is_valid_for_collection(&col));
assert!(!c.is_valid_for_collection(&col));

使用《SelfRefCol》的Crates

以下Crates使用《SelfRefCol》方便地构建相应的数据结构

• orx-linked-list：实现了单链表和双链表。

许可证

此库采用MIT许可证。有关详细信息，请参阅LICENSE。