]>
Commit | Line | Data |
---|---|---|
3157f602 XL |
1 | // Copyright 2014 The Rust Project Developers. See the COPYRIGHT |
2 | // file at the top-level directory of this distribution and at | |
3 | // http://rust-lang.org/COPYRIGHT. | |
4 | // | |
5 | // Licensed under the Apache License, Version 2.0 <LICENSE-APACHE or | |
6 | // http://www.apache.org/licenses/LICENSE-2.0> or the MIT license | |
7 | // <LICENSE-MIT or http://opensource.org/licenses/MIT>, at your | |
8 | // option. This file may not be copied, modified, or distributed | |
9 | // except according to those terms. | |
10 | ||
476ff2be | 11 | use fx::FxHashMap; |
3157f602 XL |
12 | use std::hash::Hash; |
13 | use std::ops; | |
c30ab7b3 | 14 | use std::mem; |
3157f602 XL |
15 | |
16 | #[cfg(test)] | |
17 | mod test; | |
18 | ||
19 | pub struct SnapshotMap<K, V> | |
20 | where K: Hash + Clone + Eq | |
21 | { | |
476ff2be | 22 | map: FxHashMap<K, V>, |
3157f602 XL |
23 | undo_log: Vec<UndoLog<K, V>>, |
24 | } | |
25 | ||
26 | pub struct Snapshot { | |
c30ab7b3 | 27 | len: usize, |
3157f602 XL |
28 | } |
29 | ||
30 | enum UndoLog<K, V> { | |
31 | OpenSnapshot, | |
32 | CommittedSnapshot, | |
33 | Inserted(K), | |
34 | Overwrite(K, V), | |
c30ab7b3 | 35 | Noop, |
3157f602 XL |
36 | } |
37 | ||
38 | impl<K, V> SnapshotMap<K, V> | |
39 | where K: Hash + Clone + Eq | |
40 | { | |
41 | pub fn new() -> Self { | |
42 | SnapshotMap { | |
476ff2be | 43 | map: FxHashMap(), |
c30ab7b3 | 44 | undo_log: vec![], |
3157f602 XL |
45 | } |
46 | } | |
47 | ||
0531ce1d XL |
48 | pub fn clear(&mut self) { |
49 | self.map.clear(); | |
50 | self.undo_log.clear(); | |
51 | } | |
52 | ||
3157f602 XL |
53 | pub fn insert(&mut self, key: K, value: V) -> bool { |
54 | match self.map.insert(key.clone(), value) { | |
55 | None => { | |
56 | if !self.undo_log.is_empty() { | |
57 | self.undo_log.push(UndoLog::Inserted(key)); | |
58 | } | |
59 | true | |
60 | } | |
61 | Some(old_value) => { | |
62 | if !self.undo_log.is_empty() { | |
63 | self.undo_log.push(UndoLog::Overwrite(key, old_value)); | |
64 | } | |
65 | false | |
66 | } | |
67 | } | |
68 | } | |
69 | ||
94b46f34 XL |
70 | pub fn insert_noop(&mut self) { |
71 | if !self.undo_log.is_empty() { | |
72 | self.undo_log.push(UndoLog::Noop); | |
73 | } | |
74 | } | |
75 | ||
3157f602 XL |
76 | pub fn remove(&mut self, key: K) -> bool { |
77 | match self.map.remove(&key) { | |
78 | Some(old_value) => { | |
79 | if !self.undo_log.is_empty() { | |
80 | self.undo_log.push(UndoLog::Overwrite(key, old_value)); | |
81 | } | |
82 | true | |
83 | } | |
c30ab7b3 | 84 | None => false, |
3157f602 XL |
85 | } |
86 | } | |
87 | ||
88 | pub fn get(&self, key: &K) -> Option<&V> { | |
89 | self.map.get(key) | |
90 | } | |
91 | ||
92 | pub fn snapshot(&mut self) -> Snapshot { | |
93 | self.undo_log.push(UndoLog::OpenSnapshot); | |
94 | let len = self.undo_log.len() - 1; | |
95 | Snapshot { len: len } | |
96 | } | |
97 | ||
98 | fn assert_open_snapshot(&self, snapshot: &Snapshot) { | |
99 | assert!(snapshot.len < self.undo_log.len()); | |
100 | assert!(match self.undo_log[snapshot.len] { | |
101 | UndoLog::OpenSnapshot => true, | |
c30ab7b3 | 102 | _ => false, |
3157f602 XL |
103 | }); |
104 | } | |
105 | ||
106 | pub fn commit(&mut self, snapshot: Snapshot) { | |
107 | self.assert_open_snapshot(&snapshot); | |
108 | if snapshot.len == 0 { | |
109 | // The root snapshot. | |
110 | self.undo_log.truncate(0); | |
111 | } else { | |
112 | self.undo_log[snapshot.len] = UndoLog::CommittedSnapshot; | |
113 | } | |
114 | } | |
115 | ||
c30ab7b3 SL |
116 | pub fn partial_rollback<F>(&mut self, |
117 | snapshot: &Snapshot, | |
118 | should_revert_key: &F) | |
119 | where F: Fn(&K) -> bool | |
120 | { | |
121 | self.assert_open_snapshot(snapshot); | |
122 | for i in (snapshot.len + 1..self.undo_log.len()).rev() { | |
123 | let reverse = match self.undo_log[i] { | |
124 | UndoLog::OpenSnapshot => false, | |
125 | UndoLog::CommittedSnapshot => false, | |
126 | UndoLog::Noop => false, | |
127 | UndoLog::Inserted(ref k) => should_revert_key(k), | |
128 | UndoLog::Overwrite(ref k, _) => should_revert_key(k), | |
129 | }; | |
130 | ||
131 | if reverse { | |
132 | let entry = mem::replace(&mut self.undo_log[i], UndoLog::Noop); | |
133 | self.reverse(entry); | |
134 | } | |
135 | } | |
136 | } | |
137 | ||
3157f602 XL |
138 | pub fn rollback_to(&mut self, snapshot: Snapshot) { |
139 | self.assert_open_snapshot(&snapshot); | |
140 | while self.undo_log.len() > snapshot.len + 1 { | |
c30ab7b3 SL |
141 | let entry = self.undo_log.pop().unwrap(); |
142 | self.reverse(entry); | |
143 | } | |
144 | ||
145 | let v = self.undo_log.pop().unwrap(); | |
146 | assert!(match v { | |
147 | UndoLog::OpenSnapshot => true, | |
148 | _ => false, | |
149 | }); | |
150 | assert!(self.undo_log.len() == snapshot.len); | |
151 | } | |
3157f602 | 152 | |
c30ab7b3 SL |
153 | fn reverse(&mut self, entry: UndoLog<K, V>) { |
154 | match entry { | |
155 | UndoLog::OpenSnapshot => { | |
156 | panic!("cannot rollback an uncommitted snapshot"); | |
157 | } | |
3157f602 | 158 | |
c30ab7b3 | 159 | UndoLog::CommittedSnapshot => {} |
3157f602 | 160 | |
c30ab7b3 SL |
161 | UndoLog::Inserted(key) => { |
162 | self.map.remove(&key); | |
3157f602 | 163 | } |
3157f602 | 164 | |
c30ab7b3 SL |
165 | UndoLog::Overwrite(key, old_value) => { |
166 | self.map.insert(key, old_value); | |
167 | } | |
168 | ||
169 | UndoLog::Noop => {} | |
170 | } | |
3157f602 XL |
171 | } |
172 | } | |
173 | ||
174 | impl<'k, K, V> ops::Index<&'k K> for SnapshotMap<K, V> | |
175 | where K: Hash + Clone + Eq | |
176 | { | |
177 | type Output = V; | |
178 | fn index(&self, key: &'k K) -> &V { | |
179 | &self.map[key] | |
180 | } | |
181 | } |