1 /* Copyright 2003-2020 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/move/core.hpp>
21 #include <boost/move/utility_core.hpp>
22 #include <boost/multi_index/detail/allocator_traits.hpp>
23 #include <boost/multi_index/detail/auto_space.hpp>
24 #include <boost/multi_index/detail/raw_ptr.hpp>
25 #include <boost/noncopyable.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 {
copy_map_entryboost::multi_index::detail::copy_map_entry49   copy_map_entry(Node* f,Node* s):first(f),second(s){}
50 
51   Node* first;
52   Node* second;
53 
operator <boost::multi_index::detail::copy_map_entry54   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>
operator ()boost::multi_index::detail::copy_map_value_copier63   const Value& operator()(Value& x)const{return x;}
64 };
65 
66 struct copy_map_value_mover
67 {
68   template<typename Value>
BOOST_RV_REFboost::multi_index::detail::copy_map_value_mover69   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 
copy_map(const Allocator & al,size_type size,Node * header_org,Node * header_cpy)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 
~copy_map()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 
begin() const102   const_iterator begin()const{return raw_ptr<const_iterator>(spc.data());}
end() const103   const_iterator end()const{return raw_ptr<const_iterator>(spc.data()+n);}
104 
copy_clone(Node * node)105   void copy_clone(Node* node){clone(node,copy_map_value_copier());}
move_clone(Node * node)106   void move_clone(Node* node){clone(node,copy_map_value_mover());}
107 
find(Node * node) const108   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 
release()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 
allocate()129   pointer allocate()
130   {
131     return alloc_traits::allocate(al_,1);
132   }
133 
deallocate(Node * node)134   void deallocate(Node* node)
135   {
136     alloc_traits::deallocate(al_,static_cast<pointer>(node),1);
137   }
138 
139   template<typename ValueAccess>
clone(Node * node,ValueAccess access)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
171