向 List 添加元素会导致底层存储按预期增长。另一方面，从列表中删除元素会在相应位置留下空隙。换句话说，值被取走，但取走值的内存位置不会立即用于新的元素。

当 MemoryReclaimOnThreshold<D> 策略自动回收这些空隙，当利用率低于阈值时。该阈值是常量泛型参数 D 的函数。具体来说，当封闭节点的数量与所有节点的比例超过 2^D 之一时，将回收关闭节点的内存。

• 当 D = 0 时：当利用率低于 0.00% 时（相当于从不）将回收内存。
• 当 D = 1 时：当利用率低于 50.00% 时将回收内存。
• 当 D = 2 时：当利用率低于 75.00% 时将回收内存。
• 当 D = 3 时：当利用率低于 87.50% 时将回收内存。
• ...

底层 PinnedVec 在内存回收操作中不会重新分配。相反，它有效地在已回收的内存内移动元素来填充空隙并修复节点之间的链接。然而，由于元素的位置将会移动，已经获得的 NodeIndex 可能会指向错误的位置。

• 幸运的是，NodeIndex 了解这个操作。因此，不可能错误地使用索引。如果我们获得了一个节点索引，然后列表回收内存，然后我们尝试在这个列表上使用这个节点索引，我们会收到 NodeIndexError::ReorganizedCollection。
• 不幸的是，NodeIndex 现在已经没有用了。我们所能做的就是通过例如 index_of 方法进行线性搜索来重新获得索引。

use orx_linked_list::*;

fn float_eq(x: f32, y: f32) -> bool {
    (x - y).abs() < f32::EPSILON
}

// MemoryReclaimOnThreshold<2> -> memory will be reclaimed when utilization is below 75%
let mut list = List::<Doubly, _>::new();
let a = list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');
list.push_back('e');

assert!(float_eq(list.node_utilization(), 1.00)); // utilization = 5/5 = 100%

// no reorganization; 'a' is still valid
assert_eq!(list.get_or_error(a), Ok(&'a'));
assert_eq!(list.get(a), Some(&'a'));

_ = list.pop_back(); // leaves a hole

assert!(float_eq(list.node_utilization(), 0.80)); // utilization = 4/5 = 80%

// no reorganization; 'a' is still valid
assert_eq!(list.get_or_error(a), Ok(&'a'));
assert_eq!(list.get(a), Some(&'a'));

_ = list.pop_back(); // leaves the second hole; we have utilization = 3/5 = 60%
                      // this is below the threshold 75%, and triggers reclaim
                      // we claim the two unused nodes / holes

assert!(float_eq(list.node_utilization(), 1.00)); // utilization = 3/3 = 100%

// nodes reorganized; 'a' is no more valid
assert_eq!(
    list.get_or_error(a),
    Err(NodeIndexError::ReorganizedCollection)
);
assert_eq!(list.get(a), None);

// re-obtain the index
let a = list.index_of(&'a').unwrap();
assert_eq!(list.get_or_error(a), Ok(&'a'));
assert_eq!(list.get(a), Some(&'a'));

替代策略：MemoryReclaimNever

然而，通过简单地消除情况c，我们可以确保节点索引始终有效，除非我们手动使其无效。将内存回收策略设置为MemoryReclaimNever可以确保不会有自动或隐式的内存重组。

• 使用List<Singly<MemoryReclaimNever>, T>代替List<Singly, T>，或者
• 使用List<Doubly<MemoryReclaimNever>, T>代替List<Doubly, T>。

这种方法的缺点是，如果有大量的弹出或删除操作，内存利用率可能会很低。然而，List通过以下两种方法为调用者提供了管理内存的能力：

• List::node_utilization(&self) -> f32方法可以用来查看活动/使用的节点数与使用节点数的比例。调用者可以通过以下方式决定何时采取行动。
• List::reclaim_closed_nodes(&mut self)方法可以用来手动运行内存回收操作，这将使node_utilization达到100%，同时使已创建的节点索引无效。

use orx_linked_list::*;

fn float_eq(x: f32, y: f32) -> bool {
    (x - y).abs() < f32::EPSILON
}

// MemoryReclaimNever -> memory will never be reclaimed automatically
let mut list = List::<Doubly<MemoryReclaimNever>, _>::new();
let a = list.push_back('a');
list.push_back('b');
list.push_back('c');
list.push_back('d');
list.push_back('e');

assert!(float_eq(list.node_utilization(), 1.00)); // utilization = 5/5 = 100%

// no reorganization; 'a' is still valid
assert_eq!(list.get_or_error(a), Ok(&'a'));
assert_eq!(list.get(a), Some(&'a'));

_ = list.pop_back(); // leaves a hole
_ = list.pop_back(); // leaves the second hole
_ = list.pop_back(); // leaves the third hole

assert!(float_eq(list.node_utilization(), 0.40)); // utilization = 2/5 = 40%

// still no reorganization; 'a' is and will always be valid unless we manually reclaim
assert_eq!(list.get_or_error(a), Ok(&'a'));
assert_eq!(list.get(a), Some(&'a'));

list.reclaim_closed_nodes();

// we can manually reclaim memory any time we want to maximize utilization
assert!(float_eq(list.node_utilization(), 1.00)); // utilization = 2/2 = 100%

// we are still protected by list & index validation
// nodes reorganized; 'a' is no more valid, we cannot wrongly use the index
assert_eq!(
    list.get_or_error(a),
    Err(NodeIndexError::ReorganizedCollection)
);
assert_eq!(list.get(a), None);

// re-obtain the index
let a = list.index_of(&'a').unwrap();
assert_eq!(list.get_or_error(a), Ok(&'a'));
assert_eq!(list.get(a), Some(&'a'));

内部特性

orx_linked_list::List利用了SelfRefCol的安全保证和效率特性。

• SelfRefCol将其安全保证建立在所有引用都将是同一集合的元素这一事实上。通过防止引入外部引用或泄漏引用，可以使用**常规的&引用**来安全地构建自引用集合。
• 经过仔细封装，SelfRefCol防止将外部引用传递到列表中，以及将列表节点引用泄漏到外部。一旦建立这一点，它就提供了方便地修改列表节点引用的方法。这些特性使得在这个crate中实现链表非常方便，几乎不需要使用unsafe关键字，没有通过指针的读写，也没有通过索引访问。与std::collections::LinkedList实现相比，可以观察到orx_linked_list::List是一个**更高级的实现**。
• 此外，orx_linked_list::List比标准链表**快得多**。其中一个主要原因是SelfRefCol将所有元素都保存在彼此附近，而不是在内存中的任意位置，这导致了更好的缓存局部性。

基准测试

变异结束

您可以在以下链接中查看基准测试：benches/mutation_ends.rs。

这个基准测试比较了调用 push_front、push_back、pop_front 和 pop_back 方法的性能。

迭代

您可以在以下链接中查看基准测试：benches/iter.rs。

这个基准测试比较了通过 iter 方法迭代的性能。

贡献

欢迎贡献！如果您发现错误、有问题或认为可以改进，请打开一个 issue 或创建一个 PR。

许可证

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