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> 33 #include <boost/move/detail/iterator_to_raw_pointer.hpp> 34 #include <boost/container/detail/mpl.hpp> 35 #include <boost/container/detail/placement_new.hpp> 36 #include <boost/move/detail/to_raw_pointer.hpp> 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 { 53 namespace dtl { 54 55 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(key_compare) 56 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(key_equal) 57 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(hasher) 58 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(predicate_type) 59 60 template<class Allocator, class ICont> 61 struct node_alloc_holder 62 : public allocator_traits<Allocator>::template 63 portable_rebind_alloc<typename ICont::value_type>::type //NodeAlloc 64 { 65 //If the intrusive container is an associative container, obtain the predicate, which will 66 //be of type node_compare<>. If not an associative container val_compare will be a "nat" type. 67 typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT 68 ( boost::container::dtl:: 69 , ICont, key_compare, dtl::nat) intrusive_val_compare; 70 //In that case obtain the value predicate from the node predicate via predicate_type 71 //if intrusive_val_compare is node_compare<>, nat otherwise 72 typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT 73 ( boost::container::dtl:: 74 , intrusive_val_compare 75 , predicate_type, dtl::nat) val_compare; 76 77 //If the intrusive container is a hash container, obtain the predicate, which will 78 //be of type node_compare<>. If not an associative container val_equal will be a "nat" type. 79 typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT 80 (boost::container::dtl:: 81 , ICont, key_equal, dtl::nat2) intrusive_val_equal; 82 typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT 83 (boost::container::dtl:: 84 , ICont, hasher, dtl::nat3) intrusive_val_hasher; 85 //In that case obtain the value predicate from the node predicate via predicate_type 86 //if intrusive_val_compare is node_compare<>, nat otherwise 87 typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT 88 (boost::container::dtl:: 89 , intrusive_val_equal 90 , predicate_type, dtl::nat2) val_equal; 91 typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT 92 (boost::container::dtl:: 93 , intrusive_val_hasher 94 , predicate_type, dtl::nat3) val_hasher; 95 96 typedef allocator_traits<Allocator> allocator_traits_type; 97 typedef typename allocator_traits_type::value_type val_type; 98 typedef ICont intrusive_container; 99 typedef typename ICont::value_type Node; 100 typedef typename allocator_traits_type::template 101 portable_rebind_alloc<Node>::type NodeAlloc; 102 typedef allocator_traits<NodeAlloc> node_allocator_traits_type; 103 typedef dtl::allocator_version_traits<NodeAlloc> node_allocator_version_traits_type; 104 typedef Allocator ValAlloc; 105 typedef typename node_allocator_traits_type::pointer NodePtr; 106 typedef dtl::scoped_deallocator<NodeAlloc> Deallocator; 107 typedef typename node_allocator_traits_type::size_type size_type; 108 typedef typename node_allocator_traits_type::difference_type difference_type; 109 typedef dtl::integral_constant<unsigned, 110 boost::container::dtl:: 111 version<NodeAlloc>::value> alloc_version; 112 typedef typename ICont::iterator icont_iterator; 113 typedef typename ICont::const_iterator icont_citerator; 114 typedef allocator_destroyer<NodeAlloc> Destroyer; 115 typedef allocator_traits<NodeAlloc> NodeAllocTraits; 116 typedef allocator_version_traits<NodeAlloc> AllocVersionTraits; 117 118 private: 119 BOOST_COPYABLE_AND_MOVABLE(node_alloc_holder) 120 121 public: 122 123 //Constructors for sequence containers node_alloc_holderboost::container::dtl::node_alloc_holder124 node_alloc_holder() 125 {} 126 node_alloc_holderboost::container::dtl::node_alloc_holder127 explicit node_alloc_holder(const ValAlloc &a) 128 : NodeAlloc(a) 129 {} 130 131 //Constructors for associative containers node_alloc_holderboost::container::dtl::node_alloc_holder132 node_alloc_holder(const val_compare &c, const ValAlloc &a) 133 : NodeAlloc(a), m_icont(typename ICont::key_compare(c)) 134 {} 135 node_alloc_holderboost::container::dtl::node_alloc_holder136 node_alloc_holder(const val_hasher &hf, const val_equal &eql, const ValAlloc &a) 137 : NodeAlloc(a) 138 , m_icont(typename ICont::bucket_traits() 139 , typename ICont::hasher(hf) 140 , typename ICont::key_equal(eql)) 141 {} 142 node_alloc_holderboost::container::dtl::node_alloc_holder143 node_alloc_holder(const val_hasher &hf, const ValAlloc &a) 144 : NodeAlloc(a) 145 , m_icont(typename ICont::bucket_traits() 146 , typename ICont::hasher(hf) 147 , typename ICont::key_equal()) 148 {} 149 node_alloc_holderboost::container::dtl::node_alloc_holder150 node_alloc_holder(const val_hasher &hf) 151 : m_icont(typename ICont::bucket_traits() 152 , typename ICont::hasher(hf) 153 , typename ICont::key_equal()) 154 {} 155 node_alloc_holderboost::container::dtl::node_alloc_holder156 explicit node_alloc_holder(const node_alloc_holder &x) 157 : NodeAlloc(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc())) 158 {} 159 node_alloc_holderboost::container::dtl::node_alloc_holder160 node_alloc_holder(const node_alloc_holder &x, const val_compare &c) 161 : NodeAlloc(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc())) 162 , m_icont(typename ICont::key_compare(c)) 163 {} 164 node_alloc_holderboost::container::dtl::node_alloc_holder165 node_alloc_holder(const node_alloc_holder &x, const val_hasher &hf, const val_equal &eql) 166 : NodeAlloc(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc())) 167 , m_icont( typename ICont::bucket_traits() 168 , typename ICont::hasher(hf) 169 , typename ICont::key_equal(eql)) 170 {} 171 node_alloc_holderboost::container::dtl::node_alloc_holder172 node_alloc_holder(const val_hasher &hf, const val_equal &eql) 173 : m_icont(typename ICont::bucket_traits() 174 , typename ICont::hasher(hf) 175 , typename ICont::key_equal(eql)) 176 {} 177 node_alloc_holderboost::container::dtl::node_alloc_holder178 explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x) 179 : NodeAlloc(boost::move(x.node_alloc())) 180 { this->icont().swap(x.icont()); } 181 node_alloc_holderboost::container::dtl::node_alloc_holder182 explicit node_alloc_holder(const val_compare &c) 183 : m_icont(typename ICont::key_compare(c)) 184 {} 185 186 //helpers for move assignments node_alloc_holderboost::container::dtl::node_alloc_holder187 explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const val_compare &c) 188 : NodeAlloc(boost::move(x.node_alloc())), m_icont(typename ICont::key_compare(c)) 189 { this->icont().swap(x.icont()); } 190 node_alloc_holderboost::container::dtl::node_alloc_holder191 explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const val_hasher &hf, const val_equal &eql) 192 : NodeAlloc(boost::move(x.node_alloc())) 193 , m_icont( typename ICont::bucket_traits() 194 , typename ICont::hasher(hf) 195 , typename ICont::key_equal(eql)) 196 { this->icont().swap(x.icont()); } 197 copy_assign_allocboost::container::dtl::node_alloc_holder198 void copy_assign_alloc(const node_alloc_holder &x) 199 { 200 dtl::bool_<allocator_traits_type::propagate_on_container_copy_assignment::value> flag; 201 dtl::assign_alloc( static_cast<NodeAlloc &>(*this) 202 , static_cast<const NodeAlloc &>(x), flag); 203 } 204 move_assign_allocboost::container::dtl::node_alloc_holder205 void move_assign_alloc( node_alloc_holder &x) 206 { 207 dtl::bool_<allocator_traits_type::propagate_on_container_move_assignment::value> flag; 208 dtl::move_alloc( static_cast<NodeAlloc &>(*this) 209 , static_cast<NodeAlloc &>(x), flag); 210 } 211 ~node_alloc_holderboost::container::dtl::node_alloc_holder212 ~node_alloc_holder() 213 { this->clear(alloc_version()); } 214 max_sizeboost::container::dtl::node_alloc_holder215 size_type max_size() const 216 { return allocator_traits_type::max_size(this->node_alloc()); } 217 allocate_oneboost::container::dtl::node_alloc_holder218 NodePtr allocate_one() 219 { return AllocVersionTraits::allocate_one(this->node_alloc()); } 220 deallocate_oneboost::container::dtl::node_alloc_holder221 void deallocate_one(const NodePtr &p) 222 { AllocVersionTraits::deallocate_one(this->node_alloc(), p); } 223 224 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 225 226 template<class ...Args> create_nodeboost::container::dtl::node_alloc_holder227 NodePtr create_node(Args &&...args) 228 { 229 NodePtr p = this->allocate_one(); 230 BOOST_TRY{ 231 ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) Node; 232 allocator_traits<NodeAlloc>::construct 233 (this->node_alloc() 234 , p->get_real_data_ptr(), boost::forward<Args>(args)...); 235 } 236 BOOST_CATCH(...) { 237 p->destroy_header(); 238 this->node_alloc().deallocate(p, 1); 239 BOOST_RETHROW 240 } 241 BOOST_CATCH_END 242 return (p); 243 } 244 245 #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 246 247 #define BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL(N) \ 248 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 249 NodePtr create_node(BOOST_MOVE_UREF##N)\ 250 {\ 251 NodePtr p = this->allocate_one();\ 252 BOOST_TRY{\ 253 ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) Node;\ 254 allocator_traits<NodeAlloc>::construct\ 255 ( this->node_alloc()\ 256 , p->get_real_data_ptr()\ 257 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 258 }\ 259 BOOST_CATCH(...) {\ 260 p->destroy_header();\ 261 this->node_alloc().deallocate(p, 1);\ 262 BOOST_RETHROW\ 263 }\ 264 BOOST_CATCH_END\ 265 return (p);\ 266 }\ 267 // BOOST_MOVE_ITERATE_0TO9boost::container::dtl::node_alloc_holder268 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL) 269 #undef BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL 270 271 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 272 273 template<class It> 274 NodePtr create_node_from_it(const It &it) 275 { 276 NodePtr p = this->allocate_one(); 277 BOOST_TRY{ 278 ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) Node; 279 ::boost::container::construct_in_place(this->node_alloc(), p->get_real_data_ptr(), it); 280 } 281 BOOST_CATCH(...) { 282 p->destroy_header(); 283 this->node_alloc().deallocate(p, 1); 284 BOOST_RETHROW 285 } 286 BOOST_CATCH_END 287 return (p); 288 } 289 290 template<class KeyConvertible> create_node_from_keyboost::container::dtl::node_alloc_holder291 NodePtr create_node_from_key(BOOST_FWD_REF(KeyConvertible) key) 292 { 293 NodePtr p = this->allocate_one(); 294 BOOST_TRY{ 295 ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) Node; 296 NodeAlloc &na = this->node_alloc(); 297 node_allocator_traits_type::construct 298 (na, dtl::addressof(p->get_real_data().first), boost::forward<KeyConvertible>(key)); 299 BOOST_TRY{ 300 node_allocator_traits_type::construct(na, dtl::addressof(p->get_real_data().second)); 301 } 302 BOOST_CATCH(...){ 303 node_allocator_traits_type::destroy(na, dtl::addressof(p->get_real_data().first)); 304 BOOST_RETHROW; 305 } 306 BOOST_CATCH_END 307 } 308 BOOST_CATCH(...) { 309 p->destroy_header(); 310 this->node_alloc().deallocate(p, 1); 311 BOOST_RETHROW 312 } 313 BOOST_CATCH_END 314 return (p); 315 } 316 destroy_nodeboost::container::dtl::node_alloc_holder317 void destroy_node(const NodePtr &nodep) 318 { 319 allocator_traits<NodeAlloc>::destroy(this->node_alloc(), boost::movelib::to_raw_pointer(nodep)); 320 this->deallocate_one(nodep); 321 } 322 swapboost::container::dtl::node_alloc_holder323 void swap(node_alloc_holder &x) 324 { 325 this->icont().swap(x.icont()); 326 dtl::bool_<allocator_traits_type::propagate_on_container_swap::value> flag; 327 dtl::swap_alloc(this->node_alloc(), x.node_alloc(), flag); 328 } 329 330 template<class FwdIterator, class Inserter> allocate_many_and_constructboost::container::dtl::node_alloc_holder331 void allocate_many_and_construct 332 (FwdIterator beg, difference_type n, Inserter inserter) 333 { 334 if(n){ 335 typedef typename node_allocator_version_traits_type::multiallocation_chain multiallocation_chain_t; 336 337 //Try to allocate memory in a single block 338 typedef typename multiallocation_chain_t::iterator multialloc_iterator_t; 339 multiallocation_chain_t chain; 340 NodeAlloc &nalloc = this->node_alloc(); 341 node_allocator_version_traits_type::allocate_individual(nalloc, n, chain); 342 multialloc_iterator_t itbeg = chain.begin(); 343 multialloc_iterator_t itlast = chain.last(); 344 chain.clear(); 345 346 Node *p = 0; 347 BOOST_TRY{ 348 Deallocator node_deallocator(NodePtr(), nalloc); 349 dtl::scoped_destructor<NodeAlloc> sdestructor(nalloc, 0); 350 while(n){ 351 --n; 352 p = boost::movelib::iterator_to_raw_pointer(itbeg); 353 ++itbeg; //Increment iterator before overwriting pointed memory 354 //This does not throw 355 p = ::new(p, boost_container_new_t()) Node; 356 node_deallocator.set(p); 357 //This can throw 358 boost::container::construct_in_place(nalloc, p->get_real_data_ptr(), beg); 359 sdestructor.set(p); 360 ++beg; 361 //This can throw in some containers (predicate might throw). 362 //(sdestructor will destruct the node and node_deallocator will deallocate it in case of exception) 363 inserter(*p); 364 sdestructor.set(0); 365 } 366 sdestructor.release(); 367 node_deallocator.release(); 368 } 369 BOOST_CATCH(...){ 370 p->destroy_header(); 371 chain.incorporate_after(chain.last(), &*itbeg, &*itlast, n); 372 node_allocator_version_traits_type::deallocate_individual(this->node_alloc(), chain); 373 BOOST_RETHROW 374 } 375 BOOST_CATCH_END 376 } 377 } 378 clearboost::container::dtl::node_alloc_holder379 void clear(version_1) 380 { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); } 381 clearboost::container::dtl::node_alloc_holder382 void clear(version_2) 383 { 384 typename NodeAlloc::multiallocation_chain chain; 385 allocator_destroyer_and_chain_builder<NodeAlloc> builder(this->node_alloc(), chain); 386 this->icont().clear_and_dispose(builder); 387 //BOOST_STATIC_ASSERT((::boost::has_move_emulation_enabled<typename NodeAlloc::multiallocation_chain>::value == true)); 388 if(!chain.empty()) 389 this->node_alloc().deallocate_individual(chain); 390 } 391 erase_rangeboost::container::dtl::node_alloc_holder392 icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_1) 393 { return this->icont().erase_and_dispose(first, last, Destroyer(this->node_alloc())); } 394 erase_rangeboost::container::dtl::node_alloc_holder395 icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_2) 396 { 397 typedef typename NodeAlloc::multiallocation_chain multiallocation_chain; 398 NodeAlloc & nalloc = this->node_alloc(); 399 multiallocation_chain chain; 400 allocator_destroyer_and_chain_builder<NodeAlloc> chain_builder(nalloc, chain); 401 icont_iterator ret_it = this->icont().erase_and_dispose(first, last, chain_builder); 402 nalloc.deallocate_individual(chain); 403 return ret_it; 404 } 405 406 template<class Key, class Comparator> erase_keyboost::container::dtl::node_alloc_holder407 size_type erase_key(const Key& k, const Comparator &comp, version_1) 408 { return this->icont().erase_and_dispose(k, comp, Destroyer(this->node_alloc())); } 409 410 template<class Key, class Comparator> erase_keyboost::container::dtl::node_alloc_holder411 size_type erase_key(const Key& k, const Comparator &comp, version_2) 412 { 413 allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc()); 414 return this->icont().erase_and_dispose(k, comp, chain_holder.get_chain_builder()); 415 } 416 417 protected: 418 struct cloner 419 { clonerboost::container::dtl::node_alloc_holder::cloner420 explicit cloner(node_alloc_holder &holder) 421 : m_holder(holder) 422 {} 423 operator ()boost::container::dtl::node_alloc_holder::cloner424 NodePtr operator()(const Node &other) const 425 { return m_holder.create_node(other.get_real_data()); } 426 427 node_alloc_holder &m_holder; 428 }; 429 430 struct move_cloner 431 { move_clonerboost::container::dtl::node_alloc_holder::move_cloner432 move_cloner(node_alloc_holder &holder) 433 : m_holder(holder) 434 {} 435 operator ()boost::container::dtl::node_alloc_holder::move_cloner436 NodePtr operator()(Node &other) 437 { //Use get_real_data() instead of get_real_data to allow moving const key in [multi]map 438 return m_holder.create_node(::boost::move(other.get_real_data())); 439 } 440 441 node_alloc_holder &m_holder; 442 }; 443 non_const_icontboost::container::dtl::node_alloc_holder444 ICont &non_const_icont() const 445 { return const_cast<ICont&>(this->m_icont); } 446 node_allocboost::container::dtl::node_alloc_holder447 NodeAlloc &node_alloc() 448 { return static_cast<NodeAlloc &>(*this); } 449 node_allocboost::container::dtl::node_alloc_holder450 const NodeAlloc &node_alloc() const 451 { return static_cast<const NodeAlloc &>(*this); } 452 453 public: icontboost::container::dtl::node_alloc_holder454 ICont &icont() 455 { return this->m_icont; } 456 icontboost::container::dtl::node_alloc_holder457 const ICont &icont() const 458 { return this->m_icont; } 459 460 private: 461 //The intrusive container 462 ICont m_icont; 463 }; 464 465 } //namespace dtl { 466 } //namespace container { 467 } //namespace boost { 468 469 #include <boost/container/detail/config_end.hpp> 470 471 #endif // BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_ 472