btree_plus_store/copyable/
store.rs

1use std::collections::HashSet;
2
3use crate::node::NodePtr;
4use crate::BTreeStore;
5
6/// Extension to tracing garbage-collect nodes in a store
7pub trait BTreeStoreExt<K, V> {
8    /// Remove all allocated nodes which are not reachable through `b_trees` iterator.
9    ///
10    /// # Safety
11    /// `b_trees` *must* return b-trees containing all reachable nodes in the store, AKA there must
12    /// not exist a b-tree with this store which is not in `b_trees`. Any nodes not reachable through
13    /// `b_trees` will be dropped.
14    unsafe fn tracing_gc<'a>(&self, btrees: impl IntoIterator<Item = impl BTree<'a, K, V>>)
15    where
16        K: 'a,
17        V: 'a;
18
19    // TODO: Async or background version which does [tri-color marking](https://en.wikipedia.org/wiki/Tracing_garbage_collection#Tri-color_marking)
20}
21
22/// Generic trait for different b-tree maps and sets, which returns reachable nodes.
23///
24/// This trait is [sealed](https://rust-lang.github.io/api-guidelines/future-proofing.html#sealed-traits-protect-against-downstream-implementations-c-sealed)
25pub trait BTree<'store, K, V>: crate::copyable::sealed::BTree<'store, K, V> {}
26
27impl<K, V> BTreeStoreExt<K, V> for BTreeStore<K, V> {
28    #[inline]
29    unsafe fn tracing_gc<'a>(&self, b_trees: impl IntoIterator<Item = impl BTree<'a, K, V>>)
30    where
31        K: 'a,
32        V: 'a,
33    {
34        let nodes = b_trees
35            .into_iter()
36            .flat_map(|b_tree| {
37                b_tree.assert_store(self);
38                b_tree.nodes()
39            })
40            .collect::<HashSet<_>>();
41        self.retain_shared(|node| nodes.contains(&NodePtr::from_ref(node)));
42    }
43}
btree_plus_store/copyable/store.rs

btree_plus_store/copyable/
store.rs
