| ////////////////////////////////////////////////////////////////////////////// |
| // |
| // (C) Copyright Ion Gaztanaga 2005-2009. Distributed under the Boost |
| // Software License, Version 1.0. (See accompanying file |
| // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt) |
| // |
| // See http://www.boost.org/libs/container for documentation. |
| // |
| ////////////////////////////////////////////////////////////////////////////// |
| |
| #ifndef BOOST_CONTAINERS_DETAIL_NODE_ALLOC_HPP_ |
| #define BOOST_CONTAINERS_DETAIL_NODE_ALLOC_HPP_ |
| |
| #if (defined _MSC_VER) && (_MSC_VER >= 1200) |
| # pragma once |
| #endif |
| |
| #include "config_begin.hpp" |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_WORKAROUND_HPP |
| |
| #include <utility> |
| #include <functional> |
| |
| #include INCLUDE_BOOST_CONTAINER_MOVE_HPP |
| #include <boost/intrusive/options.hpp> |
| |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_VERSION_TYPE_HPP |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_TYPE_TRAITS_HPP |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_UTILITIES_HPP |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_MPL_HPP |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_DESTROYERS_HPP |
| |
| #ifndef BOOST_CONTAINERS_PERFECT_FORWARDING |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_PREPROCESSOR_HPP |
| #endif |
| |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_ALGORITHMS_HPP |
| |
| |
| namespace boost { |
| namespace container { |
| namespace containers_detail { |
| |
| //!A deleter for scoped_ptr that deallocates the memory |
| //!allocated for an object using a STL allocator. |
| template <class Allocator> |
| struct scoped_deallocator |
| { |
| typedef typename Allocator::pointer pointer; |
| typedef containers_detail::integral_constant<unsigned, |
| boost::container::containers_detail:: |
| version<Allocator>::value> alloc_version; |
| typedef containers_detail::integral_constant<unsigned, 1> allocator_v1; |
| typedef containers_detail::integral_constant<unsigned, 2> allocator_v2; |
| |
| private: |
| void priv_deallocate(allocator_v1) |
| { m_alloc.deallocate(m_ptr, 1); } |
| |
| void priv_deallocate(allocator_v2) |
| { m_alloc.deallocate_one(m_ptr); } |
| |
| BOOST_MOVE_MACRO_MOVABLE_BUT_NOT_COPYABLE(scoped_deallocator) |
| |
| public: |
| |
| pointer m_ptr; |
| Allocator& m_alloc; |
| |
| scoped_deallocator(pointer p, Allocator& a) |
| : m_ptr(p), m_alloc(a) |
| {} |
| |
| ~scoped_deallocator() |
| { if (m_ptr)priv_deallocate(alloc_version()); } |
| |
| scoped_deallocator(BOOST_MOVE_MACRO_RV_REF(scoped_deallocator) o) |
| : m_ptr(o.m_ptr), m_alloc(o.m_alloc) |
| { o.release(); } |
| |
| pointer get() const |
| { return m_ptr; } |
| |
| void release() |
| { m_ptr = 0; } |
| }; |
| |
| template <class A> |
| class allocator_destroyer_and_chain_builder |
| { |
| typedef typename A::value_type value_type; |
| typedef typename A::multiallocation_chain multiallocation_chain; |
| |
| A & a_; |
| multiallocation_chain &c_; |
| |
| public: |
| allocator_destroyer_and_chain_builder(A &a, multiallocation_chain &c) |
| : a_(a), c_(c) |
| {} |
| |
| void operator()(const typename A::pointer &p) |
| { |
| value_type *vp = containers_detail::get_pointer(p); |
| vp->~value_type(); |
| c_.push_front(vp); |
| } |
| }; |
| |
| template <class A> |
| class allocator_multialloc_chain_node_deallocator |
| { |
| typedef typename A::value_type value_type; |
| typedef typename A::multiallocation_chain multiallocation_chain; |
| typedef allocator_destroyer_and_chain_builder<A> chain_builder; |
| |
| A & a_; |
| multiallocation_chain c_; |
| |
| public: |
| allocator_multialloc_chain_node_deallocator(A &a) |
| : a_(a), c_() |
| {} |
| |
| chain_builder get_chain_builder() |
| { return chain_builder(a_, c_); } |
| |
| ~allocator_multialloc_chain_node_deallocator() |
| { |
| if(!c_.empty()) |
| a_.deallocate_individual(BOOST_CONTAINER_MOVE_NAMESPACE::move(c_)); |
| } |
| }; |
| |
| |
| template<class ValueCompare, class Node> |
| struct node_compare |
| : private ValueCompare |
| { |
| typedef typename ValueCompare::key_type key_type; |
| typedef typename ValueCompare::value_type value_type; |
| typedef typename ValueCompare::key_of_value key_of_value; |
| |
| node_compare(const ValueCompare &pred) |
| : ValueCompare(pred) |
| {} |
| |
| ValueCompare &value_comp() |
| { return static_cast<ValueCompare &>(*this); } |
| |
| ValueCompare &value_comp() const |
| { return static_cast<const ValueCompare &>(*this); } |
| |
| bool operator()(const Node &a, const Node &b) const |
| { return ValueCompare::operator()(a.get_data(), b.get_data()); } |
| }; |
| |
| template<class A, class ICont> |
| struct node_alloc_holder |
| { |
| typedef node_alloc_holder<A, ICont> self_t; |
| typedef typename A::value_type value_type; |
| typedef typename ICont::value_type Node; |
| typedef typename A::template rebind<Node>::other NodeAlloc; |
| typedef A ValAlloc; |
| typedef typename NodeAlloc::pointer NodePtr; |
| typedef containers_detail::scoped_deallocator<NodeAlloc> Deallocator; |
| typedef typename NodeAlloc::size_type size_type; |
| typedef typename NodeAlloc::difference_type difference_type; |
| typedef containers_detail::integral_constant<unsigned, 1> allocator_v1; |
| typedef containers_detail::integral_constant<unsigned, 2> allocator_v2; |
| typedef containers_detail::integral_constant<unsigned, |
| boost::container::containers_detail:: |
| version<NodeAlloc>::value> alloc_version; |
| typedef typename ICont::iterator icont_iterator; |
| typedef typename ICont::const_iterator icont_citerator; |
| typedef allocator_destroyer<NodeAlloc> Destroyer; |
| |
| private: |
| BOOST_MOVE_MACRO_COPYABLE_AND_MOVABLE(node_alloc_holder) |
| |
| public: |
| |
| node_alloc_holder(const ValAlloc &a) |
| : members_(a) |
| {} |
| |
| node_alloc_holder(const node_alloc_holder &other) |
| : members_(other.node_alloc()) |
| {} |
| |
| node_alloc_holder(BOOST_MOVE_MACRO_RV_REF(node_alloc_holder) other) |
| : members_(BOOST_CONTAINER_MOVE_NAMESPACE::move(other.node_alloc())) |
| { this->swap(other); } |
| |
| node_alloc_holder & operator=(BOOST_MOVE_MACRO_COPY_ASSIGN_REF(node_alloc_holder) other) |
| { members_.assign(other.node_alloc()); } |
| |
| node_alloc_holder & operator=(BOOST_MOVE_MACRO_RV_REF(node_alloc_holder) other) |
| { members_.assign(other.node_alloc()); } |
| |
| template<class Pred> |
| node_alloc_holder(const ValAlloc &a, const Pred &c) |
| : members_(a, typename ICont::value_compare(c)) |
| {} |
| |
| template<class Pred> |
| node_alloc_holder(BOOST_MOVE_MACRO_RV_REF(ValAlloc) a, const Pred &c) |
| : members_(a, typename ICont::value_compare(c)) |
| {} |
| |
| template<class Pred> |
| node_alloc_holder(const node_alloc_holder &other, const Pred &c) |
| : members_(other.node_alloc(), typename ICont::value_compare(c)) |
| {} |
| |
| ~node_alloc_holder() |
| { this->clear(alloc_version()); } |
| |
| size_type max_size() const |
| { return this->node_alloc().max_size(); } |
| |
| NodePtr allocate_one() |
| { return this->allocate_one(alloc_version()); } |
| |
| NodePtr allocate_one(allocator_v1) |
| { return this->node_alloc().allocate(1); } |
| |
| NodePtr allocate_one(allocator_v2) |
| { return this->node_alloc().allocate_one(); } |
| |
| void deallocate_one(NodePtr p) |
| { return this->deallocate_one(p, alloc_version()); } |
| |
| void deallocate_one(NodePtr p, allocator_v1) |
| { this->node_alloc().deallocate(p, 1); } |
| |
| void deallocate_one(NodePtr p, allocator_v2) |
| { this->node_alloc().deallocate_one(p); } |
| |
| template<class Convertible1, class Convertible2> |
| static void construct(const NodePtr &ptr, |
| BOOST_MOVE_MACRO_RV_REF_2_TEMPL_ARGS(std::pair, Convertible1, Convertible2) value) |
| { |
| typedef typename Node::hook_type hook_type; |
| typedef typename Node::value_type::first_type first_type; |
| typedef typename Node::value_type::second_type second_type; |
| Node *nodeptr = containers_detail::get_pointer(ptr); |
| |
| //Hook constructor does not throw |
| new(static_cast<hook_type*>(nodeptr))hook_type(); |
| //Now construct pair members_holder |
| value_type *valueptr = &nodeptr->get_data(); |
| new((void*)&valueptr->first) first_type(BOOST_CONTAINER_MOVE_NAMESPACE::move(value.first)); |
| BOOST_TRY{ |
| new((void*)&valueptr->second) second_type(BOOST_CONTAINER_MOVE_NAMESPACE::move(value.second)); |
| } |
| BOOST_CATCH(...){ |
| valueptr->first.~first_type(); |
| static_cast<hook_type*>(nodeptr)->~hook_type(); |
| BOOST_RETHROW |
| } |
| BOOST_CATCH_END |
| } |
| |
| static void destroy(const NodePtr &ptr) |
| { containers_detail::get_pointer(ptr)->~Node(); } |
| |
| Deallocator create_node_and_deallocator() |
| { |
| return Deallocator(this->allocate_one(), this->node_alloc()); |
| } |
| |
| #ifdef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| template<class ...Args> |
| static void construct(const NodePtr &ptr, Args &&...args) |
| { new((void*)containers_detail::get_pointer(ptr)) Node(BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); } |
| |
| template<class ...Args> |
| NodePtr create_node(Args &&...args) |
| { |
| NodePtr p = this->allocate_one(); |
| Deallocator node_deallocator(p, this->node_alloc()); |
| self_t::construct(p, BOOST_CONTAINER_MOVE_NAMESPACE::forward<Args>(args)...); |
| node_deallocator.release(); |
| return (p); |
| } |
| |
| #else //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| static void construct(const NodePtr &ptr) |
| { new((void*)containers_detail::get_pointer(ptr)) Node(); } |
| |
| NodePtr create_node() |
| { |
| NodePtr p = this->allocate_one(); |
| Deallocator node_deallocator(p, this->node_alloc()); |
| self_t::construct(p); |
| node_deallocator.release(); |
| return (p); |
| } |
| |
| #define BOOST_PP_LOCAL_MACRO(n) \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| void construct(const NodePtr &ptr, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| new((void*)containers_detail::get_pointer(ptr)) \ |
| Node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ |
| } \ |
| //! |
| #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) |
| #include BOOST_PP_LOCAL_ITERATE() |
| |
| #define BOOST_PP_LOCAL_MACRO(n) \ |
| template<BOOST_PP_ENUM_PARAMS(n, class P)> \ |
| NodePtr create_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \ |
| { \ |
| NodePtr p = this->allocate_one(); \ |
| Deallocator node_deallocator(p, this->node_alloc()); \ |
| self_t::construct(p, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)); \ |
| node_deallocator.release(); \ |
| return (p); \ |
| } \ |
| //! |
| #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS) |
| #include BOOST_PP_LOCAL_ITERATE() |
| |
| #endif //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING |
| |
| template<class It> |
| NodePtr create_node_from_it(It it) |
| { |
| NodePtr p = this->allocate_one(); |
| Deallocator node_deallocator(p, this->node_alloc()); |
| ::boost::container::construct_in_place(containers_detail::get_pointer(p), it); |
| node_deallocator.release(); |
| return (p); |
| } |
| |
| void destroy_node(NodePtr node) |
| { |
| self_t::destroy(node); |
| this->deallocate_one(node); |
| } |
| |
| void swap(node_alloc_holder &x) |
| { |
| NodeAlloc& this_alloc = this->node_alloc(); |
| NodeAlloc& other_alloc = x.node_alloc(); |
| |
| if (this_alloc != other_alloc){ |
| containers_detail::do_swap(this_alloc, other_alloc); |
| } |
| |
| this->icont().swap(x.icont()); |
| } |
| |
| template<class FwdIterator, class Inserter> |
| FwdIterator allocate_many_and_construct |
| (FwdIterator beg, difference_type n, Inserter inserter) |
| { |
| if(n){ |
| typedef typename NodeAlloc::multiallocation_chain multiallocation_chain; |
| |
| //Try to allocate memory in a single block |
| multiallocation_chain mem(this->node_alloc().allocate_individual(n)); |
| int constructed = 0; |
| Node *p = 0; |
| BOOST_TRY{ |
| for(difference_type i = 0; i < n; ++i, ++beg, --constructed){ |
| p = containers_detail::get_pointer(mem.front()); |
| mem.pop_front(); |
| //This can throw |
| constructed = 0; |
| boost::container::construct_in_place(p, beg); |
| ++constructed; |
| //This can throw in some containers (predicate might throw) |
| inserter(*p); |
| } |
| } |
| BOOST_CATCH(...){ |
| if(constructed){ |
| this->destroy(p); |
| } |
| this->node_alloc().deallocate_individual(BOOST_CONTAINER_MOVE_NAMESPACE::move(mem)); |
| BOOST_RETHROW |
| } |
| BOOST_CATCH_END |
| } |
| return beg; |
| } |
| |
| void clear(allocator_v1) |
| { this->icont().clear_and_dispose(Destroyer(this->node_alloc())); } |
| |
| void clear(allocator_v2) |
| { |
| typename NodeAlloc::multiallocation_chain chain; |
| allocator_destroyer_and_chain_builder<NodeAlloc> builder(this->node_alloc(), chain); |
| this->icont().clear_and_dispose(builder); |
| BOOST_STATIC_ASSERT((::BOOST_CONTAINER_MOVE_NAMESPACE::is_movable<typename NodeAlloc::multiallocation_chain>::value == true)); |
| if(!chain.empty()) |
| this->node_alloc().deallocate_individual(BOOST_CONTAINER_MOVE_NAMESPACE::move(chain)); |
| } |
| |
| icont_iterator erase_range(icont_iterator first, icont_iterator last, allocator_v1) |
| { return this->icont().erase_and_dispose(first, last, Destroyer(this->node_alloc())); } |
| |
| icont_iterator erase_range(icont_iterator first, icont_iterator last, allocator_v2) |
| { |
| allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc()); |
| return this->icont().erase_and_dispose(first, last, chain_holder.get_chain_builder()); |
| } |
| |
| template<class Key, class Comparator> |
| size_type erase_key(const Key& k, const Comparator &comp, allocator_v1) |
| { return this->icont().erase_and_dispose(k, comp, Destroyer(this->node_alloc())); } |
| |
| template<class Key, class Comparator> |
| size_type erase_key(const Key& k, const Comparator &comp, allocator_v2) |
| { |
| allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc()); |
| return this->icont().erase_and_dispose(k, comp, chain_holder.get_chain_builder()); |
| } |
| |
| protected: |
| struct cloner |
| { |
| cloner(node_alloc_holder &holder) |
| : m_holder(holder) |
| {} |
| |
| NodePtr operator()(const Node &other) const |
| { return m_holder.create_node(other.get_data()); } |
| |
| node_alloc_holder &m_holder; |
| }; |
| |
| struct destroyer |
| { |
| destroyer(node_alloc_holder &holder) |
| : m_holder(holder) |
| {} |
| |
| void operator()(NodePtr n) const |
| { m_holder.destroy_node(n); } |
| |
| node_alloc_holder &m_holder; |
| }; |
| |
| struct members_holder |
| : public NodeAlloc |
| { |
| private: |
| members_holder(const members_holder&); |
| |
| public: |
| template<class ConvertibleToAlloc> |
| members_holder(const ConvertibleToAlloc &c2alloc) |
| : NodeAlloc(c2alloc) |
| {} |
| |
| template<class ConvertibleToAlloc, class Pred> |
| members_holder(const ConvertibleToAlloc &c2alloc, const Pred &c) |
| : NodeAlloc(c2alloc), m_icont(c) |
| {} |
| |
| template<class ConvertibleToAlloc> |
| void assign (const ConvertibleToAlloc &c2alloc) |
| { |
| NodeAlloc::operator=(c2alloc); |
| } |
| |
| //The intrusive container |
| ICont m_icont; |
| } members_; |
| |
| ICont &non_const_icont() const |
| { return const_cast<ICont&>(this->members_.m_icont); } |
| |
| ICont &icont() |
| { return this->members_.m_icont; } |
| |
| const ICont &icont() const |
| { return this->members_.m_icont; } |
| |
| NodeAlloc &node_alloc() |
| { return static_cast<NodeAlloc &>(this->members_); } |
| |
| const NodeAlloc &node_alloc() const |
| { return static_cast<const NodeAlloc &>(this->members_); } |
| }; |
| |
| } //namespace containers_detail { |
| } //namespace container { |
| } //namespace boost { |
| |
| #include INCLUDE_BOOST_CONTAINER_DETAIL_CONFIG_END_HPP |
| |
| #endif // BOOST_CONTAINERS_DETAIL_NODE_ALLOC_HPP_ |