Chris@16: //////////////////////////////////////////////////////////////////////////////
Chris@16: //
Chris@101: // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
Chris@16: // Software License, Version 1.0. (See accompanying file
Chris@16: // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
Chris@16: //
Chris@16: // See http://www.boost.org/libs/container for documentation.
Chris@16: //
Chris@16: //////////////////////////////////////////////////////////////////////////////
Chris@16: 
Chris@16: #ifndef BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_
Chris@16: #define BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_
Chris@16: 
Chris@101: #ifndef BOOST_CONFIG_HPP
Chris@101: #  include <boost/config.hpp>
Chris@101: #endif
Chris@101: 
Chris@101: #if defined(BOOST_HAS_PRAGMA_ONCE)
Chris@16: #  pragma once
Chris@16: #endif
Chris@16: 
Chris@101: #include <boost/container/detail/config_begin.hpp>
Chris@16: #include <boost/container/detail/workaround.hpp>
Chris@16: 
Chris@101: // container
Chris@101: #include <boost/container/allocator_traits.hpp>
Chris@101: // container/detail
Chris@101: #include <boost/container/detail/addressof.hpp>
Chris@101: #include <boost/container/detail/alloc_helpers.hpp>
Chris@101: #include <boost/container/detail/allocator_version_traits.hpp>
Chris@101: #include <boost/container/detail/construct_in_place.hpp>
Chris@101: #include <boost/container/detail/destroyers.hpp>
Chris@101: #include <boost/container/detail/iterator_to_raw_pointer.hpp>
Chris@101: #include <boost/container/detail/mpl.hpp>
Chris@101: #include <boost/container/detail/placement_new.hpp>
Chris@101: #include <boost/container/detail/to_raw_pointer.hpp>
Chris@101: #include <boost/container/detail/type_traits.hpp>
Chris@101: #include <boost/container/detail/version_type.hpp>
Chris@101: // intrusive
Chris@101: #include <boost/intrusive/detail/mpl.hpp>
Chris@16: #include <boost/intrusive/options.hpp>
Chris@101: // move
Chris@101: #include <boost/move/utility_core.hpp>
Chris@101: #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@101: #include <boost/move/detail/fwd_macros.hpp>
Chris@16: #endif
Chris@101: // other
Chris@101: #include <boost/core/no_exceptions_support.hpp>
Chris@16: 
Chris@16: 
Chris@16: namespace boost {
Chris@16: namespace container {
Chris@16: namespace container_detail {
Chris@16: 
Chris@101: BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(value_compare)
Chris@101: BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(predicate_type)
Chris@16: 
Chris@101: template<class Allocator, class ICont>
Chris@16: struct node_alloc_holder
Chris@16: {
Chris@101:    //If the intrusive container is an associative container, obtain the predicate, which will
Chris@101:    //be of type node_compare<>. If not an associative container value_compare will be a "nat" type.
Chris@101:    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT(boost::container::container_detail::, ICont,
Chris@101:       value_compare, container_detail::nat)                       intrusive_value_compare;
Chris@101:    //In that case obtain the value predicate from the node predicate via predicate_type
Chris@101:    //if intrusive_value_compare is node_compare<>, nat otherwise
Chris@101:    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT(boost::container::container_detail::, intrusive_value_compare,
Chris@101:       predicate_type, container_detail::nat)                      value_compare;
Chris@101: 
Chris@101:    typedef allocator_traits<Allocator>                                    allocator_traits_type;
Chris@16:    typedef typename allocator_traits_type::value_type             value_type;
Chris@101:    typedef ICont                                                  intrusive_container;
Chris@16:    typedef typename ICont::value_type                             Node;
Chris@16:    typedef typename allocator_traits_type::template
Chris@16:       portable_rebind_alloc<Node>::type                           NodeAlloc;
Chris@16:    typedef allocator_traits<NodeAlloc>                            node_allocator_traits_type;
Chris@16:    typedef container_detail::allocator_version_traits<NodeAlloc>  node_allocator_version_traits_type;
Chris@101:    typedef Allocator                                                      ValAlloc;
Chris@16:    typedef typename node_allocator_traits_type::pointer           NodePtr;
Chris@16:    typedef container_detail::scoped_deallocator<NodeAlloc>        Deallocator;
Chris@16:    typedef typename node_allocator_traits_type::size_type         size_type;
Chris@16:    typedef typename node_allocator_traits_type::difference_type   difference_type;
Chris@16:    typedef container_detail::integral_constant<unsigned,
Chris@16:       boost::container::container_detail::
Chris@16:          version<NodeAlloc>::value>                   alloc_version;
Chris@16:    typedef typename ICont::iterator                   icont_iterator;
Chris@16:    typedef typename ICont::const_iterator             icont_citerator;
Chris@16:    typedef allocator_destroyer<NodeAlloc>             Destroyer;
Chris@16:    typedef allocator_traits<NodeAlloc>                NodeAllocTraits;
Chris@16:    typedef allocator_version_traits<NodeAlloc>        AllocVersionTraits;
Chris@16: 
Chris@16:    private:
Chris@16:    BOOST_COPYABLE_AND_MOVABLE(node_alloc_holder)
Chris@16: 
Chris@16:    public:
Chris@16: 
Chris@16:    //Constructors for sequence containers
Chris@16:    node_alloc_holder()
Chris@16:       : members_()
Chris@16:    {}
Chris@16: 
Chris@16:    explicit node_alloc_holder(const ValAlloc &a)
Chris@16:       : members_(a)
Chris@16:    {}
Chris@16: 
Chris@16:    explicit node_alloc_holder(const node_alloc_holder &x)
Chris@16:       : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()))
Chris@16:    {}
Chris@16: 
Chris@16:    explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x)
Chris@16:       : members_(boost::move(x.node_alloc()))
Chris@16:    {  this->icont().swap(x.icont());  }
Chris@16: 
Chris@16:    //Constructors for associative containers
Chris@101:    explicit node_alloc_holder(const value_compare &c, const ValAlloc &a)
Chris@16:       : members_(a, c)
Chris@16:    {}
Chris@16: 
Chris@101:    explicit node_alloc_holder(const value_compare &c, const node_alloc_holder &x)
Chris@16:       : members_(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()), c)
Chris@16:    {}
Chris@16: 
Chris@101:    explicit node_alloc_holder(const value_compare &c)
Chris@16:       : members_(c)
Chris@16:    {}
Chris@16: 
Chris@16:    //helpers for move assignments
Chris@101:    explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const value_compare &c)
Chris@16:       : members_(boost::move(x.node_alloc()), c)
Chris@16:    {  this->icont().swap(x.icont());  }
Chris@16: 
Chris@16:    void copy_assign_alloc(const node_alloc_holder &x)
Chris@101:    {
Chris@16:       container_detail::bool_<allocator_traits_type::propagate_on_container_copy_assignment::value> flag;
Chris@16:       container_detail::assign_alloc( static_cast<NodeAlloc &>(this->members_)
Chris@16:                                     , static_cast<const NodeAlloc &>(x.members_), flag);
Chris@16:    }
Chris@16: 
Chris@16:    void move_assign_alloc( node_alloc_holder &x)
Chris@16:    {
Chris@16:       container_detail::bool_<allocator_traits_type::propagate_on_container_move_assignment::value> flag;
Chris@16:       container_detail::move_alloc( static_cast<NodeAlloc &>(this->members_)
Chris@16:                                   , static_cast<NodeAlloc &>(x.members_), flag);
Chris@16:    }
Chris@16: 
Chris@16:    ~node_alloc_holder()
Chris@16:    {  this->clear(alloc_version()); }
Chris@16: 
Chris@16:    size_type max_size() const
Chris@16:    {  return allocator_traits_type::max_size(this->node_alloc());  }
Chris@16: 
Chris@16:    NodePtr allocate_one()
Chris@16:    {  return AllocVersionTraits::allocate_one(this->node_alloc());   }
Chris@16: 
Chris@16:    void deallocate_one(const NodePtr &p)
Chris@16:    {  AllocVersionTraits::deallocate_one(this->node_alloc(), p);  }
Chris@16: 
Chris@101:    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16: 
Chris@16:    template<class ...Args>
Chris@16:    NodePtr create_node(Args &&...args)
Chris@16:    {
Chris@16:       NodePtr p = this->allocate_one();
Chris@16:       Deallocator node_deallocator(p, this->node_alloc());
Chris@16:       allocator_traits<NodeAlloc>::construct
Chris@16:          ( this->node_alloc()
Chris@16:          , container_detail::addressof(p->m_data), boost::forward<Args>(args)...);
Chris@16:       node_deallocator.release();
Chris@16:       //This does not throw
Chris@16:       typedef typename Node::hook_type hook_type;
Chris@101:       ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
Chris@16:       return (p);
Chris@16:    }
Chris@16: 
Chris@101:    #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@101:    NodePtr create_node()
Chris@101:    {
Chris@101:       NodePtr p = this->allocate_one();
Chris@101:       Deallocator node_deallocator(p, this->node_alloc());
Chris@101:       allocator_traits<NodeAlloc>::construct
Chris@101:          (this->node_alloc(), container_detail::addressof(p->m_data));
Chris@101:       node_deallocator.release();
Chris@101:       typedef typename Node::hook_type hook_type;
Chris@101:       ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
Chris@101:       return (p);
Chris@101:    }
Chris@16: 
Chris@101:    template<BOOST_MOVE_CLASS1>
Chris@101:    NodePtr create_node(BOOST_MOVE_UREF1)
Chris@101:    {
Chris@101:       NodePtr p = this->allocate_one();
Chris@101:       Deallocator node_deallocator(p, this->node_alloc());
Chris@101:       allocator_traits<NodeAlloc>::construct
Chris@101:          (this->node_alloc(), container_detail::addressof(p->m_data)
Chris@101:          , BOOST_MOVE_FWD1);
Chris@101:       node_deallocator.release();
Chris@101:       typedef typename Node::hook_type hook_type;
Chris@101:       ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
Chris@101:       return (p);
Chris@101:    }
Chris@16: 
Chris@101:    template<BOOST_MOVE_CLASS2>
Chris@101:    NodePtr create_node(BOOST_MOVE_UREF2)
Chris@101:    {
Chris@101:       NodePtr p = this->allocate_one();
Chris@101:       Deallocator node_deallocator(p, this->node_alloc());
Chris@101:       allocator_traits<NodeAlloc>::construct
Chris@101:          (this->node_alloc(), container_detail::addressof(p->m_data)
Chris@101:          , BOOST_MOVE_FWD2);
Chris@101:       node_deallocator.release();
Chris@101:       typedef typename Node::hook_type hook_type;
Chris@101:       ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
Chris@101:       return (p);
Chris@101:    }
Chris@101: 
Chris@101:    template<BOOST_MOVE_CLASS3>
Chris@101:    NodePtr create_node(BOOST_MOVE_UREF3)
Chris@101:    {
Chris@101:       NodePtr p = this->allocate_one();
Chris@101:       Deallocator node_deallocator(p, this->node_alloc());
Chris@101:       allocator_traits<NodeAlloc>::construct
Chris@101:          (this->node_alloc(), container_detail::addressof(p->m_data)
Chris@101:          , BOOST_MOVE_FWD3);
Chris@101:       node_deallocator.release();
Chris@101:       typedef typename Node::hook_type hook_type;
Chris@101:       ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
Chris@101:       return (p);
Chris@101:    }
Chris@101: 
Chris@101:    template<BOOST_MOVE_CLASS4>
Chris@101:    NodePtr create_node(BOOST_MOVE_UREF4)
Chris@101:    {
Chris@101:       NodePtr p = this->allocate_one();
Chris@101:       Deallocator node_deallocator(p, this->node_alloc());
Chris@101:       allocator_traits<NodeAlloc>::construct
Chris@101:          (this->node_alloc(), container_detail::addressof(p->m_data)
Chris@101:          , BOOST_MOVE_FWD4);
Chris@101:       node_deallocator.release();
Chris@101:       typedef typename Node::hook_type hook_type;
Chris@101:       ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
Chris@101:       return (p);
Chris@101:    }
Chris@101: 
Chris@101:    template<BOOST_MOVE_CLASS5>
Chris@101:    NodePtr create_node(BOOST_MOVE_UREF5)
Chris@101:    {
Chris@101:       NodePtr p = this->allocate_one();
Chris@101:       Deallocator node_deallocator(p, this->node_alloc());
Chris@101:       allocator_traits<NodeAlloc>::construct
Chris@101:          (this->node_alloc(), container_detail::addressof(p->m_data)
Chris@101:          , BOOST_MOVE_FWD5);
Chris@101:       node_deallocator.release();
Chris@101:       typedef typename Node::hook_type hook_type;
Chris@101:       ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
Chris@101:       return (p);
Chris@101:    }
Chris@101: 
Chris@101:    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
Chris@16: 
Chris@16:    template<class It>
Chris@16:    NodePtr create_node_from_it(const It &it)
Chris@16:    {
Chris@16:       NodePtr p = this->allocate_one();
Chris@16:       Deallocator node_deallocator(p, this->node_alloc());
Chris@16:       ::boost::container::construct_in_place(this->node_alloc(), container_detail::addressof(p->m_data), it);
Chris@16:       node_deallocator.release();
Chris@16:       //This does not throw
Chris@16:       typedef typename Node::hook_type hook_type;
Chris@101:       ::new(static_cast<hook_type*>(container_detail::to_raw_pointer(p)), boost_container_new_t()) hook_type;
Chris@16:       return (p);
Chris@16:    }
Chris@16: 
Chris@16:    void destroy_node(const NodePtr &nodep)
Chris@16:    {
Chris@16:       allocator_traits<NodeAlloc>::destroy(this->node_alloc(), container_detail::to_raw_pointer(nodep));
Chris@16:       this->deallocate_one(nodep);
Chris@16:    }
Chris@16: 
Chris@16:    void swap(node_alloc_holder &x)
Chris@16:    {
Chris@16:       this->icont().swap(x.icont());
Chris@16:       container_detail::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
Chris@16:       container_detail::swap_alloc(this->node_alloc(), x.node_alloc(), flag);
Chris@16:    }
Chris@16: 
Chris@16:    template<class FwdIterator, class Inserter>
Chris@16:    void allocate_many_and_construct
Chris@16:       (FwdIterator beg, difference_type n, Inserter inserter)
Chris@16:    {
Chris@16:       if(n){
Chris@16:          typedef typename node_allocator_version_traits_type::multiallocation_chain multiallocation_chain;
Chris@16: 
Chris@16:          //Try to allocate memory in a single block
Chris@16:          typedef typename multiallocation_chain::iterator multialloc_iterator;
Chris@16:          multiallocation_chain mem;
Chris@16:          NodeAlloc &nalloc = this->node_alloc();
Chris@16:          node_allocator_version_traits_type::allocate_individual(nalloc, n, mem);
Chris@16:          multialloc_iterator itbeg(mem.begin()), itlast(mem.last());
Chris@16:          mem.clear();
Chris@16:          Node *p = 0;
Chris@16:          BOOST_TRY{
Chris@16:             Deallocator node_deallocator(NodePtr(), nalloc);
Chris@16:             container_detail::scoped_destructor<NodeAlloc> sdestructor(nalloc, 0);
Chris@16:             while(n--){
Chris@101:                p = container_detail::iterator_to_raw_pointer(itbeg);
Chris@16:                node_deallocator.set(p);
Chris@16:                ++itbeg;
Chris@16:                //This can throw
Chris@16:                boost::container::construct_in_place(nalloc, container_detail::addressof(p->m_data), beg);
Chris@16:                sdestructor.set(p);
Chris@16:                ++beg;
Chris@16:                //This does not throw
Chris@16:                typedef typename Node::hook_type hook_type;
Chris@101:                ::new(static_cast<hook_type*>(p), boost_container_new_t()) hook_type;
Chris@16:                //This can throw in some containers (predicate might throw).
Chris@16:                //(sdestructor will destruct the node and node_deallocator will deallocate it in case of exception)
Chris@16:                inserter(*p);
Chris@16:                sdestructor.set(0);
Chris@16:             }
Chris@16:             sdestructor.release();
Chris@16:             node_deallocator.release();
Chris@16:          }
Chris@16:          BOOST_CATCH(...){
Chris@16:             mem.incorporate_after(mem.last(), &*itbeg, &*itlast, n);
Chris@16:             node_allocator_version_traits_type::deallocate_individual(this->node_alloc(), mem);
Chris@16:             BOOST_RETHROW
Chris@16:          }
Chris@16:          BOOST_CATCH_END
Chris@16:       }
Chris@16:    }
Chris@16: 
Chris@101:    void clear(version_1)
Chris@16:    {  this->icont().clear_and_dispose(Destroyer(this->node_alloc()));   }
Chris@16: 
Chris@101:    void clear(version_2)
Chris@16:    {
Chris@16:       typename NodeAlloc::multiallocation_chain chain;
Chris@16:       allocator_destroyer_and_chain_builder<NodeAlloc> builder(this->node_alloc(), chain);
Chris@16:       this->icont().clear_and_dispose(builder);
Chris@16:       //BOOST_STATIC_ASSERT((::boost::has_move_emulation_enabled<typename NodeAlloc::multiallocation_chain>::value == true));
Chris@16:       if(!chain.empty())
Chris@16:          this->node_alloc().deallocate_individual(chain);
Chris@16:    }
Chris@16: 
Chris@101:    icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_1)
Chris@16:    {  return this->icont().erase_and_dispose(first, last, Destroyer(this->node_alloc())); }
Chris@16: 
Chris@101:    icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_2)
Chris@16:    {
Chris@16:       typedef typename NodeAlloc::multiallocation_chain multiallocation_chain;
Chris@16:       NodeAlloc & nalloc = this->node_alloc();
Chris@16:       multiallocation_chain chain;
Chris@16:       allocator_destroyer_and_chain_builder<NodeAlloc> chain_builder(nalloc, chain);
Chris@16:       icont_iterator ret_it = this->icont().erase_and_dispose(first, last, chain_builder);
Chris@16:       nalloc.deallocate_individual(chain);
Chris@16:       return ret_it;
Chris@16:    }
Chris@16: 
Chris@16:    template<class Key, class Comparator>
Chris@101:    size_type erase_key(const Key& k, const Comparator &comp, version_1)
Chris@16:    {  return this->icont().erase_and_dispose(k, comp, Destroyer(this->node_alloc())); }
Chris@16: 
Chris@16:    template<class Key, class Comparator>
Chris@101:    size_type erase_key(const Key& k, const Comparator &comp, version_2)
Chris@16:    {
Chris@16:       allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc());
Chris@16:       return this->icont().erase_and_dispose(k, comp, chain_holder.get_chain_builder());
Chris@16:    }
Chris@16: 
Chris@16:    protected:
Chris@16:    struct cloner
Chris@16:    {
Chris@101:       explicit cloner(node_alloc_holder &holder)
Chris@16:          :  m_holder(holder)
Chris@16:       {}
Chris@16: 
Chris@16:       NodePtr operator()(const Node &other) const
Chris@16:       {  return m_holder.create_node(other.get_data());  }
Chris@16: 
Chris@16:       node_alloc_holder &m_holder;
Chris@16:    };
Chris@16: 
Chris@101:    struct move_cloner
Chris@101:    {
Chris@101:       move_cloner(node_alloc_holder &holder)
Chris@101:          :  m_holder(holder)
Chris@101:       {}
Chris@101: 
Chris@101:       NodePtr operator()(Node &other)
Chris@101:       {  return m_holder.create_node(::boost::move(other.get_data()));  }
Chris@101: 
Chris@101:       node_alloc_holder &m_holder;
Chris@101:    };
Chris@101: 
Chris@16:    struct members_holder
Chris@16:       :  public NodeAlloc
Chris@16:    {
Chris@16:       private:
Chris@16:       members_holder(const members_holder&);
Chris@16:       members_holder & operator=(const members_holder&);
Chris@16: 
Chris@16:       public:
Chris@16:       members_holder()
Chris@16:          : NodeAlloc(), m_icont()
Chris@16:       {}
Chris@16: 
Chris@16:       template<class ConvertibleToAlloc>
Chris@16:       explicit members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc)
Chris@16:          :  NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc))
Chris@16:          , m_icont()
Chris@16:       {}
Chris@16: 
Chris@16:       template<class ConvertibleToAlloc>
Chris@101:       members_holder(BOOST_FWD_REF(ConvertibleToAlloc) c2alloc, const value_compare &c)
Chris@16:          :  NodeAlloc(boost::forward<ConvertibleToAlloc>(c2alloc))
Chris@16:          , m_icont(typename ICont::value_compare(c))
Chris@16:       {}
Chris@16: 
Chris@101:       explicit members_holder(const value_compare &c)
Chris@16:          : NodeAlloc()
Chris@16:          , m_icont(typename ICont::value_compare(c))
Chris@16:       {}
Chris@16: 
Chris@16:       //The intrusive container
Chris@16:       ICont m_icont;
Chris@16:    };
Chris@16: 
Chris@16:    ICont &non_const_icont() const
Chris@16:    {  return const_cast<ICont&>(this->members_.m_icont);   }
Chris@16: 
Chris@16:    ICont &icont()
Chris@16:    {  return this->members_.m_icont;   }
Chris@16: 
Chris@16:    const ICont &icont() const
Chris@16:    {  return this->members_.m_icont;   }
Chris@16: 
Chris@16:    NodeAlloc &node_alloc()
Chris@16:    {  return static_cast<NodeAlloc &>(this->members_);   }
Chris@16: 
Chris@16:    const NodeAlloc &node_alloc() const
Chris@16:    {  return static_cast<const NodeAlloc &>(this->members_);   }
Chris@16: 
Chris@16:    members_holder members_;
Chris@16: };
Chris@16: 
Chris@16: }  //namespace container_detail {
Chris@16: }  //namespace container {
Chris@16: }  //namespace boost {
Chris@16: 
Chris@16: #include <boost/container/detail/config_end.hpp>
Chris@16: 
Chris@16: #endif // BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_