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}