diff options
author | Josh MacDonald <josh.macdonald@gmail.com> | 2014-11-01 00:13:18 -0700 |
---|---|---|
committer | Josh MacDonald <josh.macdonald@gmail.com> | 2014-11-01 00:13:18 -0700 |
commit | 336445673c60b7c05b015114077f49493f18e7f4 (patch) | |
tree | 844bb336d19e65c517109987e2daa39d038f3224 /xdelta3/cpp-btree/btree_container.h | |
parent | 9d4f55040311a16b32973b284e9cdfdf843ddf66 (diff) |
Checksum test under development
Diffstat (limited to 'xdelta3/cpp-btree/btree_container.h')
-rw-r--r-- | xdelta3/cpp-btree/btree_container.h | 349 |
1 files changed, 349 insertions, 0 deletions
diff --git a/xdelta3/cpp-btree/btree_container.h b/xdelta3/cpp-btree/btree_container.h new file mode 100644 index 0000000..fb617ab --- /dev/null +++ b/xdelta3/cpp-btree/btree_container.h | |||
@@ -0,0 +1,349 @@ | |||
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 | #ifndef UTIL_BTREE_BTREE_CONTAINER_H__ | ||
16 | #define UTIL_BTREE_BTREE_CONTAINER_H__ | ||
17 | |||
18 | #include <iosfwd> | ||
19 | #include <utility> | ||
20 | |||
21 | #include "btree.h" | ||
22 | |||
23 | namespace btree { | ||
24 | |||
25 | // A common base class for btree_set, btree_map, btree_multiset and | ||
26 | // btree_multimap. | ||
27 | template <typename Tree> | ||
28 | class btree_container { | ||
29 | typedef btree_container<Tree> self_type; | ||
30 | |||
31 | public: | ||
32 | typedef typename Tree::params_type params_type; | ||
33 | typedef typename Tree::key_type key_type; | ||
34 | typedef typename Tree::value_type value_type; | ||
35 | typedef typename Tree::key_compare key_compare; | ||
36 | typedef typename Tree::allocator_type allocator_type; | ||
37 | typedef typename Tree::pointer pointer; | ||
38 | typedef typename Tree::const_pointer const_pointer; | ||
39 | typedef typename Tree::reference reference; | ||
40 | typedef typename Tree::const_reference const_reference; | ||
41 | typedef typename Tree::size_type size_type; | ||
42 | typedef typename Tree::difference_type difference_type; | ||
43 | typedef typename Tree::iterator iterator; | ||
44 | typedef typename Tree::const_iterator const_iterator; | ||
45 | typedef typename Tree::reverse_iterator reverse_iterator; | ||
46 | typedef typename Tree::const_reverse_iterator const_reverse_iterator; | ||
47 | |||
48 | public: | ||
49 | // Default constructor. | ||
50 | btree_container(const key_compare &comp, const allocator_type &alloc) | ||
51 | : tree_(comp, alloc) { | ||
52 | } | ||
53 | |||
54 | // Copy constructor. | ||
55 | btree_container(const self_type &x) | ||
56 | : tree_(x.tree_) { | ||
57 | } | ||
58 | |||
59 | // Iterator routines. | ||
60 | iterator begin() { return tree_.begin(); } | ||
61 | const_iterator begin() const { return tree_.begin(); } | ||
62 | iterator end() { return tree_.end(); } | ||
63 | const_iterator end() const { return tree_.end(); } | ||
64 | reverse_iterator rbegin() { return tree_.rbegin(); } | ||
65 | const_reverse_iterator rbegin() const { return tree_.rbegin(); } | ||
66 | reverse_iterator rend() { return tree_.rend(); } | ||
67 | const_reverse_iterator rend() const { return tree_.rend(); } | ||
68 | |||
69 | // Lookup routines. | ||
70 | iterator lower_bound(const key_type &key) { | ||
71 | return tree_.lower_bound(key); | ||
72 | } | ||
73 | const_iterator lower_bound(const key_type &key) const { | ||
74 | return tree_.lower_bound(key); | ||
75 | } | ||
76 | iterator upper_bound(const key_type &key) { | ||
77 | return tree_.upper_bound(key); | ||
78 | } | ||
79 | const_iterator upper_bound(const key_type &key) const { | ||
80 | return tree_.upper_bound(key); | ||
81 | } | ||
82 | std::pair<iterator,iterator> equal_range(const key_type &key) { | ||
83 | return tree_.equal_range(key); | ||
84 | } | ||
85 | std::pair<const_iterator,const_iterator> equal_range(const key_type &key) const { | ||
86 | return tree_.equal_range(key); | ||
87 | } | ||
88 | |||
89 | // Utility routines. | ||
90 | void clear() { | ||
91 | tree_.clear(); | ||
92 | } | ||
93 | void swap(self_type &x) { | ||
94 | tree_.swap(x.tree_); | ||
95 | } | ||
96 | void dump(std::ostream &os) const { | ||
97 | tree_.dump(os); | ||
98 | } | ||
99 | void verify() const { | ||
100 | tree_.verify(); | ||
101 | } | ||
102 | |||
103 | // Size routines. | ||
104 | size_type size() const { return tree_.size(); } | ||
105 | size_type max_size() const { return tree_.max_size(); } | ||
106 | bool empty() const { return tree_.empty(); } | ||
107 | size_type height() const { return tree_.height(); } | ||
108 | size_type internal_nodes() const { return tree_.internal_nodes(); } | ||
109 | size_type leaf_nodes() const { return tree_.leaf_nodes(); } | ||
110 | size_type nodes() const { return tree_.nodes(); } | ||
111 | size_type bytes_used() const { return tree_.bytes_used(); } | ||
112 | static double average_bytes_per_value() { | ||
113 | return Tree::average_bytes_per_value(); | ||
114 | } | ||
115 | double fullness() const { return tree_.fullness(); } | ||
116 | double overhead() const { return tree_.overhead(); } | ||
117 | |||
118 | bool operator==(const self_type& x) const { | ||
119 | if (size() != x.size()) { | ||
120 | return false; | ||
121 | } | ||
122 | for (const_iterator i = begin(), xi = x.begin(); i != end(); ++i, ++xi) { | ||
123 | if (*i != *xi) { | ||
124 | return false; | ||
125 | } | ||
126 | } | ||
127 | return true; | ||
128 | } | ||
129 | |||
130 | bool operator!=(const self_type& other) const { | ||
131 | return !operator==(other); | ||
132 | } | ||
133 | |||
134 | |||
135 | protected: | ||
136 | Tree tree_; | ||
137 | }; | ||
138 | |||
139 | template <typename T> | ||
140 | inline std::ostream& operator<<(std::ostream &os, const btree_container<T> &b) { | ||
141 | b.dump(os); | ||
142 | return os; | ||
143 | } | ||
144 | |||
145 | // A common base class for btree_set and safe_btree_set. | ||
146 | template <typename Tree> | ||
147 | class btree_unique_container : public btree_container<Tree> { | ||
148 | typedef btree_unique_container<Tree> self_type; | ||
149 | typedef btree_container<Tree> super_type; | ||
150 | |||
151 | public: | ||
152 | typedef typename Tree::key_type key_type; | ||
153 | typedef typename Tree::value_type value_type; | ||
154 | typedef typename Tree::size_type size_type; | ||
155 | typedef typename Tree::key_compare key_compare; | ||
156 | typedef typename Tree::allocator_type allocator_type; | ||
157 | typedef typename Tree::iterator iterator; | ||
158 | typedef typename Tree::const_iterator const_iterator; | ||
159 | |||
160 | public: | ||
161 | // Default constructor. | ||
162 | btree_unique_container(const key_compare &comp = key_compare(), | ||
163 | const allocator_type &alloc = allocator_type()) | ||
164 | : super_type(comp, alloc) { | ||
165 | } | ||
166 | |||
167 | // Copy constructor. | ||
168 | btree_unique_container(const self_type &x) | ||
169 | : super_type(x) { | ||
170 | } | ||
171 | |||
172 | // Range constructor. | ||
173 | template <class InputIterator> | ||
174 | btree_unique_container(InputIterator b, InputIterator e, | ||
175 | const key_compare &comp = key_compare(), | ||
176 | const allocator_type &alloc = allocator_type()) | ||
177 | : super_type(comp, alloc) { | ||
178 | insert(b, e); | ||
179 | } | ||
180 | |||
181 | // Lookup routines. | ||
182 | iterator find(const key_type &key) { | ||
183 | return this->tree_.find_unique(key); | ||
184 | } | ||
185 | const_iterator find(const key_type &key) const { | ||
186 | return this->tree_.find_unique(key); | ||
187 | } | ||
188 | size_type count(const key_type &key) const { | ||
189 | return this->tree_.count_unique(key); | ||
190 | } | ||
191 | |||
192 | // Insertion routines. | ||
193 | std::pair<iterator,bool> insert(const value_type &x) { | ||
194 | return this->tree_.insert_unique(x); | ||
195 | } | ||
196 | iterator insert(iterator position, const value_type &x) { | ||
197 | return this->tree_.insert_unique(position, x); | ||
198 | } | ||
199 | template <typename InputIterator> | ||
200 | void insert(InputIterator b, InputIterator e) { | ||
201 | this->tree_.insert_unique(b, e); | ||
202 | } | ||
203 | |||
204 | // Deletion routines. | ||
205 | int erase(const key_type &key) { | ||
206 | return this->tree_.erase_unique(key); | ||
207 | } | ||
208 | // Erase the specified iterator from the btree. The iterator must be valid | ||
209 | // (i.e. not equal to end()). Return an iterator pointing to the node after | ||
210 | // the one that was erased (or end() if none exists). | ||
211 | iterator erase(const iterator &iter) { | ||
212 | return this->tree_.erase(iter); | ||
213 | } | ||
214 | void erase(const iterator &first, const iterator &last) { | ||
215 | this->tree_.erase(first, last); | ||
216 | } | ||
217 | }; | ||
218 | |||
219 | // A common base class for btree_map and safe_btree_map. | ||
220 | template <typename Tree> | ||
221 | class btree_map_container : public btree_unique_container<Tree> { | ||
222 | typedef btree_map_container<Tree> self_type; | ||
223 | typedef btree_unique_container<Tree> super_type; | ||
224 | |||
225 | public: | ||
226 | typedef typename Tree::key_type key_type; | ||
227 | typedef typename Tree::data_type data_type; | ||
228 | typedef typename Tree::value_type value_type; | ||
229 | typedef typename Tree::mapped_type mapped_type; | ||
230 | typedef typename Tree::key_compare key_compare; | ||
231 | typedef typename Tree::allocator_type allocator_type; | ||
232 | |||
233 | private: | ||
234 | // A pointer-like object which only generates its value when | ||
235 | // dereferenced. Used by operator[] to avoid constructing an empty data_type | ||
236 | // if the key already exists in the map. | ||
237 | struct generate_value { | ||
238 | generate_value(const key_type &k) | ||
239 | : key(k) { | ||
240 | } | ||
241 | value_type operator*() const { | ||
242 | return std::make_pair(key, data_type()); | ||
243 | } | ||
244 | const key_type &key; | ||
245 | }; | ||
246 | |||
247 | public: | ||
248 | // Default constructor. | ||
249 | btree_map_container(const key_compare &comp = key_compare(), | ||
250 | const allocator_type &alloc = allocator_type()) | ||
251 | : super_type(comp, alloc) { | ||
252 | } | ||
253 | |||
254 | // Copy constructor. | ||
255 | btree_map_container(const self_type &x) | ||
256 | : super_type(x) { | ||
257 | } | ||
258 | |||
259 | // Range constructor. | ||
260 | template <class InputIterator> | ||
261 | btree_map_container(InputIterator b, InputIterator e, | ||
262 | const key_compare &comp = key_compare(), | ||
263 | const allocator_type &alloc = allocator_type()) | ||
264 | : super_type(b, e, comp, alloc) { | ||
265 | } | ||
266 | |||
267 | // Insertion routines. | ||
268 | data_type& operator[](const key_type &key) { | ||
269 | return this->tree_.insert_unique(key, generate_value(key)).first->second; | ||
270 | } | ||
271 | }; | ||
272 | |||
273 | // A common base class for btree_multiset and btree_multimap. | ||
274 | template <typename Tree> | ||
275 | class btree_multi_container : public btree_container<Tree> { | ||
276 | typedef btree_multi_container<Tree> self_type; | ||
277 | typedef btree_container<Tree> super_type; | ||
278 | |||
279 | public: | ||
280 | typedef typename Tree::key_type key_type; | ||
281 | typedef typename Tree::value_type value_type; | ||
282 | typedef typename Tree::size_type size_type; | ||
283 | typedef typename Tree::key_compare key_compare; | ||
284 | typedef typename Tree::allocator_type allocator_type; | ||
285 | typedef typename Tree::iterator iterator; | ||
286 | typedef typename Tree::const_iterator const_iterator; | ||
287 | |||
288 | public: | ||
289 | // Default constructor. | ||
290 | btree_multi_container(const key_compare &comp = key_compare(), | ||
291 | const allocator_type &alloc = allocator_type()) | ||
292 | : super_type(comp, alloc) { | ||
293 | } | ||
294 | |||
295 | // Copy constructor. | ||
296 | btree_multi_container(const self_type &x) | ||
297 | : super_type(x) { | ||
298 | } | ||
299 | |||
300 | // Range constructor. | ||
301 | template <class InputIterator> | ||
302 | btree_multi_container(InputIterator b, InputIterator e, | ||
303 | const key_compare &comp = key_compare(), | ||
304 | const allocator_type &alloc = allocator_type()) | ||
305 | : super_type(comp, alloc) { | ||
306 | insert(b, e); | ||
307 | } | ||
308 | |||
309 | // Lookup routines. | ||
310 | iterator find(const key_type &key) { | ||
311 | return this->tree_.find_multi(key); | ||
312 | } | ||
313 | const_iterator find(const key_type &key) const { | ||
314 | return this->tree_.find_multi(key); | ||
315 | } | ||
316 | size_type count(const key_type &key) const { | ||
317 | return this->tree_.count_multi(key); | ||
318 | } | ||
319 | |||
320 | // Insertion routines. | ||
321 | iterator insert(const value_type &x) { | ||
322 | return this->tree_.insert_multi(x); | ||
323 | } | ||
324 | iterator insert(iterator position, const value_type &x) { | ||
325 | return this->tree_.insert_multi(position, x); | ||
326 | } | ||
327 | template <typename InputIterator> | ||
328 | void insert(InputIterator b, InputIterator e) { | ||
329 | this->tree_.insert_multi(b, e); | ||
330 | } | ||
331 | |||
332 | // Deletion routines. | ||
333 | int erase(const key_type &key) { | ||
334 | return this->tree_.erase_multi(key); | ||
335 | } | ||
336 | // Erase the specified iterator from the btree. The iterator must be valid | ||
337 | // (i.e. not equal to end()). Return an iterator pointing to the node after | ||
338 | // the one that was erased (or end() if none exists). | ||
339 | iterator erase(const iterator &iter) { | ||
340 | return this->tree_.erase(iter); | ||
341 | } | ||
342 | void erase(const iterator &first, const iterator &last) { | ||
343 | this->tree_.erase(first, last); | ||
344 | } | ||
345 | }; | ||
346 | |||
347 | } // namespace btree | ||
348 | |||
349 | #endif // UTIL_BTREE_BTREE_CONTAINER_H__ | ||