ceph/src/include/cpp-btree/btree_container.h

   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__