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> 26 #include <boost/move/detail/to_raw_pointer.hpp> 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 43 template<class Value, class KeyMapped> 44 struct node_handle_keymapped_traits 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> 52 { 53 typedef Value key_type; 54 typedef Value mapped_type; 55 }; 56 57 class node_handle_friend 58 { 59 public: 60 61 template<class NH> destroy_alloc(NH & nh)62 BOOST_CONTAINER_FORCEINLINE static void destroy_alloc(NH &nh) BOOST_NOEXCEPT 63 { nh.destroy_alloc(); } 64 65 template<class NH> get_node_pointer(NH & nh)66 BOOST_CONTAINER_FORCEINLINE static typename NH::node_pointer &get_node_pointer(NH &nh) BOOST_NOEXCEPT 67 { return nh.get_node_pointer(); } 68 }; 69 70 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. 90 template <class NodeAllocator, class KeyMapped = void> 91 class node_handle 92 { 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; 98 99 public: 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; 105 106 typedef priv_node_t container_node_type; 107 friend class node_handle_friend; 108 109 ///@cond 110 private: 111 BOOST_MOVABLE_BUT_NOT_COPYABLE(node_handle) 112 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; 117 118 node_pointer m_ptr; 119 nalloc_storage_t m_nalloc_storage; 120 move_construct_alloc(nallocator_type & al)121 void move_construct_alloc(nallocator_type &al) 122 { ::new(m_nalloc_storage.address(), boost_container_new_t()) nallocator_type(::boost::move(al)); } 123 destroy_deallocate_node()124 void destroy_deallocate_node() 125 { 126 nator_traits::destroy(this->node_alloc(), boost::movelib::to_raw_pointer(m_ptr)); 127 nator_traits::deallocate(this->node_alloc(), m_ptr, 1u); 128 } 129 130 template<class OtherNodeHandle> move_construct_end(OtherNodeHandle & nh)131 void move_construct_end(OtherNodeHandle &nh) 132 { 133 if(m_ptr){ 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(); 137 } 138 BOOST_ASSERT(nh.empty()); 139 } 140 destroy_alloc()141 void destroy_alloc() BOOST_NOEXCEPT 142 { static_cast<nallocator_type*>(m_nalloc_storage.address())->~nallocator_type(); } 143 get_node_pointer()144 node_pointer &get_node_pointer() BOOST_NOEXCEPT 145 { return m_ptr; } 146 147 ///@endcond 148 149 public: 150 //! <b>Effects</b>: Initializes m_ptr to nullptr. 151 //! 152 //! <b>Postcondition</b>: this->empty() node_handle()153 BOOST_CXX14_CONSTEXPR node_handle() BOOST_NOEXCEPT 154 : m_ptr() 155 { } 156 157 //! <b>Effects</b>: Constructs a node_handle object initializing internal pointer with p. 158 //! If p != nullptr copy constructs internal allocator from al. node_handle(node_pointer p,const nallocator_type & al)159 node_handle(node_pointer p, const nallocator_type &al) BOOST_NOEXCEPT 160 : m_ptr(p) 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> node_handle(BOOST_RV_REF_BEG node_handle<NodeAllocator,KeyMapped2> BOOST_RV_REF_END nh,typename dtl::enable_if_c<((unsigned)dtl::is_same<KeyMapped,void>::value+(unsigned)dtl::is_same<KeyMapped2,void>::value)==1u>::type * =0)176 node_handle( BOOST_RV_REF_BEG node_handle<NodeAllocator, KeyMapped2> BOOST_RV_REF_END nh 177 , typename dtl::enable_if_c 178 < ((unsigned)dtl::is_same<KeyMapped, void>::value + 179 (unsigned)dtl::is_same<KeyMapped2, void>::value) == 1u 180 >::type* = 0) BOOST_NOEXCEPT 181 : m_ptr(nh.get()) 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() node_handle(BOOST_RV_REF (node_handle)nh)189 node_handle (BOOST_RV_REF(node_handle) nh) BOOST_NOEXCEPT 190 : m_ptr(nh.m_ptr) 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 195 //! nator_traits::rebind_traits<container_node_type>::deallocate. ~node_handle()196 ~node_handle() BOOST_NOEXCEPT 197 { 198 if(!this->empty()){ 199 this->destroy_deallocate_node(); 200 this->destroy_alloc(); 201 } 202 } 203 204 //! <b>Requires</b>: Either this->empty(), or nator_traits::propagate_on_container_move_assignment is true, or 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 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(). 212 //! 213 //! <b>Returns</b>: *this. 214 //! 215 //! <b>Throws</b>: Nothing. operator =(BOOST_RV_REF (node_handle)nh)216 node_handle & operator=(BOOST_RV_REF(node_handle) nh) BOOST_NOEXCEPT 217 { 218 BOOST_ASSERT(this->empty() || nator_traits::propagate_on_container_move_assignment::value 219 || nator_traits::equal(node_alloc(), nh.node_alloc())); 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){ 226 this->destroy_deallocate_node(); 227 if(nator_traits::propagate_on_container_move_assignment::value){ 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){ 239 this->destroy_deallocate_node(); 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. value() const251 value_type& value() const BOOST_NOEXCEPT 252 { 253 BOOST_STATIC_ASSERT((dtl::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. key() const266 key_type& key() const BOOST_NOEXCEPT 267 { 268 BOOST_STATIC_ASSERT((!dtl::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. mapped() const279 mapped_type& mapped() const BOOST_NOEXCEPT 280 { 281 BOOST_STATIC_ASSERT((!dtl::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. get_allocator() const291 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 operator bool() const300 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 //! empty() const310 bool empty() const BOOST_NOEXCEPT 311 { 312 return !this->m_ptr; 313 } 314 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(). 317 //! 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()). swap(node_handle & nh)320 void swap(node_handle &nh) 321 BOOST_NOEXCEPT_IF(nator_traits::propagate_on_container_swap::value || nator_traits::is_always_equal::value) 322 { 323 BOOST_ASSERT(this->empty() || nh.empty() || nator_traits::propagate_on_container_swap::value 324 || nator_traits::equal(node_alloc(), nh.node_alloc())); 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){ 331 if(nator_traits::propagate_on_container_swap::value){ 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()); 342 this->destroy_alloc(); 343 } 344 ::boost::adl_move_swap(m_ptr, nh.m_ptr); 345 } 346 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 release()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 get() const365 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 node_alloc()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 node_alloc() const383 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 389 //! <b>Effects</b>: x.swap(y). 390 //! swap(node_handle & x,node_handle & y)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: insert_return_type_baseboost::container::insert_return_type_base412 insert_return_type_base() 413 : inserted(false), position(), node() 414 {} 415 insert_return_type_baseboost::container::insert_return_type_base416 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> insert_return_type_baseboost::container::insert_return_type_base421 insert_return_type_base(bool insert, RelatedIt it, BOOST_RV_REF(RelatedNode) node) 422 : inserted(insert), position(it), node(boost::move(node)) 423 {} 424 operator =boost::container::insert_return_type_base425 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 444