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