diff options
Diffstat (limited to 'xdelta3/cpp-btree/safe_btree.h')
-rw-r--r-- | xdelta3/cpp-btree/safe_btree.h | 395 |
1 files changed, 395 insertions, 0 deletions
diff --git a/xdelta3/cpp-btree/safe_btree.h b/xdelta3/cpp-btree/safe_btree.h new file mode 100644 index 0000000..2d85c70 --- /dev/null +++ b/xdelta3/cpp-btree/safe_btree.h | |||
@@ -0,0 +1,395 @@ | |||
1 | // Copyright 2013 Google Inc. All Rights Reserved. | ||
2 | // | ||
3 | // Licensed under the Apache License, Version 2.0 (the "License"); | ||
4 | // you may not use this file except in compliance with the License. | ||
5 | // You may obtain a copy of the License at | ||
6 | // | ||
7 | // http://www.apache.org/licenses/LICENSE-2.0 | ||
8 | // | ||
9 | // Unless required by applicable law or agreed to in writing, software | ||
10 | // distributed under the License is distributed on an "AS IS" BASIS, | ||
11 | // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. | ||
12 | // See the License for the specific language governing permissions and | ||
13 | // limitations under the License. | ||
14 | // | ||
15 | // A safe_btree<> wraps around a btree<> and removes the caveat that insertion | ||
16 | // and deletion invalidate iterators. A safe_btree<> maintains a generation | ||
17 | // number that is incremented on every mutation. A safe_btree<>::iterator keeps | ||
18 | // a pointer to the safe_btree<> it came from, the generation of the tree when | ||
19 | // it was last validated and the key the underlying btree<>::iterator points | ||
20 | // to. If an iterator is accessed and its generation differs from the tree | ||
21 | // generation it is revalidated. | ||
22 | // | ||
23 | // References and pointers returned by safe_btree iterators are not safe. | ||
24 | // | ||
25 | // See the incorrect usage examples mentioned in safe_btree_set.h and | ||
26 | // safe_btree_map.h. | ||
27 | |||
28 | #ifndef UTIL_BTREE_SAFE_BTREE_H__ | ||
29 | #define UTIL_BTREE_SAFE_BTREE_H__ | ||
30 | |||
31 | #include <stddef.h> | ||
32 | #include <iosfwd> | ||
33 | #include <utility> | ||
34 | |||
35 | #include "btree.h" | ||
36 | |||
37 | namespace btree { | ||
38 | |||
39 | template <typename Tree, typename Iterator> | ||
40 | class safe_btree_iterator { | ||
41 | public: | ||
42 | typedef typename Iterator::key_type key_type; | ||
43 | typedef typename Iterator::value_type value_type; | ||
44 | typedef typename Iterator::size_type size_type; | ||
45 | typedef typename Iterator::difference_type difference_type; | ||
46 | typedef typename Iterator::pointer pointer; | ||
47 | typedef typename Iterator::reference reference; | ||
48 | typedef typename Iterator::const_pointer const_pointer; | ||
49 | typedef typename Iterator::const_reference const_reference; | ||
50 | typedef typename Iterator::iterator_category iterator_category; | ||
51 | typedef typename Tree::iterator iterator; | ||
52 | typedef typename Tree::const_iterator const_iterator; | ||
53 | typedef safe_btree_iterator<Tree, Iterator> self_type; | ||
54 | |||
55 | void update() const { | ||
56 | if (iter_ != tree_->internal_btree()->end()) { | ||
57 | // A positive generation indicates a valid key. | ||
58 | generation_ = tree_->generation(); | ||
59 | key_ = iter_.key(); | ||
60 | } else { | ||
61 | // Use a negative generation to indicate iter_ points to end(). | ||
62 | generation_ = -tree_->generation(); | ||
63 | } | ||
64 | } | ||
65 | |||
66 | public: | ||
67 | safe_btree_iterator() | ||
68 | : generation_(0), | ||
69 | key_(), | ||
70 | iter_(), | ||
71 | tree_(NULL) { | ||
72 | } | ||
73 | safe_btree_iterator(const iterator &x) | ||
74 | : generation_(x.generation()), | ||
75 | key_(x.key()), | ||
76 | iter_(x.iter()), | ||
77 | tree_(x.tree()) { | ||
78 | } | ||
79 | safe_btree_iterator(Tree *tree, const Iterator &iter) | ||
80 | : generation_(), | ||
81 | key_(), | ||
82 | iter_(iter), | ||
83 | tree_(tree) { | ||
84 | update(); | ||
85 | } | ||
86 | |||
87 | Tree* tree() const { return tree_; } | ||
88 | int64_t generation() const { return generation_; } | ||
89 | |||
90 | Iterator* mutable_iter() const { | ||
91 | if (generation_ != tree_->generation()) { | ||
92 | if (generation_ > 0) { | ||
93 | // This does the wrong thing for a multi{set,map}. If my iter was | ||
94 | // pointing to the 2nd of 2 values with the same key, then this will | ||
95 | // reset it to point to the first. This is why we don't provide a | ||
96 | // safe_btree_multi{set,map}. | ||
97 | iter_ = tree_->internal_btree()->lower_bound(key_); | ||
98 | update(); | ||
99 | } else if (-generation_ != tree_->generation()) { | ||
100 | iter_ = tree_->internal_btree()->end(); | ||
101 | generation_ = -tree_->generation(); | ||
102 | } | ||
103 | } | ||
104 | return &iter_; | ||
105 | } | ||
106 | const Iterator& iter() const { | ||
107 | return *mutable_iter(); | ||
108 | } | ||
109 | |||
110 | // Equality/inequality operators. | ||
111 | bool operator==(const const_iterator &x) const { | ||
112 | return iter() == x.iter(); | ||
113 | } | ||
114 | bool operator!=(const const_iterator &x) const { | ||
115 | return iter() != x.iter(); | ||
116 | } | ||
117 | |||
118 | // Accessors for the key/value the iterator is pointing at. | ||
119 | const key_type& key() const { | ||
120 | return key_; | ||
121 | } | ||
122 | // This reference value is potentially invalidated by any non-const | ||
123 | // method on the tree; it is NOT safe. | ||
124 | reference operator*() const { | ||
125 | assert(generation_ > 0); | ||
126 | return iter().operator*(); | ||
127 | } | ||
128 | // This pointer value is potentially invalidated by any non-const | ||
129 | // method on the tree; it is NOT safe. | ||
130 | pointer operator->() const { | ||
131 | assert(generation_ > 0); | ||
132 | return iter().operator->(); | ||
133 | } | ||
134 | |||
135 | // Increment/decrement operators. | ||
136 | self_type& operator++() { | ||
137 | ++(*mutable_iter()); | ||
138 | update(); | ||
139 | return *this; | ||
140 | } | ||
141 | self_type& operator--() { | ||
142 | --(*mutable_iter()); | ||
143 | update(); | ||
144 | return *this; | ||
145 | } | ||
146 | self_type operator++(int) { | ||
147 | self_type tmp = *this; | ||
148 | ++*this; | ||
149 | return tmp; | ||
150 | } | ||
151 | self_type operator--(int) { | ||
152 | self_type tmp = *this; | ||
153 | --*this; | ||
154 | return tmp; | ||
155 | } | ||
156 | |||
157 | private: | ||
158 | // The generation of the tree when "iter" was updated. | ||
159 | mutable int64_t generation_; | ||
160 | // The key the iterator points to. | ||
161 | mutable key_type key_; | ||
162 | // The underlying iterator. | ||
163 | mutable Iterator iter_; | ||
164 | // The tree the iterator is associated with. | ||
165 | Tree *tree_; | ||
166 | }; | ||
167 | |||
168 | template <typename Params> | ||
169 | class safe_btree { | ||
170 | typedef safe_btree<Params> self_type; | ||
171 | |||
172 | typedef btree<Params> btree_type; | ||
173 | typedef typename btree_type::iterator tree_iterator; | ||
174 | typedef typename btree_type::const_iterator tree_const_iterator; | ||
175 | |||
176 | public: | ||
177 | typedef typename btree_type::params_type params_type; | ||
178 | typedef typename btree_type::key_type key_type; | ||
179 | typedef typename btree_type::data_type data_type; | ||
180 | typedef typename btree_type::mapped_type mapped_type; | ||
181 | typedef typename btree_type::value_type value_type; | ||
182 | typedef typename btree_type::key_compare key_compare; | ||
183 | typedef typename btree_type::allocator_type allocator_type; | ||
184 | typedef typename btree_type::pointer pointer; | ||
185 | typedef typename btree_type::const_pointer const_pointer; | ||
186 | typedef typename btree_type::reference reference; | ||
187 | typedef typename btree_type::const_reference const_reference; | ||
188 | typedef typename btree_type::size_type size_type; | ||
189 | typedef typename btree_type::difference_type difference_type; | ||
190 | typedef safe_btree_iterator<self_type, tree_iterator> iterator; | ||
191 | typedef safe_btree_iterator< | ||
192 | const self_type, tree_const_iterator> const_iterator; | ||
193 | typedef std::reverse_iterator<const_iterator> const_reverse_iterator; | ||
194 | typedef std::reverse_iterator<iterator> reverse_iterator; | ||
195 | |||
196 | public: | ||
197 | // Default constructor. | ||
198 | safe_btree(const key_compare &comp, const allocator_type &alloc) | ||
199 | : tree_(comp, alloc), | ||
200 | generation_(1) { | ||
201 | } | ||
202 | |||
203 | // Copy constructor. | ||
204 | safe_btree(const self_type &x) | ||
205 | : tree_(x.tree_), | ||
206 | generation_(1) { | ||
207 | } | ||
208 | |||
209 | iterator begin() { | ||
210 | return iterator(this, tree_.begin()); | ||
211 | } | ||
212 | const_iterator begin() const { | ||
213 | return const_iterator(this, tree_.begin()); | ||
214 | } | ||
215 | iterator end() { | ||
216 | return iterator(this, tree_.end()); | ||
217 | } | ||
218 | const_iterator end() const { | ||
219 | return const_iterator(this, tree_.end()); | ||
220 | } | ||
221 | reverse_iterator rbegin() { | ||
222 | return reverse_iterator(end()); | ||
223 | } | ||
224 | const_reverse_iterator rbegin() const { | ||
225 | return const_reverse_iterator(end()); | ||
226 | } | ||
227 | reverse_iterator rend() { | ||
228 | return reverse_iterator(begin()); | ||
229 | } | ||
230 | const_reverse_iterator rend() const { | ||
231 | return const_reverse_iterator(begin()); | ||
232 | } | ||
233 | |||
234 | // Lookup routines. | ||
235 | iterator lower_bound(const key_type &key) { | ||
236 | return iterator(this, tree_.lower_bound(key)); | ||
237 | } | ||
238 | const_iterator lower_bound(const key_type &key) const { | ||
239 | return const_iterator(this, tree_.lower_bound(key)); | ||
240 | } | ||
241 | iterator upper_bound(const key_type &key) { | ||
242 | return iterator(this, tree_.upper_bound(key)); | ||
243 | } | ||
244 | const_iterator upper_bound(const key_type &key) const { | ||
245 | return const_iterator(this, tree_.upper_bound(key)); | ||
246 | } | ||
247 | std::pair<iterator, iterator> equal_range(const key_type &key) { | ||
248 | std::pair<tree_iterator, tree_iterator> p = tree_.equal_range(key); | ||
249 | return std::make_pair(iterator(this, p.first), | ||
250 | iterator(this, p.second)); | ||
251 | } | ||
252 | std::pair<const_iterator, const_iterator> equal_range(const key_type &key) const { | ||
253 | std::pair<tree_const_iterator, tree_const_iterator> p = tree_.equal_range(key); | ||
254 | return std::make_pair(const_iterator(this, p.first), | ||
255 | const_iterator(this, p.second)); | ||
256 | } | ||
257 | iterator find_unique(const key_type &key) { | ||
258 | return iterator(this, tree_.find_unique(key)); | ||
259 | } | ||
260 | const_iterator find_unique(const key_type &key) const { | ||
261 | return const_iterator(this, tree_.find_unique(key)); | ||
262 | } | ||
263 | iterator find_multi(const key_type &key) { | ||
264 | return iterator(this, tree_.find_multi(key)); | ||
265 | } | ||
266 | const_iterator find_multi(const key_type &key) const { | ||
267 | return const_iterator(this, tree_.find_multi(key)); | ||
268 | } | ||
269 | size_type count_unique(const key_type &key) const { | ||
270 | return tree_.count_unique(key); | ||
271 | } | ||
272 | size_type count_multi(const key_type &key) const { | ||
273 | return tree_.count_multi(key); | ||
274 | } | ||
275 | |||
276 | // Insertion routines. | ||
277 | template <typename ValuePointer> | ||
278 | std::pair<iterator, bool> insert_unique(const key_type &key, ValuePointer value) { | ||
279 | std::pair<tree_iterator, bool> p = tree_.insert_unique(key, value); | ||
280 | generation_ += p.second; | ||
281 | return std::make_pair(iterator(this, p.first), p.second); | ||
282 | } | ||
283 | std::pair<iterator, bool> insert_unique(const value_type &v) { | ||
284 | std::pair<tree_iterator, bool> p = tree_.insert_unique(v); | ||
285 | generation_ += p.second; | ||
286 | return std::make_pair(iterator(this, p.first), p.second); | ||
287 | } | ||
288 | iterator insert_unique(iterator position, const value_type &v) { | ||
289 | tree_iterator tree_pos = position.iter(); | ||
290 | ++generation_; | ||
291 | return iterator(this, tree_.insert_unique(tree_pos, v)); | ||
292 | } | ||
293 | template <typename InputIterator> | ||
294 | void insert_unique(InputIterator b, InputIterator e) { | ||
295 | for (; b != e; ++b) { | ||
296 | insert_unique(*b); | ||
297 | } | ||
298 | } | ||
299 | iterator insert_multi(const value_type &v) { | ||
300 | ++generation_; | ||
301 | return iterator(this, tree_.insert_multi(v)); | ||
302 | } | ||
303 | iterator insert_multi(iterator position, const value_type &v) { | ||
304 | tree_iterator tree_pos = position.iter(); | ||
305 | ++generation_; | ||
306 | return iterator(this, tree_.insert_multi(tree_pos, v)); | ||
307 | } | ||
308 | template <typename InputIterator> | ||
309 | void insert_multi(InputIterator b, InputIterator e) { | ||
310 | for (; b != e; ++b) { | ||
311 | insert_multi(*b); | ||
312 | } | ||
313 | } | ||
314 | self_type& operator=(const self_type &x) { | ||
315 | if (&x == this) { | ||
316 | // Don't copy onto ourselves. | ||
317 | return *this; | ||
318 | } | ||
319 | ++generation_; | ||
320 | tree_ = x.tree_; | ||
321 | return *this; | ||
322 | } | ||
323 | |||
324 | // Deletion routines. | ||
325 | void erase(const iterator &begin, const iterator &end) { | ||
326 | tree_.erase(begin.iter(), end.iter()); | ||
327 | ++generation_; | ||
328 | } | ||
329 | // Erase the specified iterator from the btree. The iterator must be valid | ||
330 | // (i.e. not equal to end()). Return an iterator pointing to the node after | ||
331 | // the one that was erased (or end() if none exists). | ||
332 | iterator erase(iterator iter) { | ||
333 | tree_iterator res = tree_.erase(iter.iter()); | ||
334 | ++generation_; | ||
335 | return iterator(this, res); | ||
336 | } | ||
337 | int erase_unique(const key_type &key) { | ||
338 | int res = tree_.erase_unique(key); | ||
339 | generation_ += res; | ||
340 | return res; | ||
341 | } | ||
342 | int erase_multi(const key_type &key) { | ||
343 | int res = tree_.erase_multi(key); | ||
344 | generation_ += res; | ||
345 | return res; | ||
346 | } | ||
347 | |||
348 | // Access to the underlying btree. | ||
349 | btree_type* internal_btree() { return &tree_; } | ||
350 | const btree_type* internal_btree() const { return &tree_; } | ||
351 | |||
352 | // Utility routines. | ||
353 | void clear() { | ||
354 | ++generation_; | ||
355 | tree_.clear(); | ||
356 | } | ||
357 | void swap(self_type &x) { | ||
358 | ++generation_; | ||
359 | ++x.generation_; | ||
360 | tree_.swap(x.tree_); | ||
361 | } | ||
362 | void dump(std::ostream &os) const { | ||
363 | tree_.dump(os); | ||
364 | } | ||
365 | void verify() const { | ||
366 | tree_.verify(); | ||
367 | } | ||
368 | int64_t generation() const { | ||
369 | return generation_; | ||
370 | } | ||
371 | key_compare key_comp() const { return tree_.key_comp(); } | ||
372 | |||
373 | // Size routines. | ||
374 | size_type size() const { return tree_.size(); } | ||
375 | size_type max_size() const { return tree_.max_size(); } | ||
376 | bool empty() const { return tree_.empty(); } | ||
377 | size_type height() const { return tree_.height(); } | ||
378 | size_type internal_nodes() const { return tree_.internal_nodes(); } | ||
379 | size_type leaf_nodes() const { return tree_.leaf_nodes(); } | ||
380 | size_type nodes() const { return tree_.nodes(); } | ||
381 | size_type bytes_used() const { return tree_.bytes_used(); } | ||
382 | static double average_bytes_per_value() { | ||
383 | return btree_type::average_bytes_per_value(); | ||
384 | } | ||
385 | double fullness() const { return tree_.fullness(); } | ||
386 | double overhead() const { return tree_.overhead(); } | ||
387 | |||
388 | private: | ||
389 | btree_type tree_; | ||
390 | int64_t generation_; | ||
391 | }; | ||
392 | |||
393 | } // namespace btree | ||
394 | |||
395 | #endif // UTIL_BTREE_SAFE_BTREE_H__ | ||