src/3rdparty/cpp-btree/safe_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 // The safe_btree_map<> is like btree_map<> except that it removes the caveat
  16 // about insertion and deletion invalidating existing iterators at a small cost
  17 // in making iterators larger and slower.
  18 //
  19 // Revalidation occurs whenever an iterator is accessed.  References
  20 // and pointers returned by safe_btree_map<> iterators are not stable,
  21 // they are potentially invalidated by any non-const method on the map.
  22 //
  23 // BEGIN INCORRECT EXAMPLE
  24 //   for (auto i = safe_map->begin(); i != safe_map->end(); ++i) {
  25 //     const T *value = &i->second;  // DO NOT DO THIS
  26 //     [code that modifies safe_map and uses value];
  27 //   }
  28 // END INCORRECT EXAMPLE
  29 #ifndef UTIL_BTREE_SAFE_BTREE_MAP_H__
  30 #define UTIL_BTREE_SAFE_BTREE_MAP_H__
  31
  32 #include <functional>
  33 #include <memory>
  34 #include <utility>
  35
  36 #include "btree_container.h"
  37 #include "btree_map.h"
  38 #include "safe_btree.h"
  39
  40 namespace btree {
  41
  42 // The safe_btree_map class is needed mainly for its constructors.
  43 template <typename Key, typename Value,
  44           typename Compare = std::less<Key>,
  45           typename Alloc = std::allocator<std::pair<const Key, Value> >,
  46           int TargetNodeSize = 256>
  47 class safe_btree_map : public btree_map_container<
  48   safe_btree<btree_map_params<Key, Value, Compare, Alloc, TargetNodeSize> > > {
  49
  50   typedef safe_btree_map<Key, Value, Compare, Alloc, TargetNodeSize> self_type;
  51   typedef btree_map_params<
  52     Key, Value, Compare, Alloc, TargetNodeSize> params_type;
  53   typedef safe_btree<params_type> btree_type;
  54   typedef btree_map_container<btree_type> super_type;
  55
  56  public:
  57   typedef typename btree_type::key_compare key_compare;
  58   typedef typename btree_type::allocator_type allocator_type;
  59
  60  public:
  61   // Default constructor.
  62   safe_btree_map(const key_compare &comp = key_compare(),
  63                  const allocator_type &alloc = allocator_type())
  64       : super_type(comp, alloc) {
  65   }
  66
  67   // Copy constructor.
  68   safe_btree_map(const self_type &x)
  69       : super_type(x) {
  70   }
  71
  72   // Move constructor.
  73   safe_btree_map(self_type &&x)
  74       : super_type() {
  75     this->swap(x);
  76   }
  77
  78   // Copy/move assignment
  79   self_type& operator=(self_type x) {
  80     this->swap(x);
  81     return *this;
  82   }
  83
  84   // Range constructor.
  85   template <class InputIterator>
  86   safe_btree_map(InputIterator b, InputIterator e,
  87                  const key_compare &comp = key_compare(),
  88                  const allocator_type &alloc = allocator_type())
  89       : super_type(b, e, comp, alloc) {
  90   }
  91 };
  92
  93 template <typename K, typename V, typename C, typename A, int N>
  94 inline void swap(safe_btree_map<K, V, C, A, N> &x,
  95                  safe_btree_map<K, V, C, A, N> &y) {
  96   x.swap(y);
  97 }
  98
  99 } // namespace btree
 100
 101 #endif  // UTIL_BTREE_SAFE_BTREE_MAP_H__