1 //////////////////////////////////////////////////////////////////////////////
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)
7 // See http://www.boost.org/libs/container for documentation.
9 //////////////////////////////////////////////////////////////////////////////
11 #ifndef BOOST_CONTAINER_NODE_HANDLE_HPP
12 #define BOOST_CONTAINER_NODE_HANDLE_HPP
14 #ifndef BOOST_CONFIG_HPP
15 # include <boost/config.hpp>
18 #if defined(BOOST_HAS_PRAGMA_ONCE)
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>
26 #include <boost/move/detail/to_raw_pointer.hpp>
27 #include <boost/container/allocator_traits.hpp>
28 #include <boost/container/detail/mpl.hpp>
30 #include <boost/move/utility_core.hpp>
31 #include <boost/move/adl_move_swap.hpp>
33 #include <boost/type_traits/aligned_storage.hpp>
43 template<class Value, class KeyMapped>
44 struct node_handle_keymapped_traits
46 typedef typename KeyMapped::key_type key_type;
47 typedef typename KeyMapped::mapped_type mapped_type;
51 struct node_handle_keymapped_traits<Value, void>
53 typedef Value key_type;
54 typedef Value mapped_type;
57 class node_handle_friend
62 BOOST_CONTAINER_FORCEINLINE static void destroy_alloc(NH &nh) BOOST_NOEXCEPT
63 { nh.destroy_alloc(); }
66 BOOST_CONTAINER_FORCEINLINE static typename NH::node_pointer &get_node_pointer(NH &nh) BOOST_NOEXCEPT
67 { return nh.get_node_pointer(); }
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:.
78 //! Container types with compatible nodes
80 //! map<K, T, C1, A> <-> map<K, T, C2, A>
82 //! map<K, T, C1, A> <-> multimap<K, T, C2, A>
84 //! set<K, C1, A> <-> set<K, C2, A>
86 //! set<K, C1, A> <-> multiset<K, C2, A>
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.
90 template <class NodeAllocator, class KeyMapped = void>
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;
100 typedef priv_value_t value_type;
101 typedef typename keymapped_t::key_type key_type;
102 typedef typename keymapped_t::mapped_type mapped_type;
103 typedef typename nator_traits::template portable_rebind_alloc
104 <value_type>::type allocator_type;
106 typedef priv_node_t container_node_type;
107 friend class node_handle_friend;
111 BOOST_MOVABLE_BUT_NOT_COPYABLE(node_handle)
113 typedef typename nator_traits::pointer node_pointer;
114 typedef ::boost::aligned_storage
115 < sizeof(nallocator_type)
116 , boost::alignment_of<nallocator_type>::value> nalloc_storage_t;
119 nalloc_storage_t m_nalloc_storage;
121 void move_construct_alloc(nallocator_type &al)
122 { ::new(m_nalloc_storage.address(), boost_container_new_t()) nallocator_type(::boost::move(al)); }
124 void destroy_deallocate_node()
126 nator_traits::destroy(this->node_alloc(), boost::movelib::to_raw_pointer(m_ptr));
127 nator_traits::deallocate(this->node_alloc(), m_ptr, 1u);
130 template<class OtherNodeHandle>
131 void move_construct_end(OtherNodeHandle &nh)
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();
138 BOOST_ASSERT(nh.empty());
141 void destroy_alloc() BOOST_NOEXCEPT
142 { static_cast<nallocator_type*>(m_nalloc_storage.address())->~nallocator_type(); }
144 node_pointer &get_node_pointer() BOOST_NOEXCEPT
150 //! <b>Effects</b>: Initializes m_ptr to nullptr.
152 //! <b>Postcondition</b>: this->empty()
153 BOOST_CXX14_CONSTEXPR node_handle() BOOST_NOEXCEPT
157 //! <b>Effects</b>: Constructs a node_handle object initializing internal pointer with p.
158 //! If p != nullptr copy constructs internal allocator from al.
159 node_handle(node_pointer p, const nallocator_type &al) BOOST_NOEXCEPT
163 ::new (m_nalloc_storage.address(), boost_container_new_t()) nallocator_type(al);
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.
171 //! <b>Postcondition</b>: nh.empty()
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>
176 node_handle( BOOST_RV_REF_BEG node_handle<NodeAllocator, KeyMapped2> BOOST_RV_REF_END nh
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
180 >::type* = 0) BOOST_NOEXCEPT
182 { this->move_construct_end(nh); }
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.
188 //! <b>Postcondition</b>: nh.empty()
189 node_handle (BOOST_RV_REF(node_handle) nh) BOOST_NOEXCEPT
191 { this->move_construct_end(nh); }
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
195 //! nator_traits::rebind_traits<container_node_type>::deallocate.
196 ~node_handle() BOOST_NOEXCEPT
199 this->destroy_deallocate_node();
200 this->destroy_alloc();
204 //! <b>Requires</b>: Either this->empty(), or nator_traits::propagate_on_container_move_assignment is true, or
205 //! node_alloc() == nh.node_alloc().
207 //! <b>Effects</b>: If m_ptr != nullptr, destroys the value_type subobject in the container_node_type object
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
211 //! node_alloc(). Assigns nullptr to nh.m_ptr and assigns nullopt to nh.node_alloc().
213 //! <b>Returns</b>: *this.
215 //! <b>Throws</b>: Nothing.
216 node_handle & operator=(BOOST_RV_REF(node_handle) nh) BOOST_NOEXCEPT
218 BOOST_ASSERT(this->empty() || nator_traits::propagate_on_container_move_assignment::value
219 || nator_traits::equal(node_alloc(), nh.node_alloc()));
221 bool const was_this_non_null = !this->empty();
222 bool const was_nh_non_null = !nh.empty();
225 if(was_this_non_null){
226 this->destroy_deallocate_node();
227 if(nator_traits::propagate_on_container_move_assignment::value){
228 this->node_alloc() = ::boost::move(nh.node_alloc());
232 this->move_construct_alloc(nh.node_alloc());
235 nh.m_ptr = node_pointer();
238 else if(was_this_non_null){
239 this->destroy_deallocate_node();
240 this->destroy_alloc();
241 m_ptr = node_pointer();
246 //! <b>Requires</b>: empty() == false.
248 //! <b>Returns</b>: A reference to the value_type subobject in the container_node_type object pointed to by m_ptr
250 //! <b>Throws</b>: Nothing.
251 value_type& value() const BOOST_NOEXCEPT
253 BOOST_STATIC_ASSERT((container_detail::is_same<KeyMapped, void>::value));
254 BOOST_ASSERT(!empty());
255 return m_ptr->get_data();
258 //! <b>Requires</b>: empty() == false.
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.
263 //! <b>Throws</b>: Nothing.
265 //! <b>Requires</b>: Modifying the key through the returned reference is permitted.
266 key_type& key() const BOOST_NOEXCEPT
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()));
273 //! <b>Requires</b>: empty() == false.
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
278 //! <b>Throws</b>: Nothing.
279 mapped_type& mapped() const BOOST_NOEXCEPT
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());
286 //! <b>Requires</b>: empty() == false.
288 //! <b>Returns</b>: A copy of the internally hold allocator.
290 //! <b>Throws</b>: Nothing.
291 allocator_type get_allocator() const
293 BOOST_ASSERT(!empty());
294 return this->node_alloc();
297 //! <b>Returns</b>: m_ptr != nullptr.
299 #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
300 BOOST_CONTAINER_FORCEINLINE explicit operator bool
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
305 ()const BOOST_NOEXCEPT
306 { return m_ptr ? &bool_conversion::for_bool : explicit_bool_arg(0); }
308 //! <b>Returns</b>: m_ptr == nullptr.
310 bool empty() const BOOST_NOEXCEPT
315 //! <b>Requires</b>: this->empty(), or nh.empty(), or nator_traits::propagate_on_container_swap is true, or
316 //! node_alloc() == nh.node_alloc().
318 //! <b>Effects</b>: Calls swap(m_ptr, nh.m_ptr). If this->empty(), or nh.empty(), or nator_traits::propagate_on_-
319 //! container_swap is true calls swap(node_alloc(), nh.node_alloc()).
320 void swap(node_handle &nh)
321 BOOST_NOEXCEPT_IF(nator_traits::propagate_on_container_swap::value || nator_traits::is_always_equal::value)
323 BOOST_ASSERT(this->empty() || nh.empty() || nator_traits::propagate_on_container_swap::value
324 || nator_traits::equal(node_alloc(), nh.node_alloc()));
326 bool const was_this_non_null = !this->empty();
327 bool const was_nh_non_null = !nh.empty();
330 if(was_this_non_null){
331 if(nator_traits::propagate_on_container_swap::value){
332 ::boost::adl_move_swap(this->node_alloc(), nh.node_alloc());
336 this->move_construct_alloc(nh.node_alloc());
340 else if(was_this_non_null){
341 nh.move_construct_alloc(this->node_alloc());
342 this->destroy_alloc();
344 ::boost::adl_move_swap(m_ptr, nh.m_ptr);
347 //! <b>Effects</b>: If this->empty() returns nullptr, otherwise returns m_ptr
348 //! resets m_ptr to nullptr and destroys the internal allocator.
350 //! <b>Postcondition</b>: this->empty()
352 //! <b>Note</b>: Non-standard extensions
353 node_pointer release() BOOST_NOEXCEPT
355 node_pointer p(m_ptr);
356 m_ptr = node_pointer();
358 this->destroy_alloc();
362 //! <b>Effects</b>: Returns m_ptr.
364 //! <b>Note</b>: Non-standard extensions
365 node_pointer get() const BOOST_NOEXCEPT
370 //! <b>Effects</b>: Returns a reference to the internal node allocator.
372 //! <b>Note</b>: Non-standard extensions
373 nallocator_type &node_alloc() BOOST_NOEXCEPT
375 BOOST_ASSERT(!empty());
376 return *static_cast<nallocator_type*>(m_nalloc_storage.address());
380 //! <b>Effects</b>: Returns a reference to the internal node allocator.
382 //! <b>Note</b>: Non-standard extensions
383 const nallocator_type &node_alloc() const BOOST_NOEXCEPT
385 BOOST_ASSERT(!empty());
386 return *static_cast<const nallocator_type*>(m_nalloc_storage.address());
389 //! <b>Effects</b>: x.swap(y).
391 friend void swap(node_handle & x, node_handle & y) BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT(x.swap(y)))
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:
399 //! <ul><li>bool inserted</li>;
400 //! <li>Iterator position</li>;
401 //! <li>NodeType node</li></ul>
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
409 BOOST_MOVABLE_BUT_NOT_COPYABLE(insert_return_type_base)
412 insert_return_type_base()
413 : inserted(false), position(), node()
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))
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))
425 insert_return_type_base & operator=(BOOST_RV_REF(insert_return_type_base) other)
427 inserted = other.inserted;
428 position = other.position;
429 node = boost::move(other.node);
438 } //namespace container {
439 } //namespace boost {
441 #include <boost/container/detail/config_end.hpp>
443 #endif //BOOST_CONTAINER_NODE_HANDLE_HPP