]>
Commit | Line | Data |
---|---|---|
7c673cae FG |
1 | ////////////////////////////////////////////////////////////////////////////// |
2 | // | |
3 | // (C) Copyright Ion Gaztanaga 2016-2016. 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_NODE_HANDLE_HPP | |
12 | #define BOOST_CONTAINER_NODE_HANDLE_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 | #include <boost/static_assert.hpp> | |
25 | #include <boost/container/detail/placement_new.hpp> | |
b32b8144 | 26 | #include <boost/move/detail/to_raw_pointer.hpp> |
7c673cae FG |
27 | #include <boost/container/allocator_traits.hpp> |
28 | #include <boost/container/detail/mpl.hpp> | |
29 | ||
30 | #include <boost/move/utility_core.hpp> | |
31 | #include <boost/move/adl_move_swap.hpp> | |
32 | ||
33 | #include <boost/type_traits/aligned_storage.hpp> | |
34 | ||
35 | ||
36 | //!\file | |
37 | ||
38 | namespace boost { | |
39 | namespace container { | |
40 | ||
41 | ///@cond | |
42 | ||
b32b8144 | 43 | template<class Value, class KeyMapped> |
7c673cae | 44 | struct node_handle_keymapped_traits |
b32b8144 FG |
45 | { |
46 | typedef typename KeyMapped::key_type key_type; | |
47 | typedef typename KeyMapped::mapped_type mapped_type; | |
48 | }; | |
49 | ||
50 | template<class Value> | |
51 | struct node_handle_keymapped_traits<Value, void> | |
7c673cae FG |
52 | { |
53 | typedef Value key_type; | |
54 | typedef Value mapped_type; | |
55 | }; | |
56 | ||
b32b8144 | 57 | class node_handle_friend |
7c673cae | 58 | { |
b32b8144 FG |
59 | public: |
60 | ||
61 | template<class NH> | |
62 | BOOST_CONTAINER_FORCEINLINE static void destroy_alloc(NH &nh) BOOST_NOEXCEPT | |
63 | { nh.destroy_alloc(); } | |
64 | ||
65 | template<class NH> | |
66 | BOOST_CONTAINER_FORCEINLINE static typename NH::node_pointer &get_node_pointer(NH &nh) BOOST_NOEXCEPT | |
67 | { return nh.get_node_pointer(); } | |
7c673cae FG |
68 | }; |
69 | ||
b32b8144 | 70 | |
7c673cae FG |
71 | ///@endcond |
72 | ||
73 | //! A node_handle is an object that accepts ownership of a single element from an associative container. | |
74 | //! It may be used to transfer that ownership to another container with compatible nodes. Containers | |
75 | //! with compatible nodes have the same node handle type. Elements may be transferred in either direction | |
76 | //! between container types in the same row:. | |
77 | //! | |
78 | //! Container types with compatible nodes | |
79 | //! | |
80 | //! map<K, T, C1, A> <-> map<K, T, C2, A> | |
81 | //! | |
82 | //! map<K, T, C1, A> <-> multimap<K, T, C2, A> | |
83 | //! | |
84 | //! set<K, C1, A> <-> set<K, C2, A> | |
85 | //! | |
86 | //! set<K, C1, A> <-> multiset<K, C2, A> | |
87 | //! | |
88 | //! If a node handle is not empty, then it contains an allocator that is equal to the allocator of the container | |
89 | //! when the element was extracted. If a node handle is empty, it contains no allocator. | |
b32b8144 | 90 | template <class NodeAllocator, class KeyMapped = void> |
7c673cae FG |
91 | class node_handle |
92 | { | |
b32b8144 FG |
93 | typedef NodeAllocator nallocator_type; |
94 | typedef allocator_traits<NodeAllocator> nator_traits; | |
95 | typedef typename nator_traits::value_type priv_node_t; | |
96 | typedef typename priv_node_t::value_type priv_value_t; | |
97 | typedef node_handle_keymapped_traits<priv_value_t, KeyMapped> keymapped_t; | |
7c673cae FG |
98 | |
99 | public: | |
b32b8144 | 100 | typedef priv_value_t value_type; |
7c673cae FG |
101 | typedef typename keymapped_t::key_type key_type; |
102 | typedef typename keymapped_t::mapped_type mapped_type; | |
b32b8144 FG |
103 | typedef typename nator_traits::template portable_rebind_alloc |
104 | <value_type>::type allocator_type; | |
105 | ||
106 | typedef priv_node_t container_node_type; | |
107 | friend class node_handle_friend; | |
7c673cae FG |
108 | |
109 | ///@cond | |
110 | private: | |
111 | BOOST_MOVABLE_BUT_NOT_COPYABLE(node_handle) | |
112 | ||
b32b8144 | 113 | typedef typename nator_traits::pointer node_pointer; |
7c673cae | 114 | typedef ::boost::aligned_storage |
b32b8144 FG |
115 | < sizeof(nallocator_type) |
116 | , boost::alignment_of<nallocator_type>::value> nalloc_storage_t; | |
7c673cae FG |
117 | |
118 | node_pointer m_ptr; | |
119 | nalloc_storage_t m_nalloc_storage; | |
120 | ||
121 | void move_construct_alloc(nallocator_type &al) | |
b32b8144 | 122 | { ::new(m_nalloc_storage.address(), boost_container_new_t()) nallocator_type(::boost::move(al)); } |
7c673cae | 123 | |
b32b8144 | 124 | void destroy_deallocate_node() |
7c673cae | 125 | { |
b32b8144 FG |
126 | nator_traits::destroy(this->node_alloc(), boost::movelib::to_raw_pointer(m_ptr)); |
127 | nator_traits::deallocate(this->node_alloc(), m_ptr, 1u); | |
7c673cae FG |
128 | } |
129 | ||
130 | template<class OtherNodeHandle> | |
131 | void move_construct_end(OtherNodeHandle &nh) | |
132 | { | |
133 | if(m_ptr){ | |
b32b8144 FG |
134 | ::new (m_nalloc_storage.address(), boost_container_new_t()) nallocator_type(::boost::move(nh.node_alloc())); |
135 | node_handle_friend::destroy_alloc(nh); | |
136 | node_handle_friend::get_node_pointer(nh) = node_pointer(); | |
7c673cae FG |
137 | } |
138 | BOOST_ASSERT(nh.empty()); | |
139 | } | |
140 | ||
b32b8144 FG |
141 | void destroy_alloc() BOOST_NOEXCEPT |
142 | { static_cast<nallocator_type*>(m_nalloc_storage.address())->~nallocator_type(); } | |
7c673cae | 143 | |
b32b8144 | 144 | node_pointer &get_node_pointer() BOOST_NOEXCEPT |
7c673cae FG |
145 | { return m_ptr; } |
146 | ||
7c673cae FG |
147 | ///@endcond |
148 | ||
149 | public: | |
150 | //! <b>Effects</b>: Initializes m_ptr to nullptr. | |
151 | //! | |
152 | //! <b>Postcondition</b>: this->empty() | |
153 | BOOST_CXX14_CONSTEXPR node_handle() BOOST_NOEXCEPT | |
b32b8144 FG |
154 | : m_ptr() |
155 | { } | |
7c673cae FG |
156 | |
157 | //! <b>Effects</b>: Constructs a node_handle object initializing internal pointer with p. | |
b32b8144 | 158 | //! If p != nullptr copy constructs internal allocator from al. |
7c673cae | 159 | node_handle(node_pointer p, const nallocator_type &al) BOOST_NOEXCEPT |
b32b8144 | 160 | : m_ptr(p) |
7c673cae FG |
161 | { |
162 | if(m_ptr){ | |
163 | ::new (m_nalloc_storage.address(), boost_container_new_t()) nallocator_type(al); | |
164 | } | |
165 | } | |
166 | ||
167 | //! <b>Effects</b>: Constructs a node_handle object initializing internal pointer with a related nh's internal pointer | |
168 | //! and assigns nullptr to the later. If nh's internal pointer was not nullptr, move constructs internal | |
169 | //! allocator with nh's internal allocator and destroy nh's internal allocator. | |
170 | //! | |
171 | //! <b>Postcondition</b>: nh.empty() | |
172 | //! | |
173 | //! <b>Note</b>: Two node_handle's are related if only one of KeyMapped template parameter | |
174 | //! of a node handle is void. | |
175 | template<class KeyMapped2> | |
b32b8144 | 176 | node_handle( BOOST_RV_REF_BEG node_handle<NodeAllocator, KeyMapped2> BOOST_RV_REF_END nh |
7c673cae FG |
177 | , typename container_detail::enable_if_c |
178 | < ((unsigned)container_detail::is_same<KeyMapped, void>::value + | |
179 | (unsigned)container_detail::is_same<KeyMapped2, void>::value) == 1u | |
b32b8144 FG |
180 | >::type* = 0) BOOST_NOEXCEPT |
181 | : m_ptr(nh.get()) | |
7c673cae FG |
182 | { this->move_construct_end(nh); } |
183 | ||
184 | //! <b>Effects</b>: Constructs a node_handle object initializing internal pointer with nh's internal pointer | |
185 | //! and assigns nullptr to the later. If nh's internal pointer was not nullptr, move constructs internal | |
186 | //! allocator with nh's internal allocator and destroy nh's internal allocator. | |
187 | //! | |
188 | //! <b>Postcondition</b>: nh.empty() | |
189 | node_handle (BOOST_RV_REF(node_handle) nh) BOOST_NOEXCEPT | |
b32b8144 | 190 | : m_ptr(nh.m_ptr) |
7c673cae FG |
191 | { this->move_construct_end(nh); } |
192 | ||
193 | //! <b>Effects</b>: If !this->empty(), destroys the value_type subobject in the container_node_type object | |
194 | //! pointed to by c by calling allocator_traits<impl_defined>::destroy, then deallocates m_ptr by calling | |
b32b8144 FG |
195 | //! nator_traits::rebind_traits<container_node_type>::deallocate. |
196 | ~node_handle() BOOST_NOEXCEPT | |
7c673cae FG |
197 | { |
198 | if(!this->empty()){ | |
b32b8144 | 199 | this->destroy_deallocate_node(); |
7c673cae FG |
200 | this->destroy_alloc(); |
201 | } | |
202 | } | |
203 | ||
b32b8144 | 204 | //! <b>Requires</b>: Either this->empty(), or nator_traits::propagate_on_container_move_assignment is true, or |
7c673cae FG |
205 | //! node_alloc() == nh.node_alloc(). |
206 | //! | |
207 | //! <b>Effects</b>: If m_ptr != nullptr, destroys the value_type subobject in the container_node_type object | |
b32b8144 FG |
208 | //! pointed to by m_ptr by calling nator_traits::destroy, then deallocates m_ptr by calling |
209 | //! nator_traits::deallocate. Assigns nh.m_ptr to m_ptr. If this->empty() | |
210 | //! or nator_traits::propagate_on_container_move_assignment is true, move assigns nh.node_alloc() to | |
7c673cae | 211 | //! node_alloc(). Assigns nullptr to nh.m_ptr and assigns nullopt to nh.node_alloc(). |
b32b8144 | 212 | //! |
7c673cae FG |
213 | //! <b>Returns</b>: *this. |
214 | //! | |
215 | //! <b>Throws</b>: Nothing. | |
b32b8144 | 216 | node_handle & operator=(BOOST_RV_REF(node_handle) nh) BOOST_NOEXCEPT |
7c673cae | 217 | { |
b32b8144 FG |
218 | BOOST_ASSERT(this->empty() || nator_traits::propagate_on_container_move_assignment::value |
219 | || nator_traits::equal(node_alloc(), nh.node_alloc())); | |
7c673cae FG |
220 | |
221 | bool const was_this_non_null = !this->empty(); | |
222 | bool const was_nh_non_null = !nh.empty(); | |
223 | ||
224 | if(was_nh_non_null){ | |
225 | if(was_this_non_null){ | |
b32b8144 FG |
226 | this->destroy_deallocate_node(); |
227 | if(nator_traits::propagate_on_container_move_assignment::value){ | |
7c673cae FG |
228 | this->node_alloc() = ::boost::move(nh.node_alloc()); |
229 | } | |
230 | } | |
231 | else{ | |
232 | this->move_construct_alloc(nh.node_alloc()); | |
233 | } | |
234 | m_ptr = nh.m_ptr; | |
235 | nh.m_ptr = node_pointer(); | |
236 | nh.destroy_alloc(); | |
237 | } | |
238 | else if(was_this_non_null){ | |
b32b8144 | 239 | this->destroy_deallocate_node(); |
7c673cae FG |
240 | this->destroy_alloc(); |
241 | m_ptr = node_pointer(); | |
242 | } | |
243 | return *this; | |
244 | } | |
245 | ||
246 | //! <b>Requires</b>: empty() == false. | |
247 | //! | |
248 | //! <b>Returns</b>: A reference to the value_type subobject in the container_node_type object pointed to by m_ptr | |
249 | //! | |
250 | //! <b>Throws</b>: Nothing. | |
251 | value_type& value() const BOOST_NOEXCEPT | |
252 | { | |
253 | BOOST_STATIC_ASSERT((container_detail::is_same<KeyMapped, void>::value)); | |
254 | BOOST_ASSERT(!empty()); | |
255 | return m_ptr->get_data(); | |
256 | } | |
257 | ||
258 | //! <b>Requires</b>: empty() == false. | |
259 | //! | |
260 | //! <b>Returns</b>: A non-const reference to the key_type member of the value_type subobject in the | |
261 | //! container_node_type object pointed to by m_ptr. | |
262 | //! | |
263 | //! <b>Throws</b>: Nothing. | |
264 | //! | |
265 | //! <b>Requires</b>: Modifying the key through the returned reference is permitted. | |
266 | key_type& key() const BOOST_NOEXCEPT | |
267 | { | |
268 | BOOST_STATIC_ASSERT((!container_detail::is_same<KeyMapped, void>::value)); | |
269 | BOOST_ASSERT(!empty()); | |
270 | return const_cast<key_type &>(KeyMapped().key_of_value(m_ptr->get_data())); | |
271 | } | |
272 | ||
273 | //! <b>Requires</b>: empty() == false. | |
274 | //! | |
275 | //! <b>Returns</b>: A reference to the mapped_type member of the value_type subobject | |
276 | //! in the container_node_type object pointed to by m_ptr | |
277 | //! | |
278 | //! <b>Throws</b>: Nothing. | |
279 | mapped_type& mapped() const BOOST_NOEXCEPT | |
280 | { | |
281 | BOOST_STATIC_ASSERT((!container_detail::is_same<KeyMapped, void>::value)); | |
282 | BOOST_ASSERT(!empty()); | |
283 | return KeyMapped().mapped_of_value(m_ptr->get_data()); | |
284 | } | |
285 | ||
286 | //! <b>Requires</b>: empty() == false. | |
287 | //! | |
288 | //! <b>Returns</b>: A copy of the internally hold allocator. | |
289 | //! | |
290 | //! <b>Throws</b>: Nothing. | |
291 | allocator_type get_allocator() const | |
292 | { | |
293 | BOOST_ASSERT(!empty()); | |
294 | return this->node_alloc(); | |
295 | } | |
296 | ||
297 | //! <b>Returns</b>: m_ptr != nullptr. | |
298 | //! | |
299 | #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED | |
300 | BOOST_CONTAINER_FORCEINLINE explicit operator bool | |
301 | #else | |
302 | private: struct bool_conversion {int for_bool; int for_arg(); }; typedef int bool_conversion::* explicit_bool_arg; | |
303 | public: BOOST_CONTAINER_FORCEINLINE operator explicit_bool_arg | |
304 | #endif | |
305 | ()const BOOST_NOEXCEPT | |
306 | { return m_ptr ? &bool_conversion::for_bool : explicit_bool_arg(0); } | |
307 | ||
308 | //! <b>Returns</b>: m_ptr == nullptr. | |
309 | //! | |
310 | bool empty() const BOOST_NOEXCEPT | |
311 | { | |
312 | return !this->m_ptr; | |
313 | } | |
314 | ||
b32b8144 | 315 | //! <b>Requires</b>: this->empty(), or nh.empty(), or nator_traits::propagate_on_container_swap is true, or |
7c673cae FG |
316 | //! node_alloc() == nh.node_alloc(). |
317 | //! | |
b32b8144 | 318 | //! <b>Effects</b>: Calls swap(m_ptr, nh.m_ptr). If this->empty(), or nh.empty(), or nator_traits::propagate_on_- |
7c673cae FG |
319 | //! container_swap is true calls swap(node_alloc(), nh.node_alloc()). |
320 | void swap(node_handle &nh) | |
b32b8144 | 321 | BOOST_NOEXCEPT_IF(nator_traits::propagate_on_container_swap::value || nator_traits::is_always_equal::value) |
7c673cae | 322 | { |
b32b8144 FG |
323 | BOOST_ASSERT(this->empty() || nh.empty() || nator_traits::propagate_on_container_swap::value |
324 | || nator_traits::equal(node_alloc(), nh.node_alloc())); | |
7c673cae FG |
325 | |
326 | bool const was_this_non_null = !this->empty(); | |
327 | bool const was_nh_non_null = !nh.empty(); | |
328 | ||
329 | if(was_nh_non_null){ | |
330 | if(was_this_non_null){ | |
b32b8144 | 331 | if(nator_traits::propagate_on_container_swap::value){ |
7c673cae FG |
332 | ::boost::adl_move_swap(this->node_alloc(), nh.node_alloc()); |
333 | } | |
334 | } | |
335 | else{ | |
336 | this->move_construct_alloc(nh.node_alloc()); | |
337 | nh.destroy_alloc(); | |
338 | } | |
339 | } | |
340 | else if(was_this_non_null){ | |
341 | nh.move_construct_alloc(this->node_alloc()); | |
b32b8144 | 342 | this->destroy_alloc(); |
7c673cae FG |
343 | } |
344 | ::boost::adl_move_swap(m_ptr, nh.m_ptr); | |
345 | } | |
346 | ||
b32b8144 FG |
347 | //! <b>Effects</b>: If this->empty() returns nullptr, otherwise returns m_ptr |
348 | //! resets m_ptr to nullptr and destroys the internal allocator. | |
349 | //! | |
350 | //! <b>Postcondition</b>: this->empty() | |
351 | //! | |
352 | //! <b>Note</b>: Non-standard extensions | |
353 | node_pointer release() BOOST_NOEXCEPT | |
354 | { | |
355 | node_pointer p(m_ptr); | |
356 | m_ptr = node_pointer(); | |
357 | if(p) | |
358 | this->destroy_alloc(); | |
359 | return p; | |
360 | } | |
361 | ||
362 | //! <b>Effects</b>: Returns m_ptr. | |
363 | //! | |
364 | //! <b>Note</b>: Non-standard extensions | |
365 | node_pointer get() const BOOST_NOEXCEPT | |
366 | { | |
367 | return m_ptr; | |
368 | } | |
369 | ||
370 | //! <b>Effects</b>: Returns a reference to the internal node allocator. | |
371 | //! | |
372 | //! <b>Note</b>: Non-standard extensions | |
373 | nallocator_type &node_alloc() BOOST_NOEXCEPT | |
374 | { | |
375 | BOOST_ASSERT(!empty()); | |
376 | return *static_cast<nallocator_type*>(m_nalloc_storage.address()); | |
377 | } | |
378 | ||
379 | ||
380 | //! <b>Effects</b>: Returns a reference to the internal node allocator. | |
381 | //! | |
382 | //! <b>Note</b>: Non-standard extensions | |
383 | const nallocator_type &node_alloc() const BOOST_NOEXCEPT | |
384 | { | |
385 | BOOST_ASSERT(!empty()); | |
386 | return *static_cast<const nallocator_type*>(m_nalloc_storage.address()); | |
387 | } | |
388 | ||
7c673cae FG |
389 | //! <b>Effects</b>: x.swap(y). |
390 | //! | |
391 | friend void swap(node_handle & x, node_handle & y) BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT(x.swap(y))) | |
392 | { x.swap(y); } | |
393 | }; | |
394 | ||
395 | //! A class template used to describe the results of inserting a | |
396 | //! Container::node_type in a Container with unique keys. | |
397 | //! Includes at least the following non-static public data members: | |
398 | //! | |
399 | //! <ul><li>bool inserted</li>; | |
400 | //! <li>Iterator position</li>; | |
401 | //! <li>NodeType node</li></ul> | |
402 | //! | |
403 | //! This type is MoveConstructible, MoveAssignable, DefaultConstructible, | |
404 | //! Destructible, and lvalues of that type are swappable | |
405 | template<class Iterator, class NodeType> | |
406 | struct insert_return_type_base | |
407 | { | |
408 | private: | |
409 | BOOST_MOVABLE_BUT_NOT_COPYABLE(insert_return_type_base) | |
410 | ||
411 | public: | |
412 | insert_return_type_base() | |
413 | : inserted(false), position(), node() | |
414 | {} | |
415 | ||
416 | insert_return_type_base(BOOST_RV_REF(insert_return_type_base) other) | |
417 | : inserted(other.inserted), position(other.position), node(boost::move(other.node)) | |
418 | {} | |
419 | ||
420 | template<class RelatedIt, class RelatedNode> | |
421 | insert_return_type_base(bool insert, RelatedIt it, BOOST_RV_REF(RelatedNode) node) | |
422 | : inserted(insert), position(it), node(boost::move(node)) | |
423 | {} | |
424 | ||
425 | insert_return_type_base & operator=(BOOST_RV_REF(insert_return_type_base) other) | |
426 | { | |
427 | inserted = other.inserted; | |
428 | position = other.position; | |
429 | node = boost::move(other.node); | |
430 | return *this; | |
431 | } | |
432 | ||
433 | bool inserted; | |
434 | Iterator position; | |
435 | NodeType node; | |
436 | }; | |
437 | ||
438 | } //namespace container { | |
439 | } //namespace boost { | |
440 | ||
441 | #include <boost/container/detail/config_end.hpp> | |
442 | ||
443 | #endif //BOOST_CONTAINER_NODE_HANDLE_HPP |