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