ceph/src/boost/boost/container/detail/node_alloc_holder.hpp

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