1/* Copyright 2003-2015 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/detail/no_exceptions_support.hpp>
19#include <boost/multi_index/detail/auto_space.hpp>
20#include <boost/multi_index/detail/raw_ptr.hpp>
21#include <boost/noncopyable.hpp>
22#include <cstddef>
23#include <functional>
24
25namespace boost{
26
27namespace multi_index{
28
29namespace detail{
30
31/* copy_map is used as an auxiliary structure during copy_() operations.
32 * When a container with n nodes is replicated, node_map holds the pairings
33 * between original and copied nodes, and provides a fast way to find a
34 * copied node from an original one.
35 * The semantics of the class are not simple, and no attempt has been made
36 * to enforce it: multi_index_container handles it right. On the other hand,
37 * the const interface, which is the one provided to index implementations,
38 * only allows for:
39 * - Enumeration of pairs of (original,copied) nodes (excluding the headers),
40 * - fast retrieval of copied nodes (including the headers.)
41 */
42
43template <typename Node>
44struct copy_map_entry
45{
46 copy_map_entry(Node* f,Node* s):first(f),second(s){}
47
48 Node* first;
49 Node* second;
50
51 bool operator<(const copy_map_entry<Node>& x)const
52 {
53 return std::less<Node*>()(first,x.first);
54 }
55};
56
57template <typename Node,typename Allocator>
58class copy_map:private noncopyable
59{
60public:
61 typedef const copy_map_entry<Node>* const_iterator;
62
63 copy_map(
64 const Allocator& al,std::size_t size,Node* header_org,Node* header_cpy):
65 al_(al),size_(size),spc(al_,size_),n(0),
66 header_org_(header_org),header_cpy_(header_cpy),released(false)
67 {}
68
69 ~copy_map()
70 {
71 if(!released){
72 for(std::size_t i=0;i<n;++i){
73 boost::detail::allocator::destroy(&(spc.data()+i)->second->value());
74 deallocate((spc.data()+i)->second);
75 }
76 }
77 }
78
79 const_iterator begin()const{return raw_ptr<const_iterator>(spc.data());}
80 const_iterator end()const{return raw_ptr<const_iterator>(spc.data()+n);}
81
82 void clone(Node* node)
83 {
84 (spc.data()+n)->first=node;
85 (spc.data()+n)->second=raw_ptr<Node*>(al_.allocate(1));
86 BOOST_TRY{
87 boost::detail::allocator::construct(
88 &(spc.data()+n)->second->value(),node->value());
89 }
90 BOOST_CATCH(...){
91 deallocate((spc.data()+n)->second);
92 BOOST_RETHROW;
93 }
94 BOOST_CATCH_END
95 ++n;
96
97 if(n==size_){
98 std::sort(
99 raw_ptr<copy_map_entry<Node>*>(spc.data()),
100 raw_ptr<copy_map_entry<Node>*>(spc.data())+size_);
101 }
102 }
103
104 Node* find(Node* node)const
105 {
106 if(node==header_org_)return header_cpy_;
107 return std::lower_bound(
108 begin(),end(),copy_map_entry<Node>(node,0))->second;
109 }
110
111 void release()
112 {
113 released=true;
114 }
115
116private:
117 typedef typename boost::detail::allocator::rebind_to<
118 Allocator,Node
119 >::type allocator_type;
120 typedef typename allocator_type::pointer allocator_pointer;
121
122 allocator_type al_;
123 std::size_t size_;
124 auto_space<copy_map_entry<Node>,Allocator> spc;
125 std::size_t n;
126 Node* header_org_;
127 Node* header_cpy_;
128 bool released;
129
130 void deallocate(Node* node)
131 {
132 al_.deallocate(static_cast<allocator_pointer>(node),1);
133 }
134};
135
136} /* namespace multi_index::detail */
137
138} /* namespace multi_index */
139
140} /* namespace boost */
141
142#endif
143