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