summaryrefslogtreecommitdiff
path: root/xdelta3/cpp-btree/btree_container.h
diff options
context:
space:
mode:
Diffstat (limited to 'xdelta3/cpp-btree/btree_container.h')
-rw-r--r--xdelta3/cpp-btree/btree_container.h349
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
23namespace btree {
24
25// A common base class for btree_set, btree_map, btree_multiset and
26// btree_multimap.
27template <typename Tree>
28class 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
139template <typename T>
140inline 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.
146template <typename Tree>
147class 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.
220template <typename Tree>
221class 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.
274template <typename Tree>
275class 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__