ceph/src/boost/boost/multi_index/detail/copy_map.hpp

   1 /* Copyright 2003-2022 Joaquin M Lopez Munoz.
   2  * Distributed under the Boost Software License, Version 1.0.
   3  * (See accompanying file LICENSE_1_0.txt or copy at
   4  * http://www.boost.org/LICENSE_1_0.txt)
   5  *
   6  * See http://www.boost.org/libs/multi_index for library home page.
   7  */
   8
   9 #ifndef BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP
  10 #define BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP
  11
  12 #if defined(_MSC_VER)
  13 #pragma once
  14 #endif
  15
  16 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
  17 #include <algorithm>
  18 #include <boost/core/addressof.hpp>
  19 #include <boost/core/no_exceptions_support.hpp>
  20 #include <boost/core/noncopyable.hpp>
  21 #include <boost/move/core.hpp>
  22 #include <boost/move/utility_core.hpp>
  23 #include <boost/multi_index/detail/allocator_traits.hpp>
  24 #include <boost/multi_index/detail/auto_space.hpp>
  25 #include <boost/multi_index/detail/raw_ptr.hpp>
  26 #include <functional>
  27
  28 namespace boost{
  29
  30 namespace multi_index{
  31
  32 namespace detail{
  33
  34 /* copy_map is used as an auxiliary structure during copy_() operations.
  35  * When a container with n nodes is replicated, node_map holds the pairings
  36  * between original and copied nodes, and provides a fast way to find a
  37  * copied node from an original one.
  38  * The semantics of the class are not simple, and no attempt has been made
  39  * to enforce it: multi_index_container handles it right. On the other hand,
  40  * the const interface, which is the one provided to index implementations,
  41  * only allows for:
  42  *   - Enumeration of pairs of (original,copied) nodes (excluding the headers),
  43  *   - fast retrieval of copied nodes (including the headers.)
  44  */
  45
  46 template <typename Node>
  47 struct copy_map_entry
  48 {
  49   copy_map_entry(Node* f,Node* s):first(f),second(s){}
  50
  51   Node* first;
  52   Node* second;
  53
  54   bool operator<(const copy_map_entry<Node>& x)const
  55   {
  56     return std::less<Node*>()(first,x.first);
  57   }
  58 };
  59
  60 struct copy_map_value_copier
  61 {
  62   template<typename Value>
  63   const Value& operator()(Value& x)const{return x;}
  64 };
  65
  66 struct copy_map_value_mover
  67 {
  68   template<typename Value>
  69   BOOST_RV_REF(Value) operator()(Value& x)const{return boost::move(x);}
  70 };
  71
  72 template <typename Node,typename Allocator>
  73 class copy_map:private noncopyable
  74 {
  75   typedef typename rebind_alloc_for<
  76     Allocator,Node
  77   >::type                                  allocator_type;
  78   typedef allocator_traits<allocator_type> alloc_traits;
  79   typedef typename alloc_traits::pointer   pointer;
  80
  81 public:
  82   typedef const copy_map_entry<Node>*      const_iterator;
  83   typedef typename alloc_traits::size_type size_type;
  84
  85   copy_map(
  86     const Allocator& al,size_type size,Node* header_org,Node* header_cpy):
  87     al_(al),size_(size),spc(al_,size_),n(0),
  88     header_org_(header_org),header_cpy_(header_cpy),released(false)
  89   {}
  90
  91   ~copy_map()
  92   {
  93     if(!released){
  94       for(size_type i=0;i<n;++i){
  95         alloc_traits::destroy(
  96           al_,boost::addressof((spc.data()+i)->second->value()));
  97         deallocate((spc.data()+i)->second);
  98       }
  99     }
 100   }
 101
 102   const_iterator begin()const{return raw_ptr<const_iterator>(spc.data());}
 103   const_iterator end()const{return raw_ptr<const_iterator>(spc.data()+n);}
 104
 105   void copy_clone(Node* node){clone(node,copy_map_value_copier());}
 106   void move_clone(Node* node){clone(node,copy_map_value_mover());}
 107
 108   Node* find(Node* node)const
 109   {
 110     if(node==header_org_)return header_cpy_;
 111     return std::lower_bound(
 112       begin(),end(),copy_map_entry<Node>(node,0))->second;
 113   }
 114
 115   void release()
 116   {
 117     released=true;
 118   }
 119
 120 private:
 121   allocator_type                             al_;
 122   size_type                                  size_;
 123   auto_space<copy_map_entry<Node>,Allocator> spc;
 124   size_type                                  n;
 125   Node*                                      header_org_;
 126   Node*                                      header_cpy_;
 127   bool                                       released;
 128
 129   pointer allocate()
 130   {
 131     return alloc_traits::allocate(al_,1);
 132   }
 133
 134   void deallocate(Node* node)
 135   {
 136     alloc_traits::deallocate(al_,static_cast<pointer>(node),1);
 137   }
 138
 139   template<typename ValueAccess>
 140   void clone(Node* node,ValueAccess access)
 141   {
 142     (spc.data()+n)->first=node;
 143     (spc.data()+n)->second=raw_ptr<Node*>(allocate());
 144     BOOST_TRY{
 145       alloc_traits::construct(
 146         al_,boost::addressof((spc.data()+n)->second->value()),
 147         access(node->value()));
 148     }
 149     BOOST_CATCH(...){
 150       deallocate((spc.data()+n)->second);
 151       BOOST_RETHROW;
 152     }
 153     BOOST_CATCH_END
 154     ++n;
 155
 156     if(n==size_){
 157       std::sort(
 158         raw_ptr<copy_map_entry<Node>*>(spc.data()),
 159         raw_ptr<copy_map_entry<Node>*>(spc.data())+size_);
 160     }
 161   }
 162 };
 163
 164 } /* namespace multi_index::detail */
 165
 166 } /* namespace multi_index */
 167
 168 } /* namespace boost */
 169
 170 #endif