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 26 // A common base class for btree_set, btree_map, btree_multiset and 27 // btree_multimap. 28 template <typename Tree> 29 class btree_container 30 { 31 typedef btree_container<Tree> self_type; 32 33 public: 34 typedef typename Tree::params_type params_type; 35 typedef typename Tree::key_type key_type; 36 typedef typename Tree::value_type value_type; 37 typedef typename Tree::key_compare key_compare; 38 typedef typename Tree::allocator_type allocator_type; 39 typedef typename Tree::pointer pointer; 40 typedef typename Tree::const_pointer const_pointer; 41 typedef typename Tree::reference reference; 42 typedef typename Tree::const_reference const_reference; 43 typedef typename Tree::size_type size_type; 44 typedef typename Tree::difference_type difference_type; 45 typedef typename Tree::iterator iterator; 46 typedef typename Tree::const_iterator const_iterator; 47 typedef typename Tree::reverse_iterator reverse_iterator; 48 typedef typename Tree::const_reverse_iterator const_reverse_iterator; 49 50 public: 51 // Default constructor. btree_container(const key_compare & comp,const allocator_type & alloc)52 btree_container(const key_compare& comp, const allocator_type& alloc) 53 : tree_(comp, alloc) 54 { 55 } 56 57 // Copy constructor. btree_container(const self_type & x)58 btree_container(const self_type& x) 59 : tree_(x.tree_) 60 { 61 } 62 63 // Iterator routines. begin()64 iterator begin() 65 { 66 return tree_.begin(); 67 } begin()68 const_iterator begin() const 69 { 70 return tree_.begin(); 71 } end()72 iterator end() 73 { 74 return tree_.end(); 75 } end()76 const_iterator end() const 77 { 78 return tree_.end(); 79 } rbegin()80 reverse_iterator rbegin() 81 { 82 return tree_.rbegin(); 83 } rbegin()84 const_reverse_iterator rbegin() const 85 { 86 return tree_.rbegin(); 87 } rend()88 reverse_iterator rend() 89 { 90 return tree_.rend(); 91 } rend()92 const_reverse_iterator rend() const 93 { 94 return tree_.rend(); 95 } 96 97 // Lookup routines. lower_bound(const key_type & key)98 iterator lower_bound(const key_type& key) 99 { 100 return tree_.lower_bound(key); 101 } lower_bound(const key_type & key)102 const_iterator lower_bound(const key_type& key) const 103 { 104 return tree_.lower_bound(key); 105 } upper_bound(const key_type & key)106 iterator upper_bound(const key_type& key) 107 { 108 return tree_.upper_bound(key); 109 } upper_bound(const key_type & key)110 const_iterator upper_bound(const key_type& key) const 111 { 112 return tree_.upper_bound(key); 113 } equal_range(const key_type & key)114 std::pair<iterator, iterator> equal_range(const key_type& key) 115 { 116 return tree_.equal_range(key); 117 } equal_range(const key_type & key)118 std::pair<const_iterator, const_iterator> equal_range(const key_type& key) const 119 { 120 return tree_.equal_range(key); 121 } 122 123 // Utility routines. clear()124 void clear() 125 { 126 tree_.clear(); 127 } swap(self_type & x)128 void swap(self_type& x) 129 { 130 tree_.swap(x.tree_); 131 } dump(std::ostream & os)132 void dump(std::ostream& os) const 133 { 134 tree_.dump(os); 135 } verify()136 void verify() const 137 { 138 tree_.verify(); 139 } 140 141 // Size routines. size()142 size_type size() const 143 { 144 return tree_.size(); 145 } max_size()146 size_type max_size() const 147 { 148 return tree_.max_size(); 149 } empty()150 bool empty() const 151 { 152 return tree_.empty(); 153 } height()154 size_type height() const 155 { 156 return tree_.height(); 157 } internal_nodes()158 size_type internal_nodes() const 159 { 160 return tree_.internal_nodes(); 161 } leaf_nodes()162 size_type leaf_nodes() const 163 { 164 return tree_.leaf_nodes(); 165 } nodes()166 size_type nodes() const 167 { 168 return tree_.nodes(); 169 } bytes_used()170 size_type bytes_used() const 171 { 172 return tree_.bytes_used(); 173 } average_bytes_per_value()174 static double average_bytes_per_value() 175 { 176 return Tree::average_bytes_per_value(); 177 } fullness()178 double fullness() const 179 { 180 return tree_.fullness(); 181 } overhead()182 double overhead() const 183 { 184 return tree_.overhead(); 185 } 186 187 bool operator==(const self_type& x) const 188 { 189 if (size() != x.size()) 190 { 191 return false; 192 } 193 194 for (const_iterator i = begin(), xi = x.begin(); i != end(); ++i, ++xi) 195 { 196 if (*i != *xi) 197 { 198 return false; 199 } 200 } 201 202 return true; 203 } 204 205 bool operator!=(const self_type& other) const 206 { 207 return !operator==(other); 208 } 209 210 211 protected: 212 Tree tree_; 213 }; 214 215 template <typename T> 216 inline std::ostream& operator<<(std::ostream& os, const btree_container<T>& b) 217 { 218 b.dump(os); 219 return os; 220 } 221 222 // A common base class for btree_set and safe_btree_set. 223 template <typename Tree> 224 class btree_unique_container : public btree_container<Tree> 225 { 226 typedef btree_unique_container<Tree> self_type; 227 typedef btree_container<Tree> super_type; 228 229 public: 230 typedef typename Tree::key_type key_type; 231 typedef typename Tree::value_type value_type; 232 typedef typename Tree::size_type size_type; 233 typedef typename Tree::key_compare key_compare; 234 typedef typename Tree::allocator_type allocator_type; 235 typedef typename Tree::iterator iterator; 236 typedef typename Tree::const_iterator const_iterator; 237 238 public: 239 // Default constructor. 240 btree_unique_container(const key_compare& comp = key_compare(), 241 const allocator_type& alloc = allocator_type()) super_type(comp,alloc)242 : super_type(comp, alloc) 243 { 244 } 245 246 // Copy constructor. btree_unique_container(const self_type & x)247 btree_unique_container(const self_type& x) 248 : super_type(x) 249 { 250 } 251 252 // Range constructor. 253 template <class InputIterator> 254 btree_unique_container(InputIterator b, InputIterator e, 255 const key_compare& comp = key_compare(), 256 const allocator_type& alloc = allocator_type()) super_type(comp,alloc)257 : super_type(comp, alloc) 258 { 259 insert(b, e); 260 } 261 262 // Lookup routines. find(const key_type & key)263 iterator find(const key_type& key) 264 { 265 return this->tree_.find_unique(key); 266 } find(const key_type & key)267 const_iterator find(const key_type& key) const 268 { 269 return this->tree_.find_unique(key); 270 } count(const key_type & key)271 size_type count(const key_type& key) const 272 { 273 return this->tree_.count_unique(key); 274 } 275 276 // Insertion routines. insert(const value_type & x)277 std::pair<iterator, bool> insert(const value_type& x) 278 { 279 return this->tree_.insert_unique(x); 280 } insert(iterator position,const value_type & x)281 iterator insert(iterator position, const value_type& x) 282 { 283 return this->tree_.insert_unique(position, x); 284 } 285 template <typename InputIterator> insert(InputIterator b,InputIterator e)286 void insert(InputIterator b, InputIterator e) 287 { 288 this->tree_.insert_unique(b, e); 289 } 290 291 // Deletion routines. erase(const key_type & key)292 int erase(const key_type& key) 293 { 294 return this->tree_.erase_unique(key); 295 } 296 // Erase the specified iterator from the btree. The iterator must be valid 297 // (i.e. not equal to end()). Return an iterator pointing to the node after 298 // the one that was erased (or end() if none exists). erase(const iterator & iter)299 iterator erase(const iterator& iter) 300 { 301 return this->tree_.erase(iter); 302 } erase(const iterator & first,const iterator & last)303 void erase(const iterator& first, const iterator& last) 304 { 305 this->tree_.erase(first, last); 306 } 307 }; 308 309 // A common base class for btree_map and safe_btree_map. 310 template <typename Tree> 311 class btree_map_container : public btree_unique_container<Tree> 312 { 313 typedef btree_map_container<Tree> self_type; 314 typedef btree_unique_container<Tree> super_type; 315 316 public: 317 typedef typename Tree::key_type key_type; 318 typedef typename Tree::data_type data_type; 319 typedef typename Tree::value_type value_type; 320 typedef typename Tree::mapped_type mapped_type; 321 typedef typename Tree::key_compare key_compare; 322 typedef typename Tree::allocator_type allocator_type; 323 324 private: 325 // A pointer-like object which only generates its value when 326 // dereferenced. Used by operator[] to avoid constructing an empty data_type 327 // if the key already exists in the map. 328 struct generate_value 329 { generate_valuegenerate_value330 generate_value(const key_type& k) 331 : key(k) 332 { 333 } 334 value_type operator*() const 335 { 336 return std::make_pair(key, data_type()); 337 } 338 const key_type& key; 339 }; 340 341 public: 342 // Default constructor. 343 btree_map_container(const key_compare& comp = key_compare(), 344 const allocator_type& alloc = allocator_type()) super_type(comp,alloc)345 : super_type(comp, alloc) 346 { 347 } 348 349 // Copy constructor. btree_map_container(const self_type & x)350 btree_map_container(const self_type& x) 351 : super_type(x) 352 { 353 } 354 355 // Range constructor. 356 template <class InputIterator> 357 btree_map_container(InputIterator b, InputIterator e, 358 const key_compare& comp = key_compare(), 359 const allocator_type& alloc = allocator_type()) super_type(b,e,comp,alloc)360 : super_type(b, e, comp, alloc) 361 { 362 } 363 364 // Insertion routines. 365 data_type& operator[](const key_type& key) 366 { 367 return this->tree_.insert_unique(key, generate_value(key)).first->second; 368 } 369 }; 370 371 // A common base class for btree_multiset and btree_multimap. 372 template <typename Tree> 373 class btree_multi_container : public btree_container<Tree> 374 { 375 typedef btree_multi_container<Tree> self_type; 376 typedef btree_container<Tree> super_type; 377 378 public: 379 typedef typename Tree::key_type key_type; 380 typedef typename Tree::value_type value_type; 381 typedef typename Tree::size_type size_type; 382 typedef typename Tree::key_compare key_compare; 383 typedef typename Tree::allocator_type allocator_type; 384 typedef typename Tree::iterator iterator; 385 typedef typename Tree::const_iterator const_iterator; 386 387 public: 388 // Default constructor. 389 btree_multi_container(const key_compare& comp = key_compare(), 390 const allocator_type& alloc = allocator_type()) super_type(comp,alloc)391 : super_type(comp, alloc) 392 { 393 } 394 395 // Copy constructor. btree_multi_container(const self_type & x)396 btree_multi_container(const self_type& x) 397 : super_type(x) 398 { 399 } 400 401 // Range constructor. 402 template <class InputIterator> 403 btree_multi_container(InputIterator b, InputIterator e, 404 const key_compare& comp = key_compare(), 405 const allocator_type& alloc = allocator_type()) super_type(comp,alloc)406 : super_type(comp, alloc) 407 { 408 insert(b, e); 409 } 410 411 // Lookup routines. find(const key_type & key)412 iterator find(const key_type& key) 413 { 414 return this->tree_.find_multi(key); 415 } find(const key_type & key)416 const_iterator find(const key_type& key) const 417 { 418 return this->tree_.find_multi(key); 419 } count(const key_type & key)420 size_type count(const key_type& key) const 421 { 422 return this->tree_.count_multi(key); 423 } 424 425 // Insertion routines. insert(const value_type & x)426 iterator insert(const value_type& x) 427 { 428 return this->tree_.insert_multi(x); 429 } insert(iterator position,const value_type & x)430 iterator insert(iterator position, const value_type& x) 431 { 432 return this->tree_.insert_multi(position, x); 433 } 434 template <typename InputIterator> insert(InputIterator b,InputIterator e)435 void insert(InputIterator b, InputIterator e) 436 { 437 this->tree_.insert_multi(b, e); 438 } 439 440 // Deletion routines. erase(const key_type & key)441 int erase(const key_type& key) 442 { 443 return this->tree_.erase_multi(key); 444 } 445 // Erase the specified iterator from the btree. The iterator must be valid 446 // (i.e. not equal to end()). Return an iterator pointing to the node after 447 // the one that was erased (or end() if none exists). erase(const iterator & iter)448 iterator erase(const iterator& iter) 449 { 450 return this->tree_.erase(iter); 451 } erase(const iterator & first,const iterator & last)452 void erase(const iterator& first, const iterator& last) 453 { 454 this->tree_.erase(first, last); 455 } 456 }; 457 458 } // namespace btree 459 460 #endif // UTIL_BTREE_BTREE_CONTAINER_H__ 461