multi_index/detail/copy_map.hpp

0001 /* Copyright 2003-2022 Joaquin M Lopez Munoz.
0002  * Distributed under the Boost Software License, Version 1.0.
0003  * (See accompanying file LICENSE_1_0.txt or copy at
0004  * http://www.boost.org/LICENSE_1_0.txt)
0005  *
0006  * See http://www.boost.org/libs/multi_index for library home page.
0007  */
0008
0009 #ifndef BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP
0010 #define BOOST_MULTI_INDEX_DETAIL_COPY_MAP_HPP
0011
0012 #if defined(_MSC_VER)
0013 #pragma once
0014 #endif
0015
0016 #include <boost/config.hpp> /* keep it first to prevent nasty warns in MSVC */
0017 #include <algorithm>
0018 #include <boost/core/addressof.hpp>
0019 #include <boost/core/no_exceptions_support.hpp>
0020 #include <boost/core/noncopyable.hpp>
0021 #include <boost/move/core.hpp>
0022 #include <boost/move/utility_core.hpp>
0023 #include <boost/multi_index/detail/allocator_traits.hpp>
0024 #include <boost/multi_index/detail/auto_space.hpp>
0025 #include <boost/multi_index/detail/raw_ptr.hpp>
0026 #include <functional>
0027
0028 namespace boost{
0029
0030 namespace multi_index{
0031
0032 namespace detail{
0033
0034 /* copy_map is used as an auxiliary structure during copy_() operations.
0035  * When a container with n nodes is replicated, node_map holds the pairings
0036  * between original and copied nodes, and provides a fast way to find a
0037  * copied node from an original one.
0038  * The semantics of the class are not simple, and no attempt has been made
0039  * to enforce it: multi_index_container handles it right. On the other hand,
0040  * the const interface, which is the one provided to index implementations,
0041  * only allows for:
0042  *   - Enumeration of pairs of (original,copied) nodes (excluding the headers),
0043  *   - fast retrieval of copied nodes (including the headers.)
0044  */
0045
0046 template <typename Node>
0047 struct copy_map_entry
0048 {
0049   copy_map_entry(Node* f,Node* s):first(f),second(s){}
0050
0051   Node* first;
0052   Node* second;
0053
0054   bool operator<(const copy_map_entry<Node>& x)const
0055   {
0056     return std::less<Node*>()(first,x.first);
0057   }
0058 };
0059
0060 struct copy_map_value_copier
0061 {
0062   template<typename Value>
0063   const Value& operator()(Value& x)const{return x;}
0064 };
0065
0066 struct copy_map_value_mover
0067 {
0068   template<typename Value>
0069   BOOST_RV_REF(Value) operator()(Value& x)const{return boost::move(x);}
0070 };
0071
0072 template <typename Node,typename Allocator>
0073 class copy_map:private noncopyable
0074 {
0075   typedef typename rebind_alloc_for<
0076     Allocator,Node
0077   >::type                                  allocator_type;
0078   typedef allocator_traits<allocator_type> alloc_traits;
0079   typedef typename alloc_traits::pointer   pointer;
0080
0081 public:
0082   typedef const copy_map_entry<Node>*      const_iterator;
0083   typedef typename alloc_traits::size_type size_type;
0084
0085   copy_map(
0086     const Allocator& al,size_type size,Node* header_org,Node* header_cpy):
0087     al_(al),size_(size),spc(al_,size_),n(0),
0088     header_org_(header_org),header_cpy_(header_cpy),released(false)
0089   {}
0090
0091   ~copy_map()
0092   {
0093     if(!released){
0094       for(size_type i=0;i<n;++i){
0095         alloc_traits::destroy(
0096           al_,boost::addressof((spc.data()+i)->second->value()));
0097         deallocate((spc.data()+i)->second);
0098       }
0099     }
0100   }
0101
0102   const_iterator begin()const{return raw_ptr<const_iterator>(spc.data());}
0103   const_iterator end()const{return raw_ptr<const_iterator>(spc.data()+n);}
0104
0105   void copy_clone(Node* node){clone(node,copy_map_value_copier());}
0106   void move_clone(Node* node){clone(node,copy_map_value_mover());}
0107
0108   Node* find(Node* node)const
0109   {
0110     if(node==header_org_)return header_cpy_;
0111     return std::lower_bound(
0112       begin(),end(),copy_map_entry<Node>(node,0))->second;
0113   }
0114
0115   void release()
0116   {
0117     released=true;
0118   }
0119
0120 private:
0121   allocator_type                             al_;
0122   size_type                                  size_;
0123   auto_space<copy_map_entry<Node>,Allocator> spc;
0124   size_type                                  n;
0125   Node*                                      header_org_;
0126   Node*                                      header_cpy_;
0127   bool                                       released;
0128
0129   pointer allocate()
0130   {
0131     return alloc_traits::allocate(al_,1);
0132   }
0133
0134   void deallocate(Node* node)
0135   {
0136     alloc_traits::deallocate(al_,static_cast<pointer>(node),1);
0137   }
0138
0139   template<typename ValueAccess>
0140   void clone(Node* node,ValueAccess access)
0141   {
0142     (spc.data()+n)->first=node;
0143     (spc.data()+n)->second=raw_ptr<Node*>(allocate());
0144     BOOST_TRY{
0145       alloc_traits::construct(
0146         al_,boost::addressof((spc.data()+n)->second->value()),
0147         access(node->value()));
0148     }
0149     BOOST_CATCH(...){
0150       deallocate((spc.data()+n)->second);
0151       BOOST_RETHROW;
0152     }
0153     BOOST_CATCH_END
0154     ++n;
0155
0156     if(n==size_){
0157       std::sort(
0158         raw_ptr<copy_map_entry<Node>*>(spc.data()),
0159         raw_ptr<copy_map_entry<Node>*>(spc.data())+size_);
0160     }
0161   }
0162 };
0163
0164 } /* namespace multi_index::detail */
0165
0166 } /* namespace multi_index */
0167
0168 } /* namespace boost */
0169
0170 #endif