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/container/detail/iterator_to_raw_pointer.hpp> 34 #include <boost/container/detail/mpl.hpp> 35 #include <boost/container/detail/placement_new.hpp> 36 #include <boost/container/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 container_detail { 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(boost::container::container_detail::, ICont, 64 value_compare, container_detail::nat) intrusive_value_compare; 65 //In that case obtain the value predicate from the node predicate via predicate_type 66 //if intrusive_value_compare is node_compare<>, nat otherwise 67 typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT(boost::container::container_detail::, intrusive_value_compare, 68 predicate_type, container_detail::nat) value_compare; 69 70 typedef allocator_traits<Allocator> allocator_traits_type; 71 typedef typename allocator_traits_type::value_type value_type; 72 typedef ICont intrusive_container; 73 typedef typename ICont::value_type Node; 74 typedef typename allocator_traits_type::template 75 portable_rebind_alloc<Node>::type NodeAlloc; 76 typedef allocator_traits<NodeAlloc> node_allocator_traits_type; 77 typedef container_detail::allocator_version_traits<NodeAlloc> node_allocator_version_traits_type; 78 typedef Allocator ValAlloc; 79 typedef typename node_allocator_traits_type::pointer NodePtr; 80 typedef container_detail::scoped_deallocator<NodeAlloc> Deallocator; 81 typedef typename node_allocator_traits_type::size_type size_type; 82 typedef typename node_allocator_traits_type::difference_type difference_type; 83 typedef container_detail::integral_constant<unsigned, 84 boost::container::container_detail:: 85 version<NodeAlloc>::value> alloc_version; 86 typedef typename ICont::iterator icont_iterator; 87 typedef typename ICont::const_iterator icont_citerator; 88 typedef allocator_destroyer<NodeAlloc> Destroyer; 89 typedef allocator_traits<NodeAlloc> NodeAllocTraits; 90 typedef allocator_version_traits<NodeAlloc> AllocVersionTraits; 91 92 private: 93 BOOST_COPYABLE_AND_MOVABLE(node_alloc_holder) 94 95 public: 96 97 //Constructors for sequence containers node_alloc_holderboost::container::container_detail::node_alloc_holder98 node_alloc_holder() 99 : members_() 100 {} 101 node_alloc_holderboost::container::container_detail::node_alloc_holder102 explicit node_alloc_holder(const ValAlloc &a) 103 : members_(a) 104 {} 105 node_alloc_holderboost::container::container_detail::node_alloc_holder106 explicit node_alloc_holder(const node_alloc_holder &x) 107 : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc())) 108 {} 109 node_alloc_holderboost::container::container_detail::node_alloc_holder110 explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x) 111 : members_(boost::move(x.node_alloc())) 112 { this->icont().swap(x.icont()); } 113 114 //Constructors for associative containers node_alloc_holderboost::container::container_detail::node_alloc_holder115 explicit node_alloc_holder(const value_compare &c, const ValAlloc &a) 116 : members_(a, c) 117 {} 118 node_alloc_holderboost::container::container_detail::node_alloc_holder119 explicit node_alloc_holder(const value_compare &c, const node_alloc_holder &x) 120 : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()), c) 121 {} 122 node_alloc_holderboost::container::container_detail::node_alloc_holder123 explicit node_alloc_holder(const value_compare &c) 124 : members_(c) 125 {} 126 127 //helpers for move assignments node_alloc_holderboost::container::container_detail::node_alloc_holder128 explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const value_compare &c) 129 : members_(boost::move(x.node_alloc()), c) 130 { this->icont().swap(x.icont()); } 131 copy_assign_allocboost::container::container_detail::node_alloc_holder132 void copy_assign_alloc(const node_alloc_holder &x) 133 { 134 container_detail::bool_<allocator_traits_type::propagate_on_container_copy_assignment::value> flag; 135 container_detail::assign_alloc( static_cast<NodeAlloc &>(this->members_) 136 , static_cast<const NodeAlloc &>(x.members_), flag); 137 } 138 move_assign_allocboost::container::container_detail::node_alloc_holder139 void move_assign_alloc( node_alloc_holder &x) 140 { 141 container_detail::bool_<allocator_traits_type::propagate_on_container_move_assignment::value> flag; 142 container_detail::move_alloc( static_cast<NodeAlloc &>(this->members_) 143 , static_cast<NodeAlloc &>(x.members_), flag); 144 } 145 ~node_alloc_holderboost::container::container_detail::node_alloc_holder146 ~node_alloc_holder() 147 { this->clear(alloc_version()); } 148 max_sizeboost::container::container_detail::node_alloc_holder149 size_type max_size() const 150 { return allocator_traits_type::max_size(this->node_alloc()); } 151 allocate_oneboost::container::container_detail::node_alloc_holder152 NodePtr allocate_one() 153 { return AllocVersionTraits::allocate_one(this->node_alloc()); } 154 deallocate_oneboost::container::container_detail::node_alloc_holder155 void deallocate_one(const NodePtr &p) 156 { AllocVersionTraits::deallocate_one(this->node_alloc(), p); } 157 158 #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 159 160 template<class ...Args> create_nodeboost::container::container_detail::node_alloc_holder161 NodePtr create_node(Args &&...args) 162 { 163 NodePtr p = this->allocate_one(); 164 Deallocator node_deallocator(p, this->node_alloc()); 165 allocator_traits<NodeAlloc>::construct 166 ( this->node_alloc() 167 , container_detail::addressof(p->m_data), boost::forward<Args>(args)...); 168 node_deallocator.release(); 169 //This does not throw 170 typedef typename Node::hook_type hook_type; 171 ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type; 172 return (p); 173 } 174 175 #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 176 177 #define BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL(N) \ 178 BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \ 179 NodePtr create_node(BOOST_MOVE_UREF##N)\ 180 {\ 181 NodePtr p = this->allocate_one();\ 182 Deallocator node_deallocator(p, this->node_alloc());\ 183 allocator_traits<NodeAlloc>::construct\ 184 ( this->node_alloc()\ 185 , container_detail::addressof(p->m_data)\ 186 BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\ 187 node_deallocator.release();\ 188 typedef typename Node::hook_type hook_type;\ 189 ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;\ 190 return (p);\ 191 }\ 192 // BOOST_MOVE_ITERATE_0TO9boost::container::container_detail::node_alloc_holder193 BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL) 194 #undef BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL 195 196 #endif // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES) 197 198 template<class It> 199 NodePtr create_node_from_it(const It &it) 200 { 201 NodePtr p = this->allocate_one(); 202 Deallocator node_deallocator(p, this->node_alloc()); 203 ::boost::container::construct_in_place(this->node_alloc(), container_detail::addressof(p->m_data), it); 204 node_deallocator.release(); 205 //This does not throw 206 typedef typename Node::hook_type hook_type; 207 ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type; 208 return (p); 209 } 210 destroy_nodeboost::container::container_detail::node_alloc_holder211 void destroy_node(const NodePtr &nodep) 212 { 213 allocator_traits<NodeAlloc>::destroy(this->node_alloc(), container_detail::to_raw_pointer(nodep)); 214 this->deallocate_one(nodep); 215 } 216 swapboost::container::container_detail::node_alloc_holder217 void swap(node_alloc_holder &x) 218 { 219 this->icont().swap(x.icont()); 220 container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag; 221 container_detail::swap_alloc(this->node_alloc(), x.node_alloc(), flag); 222 } 223 224 template<class FwdIterator, class Inserter> allocate_many_and_constructboost::container::container_detail::node_alloc_holder225 void allocate_many_and_construct 226 (FwdIterator beg, difference_type n, Inserter inserter) 227 { 228 if(n){ 229 typedef typename node_allocator_version_traits_type::multiallocation_chain multiallocation_chain; 230 231 //Try to allocate memory in a single block 232 typedef typename multiallocation_chain::iterator multialloc_iterator; 233 multiallocation_chain mem; 234 NodeAlloc &nalloc = this->node_alloc(); 235 node_allocator_version_traits_type::allocate_individual(nalloc, n, mem); 236 multialloc_iterator itbeg(mem.begin()), itlast(mem.last()); 237 mem.clear(); 238 Node *p = 0; 239 BOOST_TRY{ 240 Deallocator node_deallocator(NodePtr(), nalloc); 241 container_detail::scoped_destructor<NodeAlloc> sdestructor(nalloc, 0); 242 while(n--){ 243 p = container_detail::iterator_to_raw_pointer(itbeg); 244 node_deallocator.set(p); 245 ++itbeg; 246 //This can throw 247 boost::container::construct_in_place(nalloc, container_detail::addressof(p->m_data), beg); 248 sdestructor.set(p); 249 ++beg; 250 //This does not throw 251 typedef typename Node::hook_type hook_type; 252 ::new(static_cast<hook_type*>(p), boost_container_new_t()) hook_type; 253 //This can throw in some containers (predicate might throw). 254 //(sdestructor will destruct the node and node_deallocator will deallocate it in case of exception) 255 inserter(*p); 256 sdestructor.set(0); 257 } 258 sdestructor.release(); 259 node_deallocator.release(); 260 } 261 BOOST_CATCH(...){ 262 mem.incorporate_after(mem.last(), &*itbeg, &*itlast, n); 263 node_allocator_version_traits_type::deallocate_individual(this->node_alloc(), mem); 264 BOOST_RETHROW 265 } 266 BOOST_CATCH_END 267 } 268 } 269 clearboost::container::container_detail::node_alloc_holder270 void clear(version_1) 271 { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); } 272 clearboost::container::container_detail::node_alloc_holder273 void clear(version_2) 274 { 275 typename NodeAlloc::multiallocation_chain chain; 276 allocator_destroyer_and_chain_builder<NodeAlloc> builder(this->node_alloc(), chain); 277 this->icont().clear_and_dispose(builder); 278 //BOOST_STATIC_ASSERT((::boost::has_move_emulation_enabled<typename NodeAlloc::multiallocation_chain>::value == true)); 279 if(!chain.empty()) 280 this->node_alloc().deallocate_individual(chain); 281 } 282 erase_rangeboost::container::container_detail::node_alloc_holder283 icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_1) 284 { return this->icont().erase_and_dispose(first, last, Destroyer(this->node_alloc())); } 285 erase_rangeboost::container::container_detail::node_alloc_holder286 icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_2) 287 { 288 typedef typename NodeAlloc::multiallocation_chain multiallocation_chain; 289 NodeAlloc & nalloc = this->node_alloc(); 290 multiallocation_chain chain; 291 allocator_destroyer_and_chain_builder<NodeAlloc> chain_builder(nalloc, chain); 292 icont_iterator ret_it = this->icont().erase_and_dispose(first, last, chain_builder); 293 nalloc.deallocate_individual(chain); 294 return ret_it; 295 } 296 297 template<class Key, class Comparator> erase_keyboost::container::container_detail::node_alloc_holder298 size_type erase_key(const Key& k, const Comparator &comp, version_1) 299 { return this->icont().erase_and_dispose(k, comp, Destroyer(this->node_alloc())); } 300 301 template<class Key, class Comparator> erase_keyboost::container::container_detail::node_alloc_holder302 size_type erase_key(const Key& k, const Comparator &comp, version_2) 303 { 304 allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc()); 305 return this->icont().erase_and_dispose(k, comp, chain_holder.get_chain_builder()); 306 } 307 308 protected: 309 struct cloner 310 { clonerboost::container::container_detail::node_alloc_holder::cloner311 explicit cloner(node_alloc_holder &holder) 312 : m_holder(holder) 313 {} 314 operator ()boost::container::container_detail::node_alloc_holder::cloner315 NodePtr operator()(const Node &other) const 316 { return m_holder.create_node(other.m_data); } 317 318 node_alloc_holder &m_holder; 319 }; 320 321 struct move_cloner 322 { move_clonerboost::container::container_detail::node_alloc_holder::move_cloner323 move_cloner(node_alloc_holder &holder) 324 : m_holder(holder) 325 {} 326 operator ()boost::container::container_detail::node_alloc_holder::move_cloner327 NodePtr operator()(Node &other) 328 { //Use m_data instead of get_data to allow moving const key in [multi]map 329 return m_holder.create_node(::boost::move(other.m_data)); 330 } 331 332 node_alloc_holder &m_holder; 333 }; 334 335 struct members_holder 336 : public NodeAlloc 337 { 338 private: 339 members_holder(const members_holder&); 340 members_holder & operator=(const members_holder&); 341 342 public: members_holderboost::container::container_detail::node_alloc_holder::members_holder343 members_holder() 344 : NodeAlloc(), m_icont() 345 {} 346 347 template<class ConvertibleToAlloc> members_holderboost::container::container_detail::node_alloc_holder::members_holder348 explicit members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc) 349 : NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc)) 350 , m_icont() 351 {} 352 353 template<class ConvertibleToAlloc> members_holderboost::container::container_detail::node_alloc_holder::members_holder354 members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc, const value_compare &c) 355 : NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc)) 356 , m_icont(typename ICont::key_compare(c)) 357 {} 358 members_holderboost::container::container_detail::node_alloc_holder::members_holder359 explicit members_holder(const value_compare &c) 360 : NodeAlloc() 361 , m_icont(typename ICont::key_compare(c)) 362 {} 363 364 //The intrusive container 365 ICont m_icont; 366 }; 367 non_const_icontboost::container::container_detail::node_alloc_holder368 ICont &non_const_icont() const 369 { return const_cast<ICont&>(this->members_.m_icont); } 370 icontboost::container::container_detail::node_alloc_holder371 ICont &icont() 372 { return this->members_.m_icont; } 373 icontboost::container::container_detail::node_alloc_holder374 const ICont &icont() const 375 { return this->members_.m_icont; } 376 node_allocboost::container::container_detail::node_alloc_holder377 NodeAlloc &node_alloc() 378 { return static_cast<NodeAlloc &>(this->members_); } 379 node_allocboost::container::container_detail::node_alloc_holder380 const NodeAlloc &node_alloc() const 381 { return static_cast<const NodeAlloc &>(this->members_); } 382 383 members_holder members_; 384 }; 385 386 } //namespace container_detail { 387 } //namespace container { 388 } //namespace boost { 389 390 #include <boost/container/detail/config_end.hpp> 391 392 #endif // BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_ 393