rustc_data_structures/snapshot_map/
mod.rs

Help
1use std::borrow::{Borrow, BorrowMut};
2use std::hash::Hash;
3use std::marker::PhantomData;
4use std::ops;
5
6use crate::fx::FxHashMap;
7pub use crate::undo_log::Snapshot;
8use crate::undo_log::{Rollback, Snapshots, UndoLogs, VecLog};
9
10#[cfg(test)]
11mod tests;
12
13pub type SnapshotMapStorage<K, V> = SnapshotMap<K, V, FxHashMap<K, V>, ()>;
14pub type SnapshotMapRef<'a, K, V, L> = SnapshotMap<K, V, &'a mut FxHashMap<K, V>, &'a mut L>;
15
16#[derive(Clone)]
17pub struct SnapshotMap<K, V, M = FxHashMap<K, V>, L = VecLog<UndoLog<K, V>>> {
18    map: M,
19    undo_log: L,
20    _marker: PhantomData<(K, V)>,
21}
22
23// HACK(eddyb) manual impl avoids `Default` bounds on `K` and `V`.
24impl<K, V, M, L> Default for SnapshotMap<K, V, M, L>
25where
26    M: Default,
27    L: Default,
28{
29    fn default() -> Self {
30        SnapshotMap { map: Default::default(), undo_log: Default::default(), _marker: PhantomData }
31    }
32}
33
34#[derive(Clone)]
35pub enum UndoLog<K, V> {
36    Inserted(K),
37    Overwrite(K, V),
38    Purged,
39}
40
41impl<K, V, M, L> SnapshotMap<K, V, M, L> {
42    #[inline]
43    pub fn with_log<L2>(&mut self, undo_log: L2) -> SnapshotMap<K, V, &mut M, L2> {
44        SnapshotMap { map: &mut self.map, undo_log, _marker: PhantomData }
45    }
46}
47
48impl<K, V, M, L> SnapshotMap<K, V, M, L>
49where
50    K: Hash + Clone + Eq,
51    M: BorrowMut<FxHashMap<K, V>> + Borrow<FxHashMap<K, V>>,
52    L: UndoLogs<UndoLog<K, V>>,
53{
54    pub fn clear(&mut self) {
55        self.map.borrow_mut().clear();
56        self.undo_log.clear();
57    }
58
59    pub fn insert(&mut self, key: K, value: V) -> bool {
60        match self.map.borrow_mut().insert(key.clone(), value) {
61            None => {
62                self.undo_log.push(UndoLog::Inserted(key));
63                true
64            }
65            Some(old_value) => {
66                self.undo_log.push(UndoLog::Overwrite(key, old_value));
67                false
68            }
69        }
70    }
71
72    pub fn remove(&mut self, key: K) -> bool {
73        match self.map.borrow_mut().remove(&key) {
74            Some(old_value) => {
75                self.undo_log.push(UndoLog::Overwrite(key, old_value));
76                true
77            }
78            None => false,
79        }
80    }
81
82    pub fn get(&self, key: &K) -> Option<&V> {
83        self.map.borrow().get(key)
84    }
85}
86
87impl<K, V> SnapshotMap<K, V>
88where
89    K: Hash + Clone + Eq,
90{
91    pub fn snapshot(&mut self) -> Snapshot {
92        self.undo_log.start_snapshot()
93    }
94
95    pub fn commit(&mut self, snapshot: Snapshot) {
96        self.undo_log.commit(snapshot)
97    }
98
99    pub fn rollback_to(&mut self, snapshot: Snapshot) {
100        let map = &mut self.map;
101        self.undo_log.rollback_to(|| map, snapshot)
102    }
103}
104
105impl<'k, K, V, M, L> ops::Index<&'k K> for SnapshotMap<K, V, M, L>
106where
107    K: Hash + Clone + Eq,
108    M: Borrow<FxHashMap<K, V>>,
109{
110    type Output = V;
111    fn index(&self, key: &'k K) -> &V {
112        &self.map.borrow()[key]
113    }
114}
115
116impl<K, V, M, L> Rollback<UndoLog<K, V>> for SnapshotMap<K, V, M, L>
117where
118    K: Eq + Hash,
119    M: Rollback<UndoLog<K, V>>,
120{
121    fn reverse(&mut self, undo: UndoLog<K, V>) {
122        self.map.reverse(undo)
123    }
124}
125
126impl<K, V> Rollback<UndoLog<K, V>> for FxHashMap<K, V>
127where
128    K: Eq + Hash,
129{
130    fn reverse(&mut self, undo: UndoLog<K, V>) {
131        match undo {
132            UndoLog::Inserted(key) => {
133                self.remove(&key);
134            }
135
136            UndoLog::Overwrite(key, old_value) => {
137                self.insert(key, old_value);
138            }
139
140            UndoLog::Purged => {}
141        }
142    }
143}
rustc_data_structures/snapshot_map/mod.rs

rustc_data_structures/snapshot_map/
mod.rs
