ceph/src/boost/libs/intrusive/include/boost/intrusive/rbtree.hpp

   1 /////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga  2006-2014
   4 //
   5 // Distributed under the Boost Software License, Version 1.0.
   6 //    (See accompanying file LICENSE_1_0.txt or copy at
   7 //          http://www.boost.org/LICENSE_1_0.txt)
   8 //
   9 // See http://www.boost.org/libs/intrusive for documentation.
  10 //
  11 /////////////////////////////////////////////////////////////////////////////
  12 #ifndef BOOST_INTRUSIVE_RBTREE_HPP
  13 #define BOOST_INTRUSIVE_RBTREE_HPP
  14
  15 #include <boost/intrusive/detail/config_begin.hpp>
  16 #include <boost/intrusive/intrusive_fwd.hpp>
  17 #include <cstddef>
  18 #include <boost/intrusive/detail/minimal_less_equal_header.hpp>
  19 #include <boost/intrusive/detail/minimal_pair_header.hpp>   //std::pair
  20
  21 #include <boost/intrusive/set_hook.hpp>
  22 #include <boost/intrusive/detail/rbtree_node.hpp>
  23 #include <boost/intrusive/bstree.hpp>
  24 #include <boost/intrusive/detail/tree_node.hpp>
  25 #include <boost/intrusive/detail/mpl.hpp>
  26 #include <boost/intrusive/pointer_traits.hpp>
  27 #include <boost/intrusive/detail/get_value_traits.hpp>
  28 #include <boost/intrusive/rbtree_algorithms.hpp>
  29 #include <boost/intrusive/link_mode.hpp>
  30
  31 #include <boost/move/utility_core.hpp>
  32 #include <boost/static_assert.hpp>
  33
  34 #if defined(BOOST_HAS_PRAGMA_ONCE)
  35 #  pragma once
  36 #endif
  37
  38 namespace boost {
  39 namespace intrusive {
  40
  41 /// @cond
  42
  43 struct default_rbtree_hook_applier
  44 {  template <class T> struct apply{ typedef typename T::default_rbtree_hook type;  };  };
  45
  46 template<>
  47 struct is_default_hook_tag<default_rbtree_hook_applier>
  48 {  static const bool value = true;  };
  49
  50 struct rbtree_defaults
  51    : bstree_defaults
  52 {
  53    typedef default_rbtree_hook_applier proto_value_traits;
  54 };
  55
  56 /// @endcond
  57
  58 //! The class template rbtree is an intrusive red-black tree container, that
  59 //! is used to construct intrusive set and multiset containers. The no-throw
  60 //! guarantee holds only, if the key_compare object
  61 //! doesn't throw.
  62 //!
  63 //! The template parameter \c T is the type to be managed by the container.
  64 //! The user can specify additional options and if no options are provided
  65 //! default options are used.
  66 //!
  67 //! The container supports the following options:
  68 //! \c base_hook<>/member_hook<>/value_traits<>,
  69 //! \c constant_time_size<>, \c size_type<> and
  70 //! \c compare<>.
  71 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED)
  72 template<class T, class ...Options>
  73 #else
  74 template<class ValueTraits, class VoidOrKeyOfValue, class VoidOrKeyComp, class SizeType, bool ConstantTimeSize, typename HeaderHolder>
  75 #endif
  76 class rbtree_impl
  77    /// @cond
  78    :  public bstree_impl<ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType, ConstantTimeSize, RbTreeAlgorithms, HeaderHolder>
  79    /// @endcond
  80 {
  81    public:
  82    typedef ValueTraits                                               value_traits;
  83    /// @cond
  84    typedef bstree_impl< ValueTraits, VoidOrKeyOfValue, VoidOrKeyComp, SizeType
  85                       , ConstantTimeSize, RbTreeAlgorithms
  86                       , HeaderHolder>                                tree_type;
  87    typedef tree_type                                                 implementation_defined;
  88    /// @endcond
  89
  90    typedef typename implementation_defined::pointer                  pointer;
  91    typedef typename implementation_defined::const_pointer            const_pointer;
  92    typedef typename implementation_defined::value_type               value_type;
  93    typedef typename implementation_defined::key_type                 key_type;
  94    typedef typename implementation_defined::key_of_value             key_of_value;
  95    typedef typename implementation_defined::reference                reference;
  96    typedef typename implementation_defined::const_reference          const_reference;
  97    typedef typename implementation_defined::difference_type          difference_type;
  98    typedef typename implementation_defined::size_type                size_type;
  99    typedef typename implementation_defined::value_compare            value_compare;
 100    typedef typename implementation_defined::key_compare              key_compare;
 101    typedef typename implementation_defined::iterator                 iterator;
 102    typedef typename implementation_defined::const_iterator           const_iterator;
 103    typedef typename implementation_defined::reverse_iterator         reverse_iterator;
 104    typedef typename implementation_defined::const_reverse_iterator   const_reverse_iterator;
 105    typedef typename implementation_defined::node_traits              node_traits;
 106    typedef typename implementation_defined::node                     node;
 107    typedef typename implementation_defined::node_ptr                 node_ptr;
 108    typedef typename implementation_defined::const_node_ptr           const_node_ptr;
 109    typedef typename implementation_defined::node_algorithms          node_algorithms;
 110
 111    static const bool constant_time_size = implementation_defined::constant_time_size;
 112    /// @cond
 113    private:
 114
 115    //noncopyable
 116    BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree_impl)
 117
 118    /// @endcond
 119
 120    public:
 121
 122    typedef typename implementation_defined::insert_commit_data insert_commit_data;
 123
 124    //! @copydoc ::boost::intrusive::bstree::bstree()
 125    rbtree_impl()
 126       :  tree_type()
 127    {}
 128
 129    //! @copydoc ::boost::intrusive::bstree::bstree(const key_compare &,const value_traits &)
 130    explicit rbtree_impl( const key_compare &cmp, const value_traits &v_traits = value_traits())
 131       :  tree_type(cmp, v_traits)
 132    {}
 133
 134    //! @copydoc ::boost::intrusive::bstree::bstree(bool,Iterator,Iterator,const key_compare &,const value_traits &)
 135    template<class Iterator>
 136    rbtree_impl( bool unique, Iterator b, Iterator e
 137               , const key_compare &cmp     = key_compare()
 138               , const value_traits &v_traits = value_traits())
 139       : tree_type(unique, b, e, cmp, v_traits)
 140    {}
 141
 142    //! @copydoc ::boost::intrusive::bstree::bstree(bstree &&)
 143    rbtree_impl(BOOST_RV_REF(rbtree_impl) x)
 144       :  tree_type(BOOST_MOVE_BASE(tree_type, x))
 145    {}
 146
 147    //! @copydoc ::boost::intrusive::bstree::operator=(bstree &&)
 148    rbtree_impl& operator=(BOOST_RV_REF(rbtree_impl) x)
 149    {  return static_cast<rbtree_impl&>(tree_type::operator=(BOOST_MOVE_BASE(tree_type, x))); }
 150
 151    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 152    //! @copydoc ::boost::intrusive::bstree::~bstree()
 153    ~rbtree_impl();
 154
 155    //! @copydoc ::boost::intrusive::bstree::begin()
 156    iterator begin();
 157
 158    //! @copydoc ::boost::intrusive::bstree::begin()const
 159    const_iterator begin() const;
 160
 161    //! @copydoc ::boost::intrusive::bstree::cbegin()const
 162    const_iterator cbegin() const;
 163
 164    //! @copydoc ::boost::intrusive::bstree::end()
 165    iterator end();
 166
 167    //! @copydoc ::boost::intrusive::bstree::end()const
 168    const_iterator end() const;
 169
 170    //! @copydoc ::boost::intrusive::bstree::cend()const
 171    const_iterator cend() const;
 172
 173    //! @copydoc ::boost::intrusive::bstree::rbegin()
 174    reverse_iterator rbegin();
 175
 176    //! @copydoc ::boost::intrusive::bstree::rbegin()const
 177    const_reverse_iterator rbegin() const;
 178
 179    //! @copydoc ::boost::intrusive::bstree::crbegin()const
 180    const_reverse_iterator crbegin() const;
 181
 182    //! @copydoc ::boost::intrusive::bstree::rend()
 183    reverse_iterator rend();
 184
 185    //! @copydoc ::boost::intrusive::bstree::rend()const
 186    const_reverse_iterator rend() const;
 187
 188    //! @copydoc ::boost::intrusive::bstree::crend()const
 189    const_reverse_iterator crend() const;
 190
 191    //! @copydoc ::boost::intrusive::bstree::root()
 192    iterator root();
 193
 194    //! @copydoc ::boost::intrusive::bstree::root()const
 195    const_iterator root() const;
 196
 197    //! @copydoc ::boost::intrusive::bstree::croot()const
 198    const_iterator croot() const;
 199
 200    //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(iterator)
 201    static rbtree_impl &container_from_end_iterator(iterator end_iterator);
 202
 203    //! @copydoc ::boost::intrusive::bstree::container_from_end_iterator(const_iterator)
 204    static const rbtree_impl &container_from_end_iterator(const_iterator end_iterator);
 205
 206    //! @copydoc ::boost::intrusive::bstree::container_from_iterator(iterator)
 207    static rbtree_impl &container_from_iterator(iterator it);
 208
 209    //! @copydoc ::boost::intrusive::bstree::container_from_iterator(const_iterator)
 210    static const rbtree_impl &container_from_iterator(const_iterator it);
 211
 212    //! @copydoc ::boost::intrusive::bstree::key_comp()const
 213    key_compare key_comp() const;
 214
 215    //! @copydoc ::boost::intrusive::bstree::value_comp()const
 216    value_compare value_comp() const;
 217
 218    //! @copydoc ::boost::intrusive::bstree::empty()const
 219    bool empty() const;
 220
 221    //! @copydoc ::boost::intrusive::bstree::size()const
 222    size_type size() const;
 223
 224    //! @copydoc ::boost::intrusive::bstree::swap
 225    void swap(rbtree_impl& other);
 226
 227    //! @copydoc ::boost::intrusive::bstree::clone_from(const bstree&,Cloner,Disposer)
 228    template <class Cloner, class Disposer>
 229    void clone_from(const rbtree_impl &src, Cloner cloner, Disposer disposer);
 230
 231    #else //BOOST_INTRUSIVE_DOXYGEN_INVOKED
 232
 233    using tree_type::clone_from;
 234
 235    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 236
 237    //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer)
 238    template <class Cloner, class Disposer>
 239    void clone_from(BOOST_RV_REF(rbtree_impl) src, Cloner cloner, Disposer disposer)
 240    {  tree_type::clone_from(BOOST_MOVE_BASE(tree_type, src), cloner, disposer);  }
 241
 242    #ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 243
 244    //! @copydoc ::boost::intrusive::bstree::clone_from(bstree&&,Cloner,Disposer)
 245    template <class Cloner, class Disposer>
 246    void clone_from(rbtree_impl &&src, Cloner cloner, Disposer disposer);
 247
 248    //! @copydoc ::boost::intrusive::bstree::insert_equal(reference)
 249    iterator insert_equal(reference value);
 250
 251    //! @copydoc ::boost::intrusive::bstree::insert_equal(const_iterator,reference)
 252    iterator insert_equal(const_iterator hint, reference value);
 253
 254    //! @copydoc ::boost::intrusive::bstree::insert_equal(Iterator,Iterator)
 255    template<class Iterator>
 256    void insert_equal(Iterator b, Iterator e);
 257
 258    //! @copydoc ::boost::intrusive::bstree::insert_unique(reference)
 259    std::pair<iterator, bool> insert_unique(reference value);
 260
 261    //! @copydoc ::boost::intrusive::bstree::insert_unique(const_iterator,reference)
 262    iterator insert_unique(const_iterator hint, reference value);
 263
 264    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
 265    template<class KeyType, class KeyTypeKeyCompare>
 266    std::pair<iterator, bool> insert_unique_check
 267       (const KeyType &key, KeyTypeKeyCompare comp, insert_commit_data &commit_data);
 268
 269    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const KeyType&,KeyTypeKeyCompare,insert_commit_data&)
 270    template<class KeyType, class KeyTypeKeyCompare>
 271    std::pair<iterator, bool> insert_unique_check
 272       (const_iterator hint, const KeyType &key
 273       ,KeyTypeKeyCompare comp, insert_commit_data &commit_data);
 274
 275    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const key_type&,insert_commit_data&)
 276    std::pair<iterator, bool> insert_unique_check
 277       (const key_type &key, insert_commit_data &commit_data);
 278
 279    //! @copydoc ::boost::intrusive::bstree::insert_unique_check(const_iterator,const key_type&,insert_commit_data&)
 280    std::pair<iterator, bool> insert_unique_check
 281       (const_iterator hint, const key_type &key, insert_commit_data &commit_data);
 282
 283    //! @copydoc ::boost::intrusive::bstree::insert_unique_commit
 284    iterator insert_unique_commit(reference value, const insert_commit_data &commit_data);
 285
 286    //! @copydoc ::boost::intrusive::bstree::insert_unique(Iterator,Iterator)
 287    template<class Iterator>
 288    void insert_unique(Iterator b, Iterator e);
 289
 290    //! @copydoc ::boost::intrusive::bstree::insert_before
 291    iterator insert_before(const_iterator pos, reference value);
 292
 293    //! @copydoc ::boost::intrusive::bstree::push_back
 294    void push_back(reference value);
 295
 296    //! @copydoc ::boost::intrusive::bstree::push_front
 297    void push_front(reference value);
 298
 299    //! @copydoc ::boost::intrusive::bstree::erase(const_iterator)
 300    iterator erase(const_iterator i);
 301
 302    //! @copydoc ::boost::intrusive::bstree::erase(const_iterator,const_iterator)
 303    iterator erase(const_iterator b, const_iterator e);
 304
 305    //! @copydoc ::boost::intrusive::bstree::erase(const key_type &key)
 306    size_type erase(const key_type &key);
 307
 308    //! @copydoc ::boost::intrusive::bstree::erase(const KeyType&,KeyTypeKeyCompare)
 309    template<class KeyType, class KeyTypeKeyCompare>
 310    size_type erase(const KeyType& key, KeyTypeKeyCompare comp);
 311
 312    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,Disposer)
 313    template<class Disposer>
 314    iterator erase_and_dispose(const_iterator i, Disposer disposer);
 315
 316    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const_iterator,const_iterator,Disposer)
 317    template<class Disposer>
 318    iterator erase_and_dispose(const_iterator b, const_iterator e, Disposer disposer);
 319
 320    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const key_type &, Disposer)
 321    template<class Disposer>
 322    size_type erase_and_dispose(const key_type &key, Disposer disposer);
 323
 324    //! @copydoc ::boost::intrusive::bstree::erase_and_dispose(const KeyType&,KeyTypeKeyCompare,Disposer)
 325    template<class KeyType, class KeyTypeKeyCompare, class Disposer>
 326    size_type erase_and_dispose(const KeyType& key, KeyTypeKeyCompare comp, Disposer disposer);
 327
 328    //! @copydoc ::boost::intrusive::bstree::clear
 329    void clear();
 330
 331    //! @copydoc ::boost::intrusive::bstree::clear_and_dispose
 332    template<class Disposer>
 333    void clear_and_dispose(Disposer disposer);
 334
 335    //! @copydoc ::boost::intrusive::bstree::count(const key_type &)const
 336    size_type count(const key_type &key) const;
 337
 338    //! @copydoc ::boost::intrusive::bstree::count(const KeyType&,KeyTypeKeyCompare)const
 339    template<class KeyType, class KeyTypeKeyCompare>
 340    size_type count(const KeyType& key, KeyTypeKeyCompare comp) const;
 341
 342    //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)
 343    iterator lower_bound(const key_type &key);
 344
 345    //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)
 346    template<class KeyType, class KeyTypeKeyCompare>
 347    iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp);
 348
 349    //! @copydoc ::boost::intrusive::bstree::lower_bound(const key_type &)const
 350    const_iterator lower_bound(const key_type &key) const;
 351
 352    //! @copydoc ::boost::intrusive::bstree::lower_bound(const KeyType&,KeyTypeKeyCompare)const
 353    template<class KeyType, class KeyTypeKeyCompare>
 354    const_iterator lower_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 355
 356    //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)
 357    iterator upper_bound(const key_type &key);
 358
 359    //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)
 360    template<class KeyType, class KeyTypeKeyCompare>
 361    iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp);
 362
 363    //! @copydoc ::boost::intrusive::bstree::upper_bound(const key_type &)const
 364    const_iterator upper_bound(const key_type &key) const;
 365
 366    //! @copydoc ::boost::intrusive::bstree::upper_bound(const KeyType&,KeyTypeKeyCompare)const
 367    template<class KeyType, class KeyTypeKeyCompare>
 368    const_iterator upper_bound(const KeyType& key, KeyTypeKeyCompare comp) const;
 369
 370    //! @copydoc ::boost::intrusive::bstree::find(const key_type &)
 371    iterator find(const key_type &key);
 372
 373    //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)
 374    template<class KeyType, class KeyTypeKeyCompare>
 375    iterator find(const KeyType& key, KeyTypeKeyCompare comp);
 376
 377    //! @copydoc ::boost::intrusive::bstree::find(const key_type &)const
 378    const_iterator find(const key_type &key) const;
 379
 380    //! @copydoc ::boost::intrusive::bstree::find(const KeyType&,KeyTypeKeyCompare)const
 381    template<class KeyType, class KeyTypeKeyCompare>
 382    const_iterator find(const KeyType& key, KeyTypeKeyCompare comp) const;
 383
 384    //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)
 385    std::pair<iterator,iterator> equal_range(const key_type &key);
 386
 387    //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)
 388    template<class KeyType, class KeyTypeKeyCompare>
 389    std::pair<iterator,iterator> equal_range(const KeyType& key, KeyTypeKeyCompare comp);
 390
 391    //! @copydoc ::boost::intrusive::bstree::equal_range(const key_type &)const
 392    std::pair<const_iterator, const_iterator>
 393       equal_range(const key_type &key) const;
 394
 395    //! @copydoc ::boost::intrusive::bstree::equal_range(const KeyType&,KeyTypeKeyCompare)const
 396    template<class KeyType, class KeyTypeKeyCompare>
 397    std::pair<const_iterator, const_iterator>
 398       equal_range(const KeyType& key, KeyTypeKeyCompare comp) const;
 399
 400    //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)
 401    std::pair<iterator,iterator> bounded_range
 402       (const key_type &lower, const key_type &upper_key, bool left_closed, bool right_closed);
 403
 404    //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)
 405    template<class KeyType, class KeyTypeKeyCompare>
 406    std::pair<iterator,iterator> bounded_range
 407       (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed);
 408
 409    //! @copydoc ::boost::intrusive::bstree::bounded_range(const key_type &,const key_type &,bool,bool)const
 410    std::pair<const_iterator, const_iterator>
 411       bounded_range(const key_type &lower_key, const key_type &upper_key, bool left_closed, bool right_closed) const;
 412
 413    //! @copydoc ::boost::intrusive::bstree::bounded_range(const KeyType&,const KeyType&,KeyTypeKeyCompare,bool,bool)const
 414    template<class KeyType, class KeyTypeKeyCompare>
 415    std::pair<const_iterator, const_iterator> bounded_range
 416          (const KeyType& lower_key, const KeyType& upper_key, KeyTypeKeyCompare comp, bool left_closed, bool right_closed) const;
 417
 418    //! @copydoc ::boost::intrusive::bstree::s_iterator_to(reference)
 419    static iterator s_iterator_to(reference value);
 420
 421    //! @copydoc ::boost::intrusive::bstree::s_iterator_to(const_reference)
 422    static const_iterator s_iterator_to(const_reference value);
 423
 424    //! @copydoc ::boost::intrusive::bstree::iterator_to(reference)
 425    iterator iterator_to(reference value);
 426
 427    //! @copydoc ::boost::intrusive::bstree::iterator_to(const_reference)const
 428    const_iterator iterator_to(const_reference value) const;
 429
 430    //! @copydoc ::boost::intrusive::bstree::init_node(reference)
 431    static void init_node(reference value);
 432
 433    //! @copydoc ::boost::intrusive::bstree::unlink_leftmost_without_rebalance
 434    pointer unlink_leftmost_without_rebalance();
 435
 436    //! @copydoc ::boost::intrusive::bstree::replace_node
 437    void replace_node(iterator replace_this, reference with_this);
 438
 439    //! @copydoc ::boost::intrusive::bstree::remove_node
 440    void remove_node(reference value);
 441
 442    //! @copydoc ::boost::intrusive::bstree::merge_unique(bstree<T, Options2...>&)
 443    template<class T, class ...Options2>
 444    void merge_unique(rbtree<T, Options2...> &);
 445
 446    //! @copydoc ::boost::intrusive::bstree::merge_equal(bstree<T, Options2...>&)
 447    template<class T, class ...Options2>
 448    void merge_equal(rbtree<T, Options2...> &);
 449
 450    friend bool operator< (const rbtree_impl &x, const rbtree_impl &y);
 451
 452    friend bool operator==(const rbtree_impl &x, const rbtree_impl &y);
 453
 454    friend bool operator!= (const rbtree_impl &x, const rbtree_impl &y);
 455
 456    friend bool operator>(const rbtree_impl &x, const rbtree_impl &y);
 457
 458    friend bool operator<=(const rbtree_impl &x, const rbtree_impl &y);
 459
 460    friend bool operator>=(const rbtree_impl &x, const rbtree_impl &y);
 461
 462    friend void swap(rbtree_impl &x, rbtree_impl &y);
 463    #endif   //#ifdef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 464 };
 465
 466
 467 //! Helper metafunction to define a \c rbtree that yields to the same type when the
 468 //! same options (either explicitly or implicitly) are used.
 469 #if defined(BOOST_INTRUSIVE_DOXYGEN_INVOKED) || defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 470 template<class T, class ...Options>
 471 #else
 472 template<class T, class O1 = void, class O2 = void
 473                 , class O3 = void, class O4 = void
 474                 , class O5 = void, class O6 = void>
 475 #endif
 476 struct make_rbtree
 477 {
 478    /// @cond
 479    typedef typename pack_options
 480       < rbtree_defaults,
 481       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 482       O1, O2, O3, O4, O5, O6
 483       #else
 484       Options...
 485       #endif
 486       >::type packed_options;
 487
 488    typedef typename detail::get_value_traits
 489       <T, typename packed_options::proto_value_traits>::type value_traits;
 490
 491    typedef rbtree_impl
 492          < value_traits
 493          , typename packed_options::key_of_value
 494          , typename packed_options::compare
 495          , typename packed_options::size_type
 496          , packed_options::constant_time_size
 497          , typename packed_options::header_holder_type
 498          > implementation_defined;
 499    /// @endcond
 500    typedef implementation_defined type;
 501 };
 502
 503
 504 #ifndef BOOST_INTRUSIVE_DOXYGEN_INVOKED
 505
 506 #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 507 template<class T, class O1, class O2, class O3, class O4, class O5, class O6>
 508 #else
 509 template<class T, class ...Options>
 510 #endif
 511 class rbtree
 512    :  public make_rbtree<T,
 513       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 514       O1, O2, O3, O4, O5, O6
 515       #else
 516       Options...
 517       #endif
 518       >::type
 519 {
 520    typedef typename make_rbtree
 521       <T,
 522       #if !defined(BOOST_INTRUSIVE_VARIADIC_TEMPLATES)
 523       O1, O2, O3, O4, O5, O6
 524       #else
 525       Options...
 526       #endif
 527       >::type   Base;
 528    BOOST_MOVABLE_BUT_NOT_COPYABLE(rbtree)
 529
 530    public:
 531    typedef typename Base::key_compare        key_compare;
 532    typedef typename Base::value_traits       value_traits;
 533    typedef typename Base::iterator           iterator;
 534    typedef typename Base::const_iterator     const_iterator;
 535    typedef typename Base::reverse_iterator           reverse_iterator;
 536    typedef typename Base::const_reverse_iterator     const_reverse_iterator;
 537
 538    //Assert if passed value traits are compatible with the type
 539    BOOST_STATIC_ASSERT((detail::is_same<typename value_traits::value_type, T>::value));
 540
 541    rbtree()
 542       :  Base()
 543    {}
 544
 545    explicit rbtree( const key_compare &cmp, const value_traits &v_traits = value_traits())
 546       :  Base(cmp, v_traits)
 547    {}
 548
 549    template<class Iterator>
 550    rbtree( bool unique, Iterator b, Iterator e
 551          , const key_compare &cmp = key_compare()
 552          , const value_traits &v_traits = value_traits())
 553       :  Base(unique, b, e, cmp, v_traits)
 554    {}
 555
 556    rbtree(BOOST_RV_REF(rbtree) x)
 557       :  Base(BOOST_MOVE_BASE(Base, x))
 558    {}
 559
 560    rbtree& operator=(BOOST_RV_REF(rbtree) x)
 561    {  return static_cast<rbtree &>(this->Base::operator=(BOOST_MOVE_BASE(Base, x)));  }
 562
 563    template <class Cloner, class Disposer>
 564    void clone_from(const rbtree &src, Cloner cloner, Disposer disposer)
 565    {  Base::clone_from(src, cloner, disposer);  }
 566
 567    template <class Cloner, class Disposer>
 568    void clone_from(BOOST_RV_REF(rbtree) src, Cloner cloner, Disposer disposer)
 569    {  Base::clone_from(BOOST_MOVE_BASE(Base, src), cloner, disposer);  }
 570
 571    static rbtree &container_from_end_iterator(iterator end_iterator)
 572    {  return static_cast<rbtree &>(Base::container_from_end_iterator(end_iterator));   }
 573
 574    static const rbtree &container_from_end_iterator(const_iterator end_iterator)
 575    {  return static_cast<const rbtree &>(Base::container_from_end_iterator(end_iterator));   }
 576
 577    static rbtree &container_from_iterator(iterator it)
 578    {  return static_cast<rbtree &>(Base::container_from_iterator(it));   }
 579
 580    static const rbtree &container_from_iterator(const_iterator it)
 581    {  return static_cast<const rbtree &>(Base::container_from_iterator(it));   }
 582 };
 583
 584 #endif
 585
 586 } //namespace intrusive
 587 } //namespace boost
 588
 589 #include <boost/intrusive/detail/config_end.hpp>
 590
 591 #endif //BOOST_INTRUSIVE_RBTREE_HPP