1 use crate::fx::FxHashMap;
9 pub struct SnapshotMap<K, V>
10 where K: Hash + Clone + Eq
13 undo_log: Vec<UndoLog<K, V>>,
14 num_open_snapshots: usize,
17 // HACK(eddyb) manual impl avoids `Default` bounds on `K` and `V`.
18 impl<K, V> Default for SnapshotMap<K, V>
19 where K: Hash + Clone + Eq
21 fn default() -> Self {
23 map: Default::default(),
24 undo_log: Default::default(),
25 num_open_snapshots: 0,
40 impl<K, V> SnapshotMap<K, V>
41 where K: Hash + Clone + Eq
43 pub fn clear(&mut self) {
45 self.undo_log.clear();
46 self.num_open_snapshots = 0;
49 fn in_snapshot(&self) -> bool {
50 self.num_open_snapshots > 0
53 pub fn insert(&mut self, key: K, value: V) -> bool {
54 match self.map.insert(key.clone(), value) {
56 if self.in_snapshot() {
57 self.undo_log.push(UndoLog::Inserted(key));
62 if self.in_snapshot() {
63 self.undo_log.push(UndoLog::Overwrite(key, old_value));
70 pub fn remove(&mut self, key: K) -> bool {
71 match self.map.remove(&key) {
73 if self.in_snapshot() {
74 self.undo_log.push(UndoLog::Overwrite(key, old_value));
82 pub fn get(&self, key: &K) -> Option<&V> {
86 pub fn snapshot(&mut self) -> Snapshot {
87 let len = self.undo_log.len();
88 self.num_open_snapshots += 1;
92 fn assert_open_snapshot(&self, snapshot: &Snapshot) {
93 assert!(self.undo_log.len() >= snapshot.len);
94 assert!(self.num_open_snapshots > 0);
97 pub fn commit(&mut self, snapshot: Snapshot) {
98 self.assert_open_snapshot(&snapshot);
99 if self.num_open_snapshots == 1 {
100 // The root snapshot. It's safe to clear the undo log because
101 // there's no snapshot further out that we might need to roll back
103 assert!(snapshot.len == 0);
104 self.undo_log.clear();
107 self.num_open_snapshots -= 1;
110 pub fn partial_rollback<F>(&mut self,
112 should_revert_key: &F)
113 where F: Fn(&K) -> bool
115 self.assert_open_snapshot(snapshot);
116 for i in (snapshot.len .. self.undo_log.len()).rev() {
117 let reverse = match self.undo_log[i] {
118 UndoLog::Purged => false,
119 UndoLog::Inserted(ref k) => should_revert_key(k),
120 UndoLog::Overwrite(ref k, _) => should_revert_key(k),
124 let entry = mem::replace(&mut self.undo_log[i], UndoLog::Purged);
130 pub fn rollback_to(&mut self, snapshot: Snapshot) {
131 self.assert_open_snapshot(&snapshot);
132 while self.undo_log.len() > snapshot.len {
133 let entry = self.undo_log.pop().unwrap();
137 self.num_open_snapshots -= 1;
140 fn reverse(&mut self, entry: UndoLog<K, V>) {
142 UndoLog::Inserted(key) => {
143 self.map.remove(&key);
146 UndoLog::Overwrite(key, old_value) => {
147 self.map.insert(key, old_value);
150 UndoLog::Purged => {}
155 impl<'k, K, V> ops::Index<&'k K> for SnapshotMap<K, V>
156 where K: Hash + Clone + Eq
159 fn index(&self, key: &'k K) -> &V {