container/detail/node_alloc_holder.hpp

0001 //////////////////////////////////////////////////////////////////////////////
0002 //
0003 // (C) Copyright Ion Gaztanaga 2005-2013. Distributed under the Boost
0004 // Software License, Version 1.0. (See accompanying file
0005 // LICENSE_1_0.txt or copy at http://www.boost.org/LICENSE_1_0.txt)
0006 //
0007 // See http://www.boost.org/libs/container for documentation.
0008 //
0009 //////////////////////////////////////////////////////////////////////////////
0010
0011 #ifndef BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_
0012 #define BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_
0013
0014 #ifndef BOOST_CONFIG_HPP
0015 #  include <boost/config.hpp>
0016 #endif
0017
0018 #if defined(BOOST_HAS_PRAGMA_ONCE)
0019 #  pragma once
0020 #endif
0021
0022 #include <boost/container/detail/config_begin.hpp>
0023 #include <boost/container/detail/workaround.hpp>
0024
0025 // container
0026 #include <boost/container/allocator_traits.hpp>
0027 // container/detail
0028 #include <boost/container/detail/addressof.hpp>
0029 #include <boost/container/detail/alloc_helpers.hpp>
0030 #include <boost/container/detail/allocator_version_traits.hpp>
0031 #include <boost/container/detail/construct_in_place.hpp>
0032 #include <boost/container/detail/destroyers.hpp>
0033 #include <boost/move/detail/iterator_to_raw_pointer.hpp>
0034 #include <boost/container/detail/mpl.hpp>
0035 #include <boost/container/detail/placement_new.hpp>
0036 #include <boost/move/detail/to_raw_pointer.hpp>
0037 #include <boost/container/detail/type_traits.hpp>
0038 #include <boost/container/detail/version_type.hpp>
0039 #include <boost/container/detail/is_pair.hpp>
0040 // intrusive
0041 #include <boost/intrusive/detail/mpl.hpp>
0042 #include <boost/intrusive/options.hpp>
0043 // move
0044 #include <boost/move/utility_core.hpp>
0045 #if defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0046 #include <boost/move/detail/fwd_macros.hpp>
0047 #endif
0048
0049
0050 namespace boost {
0051 namespace container {
0052
0053 //This trait is used to type-pun std::pair because in C++03
0054 //compilers std::pair is useless for C++11 features
0055 template<class T, bool>
0056 struct node_internal_data_type
0057 {
0058    typedef T type;
0059 };
0060
0061 template<class T>
0062 struct node_internal_data_type< T, true>
0063 {
0064    typedef dtl::pair< typename dtl::remove_const<typename T::first_type>::type
0065                      , typename T::second_type>
0066                      type;
0067 };
0068
0069 template <class T, class HookDefiner, bool PairBased = false>
0070 struct base_node
0071    :  public HookDefiner::type
0072 {
0073    public:
0074    typedef T value_type;
0075    typedef typename node_internal_data_type<T, PairBased && dtl::is_pair<T>::value>::type internal_type;
0076    typedef typename HookDefiner::type hook_type;
0077
0078    typedef typename dtl::aligned_storage<sizeof(T), dtl::alignment_of<T>::value>::type storage_t;
0079    storage_t m_storage;
0080
0081    #if defined(BOOST_GCC) && (BOOST_GCC >= 40600) && (BOOST_GCC < 80000)
0082       #pragma GCC diagnostic push
0083       #pragma GCC diagnostic ignored "-Wstrict-aliasing"
0084       #define BOOST_CONTAINER_DISABLE_ALIASING_WARNING
0085    #  endif
0086    public:
0087
0088    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0089
0090    template<class Alloc, class ...Args>
0091    explicit base_node(Alloc &a, Args &&...args)
0092       : hook_type()
0093    {
0094       ::boost::container::allocator_traits<Alloc>::construct
0095          (a, &this->get_real_data(), ::boost::forward<Args>(args)...);
0096    }
0097
0098    #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0099
0100    #define BOOST_CONTAINER_BASE_NODE_CONSTRUCT_IMPL(N) \
0101    template< class Alloc BOOST_MOVE_I##N BOOST_MOVE_CLASS##N > \
0102    explicit base_node(Alloc &a BOOST_MOVE_I##N BOOST_MOVE_UREF##N)\
0103       : hook_type()\
0104    {\
0105       ::boost::container::allocator_traits<Alloc>::construct\
0106          (a, &this->get_real_data() BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
0107    }\
0108    //
0109    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_BASE_NODE_CONSTRUCT_IMPL)
0110    #undef BOOST_CONTAINER_BASE_NODE_CONSTRUCT_IMPL
0111
0112    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0113
0114    template<class Alloc, class It>
0115    explicit base_node(iterator_arg_t, Alloc &a, It it)
0116       : hook_type()
0117    {
0118       ::boost::container::construct_in_place(a, &this->get_real_data(), it);
0119    }
0120
0121    BOOST_CONTAINER_FORCEINLINE T &get_data()
0122    {  return *move_detail::force_ptr<T*>(this->m_storage.data);   }
0123
0124    BOOST_CONTAINER_FORCEINLINE const T &get_data() const
0125    {  return *move_detail::force_ptr<const T*>(this->m_storage.data);  }
0126
0127    BOOST_CONTAINER_FORCEINLINE internal_type &get_real_data()
0128    {  return *move_detail::force_ptr<internal_type*>(this->m_storage.data);   }
0129
0130    BOOST_CONTAINER_FORCEINLINE const internal_type &get_real_data() const
0131    {  return *move_detail::force_ptr<const internal_type*>(this->m_storage.data);  }
0132
0133    #if defined(BOOST_CONTAINER_DISABLE_ALIASING_WARNING)
0134       #pragma GCC diagnostic pop
0135       #undef BOOST_CONTAINER_DISABLE_ALIASING_WARNING
0136    #  endif
0137
0138    template<class Alloc>
0139    BOOST_CONTAINER_FORCEINLINE void destructor(Alloc &a) BOOST_NOEXCEPT
0140    {
0141       allocator_traits<Alloc>::destroy
0142          (a, &this->get_real_data());
0143       this->~base_node();
0144    }
0145
0146    template<class Pair>
0147    BOOST_CONTAINER_FORCEINLINE
0148    typename dtl::enable_if< dtl::is_pair<Pair>, void >::type
0149       do_assign(const Pair &p)
0150    {
0151       typedef typename Pair::first_type first_type;
0152       const_cast<typename dtl::remove_const<first_type>::type &>(this->get_real_data().first) = p.first;
0153       this->get_real_data().second  = p.second;
0154    }
0155
0156    template<class V>
0157    BOOST_CONTAINER_FORCEINLINE
0158    typename dtl::disable_if< dtl::is_pair<V>, void >::type
0159       do_assign(const V &v)
0160    {  this->get_real_data() = v; }
0161
0162    template<class Pair>
0163    BOOST_CONTAINER_FORCEINLINE
0164    typename dtl::enable_if< dtl::is_pair<Pair>, void >::type
0165       do_move_assign(Pair &p)
0166    {
0167       typedef typename Pair::first_type first_type;
0168       const_cast<first_type&>(this->get_real_data().first) = ::boost::move(p.first);
0169       this->get_real_data().second = ::boost::move(p.second);
0170    }
0171
0172    template<class V>
0173    BOOST_CONTAINER_FORCEINLINE
0174    typename dtl::disable_if< dtl::is_pair<V>, void >::type
0175       do_move_assign(V &v)
0176    {  this->get_real_data() = ::boost::move(v); }
0177
0178    private:
0179    base_node();
0180
0181    BOOST_CONTAINER_FORCEINLINE ~base_node()
0182    { }
0183 };
0184
0185
0186 namespace dtl {
0187
0188 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(key_compare)
0189 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(key_equal)
0190 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(hasher)
0191 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(predicate_type)
0192 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(bucket_traits)
0193 BOOST_INTRUSIVE_INSTANTIATE_DEFAULT_TYPE_TMPLT(bucket_type)
0194
0195 template<class Allocator, class ICont>
0196 struct node_alloc_holder
0197    : public allocator_traits<Allocator>::template
0198             portable_rebind_alloc<typename ICont::value_type>::type   //NodeAlloc
0199 {
0200    //If the intrusive container is an associative container, obtain the predicate, which will
0201    //be of type node_compare<>. If not an associative container val_compare will be a "nat" type.
0202    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
0203       ( boost::container::dtl::
0204       , ICont, key_compare, dtl::nat)                 intrusive_key_compare;
0205
0206    //If the intrusive container is a hash container, obtain the predicate, which will
0207    //be of type node_compare<>. If not an associative container val_equal will be a "nat" type.
0208    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
0209       (boost::container::dtl::
0210          , ICont, key_equal, dtl::nat2)              intrusive_val_equal;
0211    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
0212    (boost::container::dtl::
0213       , ICont, hasher, dtl::nat3)                    intrusive_val_hasher;
0214    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
0215    (boost::container::dtl::
0216       , ICont, bucket_traits, dtl::natN<0>)           intrusive_bucket_traits;
0217    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
0218    (boost::container::dtl::
0219       , ICont, bucket_type, dtl::natN<1>)            intrusive_bucket_type;
0220    //In that case obtain the value predicate from the node predicate via predicate_type
0221    //if intrusive_key_compare is node_compare<>, nat otherwise
0222    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
0223    (boost::container::dtl::
0224       , intrusive_val_equal
0225       , predicate_type, dtl::nat2)                    val_equal;
0226    typedef BOOST_INTRUSIVE_OBTAIN_TYPE_WITH_DEFAULT
0227    (boost::container::dtl::
0228       , intrusive_val_hasher
0229       , predicate_type, dtl::nat3)                    val_hasher;
0230
0231    typedef allocator_traits<Allocator>                            allocator_traits_type;
0232    typedef typename allocator_traits_type::value_type             val_type;
0233    typedef ICont                                                  intrusive_container;
0234    typedef typename ICont::value_type                             Node;
0235    typedef typename allocator_traits_type::template
0236       portable_rebind_alloc<Node>::type                           NodeAlloc;
0237    typedef allocator_traits<NodeAlloc>                            node_allocator_traits_type;
0238    typedef dtl::allocator_version_traits<NodeAlloc>  node_allocator_version_traits_type;
0239    typedef Allocator                                              ValAlloc;
0240    typedef typename node_allocator_traits_type::pointer           NodePtr;
0241    typedef dtl::scoped_deallocator<NodeAlloc>        Deallocator;
0242    typedef typename node_allocator_traits_type::size_type         size_type;
0243    typedef typename node_allocator_traits_type::difference_type   difference_type;
0244    typedef dtl::integral_constant<unsigned,
0245       boost::container::dtl::
0246          version<NodeAlloc>::value>                               alloc_version;
0247    typedef typename ICont::iterator                               icont_iterator;
0248    typedef typename ICont::const_iterator                         icont_citerator;
0249    typedef allocator_node_destroyer<NodeAlloc>                         Destroyer;
0250    typedef allocator_traits<NodeAlloc>                            NodeAllocTraits;
0251    typedef allocator_version_traits<NodeAlloc>                    AllocVersionTraits;
0252
0253    private:
0254    BOOST_COPYABLE_AND_MOVABLE(node_alloc_holder)
0255
0256    public:
0257
0258    //Constructors for sequence containers
0259    BOOST_CONTAINER_FORCEINLINE node_alloc_holder()
0260    {}
0261
0262    explicit node_alloc_holder(const intrusive_bucket_traits& bt)
0263       : m_icont(bt)
0264    {}
0265
0266    explicit node_alloc_holder(const ValAlloc &a)
0267       : NodeAlloc(a)
0268    {}
0269
0270    node_alloc_holder(const intrusive_bucket_traits& bt, const ValAlloc& a)
0271       : NodeAlloc(a)
0272       , m_icont(bt)
0273    {}
0274
0275    //Constructors for associative containers
0276    node_alloc_holder(const intrusive_key_compare &c, const ValAlloc &a)
0277       : NodeAlloc(a), m_icont(c)
0278    {}
0279
0280    node_alloc_holder(const intrusive_bucket_traits & bt, const val_hasher &hf, const val_equal &eql, const ValAlloc &a)
0281       : NodeAlloc(a)
0282       , m_icont(bt
0283          , typename ICont::hasher(hf)
0284          , typename ICont::key_equal(eql))
0285    {}
0286
0287    node_alloc_holder(const intrusive_bucket_traits& bt, const val_hasher &hf, const ValAlloc &a)
0288       : NodeAlloc(a)
0289       , m_icont(bt
0290          , typename ICont::hasher(hf)
0291          , typename ICont::key_equal())
0292    {}
0293
0294    node_alloc_holder(const intrusive_bucket_traits& bt, const val_hasher &hf)
0295       : m_icont(bt
0296          , typename ICont::hasher(hf)
0297          , typename ICont::key_equal())
0298    {}
0299
0300    explicit node_alloc_holder(const node_alloc_holder &x)
0301       : NodeAlloc(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()))
0302    {}
0303
0304    node_alloc_holder(const node_alloc_holder &x, const intrusive_key_compare &c)
0305       : NodeAlloc(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()))
0306       , m_icont(c)
0307    {}
0308
0309    node_alloc_holder(const node_alloc_holder &x, const intrusive_bucket_traits& bt, const val_hasher &hf, const val_equal &eql)
0310       : NodeAlloc(NodeAllocTraits::select_on_container_copy_construction(x.node_alloc()))
0311       , m_icont( bt
0312                , typename ICont::hasher(hf)
0313                , typename ICont::key_equal(eql))
0314    {}
0315
0316    node_alloc_holder(const val_hasher &hf, const intrusive_bucket_traits& bt, const val_equal &eql)
0317       : m_icont(bt
0318          , typename ICont::hasher(hf)
0319          , typename ICont::key_equal(eql))
0320    {}
0321
0322    explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x)
0323       : NodeAlloc(boost::move(BOOST_MOVE_TO_LV(x).node_alloc()))
0324    {  this->icont().swap(x.icont());  }
0325
0326    explicit node_alloc_holder(const intrusive_key_compare &c)
0327       : m_icont(c)
0328    {}
0329
0330    //helpers for move assignments
0331    explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const intrusive_key_compare &c)
0332       : NodeAlloc(boost::move(BOOST_MOVE_TO_LV(x).node_alloc())), m_icont(c)
0333    {  this->icont().swap(x.icont());  }
0334
0335    explicit node_alloc_holder(BOOST_RV_REF(node_alloc_holder) x, const intrusive_bucket_traits& bt, const val_hasher &hf, const val_equal &eql)
0336       : NodeAlloc(boost::move(BOOST_MOVE_TO_LV(x).node_alloc()))
0337       , m_icont( bt
0338                , typename ICont::hasher(hf)
0339                , typename ICont::key_equal(eql))
0340    {  this->icont().swap(BOOST_MOVE_TO_LV(x).icont());   }
0341
0342    BOOST_CONTAINER_FORCEINLINE void copy_assign_alloc(const node_alloc_holder &x)
0343    {
0344       dtl::bool_<allocator_traits_type::propagate_on_container_copy_assignment::value> flag;
0345       dtl::assign_alloc( static_cast<NodeAlloc &>(*this)
0346                        , static_cast<const NodeAlloc &>(x), flag);
0347    }
0348
0349    BOOST_CONTAINER_FORCEINLINE void move_assign_alloc( node_alloc_holder &x)
0350    {
0351       dtl::bool_<allocator_traits_type::propagate_on_container_move_assignment::value> flag;
0352       dtl::move_alloc( static_cast<NodeAlloc &>(*this)
0353                      , static_cast<NodeAlloc &>(x), flag);
0354    }
0355
0356    BOOST_CONTAINER_FORCEINLINE ~node_alloc_holder()
0357    {  this->clear(alloc_version()); }
0358
0359    BOOST_CONTAINER_FORCEINLINE size_type max_size() const
0360    {  return allocator_traits_type::max_size(this->node_alloc());  }
0361
0362    BOOST_CONTAINER_FORCEINLINE NodePtr allocate_one()
0363    {  return AllocVersionTraits::allocate_one(this->node_alloc());   }
0364
0365    BOOST_CONTAINER_FORCEINLINE void deallocate_one(const NodePtr &p)
0366    {  AllocVersionTraits::deallocate_one(this->node_alloc(), p);  }
0367
0368    #if !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0369
0370    template<class ...Args>
0371    NodePtr create_node(Args &&...args)
0372    {
0373       NodePtr p = this->allocate_one();
0374       NodeAlloc &nalloc = this->node_alloc();
0375       Deallocator node_deallocator(p, nalloc);
0376       ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t())
0377          Node(nalloc, boost::forward<Args>(args)...);
0378       node_deallocator.release();
0379       return (p);
0380    }
0381
0382    #else //defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0383
0384    #define BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL(N) \
0385    BOOST_MOVE_TMPL_LT##N BOOST_MOVE_CLASS##N BOOST_MOVE_GT##N \
0386    NodePtr create_node(BOOST_MOVE_UREF##N)\
0387    {\
0388       NodePtr p = this->allocate_one();\
0389       NodeAlloc &nalloc = this->node_alloc();\
0390       Deallocator node_deallocator(p, nalloc);\
0391       ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t())\
0392          Node(nalloc BOOST_MOVE_I##N BOOST_MOVE_FWD##N);\
0393       node_deallocator.release();\
0394       return (p);\
0395    }\
0396    //
0397    BOOST_MOVE_ITERATE_0TO9(BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL)
0398    #undef BOOST_CONTAINER_NODE_ALLOC_HOLDER_CONSTRUCT_IMPL
0399
0400    #endif   // !defined(BOOST_NO_CXX11_VARIADIC_TEMPLATES)
0401
0402    template<class It>
0403    NodePtr create_node_from_it(const It &it)
0404    {
0405       NodePtr p = this->allocate_one();
0406       NodeAlloc &nalloc = this->node_alloc();
0407       Deallocator node_deallocator(p, nalloc);
0408       ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t())
0409          Node(iterator_arg_t(), nalloc, it);
0410       node_deallocator.release();
0411       return (p);
0412    }
0413
0414    template<class KeyConvertible>
0415    NodePtr create_node_from_key(BOOST_FWD_REF(KeyConvertible) key)
0416    {
0417       NodePtr p = this->allocate_one();
0418       BOOST_CONTAINER_TRY{
0419          ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t()) Node;
0420          NodeAlloc &na = this->node_alloc();
0421          node_allocator_traits_type::construct
0422             (na, dtl::addressof(p->get_real_data().first), boost::forward<KeyConvertible>(key));
0423          BOOST_CONTAINER_TRY{
0424             node_allocator_traits_type::construct(na, dtl::addressof(p->get_real_data().second));
0425          }
0426          BOOST_CONTAINER_CATCH(...){
0427             node_allocator_traits_type::destroy(na, dtl::addressof(p->get_real_data().first));
0428             BOOST_CONTAINER_RETHROW;
0429          }
0430          BOOST_CONTAINER_CATCH_END
0431       }
0432       BOOST_CONTAINER_CATCH(...) {
0433          p->destroy_header();
0434          this->node_alloc().deallocate(p, 1);
0435          BOOST_CONTAINER_RETHROW
0436       }
0437       BOOST_CONTAINER_CATCH_END
0438       return (p);
0439    }
0440
0441    void destroy_node(const NodePtr &nodep)
0442    {
0443       boost::movelib::to_raw_pointer(nodep)->destructor(this->node_alloc());
0444       this->deallocate_one(nodep);
0445    }
0446
0447    void swap(node_alloc_holder &x)
0448    {
0449       this->icont().swap(x.icont());
0450       dtl::bool_<allocator_traits_type::propagate_on_container_swap::value> flag;
0451       dtl::swap_alloc(this->node_alloc(), x.node_alloc(), flag);
0452    }
0453
0454    template<class FwdIterator, class Inserter>
0455    void allocate_many_and_construct
0456       (FwdIterator beg, size_type n, Inserter inserter)
0457    {
0458       if(n){
0459          typedef typename node_allocator_version_traits_type::multiallocation_chain multiallocation_chain_t;
0460
0461          //Try to allocate memory in a single block
0462          typedef typename multiallocation_chain_t::iterator multialloc_iterator_t;
0463          multiallocation_chain_t chain;
0464          NodeAlloc &nalloc = this->node_alloc();
0465          node_allocator_version_traits_type::allocate_individual(nalloc, n, chain);
0466          multialloc_iterator_t itbeg  = chain.begin();
0467          multialloc_iterator_t itlast = chain.last();
0468          chain.clear();
0469
0470          Node *p = 0;
0471             BOOST_CONTAINER_TRY{
0472             Deallocator node_deallocator(NodePtr(), nalloc);
0473             dtl::scoped_node_destructor<NodeAlloc> sdestructor(nalloc, 0);
0474             while(n){
0475                --n;
0476                p = boost::movelib::iterator_to_raw_pointer(itbeg);
0477                ++itbeg; //Increment iterator before overwriting pointed memory
0478                //This does not throw
0479                ::new(boost::movelib::iterator_to_raw_pointer(p), boost_container_new_t())
0480                   Node(iterator_arg_t(), nalloc, beg);
0481                sdestructor.set(p);
0482                ++beg;
0483                //This can throw in some containers (predicate might throw).
0484                //(sdestructor will destruct the node and node_deallocator will deallocate it in case of exception)
0485                inserter(*p);
0486                sdestructor.release();
0487             }
0488             sdestructor.release();
0489             node_deallocator.release();
0490          }
0491          BOOST_CONTAINER_CATCH(...){
0492             chain.incorporate_after(chain.last(), &*itbeg, &*itlast, n);
0493             node_allocator_version_traits_type::deallocate_individual(this->node_alloc(), chain);
0494             BOOST_CONTAINER_RETHROW
0495          }
0496          BOOST_CONTAINER_CATCH_END
0497       }
0498    }
0499
0500    BOOST_CONTAINER_FORCEINLINE void clear(version_1)
0501    {  this->icont().clear_and_dispose(Destroyer(this->node_alloc()));   }
0502
0503    void clear(version_2)
0504    {
0505       typename NodeAlloc::multiallocation_chain chain;
0506       allocator_node_destroyer_and_chain_builder<NodeAlloc> builder(this->node_alloc(), chain);
0507       this->icont().clear_and_dispose(builder);
0508       //BOOST_STATIC_ASSERT((::boost::has_move_emulation_enabled<typename NodeAlloc::multiallocation_chain>::value == true));
0509       if(!chain.empty())
0510          this->node_alloc().deallocate_individual(chain);
0511    }
0512
0513    icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_1)
0514    {  return this->icont().erase_and_dispose(first, last, Destroyer(this->node_alloc())); }
0515
0516    icont_iterator erase_range(const icont_iterator &first, const icont_iterator &last, version_2)
0517    {
0518       NodeAlloc & nalloc = this->node_alloc();
0519       typename NodeAlloc::multiallocation_chain chain;
0520       allocator_node_destroyer_and_chain_builder<NodeAlloc> chain_builder(nalloc, chain);
0521       icont_iterator ret_it = this->icont().erase_and_dispose(first, last, chain_builder);
0522       nalloc.deallocate_individual(chain);
0523       return ret_it;
0524    }
0525
0526    template<class Key>
0527    BOOST_CONTAINER_FORCEINLINE size_type erase_key(const Key& k, version_1)
0528    {  return this->icont().erase_and_dispose(k, Destroyer(this->node_alloc())); }
0529
0530    template<class Key>
0531    BOOST_CONTAINER_FORCEINLINE size_type erase_key(const Key& k, version_2)
0532    {
0533       allocator_multialloc_chain_node_deallocator<NodeAlloc> chain_holder(this->node_alloc());
0534       return this->icont().erase_and_dispose(k, chain_holder.get_chain_builder());
0535    }
0536
0537    protected:
0538    struct cloner
0539    {
0540       BOOST_CONTAINER_FORCEINLINE explicit cloner(node_alloc_holder &holder)
0541          :  m_holder(holder)
0542       {}
0543
0544       BOOST_CONTAINER_FORCEINLINE NodePtr operator()(const Node &other) const
0545       {  return m_holder.create_node(other.get_real_data());  }
0546
0547       node_alloc_holder &m_holder;
0548    };
0549
0550    struct move_cloner
0551    {
0552       BOOST_CONTAINER_FORCEINLINE move_cloner(node_alloc_holder &holder)
0553          :  m_holder(holder)
0554       {}
0555
0556       BOOST_CONTAINER_FORCEINLINE NodePtr operator()(Node &other)
0557       {  //Use get_real_data() instead of get_real_data to allow moving const key in [multi]map
0558          return m_holder.create_node(::boost::move(other.get_real_data()));
0559       }
0560
0561       node_alloc_holder &m_holder;
0562    };
0563
0564    BOOST_CONTAINER_FORCEINLINE ICont &non_const_icont() const
0565    {  return const_cast<ICont&>(this->m_icont);   }
0566
0567    BOOST_CONTAINER_FORCEINLINE NodeAlloc &node_alloc()
0568    {  return static_cast<NodeAlloc &>(*this);   }
0569
0570    BOOST_CONTAINER_FORCEINLINE const NodeAlloc &node_alloc() const
0571    {  return static_cast<const NodeAlloc &>(*this);   }
0572
0573    public:
0574    BOOST_CONTAINER_FORCEINLINE ICont &icont()
0575    {  return this->m_icont;   }
0576
0577    BOOST_CONTAINER_FORCEINLINE const ICont &icont() const
0578    {  return this->m_icont;   }
0579
0580    protected:
0581    //The intrusive container
0582    ICont m_icont;
0583 };
0584
0585 template<class Node, class KeyOfValue>
0586 struct key_of_node : KeyOfValue
0587 {
0588    typedef typename KeyOfValue::type type;
0589
0590    BOOST_CONTAINER_FORCEINLINE key_of_node()
0591    {}
0592
0593    BOOST_CONTAINER_FORCEINLINE const type& operator()(const Node& x) const
0594    {  return this->KeyOfValue::operator()(x.get_data());  }
0595 };
0596
0597
0598 }  //namespace dtl {
0599 }  //namespace container {
0600 }  //namespace boost {
0601
0602 #include <boost/container/detail/config_end.hpp>
0603
0604 #endif // BOOST_CONTAINER_DETAIL_NODE_ALLOC_HPP_