ceph/src/boost/boost/container/node_handle.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2016-2016. 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_NODE_HANDLE_HPP
  12 #define BOOST_CONTAINER_NODE_HANDLE_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 #include <boost/static_assert.hpp>
  25 #include <boost/container/detail/placement_new.hpp>
  26 #include <boost/move/detail/to_raw_pointer.hpp>
  27 #include <boost/container/allocator_traits.hpp>
  28 #include <boost/container/detail/mpl.hpp>
  29
  30 #include <boost/move/utility_core.hpp>
  31 #include <boost/move/adl_move_swap.hpp>
  32
  33 #include <boost/type_traits/aligned_storage.hpp>
  34
  35
  36 //!\file
  37
  38 namespace boost {
  39 namespace container {
  40
  41 ///@cond
  42
  43 template<class Value, class KeyMapped>
  44 struct node_handle_keymapped_traits
  45 {
  46    typedef typename KeyMapped::key_type      key_type;
  47    typedef typename KeyMapped::mapped_type   mapped_type;
  48 };
  49
  50 template<class Value>
  51 struct node_handle_keymapped_traits<Value, void>
  52 {
  53    typedef Value key_type;
  54    typedef Value mapped_type;
  55 };
  56
  57 class node_handle_friend
  58 {
  59    public:
  60
  61    template<class NH>
  62    BOOST_CONTAINER_FORCEINLINE static void destroy_alloc(NH &nh) BOOST_NOEXCEPT
  63    {  nh.destroy_alloc();  }
  64
  65    template<class NH>
  66    BOOST_CONTAINER_FORCEINLINE static typename NH::node_pointer &get_node_pointer(NH &nh) BOOST_NOEXCEPT
  67    {  return nh.get_node_pointer();  }
  68 };
  69
  70
  71 ///@endcond
  72
  73 //! A node_handle is an object that accepts ownership of a single element from an associative container.
  74 //! It may be used to transfer that ownership to another container with compatible nodes. Containers
  75 //! with compatible nodes have the same node handle type. Elements may be transferred in either direction
  76 //! between container types in the same row:.
  77 //!
  78 //! Container types with compatible nodes
  79 //!
  80 //! map<K, T, C1, A> <-> map<K, T, C2, A>
  81 //!
  82 //! map<K, T, C1, A> <-> multimap<K, T, C2, A>
  83 //!
  84 //! set<K, C1, A> <-> set<K, C2, A>
  85 //!
  86 //! set<K, C1, A> <-> multiset<K, C2, A>
  87 //!
  88 //! If a node handle is not empty, then it contains an allocator that is equal to the allocator of the container
  89 //! when the element was extracted. If a node handle is empty, it contains no allocator.
  90 template <class NodeAllocator, class KeyMapped = void>
  91 class node_handle
  92 {
  93    typedef NodeAllocator                                          nallocator_type;
  94    typedef allocator_traits<NodeAllocator>                        nator_traits;
  95    typedef typename nator_traits::value_type                      priv_node_t;
  96    typedef typename priv_node_t::value_type                       priv_value_t;
  97    typedef node_handle_keymapped_traits<priv_value_t, KeyMapped>  keymapped_t;
  98
  99    public:
 100    typedef priv_value_t                                           value_type;
 101    typedef typename keymapped_t::key_type                         key_type;
 102    typedef typename keymapped_t::mapped_type                      mapped_type;
 103    typedef typename nator_traits::template portable_rebind_alloc
 104       <value_type>::type                                          allocator_type;
 105
 106    typedef priv_node_t                                            container_node_type;
 107    friend class node_handle_friend;
 108
 109    ///@cond
 110    private:
 111    BOOST_MOVABLE_BUT_NOT_COPYABLE(node_handle)
 112
 113    typedef typename nator_traits::pointer                         node_pointer;
 114    typedef ::boost::aligned_storage
 115       < sizeof(nallocator_type)
 116       , boost::alignment_of<nallocator_type>::value>              nalloc_storage_t;
 117
 118    node_pointer      m_ptr;
 119    nalloc_storage_t  m_nalloc_storage;
 120
 121    void move_construct_alloc(nallocator_type &al)
 122    {  ::new(m_nalloc_storage.address(), boost_container_new_t()) nallocator_type(::boost::move(al));   }
 123
 124    void destroy_deallocate_node()
 125    {
 126       boost::movelib::to_raw_pointer(m_ptr)->destructor(this->node_alloc());
 127       nator_traits::deallocate(this->node_alloc(), m_ptr, 1u);
 128    }
 129
 130    template<class OtherNodeHandle>
 131    void move_construct_end(OtherNodeHandle &nh)
 132    {
 133       if(m_ptr){
 134          ::new (m_nalloc_storage.address(), boost_container_new_t()) nallocator_type(::boost::move(nh.node_alloc()));
 135          node_handle_friend::destroy_alloc(nh);
 136          node_handle_friend::get_node_pointer(nh) = node_pointer();
 137       }
 138       BOOST_ASSERT(nh.empty());
 139    }
 140
 141    void destroy_alloc() BOOST_NOEXCEPT
 142    {  static_cast<nallocator_type*>(m_nalloc_storage.address())->~nallocator_type();  }
 143
 144    node_pointer &get_node_pointer() BOOST_NOEXCEPT
 145    {  return m_ptr;  }
 146
 147    ///@endcond
 148
 149    public:
 150    //! <b>Effects</b>: Initializes m_ptr to nullptr.
 151    //!
 152    //! <b>Postcondition</b>: this->empty()
 153    BOOST_CXX14_CONSTEXPR node_handle() BOOST_NOEXCEPT
 154       :  m_ptr()
 155    { }
 156
 157    //! <b>Effects</b>: Constructs a node_handle object initializing internal pointer with p.
 158    //!   If p != nullptr copy constructs internal allocator from al.
 159    node_handle(node_pointer p, const nallocator_type &al) BOOST_NOEXCEPT
 160       :  m_ptr(p)
 161    {
 162       if(m_ptr){
 163          ::new (m_nalloc_storage.address(), boost_container_new_t()) nallocator_type(al);
 164       }
 165    }
 166
 167    //! <b>Effects</b>: Constructs a node_handle object initializing internal pointer with a related nh's internal pointer
 168    //!   and assigns nullptr to the later. If nh's internal pointer was not nullptr, move constructs internal
 169    //!   allocator with nh's internal allocator and destroy nh's internal allocator.
 170    //!
 171    //! <b>Postcondition</b>: nh.empty()
 172    //!
 173    //! <b>Note</b>: Two node_handle's are related if only one of KeyMapped template parameter
 174    //!   of a node handle is void.
 175    template<class KeyMapped2>
 176    node_handle( BOOST_RV_REF_BEG node_handle<NodeAllocator, KeyMapped2> BOOST_RV_REF_END nh
 177                , typename dtl::enable_if_c
 178                   < ((unsigned)dtl::is_same<KeyMapped,  void>::value +
 179                      (unsigned)dtl::is_same<KeyMapped2, void>::value) == 1u
 180                   >::type* = 0) BOOST_NOEXCEPT
 181       :  m_ptr(nh.get())
 182    {  this->move_construct_end(nh);  }
 183
 184    //! <b>Effects</b>: Constructs a node_handle object initializing internal pointer with nh's internal pointer
 185    //!   and assigns nullptr to the later. If nh's internal pointer was not nullptr, move constructs internal
 186    //!   allocator with nh's internal allocator and destroy nh's internal allocator.
 187    //!
 188    //! <b>Postcondition</b>: nh.empty()
 189    node_handle (BOOST_RV_REF(node_handle) nh) BOOST_NOEXCEPT
 190       : m_ptr(nh.m_ptr)
 191    {  this->move_construct_end(nh);  }
 192
 193    //! <b>Effects</b>: If !this->empty(), destroys the value_type subobject in the container_node_type object
 194    //!   pointed to by c by calling allocator_traits<impl_defined>::destroy, then deallocates m_ptr by calling
 195    //!   nator_traits::rebind_traits<container_node_type>::deallocate.
 196    ~node_handle() BOOST_NOEXCEPT
 197    {
 198       if(!this->empty()){
 199          this->destroy_deallocate_node();
 200          this->destroy_alloc();
 201       }
 202    }
 203
 204    //! <b>Requires</b>: Either this->empty(), or nator_traits::propagate_on_container_move_assignment is true, or
 205    //!   node_alloc() == nh.node_alloc().
 206    //!
 207    //! <b>Effects</b>: If m_ptr != nullptr, destroys the value_type subobject in the container_node_type object
 208    //!   pointed to by m_ptr by calling nator_traits::destroy, then deallocates m_ptr by calling
 209    //!   nator_traits::deallocate. Assigns nh.m_ptr to m_ptr. If this->empty()
 210    //!   or nator_traits::propagate_on_container_move_assignment is true, move assigns nh.node_alloc() to
 211    //!   node_alloc(). Assigns nullptr to nh.m_ptr and assigns nullopt to nh.node_alloc().
 212    //!
 213    //! <b>Returns</b>: *this.
 214    //!
 215    //! <b>Throws</b>: Nothing.
 216    node_handle & operator=(BOOST_RV_REF(node_handle) nh) BOOST_NOEXCEPT
 217    {
 218       BOOST_ASSERT(this->empty() || nator_traits::propagate_on_container_move_assignment::value
 219                    || nator_traits::equal(node_alloc(), nh.node_alloc()));
 220
 221       bool const was_this_non_null = !this->empty();
 222       bool const was_nh_non_null   = !nh.empty();
 223
 224       if(was_nh_non_null){
 225          if(was_this_non_null){
 226             this->destroy_deallocate_node();
 227             if(nator_traits::propagate_on_container_move_assignment::value){
 228                this->node_alloc() = ::boost::move(nh.node_alloc());
 229             }
 230          }
 231          else{
 232             this->move_construct_alloc(nh.node_alloc());
 233          }
 234          m_ptr = nh.m_ptr;
 235          nh.m_ptr = node_pointer();
 236          nh.destroy_alloc();
 237       }
 238       else if(was_this_non_null){
 239          this->destroy_deallocate_node();
 240          this->destroy_alloc();
 241          m_ptr = node_pointer();
 242       }
 243       return *this;
 244    }
 245
 246    //! <b>Requires</b>: empty() == false.
 247    //!
 248    //! <b>Returns</b>: A reference to the value_type subobject in the container_node_type object pointed to by m_ptr
 249    //!
 250    //! <b>Throws</b>: Nothing.
 251    value_type& value() const BOOST_NOEXCEPT
 252    {
 253       BOOST_STATIC_ASSERT((dtl::is_same<KeyMapped, void>::value));
 254       BOOST_ASSERT(!empty());
 255       return m_ptr->get_data();
 256    }
 257
 258    //! <b>Requires</b>: empty() == false.
 259    //!
 260    //! <b>Returns</b>: A non-const reference to the key_type member of the value_type subobject in the
 261    //!   container_node_type object pointed to by m_ptr.
 262    //!
 263    //! <b>Throws</b>: Nothing.
 264    //!
 265    //! <b>Requires</b>: Modifying the key through the returned reference is permitted.
 266    key_type& key() const BOOST_NOEXCEPT
 267    {
 268       BOOST_STATIC_ASSERT((!dtl::is_same<KeyMapped, void>::value));
 269       BOOST_ASSERT(!empty());
 270       return const_cast<key_type &>(KeyMapped().key_of_value(m_ptr->get_data()));
 271    }
 272
 273    //! <b>Requires</b>: empty() == false.
 274    //!
 275    //! <b>Returns</b>: A reference to the mapped_type member of the value_type subobject
 276    //!   in the container_node_type object pointed to by m_ptr
 277    //!
 278    //! <b>Throws</b>: Nothing.
 279    mapped_type& mapped() const BOOST_NOEXCEPT
 280    {
 281       BOOST_STATIC_ASSERT((!dtl::is_same<KeyMapped, void>::value));
 282       BOOST_ASSERT(!empty());
 283       return KeyMapped().mapped_of_value(m_ptr->get_data());
 284    }
 285
 286    //! <b>Requires</b>: empty() == false.
 287    //!
 288    //! <b>Returns</b>: A copy of the internally hold allocator.
 289    //!
 290    //! <b>Throws</b>: Nothing.
 291    allocator_type get_allocator() const
 292    {
 293       BOOST_ASSERT(!empty());
 294       return this->node_alloc();
 295    }
 296
 297    //! <b>Returns</b>: m_ptr != nullptr.
 298    //!
 299    #ifdef BOOST_CONTAINER_DOXYGEN_INVOKED
 300    BOOST_CONTAINER_FORCEINLINE explicit operator bool
 301    #else
 302    private: struct bool_conversion {int for_bool; int for_arg(); }; typedef int bool_conversion::* explicit_bool_arg;
 303    public: BOOST_CONTAINER_FORCEINLINE operator explicit_bool_arg
 304    #endif
 305       ()const BOOST_NOEXCEPT
 306    {  return m_ptr ? &bool_conversion::for_bool  : explicit_bool_arg(0);  }
 307
 308    //! <b>Returns</b>: m_ptr == nullptr.
 309    //!
 310    bool empty() const BOOST_NOEXCEPT
 311    {
 312       return !this->m_ptr;
 313    }
 314
 315    //! <b>Requires</b>: this->empty(), or nh.empty(), or nator_traits::propagate_on_container_swap is true, or
 316    //!   node_alloc() == nh.node_alloc().
 317    //!
 318    //! <b>Effects</b>: Calls swap(m_ptr, nh.m_ptr). If this->empty(), or nh.empty(), or nator_traits::propagate_on_-
 319    //!   container_swap is true calls swap(node_alloc(), nh.node_alloc()).
 320    void swap(node_handle &nh)
 321       BOOST_NOEXCEPT_IF(nator_traits::propagate_on_container_swap::value || nator_traits::is_always_equal::value)
 322    {
 323       BOOST_ASSERT(this->empty() || nh.empty() || nator_traits::propagate_on_container_swap::value
 324                    || nator_traits::equal(node_alloc(), nh.node_alloc()));
 325
 326       bool const was_this_non_null = !this->empty();
 327       bool const was_nh_non_null   = !nh.empty();
 328
 329       if(was_nh_non_null){
 330          if(was_this_non_null){
 331             if(nator_traits::propagate_on_container_swap::value){
 332                ::boost::adl_move_swap(this->node_alloc(), nh.node_alloc());
 333             }
 334          }
 335          else{
 336             this->move_construct_alloc(nh.node_alloc());
 337             nh.destroy_alloc();
 338          }
 339       }
 340       else if(was_this_non_null){
 341          nh.move_construct_alloc(this->node_alloc());
 342          this->destroy_alloc();
 343       }
 344       ::boost::adl_move_swap(m_ptr, nh.m_ptr);
 345    }
 346
 347    //! <b>Effects</b>: If this->empty() returns nullptr, otherwise returns m_ptr
 348    //!   resets m_ptr to nullptr and destroys the internal allocator.
 349    //!
 350    //! <b>Postcondition</b>: this->empty()
 351    //!
 352    //! <b>Note</b>: Non-standard extensions
 353    node_pointer release() BOOST_NOEXCEPT
 354    {
 355       node_pointer p(m_ptr);
 356       m_ptr = node_pointer();
 357       if(p)
 358          this->destroy_alloc();
 359       return p;
 360    }
 361
 362    //! <b>Effects</b>: Returns m_ptr.
 363    //!
 364    //! <b>Note</b>: Non-standard extensions
 365    node_pointer get() const BOOST_NOEXCEPT
 366    {
 367       return m_ptr;
 368    }
 369
 370    //! <b>Effects</b>: Returns a reference to the internal node allocator.
 371    //!
 372    //! <b>Note</b>: Non-standard extensions
 373    nallocator_type &node_alloc() BOOST_NOEXCEPT
 374    {
 375       BOOST_ASSERT(!empty());
 376       return *static_cast<nallocator_type*>(m_nalloc_storage.address());
 377    }
 378
 379
 380    //! <b>Effects</b>: Returns a reference to the internal node allocator.
 381    //!
 382    //! <b>Note</b>: Non-standard extensions
 383    const nallocator_type &node_alloc() const BOOST_NOEXCEPT
 384    {
 385       BOOST_ASSERT(!empty());
 386       return *static_cast<const nallocator_type*>(m_nalloc_storage.address());
 387    }
 388
 389    //! <b>Effects</b>: x.swap(y).
 390    //!
 391    friend void swap(node_handle & x, node_handle & y) BOOST_NOEXCEPT_IF(BOOST_NOEXCEPT(x.swap(y)))
 392    {  x.swap(y);  }
 393 };
 394
 395 //! A class template used to describe the results of inserting a
 396 //! Container::node_type in a Container with unique keys.
 397 //! Includes at least the following non-static public data members:
 398 //!
 399 //! <ul><li>bool inserted</li>;
 400 //! <li>Iterator position</li>;
 401 //! <li>NodeType node</li></ul>
 402 //!
 403 //! This type is MoveConstructible, MoveAssignable, DefaultConstructible,
 404 //! Destructible, and lvalues of that type are swappable
 405 template<class Iterator, class NodeType>
 406 struct insert_return_type_base
 407 {
 408    private:
 409    BOOST_MOVABLE_BUT_NOT_COPYABLE(insert_return_type_base)
 410
 411    public:
 412    insert_return_type_base()
 413       : inserted(false), position(), node()
 414    {}
 415
 416    insert_return_type_base(BOOST_RV_REF(insert_return_type_base) other)
 417       : inserted(other.inserted), position(other.position), node(boost::move(other.node))
 418    {}
 419
 420    template<class RelatedIt, class RelatedNode>
 421    insert_return_type_base(bool insert, RelatedIt it, BOOST_RV_REF(RelatedNode) n)
 422       : inserted(insert), position(it), node(boost::move(n))
 423    {}
 424
 425    insert_return_type_base & operator=(BOOST_RV_REF(insert_return_type_base) other)
 426    {
 427       inserted = other.inserted;
 428       position = other.position;
 429       node = boost::move(other.node);
 430       return *this;
 431    }
 432
 433    bool  inserted;
 434    Iterator position;
 435    NodeType node;
 436 };
 437
 438 }  //namespace container {
 439 }  //namespace boost {
 440
 441 #include <boost/container/detail/config_end.hpp>
 442
 443 #endif   //BOOST_CONTAINER_NODE_HANDLE_HPP