1 use crate::fx::FxHashMap; 2 use crate::undo_log::{Rollback, Snapshots, UndoLogs, VecLog}; 3 use std::borrow::{Borrow, BorrowMut}; 4 use std::hash::Hash; 5 use std::marker::PhantomData; 6 use std::ops; 7 8 pub use crate::undo_log::Snapshot; 9 10 #[cfg(test)] 11 mod tests; 12 13 pub type SnapshotMapStorage<K, V> = SnapshotMap<K, V, FxHashMap<K, V>, ()>; 14 pub type SnapshotMapRef<'a, K, V, L> = SnapshotMap<K, V, &'a mut FxHashMap<K, V>, &'a mut L>; 15 16 #[derive(Clone)] 17 pub 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`. 24 impl<K, V, M, L> Default for SnapshotMap<K, V, M, L> 25 where 26 M: Default, 27 L: Default, 28 { default() -> Self29 fn default() -> Self { 30 SnapshotMap { map: Default::default(), undo_log: Default::default(), _marker: PhantomData } 31 } 32 } 33 34 #[derive(Clone)] 35 pub enum UndoLog<K, V> { 36 Inserted(K), 37 Overwrite(K, V), 38 Purged, 39 } 40 41 impl<K, V, M, L> SnapshotMap<K, V, M, L> { 42 #[inline] with_log<L2>(&mut self, undo_log: L2) -> SnapshotMap<K, V, &mut M, L2>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 48 impl<K, V, M, L> SnapshotMap<K, V, M, L> 49 where 50 K: Hash + Clone + Eq, 51 M: BorrowMut<FxHashMap<K, V>> + Borrow<FxHashMap<K, V>>, 52 L: UndoLogs<UndoLog<K, V>>, 53 { clear(&mut self)54 pub fn clear(&mut self) { 55 self.map.borrow_mut().clear(); 56 self.undo_log.clear(); 57 } 58 insert(&mut self, key: K, value: V) -> bool59 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 remove(&mut self, key: K) -> bool72 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 get(&self, key: &K) -> Option<&V>82 pub fn get(&self, key: &K) -> Option<&V> { 83 self.map.borrow().get(key) 84 } 85 } 86 87 impl<K, V> SnapshotMap<K, V> 88 where 89 K: Hash + Clone + Eq, 90 { snapshot(&mut self) -> Snapshot91 pub fn snapshot(&mut self) -> Snapshot { 92 self.undo_log.start_snapshot() 93 } 94 commit(&mut self, snapshot: Snapshot)95 pub fn commit(&mut self, snapshot: Snapshot) { 96 self.undo_log.commit(snapshot) 97 } 98 rollback_to(&mut self, snapshot: Snapshot)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 105 impl<'k, K, V, M, L> ops::Index<&'k K> for SnapshotMap<K, V, M, L> 106 where 107 K: Hash + Clone + Eq, 108 M: Borrow<FxHashMap<K, V>>, 109 { 110 type Output = V; index(&self, key: &'k K) -> &V111 fn index(&self, key: &'k K) -> &V { 112 &self.map.borrow()[key] 113 } 114 } 115 116 impl<K, V, M, L> Rollback<UndoLog<K, V>> for SnapshotMap<K, V, M, L> 117 where 118 K: Eq + Hash, 119 M: Rollback<UndoLog<K, V>>, 120 { reverse(&mut self, undo: UndoLog<K, V>)121 fn reverse(&mut self, undo: UndoLog<K, V>) { 122 self.map.reverse(undo) 123 } 124 } 125 126 impl<K, V> Rollback<UndoLog<K, V>> for FxHashMap<K, V> 127 where 128 K: Eq + Hash, 129 { reverse(&mut self, undo: UndoLog<K, V>)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 } 144