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
28namespace boost{
29
30namespace multi_index{
31
32namespace 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
46template <typename Node>
47struct 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
60struct copy_map_value_copier
61{
62 template<typename Value>
63 const Value& operator()(Value& x)const{return x;}
64};
65
66struct copy_map_value_mover
67{
68 template<typename Value>
69 BOOST_RV_REF(Value) operator()(Value& x)const{return boost::move(x);}
70};
71
72template <typename Node,typename Allocator>
73class 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
81public:
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(node: (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
120private:
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(node: (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