diff options
Diffstat (limited to 'xdelta3/cpp-btree/safe_btree_set.h')
-rw-r--r-- | xdelta3/cpp-btree/safe_btree_set.h | 88 |
1 files changed, 88 insertions, 0 deletions
diff --git a/xdelta3/cpp-btree/safe_btree_set.h b/xdelta3/cpp-btree/safe_btree_set.h new file mode 100644 index 0000000..a6cd541 --- /dev/null +++ b/xdelta3/cpp-btree/safe_btree_set.h | |||
@@ -0,0 +1,88 @@ | |||
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 | // The safe_btree_set<> is like btree_set<> except that it removes the caveat | ||
16 | // about insertion and deletion invalidating existing iterators at a small cost | ||
17 | // in making iterators larger and slower. | ||
18 | // | ||
19 | // Revalidation occurs whenever an iterator is accessed. References | ||
20 | // and pointers returned by safe_btree_map<> iterators are not stable, | ||
21 | // they are potentially invalidated by any non-const method on the set. | ||
22 | // | ||
23 | // BEGIN INCORRECT EXAMPLE | ||
24 | // for (auto i = safe_set->begin(); i != safe_set->end(); ++i) { | ||
25 | // const T &value = *i; // DO NOT DO THIS | ||
26 | // [code that modifies safe_set and uses value]; | ||
27 | // } | ||
28 | // END INCORRECT EXAMPLE | ||
29 | |||
30 | #ifndef UTIL_BTREE_SAFE_BTREE_SET_H__ | ||
31 | #define UTIL_BTREE_SAFE_BTREE_SET_H__ | ||
32 | |||
33 | #include <functional> | ||
34 | #include <memory> | ||
35 | |||
36 | #include "btree_container.h" | ||
37 | #include "btree_set.h" | ||
38 | #include "safe_btree.h" | ||
39 | |||
40 | namespace btree { | ||
41 | |||
42 | // The safe_btree_set class is needed mainly for its constructors. | ||
43 | template <typename Key, | ||
44 | typename Compare = std::less<Key>, | ||
45 | typename Alloc = std::allocator<Key>, | ||
46 | int TargetNodeSize = 256> | ||
47 | class safe_btree_set : public btree_unique_container< | ||
48 | safe_btree<btree_set_params<Key, Compare, Alloc, TargetNodeSize> > > { | ||
49 | |||
50 | typedef safe_btree_set<Key, Compare, Alloc, TargetNodeSize> self_type; | ||
51 | typedef btree_set_params<Key, Compare, Alloc, TargetNodeSize> params_type; | ||
52 | typedef safe_btree<params_type> btree_type; | ||
53 | typedef btree_unique_container<btree_type> super_type; | ||
54 | |||
55 | public: | ||
56 | typedef typename btree_type::key_compare key_compare; | ||
57 | typedef typename btree_type::allocator_type allocator_type; | ||
58 | |||
59 | public: | ||
60 | // Default constructor. | ||
61 | safe_btree_set(const key_compare &comp = key_compare(), | ||
62 | const allocator_type &alloc = allocator_type()) | ||
63 | : super_type(comp, alloc) { | ||
64 | } | ||
65 | |||
66 | // Copy constructor. | ||
67 | safe_btree_set(const self_type &x) | ||
68 | : super_type(x) { | ||
69 | } | ||
70 | |||
71 | // Range constructor. | ||
72 | template <class InputIterator> | ||
73 | safe_btree_set(InputIterator b, InputIterator e, | ||
74 | const key_compare &comp = key_compare(), | ||
75 | const allocator_type &alloc = allocator_type()) | ||
76 | : super_type(b, e, comp, alloc) { | ||
77 | } | ||
78 | }; | ||
79 | |||
80 | template <typename K, typename C, typename A, int N> | ||
81 | inline void swap(safe_btree_set<K, C, A, N> &x, | ||
82 | safe_btree_set<K, C, A, N> &y) { | ||
83 | x.swap(y); | ||
84 | } | ||
85 | |||
86 | } // namespace btree | ||
87 | |||
88 | #endif // UTIL_BTREE_SAFE_BTREE_SET_H__ | ||