ceph/src/include/cpp-btree/btree_map.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 // A btree_map<> implements the STL unique sorted associative container
  16 // interface and the pair associative container interface (a.k.a map<>) using a
  17 // btree. A btree_multimap<> implements the STL multiple sorted associative
  18 // container interface and the pair associtive container interface (a.k.a
  19 // multimap<>) using a btree. See btree.h for details of the btree
  20 // implementation and caveats.
  21
  22 #ifndef UTIL_BTREE_BTREE_MAP_H__
  23 #define UTIL_BTREE_BTREE_MAP_H__
  24
  25 #include <algorithm>
  26 #include <functional>
  27 #include <memory>
  28 #include <string>
  29 #include <utility>
  30
  31 #include "btree.h"
  32 #include "btree_container.h"
  33
  34 namespace btree {
  35
  36 // The btree_map class is needed mainly for its constructors.
  37 template <typename Key, typename Value,
  38           typename Compare = std::less<Key>,
  39           typename Alloc = std::allocator<std::pair<const Key, Value> >,
  40           int TargetNodeSize = 256>
  41 class btree_map : public btree_map_container<
  42   btree<btree_map_params<Key, Value, Compare, Alloc, TargetNodeSize> > > {
  43
  44   typedef btree_map<Key, Value, Compare, Alloc, TargetNodeSize> self_type;
  45   typedef btree_map_params<
  46     Key, Value, Compare, Alloc, TargetNodeSize> params_type;
  47   typedef btree<params_type> btree_type;
  48   typedef btree_map_container<btree_type> super_type;
  49
  50  public:
  51   typedef typename btree_type::key_compare key_compare;
  52   typedef typename btree_type::allocator_type allocator_type;
  53
  54  public:
  55   // Default constructor.
  56   btree_map(const key_compare &comp = key_compare(),
  57             const allocator_type &alloc = allocator_type())
  58       : super_type(comp, alloc) {
  59   }
  60
  61   // Copy constructor.
  62   btree_map(const self_type &x)
  63       : super_type(x) {
  64   }
  65
  66   // Range constructor.
  67   template <class InputIterator>
  68   btree_map(InputIterator b, InputIterator e,
  69             const key_compare &comp = key_compare(),
  70             const allocator_type &alloc = allocator_type())
  71       : super_type(b, e, comp, alloc) {
  72   }
  73 };
  74
  75 template <typename K, typename V, typename C, typename A, int N>
  76 inline void swap(btree_map<K, V, C, A, N> &x,
  77                  btree_map<K, V, C, A, N> &y) {
  78   x.swap(y);
  79 }
  80
  81 // The btree_multimap class is needed mainly for its constructors.
  82 template <typename Key, typename Value,
  83           typename Compare = std::less<Key>,
  84           typename Alloc = std::allocator<std::pair<const Key, Value> >,
  85           int TargetNodeSize = 256>
  86 class btree_multimap : public btree_multi_container<
  87   btree<btree_map_params<Key, Value, Compare, Alloc, TargetNodeSize> > > {
  88
  89   typedef btree_multimap<Key, Value, Compare, Alloc, TargetNodeSize> self_type;
  90   typedef btree_map_params<
  91     Key, Value, Compare, Alloc, TargetNodeSize> params_type;
  92   typedef btree<params_type> btree_type;
  93   typedef btree_multi_container<btree_type> super_type;
  94
  95  public:
  96   typedef typename btree_type::key_compare key_compare;
  97   typedef typename btree_type::allocator_type allocator_type;
  98   typedef typename btree_type::data_type data_type;
  99   typedef typename btree_type::mapped_type mapped_type;
 100
 101  public:
 102   // Default constructor.
 103   btree_multimap(const key_compare &comp = key_compare(),
 104                  const allocator_type &alloc = allocator_type())
 105       : super_type(comp, alloc) {
 106   }
 107
 108   // Copy constructor.
 109   btree_multimap(const self_type &x)
 110       : super_type(x) {
 111   }
 112
 113   // Range constructor.
 114   template <class InputIterator>
 115   btree_multimap(InputIterator b, InputIterator e,
 116                  const key_compare &comp = key_compare(),
 117                  const allocator_type &alloc = allocator_type())
 118       : super_type(b, e, comp, alloc) {
 119   }
 120 };
 121
 122 template <typename K, typename V, typename C, typename A, int N>
 123 inline void swap(btree_multimap<K, V, C, A, N> &x,
 124                  btree_multimap<K, V, C, A, N> &y) {
 125   x.swap(y);
 126 }
 127
 128 } // namespace btree
 129
 130 #endif  // UTIL_BTREE_BTREE_MAP_H__