]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ////////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost | |
4 | // Software License, Version 1.0. (See accompanying file | |
5 | // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) | |
6 | // | |
7 | // See http://www.boost.org/libs/container for documentation. | |
8 | // | |
9 | ////////////////////////////////////////////////////////////////////////////// | |
10 | ||
11 | #ifndef BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_ | |
12 | #define BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_ | |
13 | ||
14 | #ifndef BOOST_CONFIG_HPP | |
15 | # include <boost/config.hpp> | |
16 | #endif | |
17 | ||
18 | #if defined(BOOST_HAS_PRAGMA_ONCE) | |
19 | # pragma once | |
20 | #endif | |
21 | ||
22 | #include <boost/container/detail/config_begin.hpp> | |
23 | #include <boost/container/detail/workaround.hpp> | |
24 | ||
25 | // container | |
26 | #include <boost/container/allocator_traits.hpp> | |
27 | // container/detail | |
28 | #include <boost/container/detail/addressof.hpp> | |
29 | #include <boost/container/detail/alloc_helpers.hpp> | |
30 | #include <boost/container/detail/allocator_version_traits.hpp> | |
31 | #include <boost/container/detail/construct_in_place.hpp> | |
32 | #include <boost/container/detail/destroyers.hpp> | |
b32b8144 | 33 | #include <boost/move/detail/iterator_to_raw_pointer.hpp> |
7c673cae FG |
34 | #include <boost/container/detail/mpl.hpp> |
35 | #include <boost/container/detail/placement_new.hpp> | |
b32b8144 | 36 | #include <boost/move/detail/to_raw_pointer.hpp> |
7c673cae FG |
37 | #include <boost/container/detail/type_traits.hpp> |
38 | #include <boost/container/detail/version_type.hpp> | |
39 | // intrusive | |
40 | #include <boost/intrusive/detail/mpl.hpp> | |
41 | #include <boost/intrusive/options.hpp> | |
42 | // move | |
43 | #include <boost/move/utility_core.hpp> | |
44 | #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
45 | #include <boost/move/detail/fwd_macros.hpp> | |
46 | #endif | |
47 | // other | |
48 | #include <boost/core/no_exceptions_support.hpp> | |
49 | ||
50 | ||
51 | namespace boost { | |
52 | namespace container { | |
11fdf7f2 | 53 | namespace dtl { |
7c673cae FG |
54 | |
55 | BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(value_compare) | |
56 | BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(predicate_type) | |
57 | ||
58 | template<class Allocator, class ICont> | |
59 | struct node_alloc_holder | |
60 | { | |
61 | //If the intrusive container is an associative container, obtain the predicate, which will | |
62 | //be of type node_compare<>. If not an associative container value_compare will be a "nat" type. | |
63 | typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT | |
11fdf7f2 TL |
64 | ( boost::container::dtl:: |
65 | , ICont, value_compare, dtl::nat) intrusive_value_compare; | |
7c673cae FG |
66 | //In that case obtain the value predicate from the node predicate via predicate_type |
67 | //if intrusive_value_compare is node_compare<>, nat otherwise | |
68 | typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT | |
11fdf7f2 | 69 | ( boost::container::dtl:: |
7c673cae | 70 | , intrusive_value_compare |
11fdf7f2 | 71 | , predicate_type, dtl::nat) value_compare; |
7c673cae FG |
72 | |
73 | typedef allocator_traits<Allocator> allocator_traits_type; | |
74 | typedef typename allocator_traits_type::value_type value_type; | |
75 | typedef ICont intrusive_container; | |
76 | typedef typename ICont::value_type Node; | |
77 | typedef typename allocator_traits_type::template | |
78 | portable_rebind_alloc<Node>::type NodeAlloc; | |
79 | typedef allocator_traits<NodeAlloc> node_allocator_traits_type; | |
11fdf7f2 | 80 | typedef dtl::allocator_version_traits<NodeAlloc> node_allocator_version_traits_type; |
7c673cae FG |
81 | typedef Allocator ValAlloc; |
82 | typedef typename node_allocator_traits_type::pointer NodePtr; | |
11fdf7f2 | 83 | typedef dtl::scoped_deallocator<NodeAlloc> Deallocator; |
7c673cae FG |
84 | typedef typename node_allocator_traits_type::size_type size_type; |
85 | typedef typename node_allocator_traits_type::difference_type difference_type; | |
11fdf7f2 TL |
86 | typedef dtl::integral_constant<unsigned, |
87 | boost::container::dtl:: | |
7c673cae FG |
88 | version<NodeAlloc>::value> alloc_version; |
89 | typedef typename ICont::iterator icont_iterator; | |
90 | typedef typename ICont::const_iterator icont_citerator; | |
91 | typedef allocator_destroyer<NodeAlloc> Destroyer; | |
92 | typedef allocator_traits<NodeAlloc> NodeAllocTraits; | |
93 | typedef allocator_version_traits<NodeAlloc> AllocVersionTraits; | |
94 | ||
95 | private: | |
96 | BOOST_COPYABLE_AND_MOVABLE(node_alloc_holder) | |
97 | ||
98 | public: | |
99 | ||
100 | //Constructors for sequence containers | |
101 | node_alloc_holder() | |
102 | : members_() | |
103 | {} | |
104 | ||
105 | explicit node_alloc_holder(const ValAlloc &a) | |
106 | : members_(a) | |
107 | {} | |
108 | ||
b32b8144 FG |
109 | //Constructors for associative containers |
110 | node_alloc_holder(const value_compare &c, const ValAlloc &a) | |
111 | : members_(a, c) | |
112 | {} | |
113 | ||
7c673cae FG |
114 | explicit node_alloc_holder(const node_alloc_holder &x) |
115 | : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc())) | |
116 | {} | |
117 | ||
b32b8144 FG |
118 | node_alloc_holder(const node_alloc_holder &x, const value_compare &c) |
119 | : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()), c) | |
120 | {} | |
121 | ||
7c673cae FG |
122 | explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x) |
123 | : members_(boost::move(x.node_alloc())) | |
124 | { this->icont().swap(x.icont()); } | |
125 | ||
7c673cae FG |
126 | explicit node_alloc_holder(const value_compare &c) |
127 | : members_(c) | |
128 | {} | |
129 | ||
130 | //helpers for move assignments | |
131 | explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const value_compare &c) | |
132 | : members_(boost::move(x.node_alloc()), c) | |
133 | { this->icont().swap(x.icont()); } | |
134 | ||
135 | void copy_assign_alloc(const node_alloc_holder &x) | |
136 | { | |
11fdf7f2 TL |
137 | dtl::bool_<allocator_traits_type::propagate_on_container_copy_assignment::value> flag; |
138 | dtl::assign_alloc( static_cast<NodeAlloc &>(this->members_) | |
7c673cae FG |
139 | , static_cast<const NodeAlloc &>(x.members_), flag); |
140 | } | |
141 | ||
142 | void move_assign_alloc( node_alloc_holder &x) | |
143 | { | |
11fdf7f2 TL |
144 | dtl::bool_<allocator_traits_type::propagate_on_container_move_assignment::value> flag; |
145 | dtl::move_alloc( static_cast<NodeAlloc &>(this->members_) | |
7c673cae FG |
146 | , static_cast<NodeAlloc &>(x.members_), flag); |
147 | } | |
148 | ||
149 | ~node_alloc_holder() | |
150 | { this->clear(alloc_version()); } | |
151 | ||
152 | size_type max_size() const | |
153 | { return allocator_traits_type::max_size(this->node_alloc()); } | |
154 | ||
155 | NodePtr allocate_one() | |
156 | { return AllocVersionTraits::allocate_one(this->node_alloc()); } | |
157 | ||
158 | void deallocate_one(const NodePtr &p) | |
159 | { AllocVersionTraits::deallocate_one(this->node_alloc(), p); } | |
160 | ||
161 | #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
162 | ||
163 | template<class ...Args> | |
164 | NodePtr create_node(Args &&...args) | |
165 | { | |
166 | NodePtr p = this->allocate_one(); | |
167 | Deallocator node_deallocator(p, this->node_alloc()); | |
168 | allocator_traits<NodeAlloc>::construct | |
169 | ( this->node_alloc() | |
11fdf7f2 | 170 | , dtl::addressof(p->m_data), boost::forward<Args>(args)...); |
7c673cae FG |
171 | node_deallocator.release(); |
172 | //This does not throw | |
173 | typedef typename Node::hook_type hook_type; | |
b32b8144 | 174 | ::new(static_cast<hook_type*>(boost::movelib::to_raw_pointer(p)), boost_container_new_t()) hook_type; |
7c673cae FG |
175 | return (p); |
176 | } | |
177 | ||
178 | #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
179 | ||
180 | #define BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL(N) \ | |
181 | BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ | |
182 | NodePtr create_node(BOOST_MOVE_UREF##N)\ | |
183 | {\ | |
184 | NodePtr p = this->allocate_one();\ | |
185 | Deallocator node_deallocator(p, this->node_alloc());\ | |
186 | allocator_traits<NodeAlloc>::construct\ | |
187 | ( this->node_alloc()\ | |
11fdf7f2 | 188 | , dtl::addressof(p->m_data)\ |
7c673cae FG |
189 | BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ |
190 | node_deallocator.release();\ | |
191 | typedef typename Node::hook_type hook_type;\ | |
b32b8144 | 192 | ::new(static_cast<hook_type*>(boost::movelib::to_raw_pointer(p)), boost_container_new_t()) hook_type;\ |
7c673cae FG |
193 | return (p);\ |
194 | }\ | |
195 | // | |
196 | BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL) | |
197 | #undef BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL | |
198 | ||
199 | #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) | |
200 | ||
201 | template<class It> | |
202 | NodePtr create_node_from_it(const It &it) | |
203 | { | |
204 | NodePtr p = this->allocate_one(); | |
205 | Deallocator node_deallocator(p, this->node_alloc()); | |
11fdf7f2 | 206 | ::boost::container::construct_in_place(this->node_alloc(), dtl::addressof(p->m_data), it); |
7c673cae FG |
207 | node_deallocator.release(); |
208 | //This does not throw | |
209 | typedef typename Node::hook_type hook_type; | |
b32b8144 | 210 | ::new(static_cast<hook_type*>(boost::movelib::to_raw_pointer(p)), boost_container_new_t()) hook_type; |
7c673cae FG |
211 | return (p); |
212 | } | |
213 | ||
214 | template<class KeyConvertible> | |
215 | NodePtr create_node_from_key(BOOST_FWD_REF(KeyConvertible) key) | |
216 | { | |
217 | NodePtr p = this->allocate_one(); | |
218 | NodeAlloc &na = this->node_alloc(); | |
219 | Deallocator node_deallocator(p, this->node_alloc()); | |
220 | node_allocator_traits_type::construct | |
11fdf7f2 | 221 | (na, dtl::addressof(p->m_data.first), boost::forward<KeyConvertible>(key)); |
7c673cae | 222 | BOOST_TRY{ |
11fdf7f2 | 223 | node_allocator_traits_type::construct(na, dtl::addressof(p->m_data.second)); |
7c673cae FG |
224 | } |
225 | BOOST_CATCH(...){ | |
11fdf7f2 | 226 | node_allocator_traits_type::destroy(na, dtl::addressof(p->m_data.first)); |
7c673cae FG |
227 | BOOST_RETHROW; |
228 | } | |
229 | BOOST_CATCH_END | |
230 | node_deallocator.release(); | |
231 | //This does not throw | |
232 | typedef typename Node::hook_type hook_type; | |
b32b8144 | 233 | ::new(static_cast<hook_type*>(boost::movelib::to_raw_pointer(p)), boost_container_new_t()) hook_type; |
7c673cae FG |
234 | return (p); |
235 | } | |
236 | ||
237 | void destroy_node(const NodePtr &nodep) | |
238 | { | |
b32b8144 | 239 | allocator_traits<NodeAlloc>::destroy(this->node_alloc(), boost::movelib::to_raw_pointer(nodep)); |
7c673cae FG |
240 | this->deallocate_one(nodep); |
241 | } | |
242 | ||
243 | void swap(node_alloc_holder &x) | |
244 | { | |
245 | this->icont().swap(x.icont()); | |
11fdf7f2 TL |
246 | dtl::bool_<allocator_traits_type::propagate_on_container_swap::value> flag; |
247 | dtl::swap_alloc(this->node_alloc(), x.node_alloc(), flag); | |
7c673cae FG |
248 | } |
249 | ||
250 | template<class FwdIterator, class Inserter> | |
251 | void allocate_many_and_construct | |
252 | (FwdIterator beg, difference_type n, Inserter inserter) | |
253 | { | |
254 | if(n){ | |
255 | typedef typename node_allocator_version_traits_type::multiallocation_chain multiallocation_chain; | |
256 | ||
257 | //Try to allocate memory in a single block | |
258 | typedef typename multiallocation_chain::iterator multialloc_iterator; | |
259 | multiallocation_chain mem; | |
260 | NodeAlloc &nalloc = this->node_alloc(); | |
261 | node_allocator_version_traits_type::allocate_individual(nalloc, n, mem); | |
262 | multialloc_iterator itbeg(mem.begin()), itlast(mem.last()); | |
263 | mem.clear(); | |
264 | Node *p = 0; | |
265 | BOOST_TRY{ | |
266 | Deallocator node_deallocator(NodePtr(), nalloc); | |
11fdf7f2 | 267 | dtl::scoped_destructor<NodeAlloc> sdestructor(nalloc, 0); |
7c673cae | 268 | while(n--){ |
b32b8144 | 269 | p = boost::movelib::iterator_to_raw_pointer(itbeg); |
7c673cae FG |
270 | node_deallocator.set(p); |
271 | ++itbeg; | |
272 | //This can throw | |
11fdf7f2 | 273 | boost::container::construct_in_place(nalloc, dtl::addressof(p->m_data), beg); |
7c673cae FG |
274 | sdestructor.set(p); |
275 | ++beg; | |
276 | //This does not throw | |
277 | typedef typename Node::hook_type hook_type; | |
278 | ::new(static_cast<hook_type*>(p), boost_container_new_t()) hook_type; | |
279 | //This can throw in some containers (predicate might throw). | |
280 | //(sdestructor will destruct the node and node_deallocator will deallocate it in case of exception) | |
281 | inserter(*p); | |
282 | sdestructor.set(0); | |
283 | } | |
284 | sdestructor.release(); | |
285 | node_deallocator.release(); | |
286 | } | |
287 | BOOST_CATCH(...){ | |
288 | mem.incorporate_after(mem.last(), &*itbeg, &*itlast, n); | |
289 | node_allocator_version_traits_type::deallocate_individual(this->node_alloc(), mem); | |
290 | BOOST_RETHROW | |
291 | } | |
292 | BOOST_CATCH_END | |
293 | } | |
294 | } | |
295 | ||
296 | void clear(version_1) | |
297 | { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); } | |
298 | ||
299 | void clear(version_2) | |
300 | { | |
301 | typename NodeAlloc::multiallocation_chain chain; | |
302 | allocator_destroyer_and_chain_builder<NodeAlloc> builder(this->node_alloc(), chain); | |
303 | this->icont().clear_and_dispose(builder); | |
304 | //BOOST_STATIC_ASSERT((::boost::has_move_emulation_enabled<typename NodeAlloc::multiallocation_chain>::value == true)); | |
305 | if(!chain.empty()) | |
306 | this->node_alloc().deallocate_individual(chain); | |
307 | } | |
308 | ||
309 | icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_1) | |
310 | { return this->icont().erase_and_dispose(first, last, Destroyer(this->node_alloc())); } | |
311 | ||
312 | icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_2) | |
313 | { | |
314 | typedef typename NodeAlloc::multiallocation_chain multiallocation_chain; | |
315 | NodeAlloc & nalloc = this->node_alloc(); | |
316 | multiallocation_chain chain; | |
317 | allocator_destroyer_and_chain_builder<NodeAlloc> chain_builder(nalloc, chain); | |
318 | icont_iterator ret_it = this->icont().erase_and_dispose(first, last, chain_builder); | |
319 | nalloc.deallocate_individual(chain); | |
320 | return ret_it; | |
321 | } | |
322 | ||
323 | template<class Key, class Comparator> | |
324 | size_type erase_key(const Key& k, const Comparator &comp, version_1) | |
325 | { return this->icont().erase_and_dispose(k, comp, Destroyer(this->node_alloc())); } | |
326 | ||
327 | template<class Key, class Comparator> | |
328 | size_type erase_key(const Key& k, const Comparator &comp, version_2) | |
329 | { | |
330 | allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc()); | |
331 | return this->icont().erase_and_dispose(k, comp, chain_holder.get_chain_builder()); | |
332 | } | |
333 | ||
334 | protected: | |
335 | struct cloner | |
336 | { | |
337 | explicit cloner(node_alloc_holder &holder) | |
338 | : m_holder(holder) | |
339 | {} | |
340 | ||
341 | NodePtr operator()(const Node &other) const | |
342 | { return m_holder.create_node(other.m_data); } | |
343 | ||
344 | node_alloc_holder &m_holder; | |
345 | }; | |
346 | ||
347 | struct move_cloner | |
348 | { | |
349 | move_cloner(node_alloc_holder &holder) | |
350 | : m_holder(holder) | |
351 | {} | |
352 | ||
353 | NodePtr operator()(Node &other) | |
354 | { //Use m_data instead of get_data to allow moving const key in [multi]map | |
355 | return m_holder.create_node(::boost::move(other.m_data)); | |
356 | } | |
357 | ||
358 | node_alloc_holder &m_holder; | |
359 | }; | |
360 | ||
361 | struct members_holder | |
362 | : public NodeAlloc | |
363 | { | |
364 | private: | |
365 | members_holder(const members_holder&); | |
366 | members_holder & operator=(const members_holder&); | |
367 | ||
368 | public: | |
369 | members_holder() | |
370 | : NodeAlloc(), m_icont() | |
371 | {} | |
372 | ||
373 | template<class ConvertibleToAlloc> | |
374 | explicit members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc) | |
375 | : NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc)) | |
376 | , m_icont() | |
377 | {} | |
378 | ||
379 | template<class ConvertibleToAlloc> | |
380 | members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc, const value_compare &c) | |
381 | : NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc)) | |
382 | , m_icont(typename ICont::key_compare(c)) | |
383 | {} | |
384 | ||
385 | explicit members_holder(const value_compare &c) | |
386 | : NodeAlloc() | |
387 | , m_icont(typename ICont::key_compare(c)) | |
388 | {} | |
389 | ||
390 | //The intrusive container | |
391 | ICont m_icont; | |
392 | }; | |
393 | ||
394 | ICont &non_const_icont() const | |
395 | { return const_cast<ICont&>(this->members_.m_icont); } | |
396 | ||
397 | NodeAlloc &node_alloc() | |
398 | { return static_cast<NodeAlloc &>(this->members_); } | |
399 | ||
400 | const NodeAlloc &node_alloc() const | |
401 | { return static_cast<const NodeAlloc &>(this->members_); } | |
402 | ||
403 | members_holder members_; | |
404 | ||
405 | public: | |
406 | ICont &icont() | |
407 | { return this->members_.m_icont; } | |
408 | ||
409 | const ICont &icont() const | |
410 | { return this->members_.m_icont; } | |
411 | }; | |
412 | ||
11fdf7f2 | 413 | } //namespace dtl { |
7c673cae FG |
414 | } //namespace container { |
415 | } //namespace boost { | |
416 | ||
417 | #include <boost/container/detail/config_end.hpp> | |
418 | ||
419 | #endif // BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_ |