Skip to main content

memfork_core/
store.rs

1//! The persistent-map seam (DESIGN §4.1).
2//!
3//! `Root` is a persistent, structurally shared ordered map. Branching copies
4//! nothing: a fork and its parent share every node until one of them is
5//! written to, and a write copies only the path from the root to the changed
6//! key. Nothing here uses OS `fork()`, copy-on-write pages or any other
7//! platform snapshot trick — none of which would work the same way on three
8//! operating systems.
9//!
10//! The concrete structure sits behind [`Store`] so it can be replaced without
11//! touching the engine.
12
13use std::sync::Arc;
14
15use crate::entry::Entry;
16
17/// A persistent ordered map from key to entry.
18///
19/// Implementations must iterate in ascending key order, because that ordering
20/// is what makes commit ids and listings reproducible.
21pub trait Store: Clone + core::fmt::Debug + Default + Send + Sync {
22    /// Look a key up.
23    fn get(&self, key: &str) -> Option<&Arc<Entry>>;
24
25    /// Return a new map with `key` set, leaving `self` untouched.
26    fn insert(&self, key: String, value: Arc<Entry>) -> Self;
27
28    /// Return a new map with `key` removed, leaving `self` untouched.
29    fn remove(&self, key: &str) -> Self;
30
31    /// Set `key` in place. Equivalent to `*self = self.insert(..)`, but skips
32    /// copying nodes this map holds exclusively.
33    fn insert_mut(&mut self, key: String, value: Arc<Entry>);
34
35    /// Remove `key` in place. Returns whether the key was present.
36    fn remove_mut(&mut self, key: &str) -> bool;
37
38    /// Number of entries.
39    fn len(&self) -> usize;
40
41    /// Whether the map is empty.
42    fn is_empty(&self) -> bool {
43        self.len() == 0
44    }
45
46    /// All entries, in ascending key order.
47    fn iter(&self) -> impl Iterator<Item = (&String, &Arc<Entry>)>;
48
49    /// All entries whose key starts with `prefix`, in ascending key order.
50    fn range_prefix<'a>(
51        &'a self,
52        prefix: &'a str,
53    ) -> impl Iterator<Item = (&'a String, &'a Arc<Entry>)>;
54
55    /// Whether two maps are the same allocation, i.e. share all their nodes.
56    ///
57    /// Used by the test that shows forking copies nothing.
58    fn shares_allocation_with(&self, other: &Self) -> bool;
59}
60
61/// The persistent ordered map used by the engine.
62///
63/// A red-black tree map with atomically reference-counted nodes: `O(log n)`
64/// reads and writes, `O(1)` cloning, ascending-order iteration, and `Send +
65/// Sync` so a root can be handed to any number of reader threads.
66pub type Root = rpds::RedBlackTreeMapSync<String, Arc<Entry>>;
67
68impl Store for Root {
69    fn get(&self, key: &str) -> Option<&Arc<Entry>> {
70        Root::get(self, key)
71    }
72
73    fn insert(&self, key: String, value: Arc<Entry>) -> Self {
74        Root::insert(self, key, value)
75    }
76
77    fn remove(&self, key: &str) -> Self {
78        Root::remove(self, key)
79    }
80
81    fn insert_mut(&mut self, key: String, value: Arc<Entry>) {
82        Root::insert_mut(self, key, value);
83    }
84
85    fn remove_mut(&mut self, key: &str) -> bool {
86        Root::remove_mut(self, key)
87    }
88
89    fn len(&self) -> usize {
90        self.size()
91    }
92
93    fn iter(&self) -> impl Iterator<Item = (&String, &Arc<Entry>)> {
94        Root::iter(self)
95    }
96
97    fn range_prefix<'a>(
98        &'a self,
99        prefix: &'a str,
100    ) -> impl Iterator<Item = (&'a String, &'a Arc<Entry>)> {
101        // Seek to the first key at or after the prefix, then stop at the first
102        // key that no longer carries it. Walking forward from the seek point
103        // avoids constructing an upper bound, which for a byte-incremented
104        // prefix would not always be valid UTF-8.
105        self.range::<String, _>(prefix.to_owned()..)
106            .take_while(move |(k, _)| k.starts_with(prefix))
107    }
108
109    fn shares_allocation_with(&self, other: &Self) -> bool {
110        self.ptr_eq(other)
111    }
112}