boost/interprocess/containers/container/detail/tree.hpp

   1 //////////////////////////////////////////////////////////////////////////////
   2 //
   3 // (C) Copyright Ion Gaztanaga 2005-2008. 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 // This file comes from SGI's stl_tree file. Modified by Ion Gaztanaga 2005.
  12 // Renaming, isolating and porting to generic algorithms. Pointer typedef
  13 // set to allocator::pointer to allow placing it in shared memory.
  14 //
  15 ///////////////////////////////////////////////////////////////////////////////
  16 /*
  17  *
  18  * Copyright (c) 1994
  19  * Hewlett-Packard Company
  20  *
  21  * Permission to use, copy, modify, distribute and sell this software
  22  * and its documentation for any purpose is hereby granted without fee,
  23  * provided that the above copyright notice appear in all copies and
  24  * that both that copyright notice and this permission notice appear
  25  * in supporting documentation.  Hewlett-Packard Company makes no
  26  * representations about the suitability of this software for any
  27  * purpose.  It is provided "as is" without express or implied warranty.
  28  *
  29  *
  30  * Copyright (c) 1996
  31  * Silicon Graphics Computer Systems, Inc.
  32  *
  33  * Permission to use, copy, modify, distribute and sell this software
  34  * and its documentation for any purpose is hereby granted without fee,
  35  * provided that the above copyright notice appear in all copies and
  36  * that both that copyright notice and this permission notice appear
  37  * in supporting documentation.  Silicon Graphics makes no
  38  * representations about the suitability of this software for any
  39  * purpose.  It is provided "as is" without express or implied warranty.
  40  *
  41  */
  42 #ifndef BOOST_CONTAINERS_TREE_HPP
  43 #define BOOST_CONTAINERS_TREE_HPP
  44
  45 #include <boost/interprocess/containers/container/detail/config_begin.hpp>
  46 #include <boost/interprocess/containers/container/detail/workaround.hpp>
  47
  48 #include <boost/interprocess/detail/move.hpp>
  49 #include <boost/pointer_to_other.hpp>
  50 #include <boost/type_traits/has_trivial_destructor.hpp>
  51 #include <boost/detail/no_exceptions_support.hpp>
  52 #include <boost/intrusive/rbtree.hpp>
  53
  54 #include <boost/interprocess/containers/container/detail/utilities.hpp>
  55 #include <boost/interprocess/containers/container/detail/algorithms.hpp>
  56 #include <boost/interprocess/containers/container/detail/node_alloc_holder.hpp>
  57 #include <boost/interprocess/containers/container/detail/destroyers.hpp>
  58 #include <boost/interprocess/containers/container/detail/pair.hpp>
  59 #ifndef BOOST_CONTAINERS_PERFECT_FORWARDING
  60 #include <boost/interprocess/containers/container/detail/preprocessor.hpp>
  61 #endif
  62
  63 #include <utility>   //std::pair
  64 #include <iterator>
  65 #include <algorithm>
  66
  67 namespace boost {
  68 namespace interprocess_container {
  69 namespace containers_detail {
  70
  71 template<class Key, class Value, class KeyCompare, class KeyOfValue>
  72 struct value_compare_impl
  73    :  public KeyCompare
  74 {
  75    typedef Value        value_type;
  76    typedef KeyCompare   key_compare;
  77    typedef KeyOfValue   key_of_value;
  78    typedef Key          key_type;
  79
  80    value_compare_impl(key_compare kcomp)
  81       :  key_compare(kcomp)
  82    {}
  83
  84    const key_compare &key_comp() const
  85    {  return static_cast<const key_compare &>(*this);  }
  86
  87    key_compare &key_comp()
  88    {  return static_cast<key_compare &>(*this);  }
  89
  90    template<class A, class B>
  91    bool operator()(const A &a, const B &b) const
  92    {  return key_compare::operator()(KeyOfValue()(a), KeyOfValue()(b)); }
  93 };
  94
  95 template<class VoidPointer>
  96 struct rbtree_hook
  97 {
  98    typedef typename containers_detail::bi::make_set_base_hook
  99       < containers_detail::bi::void_pointer<VoidPointer>
 100       , containers_detail::bi::link_mode<containers_detail::bi::normal_link>
 101       , containers_detail::bi::optimize_size<true>
 102       >::type  type;
 103 };
 104
 105 template<class T>
 106 struct rbtree_type
 107 {
 108    typedef T type;
 109 };
 110
 111 template<class T1, class T2>
 112 struct rbtree_type< std::pair<T1, T2> >
 113 {
 114    typedef pair<T1, T2> type;
 115 };
 116
 117 template <class T, class VoidPointer>
 118 struct rbtree_node
 119    :  public rbtree_hook<VoidPointer>::type
 120 {
 121    typedef typename rbtree_hook<VoidPointer>::type hook_type;
 122
 123    typedef T value_type;
 124    typedef typename rbtree_type<T>::type internal_type;
 125
 126    typedef rbtree_node<T, VoidPointer> node_type;
 127
 128    #ifndef BOOST_CONTAINERS_PERFECT_FORWARDING
 129
 130    rbtree_node()
 131       : m_data()
 132    {}
 133
 134    rbtree_node(const rbtree_node &other)
 135       : m_data(other.m_data)
 136    {}
 137
 138    #define BOOST_PP_LOCAL_MACRO(n)                                                           \
 139    template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                \
 140    rbtree_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _))                        \
 141       : m_data(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _))                     \
 142    {}                                                                                        \
 143    //!
 144    #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS)
 145    #include BOOST_PP_LOCAL_ITERATE()
 146
 147    #else //#ifndef BOOST_CONTAINERS_PERFECT_FORWARDING
 148
 149    rbtree_node()
 150       : m_data()
 151    {}
 152
 153    template<class ...Args>
 154    rbtree_node(Args &&...args)
 155       : m_data(boost::interprocess::forward<Args>(args)...)
 156    {}
 157    #endif//#ifndef BOOST_CONTAINERS_PERFECT_FORWARDING
 158
 159    rbtree_node &operator=(const rbtree_node &other)
 160    {  do_assign(other.m_data);   return *this;  }
 161
 162    T &get_data()
 163    {
 164       T* ptr = reinterpret_cast<T*>(&this->m_data);
 165       return *ptr;
 166    }
 167
 168    const T &get_data() const
 169    {
 170       const T* ptr = reinterpret_cast<const T*>(&this->m_data);
 171       return *ptr;
 172    }
 173
 174    private:
 175    internal_type m_data;
 176
 177    template<class A, class B>
 178    void do_assign(const std::pair<const A, B> &p)
 179    {
 180       const_cast<A&>(m_data.first) = p.first;
 181       m_data.second  = p.second;
 182    }
 183
 184    template<class A, class B>
 185    void do_assign(const pair<const A, B> &p)
 186    {
 187       const_cast<A&>(m_data.first) = p.first;
 188       m_data.second  = p.second;
 189    }
 190
 191    template<class V>
 192    void do_assign(const V &v)
 193    {  m_data = v; }
 194
 195    public:
 196    template<class Convertible>
 197    static void construct(node_type *ptr, BOOST_INTERPROCESS_FWD_REF(Convertible) convertible)
 198    {  new(ptr) node_type(boost::interprocess::forward<Convertible>(convertible));  }
 199 };
 200
 201 }//namespace containers_detail {
 202 #if !defined(BOOST_HAS_RVALUE_REFS)
 203 template<class T, class VoidPointer>
 204 struct has_own_construct_from_it
 205    < boost::interprocess_container::containers_detail::rbtree_node<T, VoidPointer> >
 206 {
 207    static const bool value = true;
 208 };
 209 #endif
 210 namespace containers_detail {
 211
 212 template<class A, class ValueCompare>
 213 struct intrusive_rbtree_type
 214 {
 215    typedef typename A::value_type                  value_type;
 216    typedef typename boost::pointer_to_other
 217       <typename A::pointer, void>::type            void_pointer;
 218    typedef typename containers_detail::rbtree_node
 219          <value_type, void_pointer>                node_type;
 220    typedef node_compare<ValueCompare, node_type>   node_compare_type;
 221    typedef typename containers_detail::bi::make_rbtree
 222       <node_type
 223       ,containers_detail::bi::compare<node_compare_type>
 224       ,containers_detail::bi::base_hook<typename rbtree_hook<void_pointer>::type>
 225       ,containers_detail::bi::constant_time_size<true>
 226       ,containers_detail::bi::size_type<typename A::size_type>
 227       >::type                                      container_type;
 228    typedef container_type                          type ;
 229 };
 230
 231 }  //namespace containers_detail {
 232
 233 namespace containers_detail {
 234
 235 template <class Key, class Value, class KeyOfValue,
 236           class KeyCompare, class A>
 237 class rbtree
 238    : protected containers_detail::node_alloc_holder
 239       <A, typename containers_detail::intrusive_rbtree_type
 240          <A, value_compare_impl<Key, Value, KeyCompare, KeyOfValue>
 241          >::type
 242       >
 243 {
 244    typedef typename containers_detail::intrusive_rbtree_type
 245          <A, value_compare_impl
 246             <Key, Value, KeyCompare, KeyOfValue>
 247          >::type                                      Icont;
 248    typedef containers_detail::node_alloc_holder<A, Icont>        AllocHolder;
 249    typedef typename AllocHolder::NodePtr              NodePtr;
 250    typedef rbtree < Key, Value, KeyOfValue
 251                   , KeyCompare, A>                    ThisType;
 252    typedef typename AllocHolder::NodeAlloc            NodeAlloc;
 253    typedef typename AllocHolder::ValAlloc             ValAlloc;
 254    typedef typename AllocHolder::Node                 Node;
 255    typedef typename Icont::iterator                   iiterator;
 256    typedef typename Icont::const_iterator             iconst_iterator;
 257    typedef containers_detail::allocator_destroyer<NodeAlloc>     Destroyer;
 258    typedef typename AllocHolder::allocator_v1         allocator_v1;
 259    typedef typename AllocHolder::allocator_v2         allocator_v2;
 260    typedef typename AllocHolder::alloc_version        alloc_version;
 261
 262    class RecyclingCloner;
 263    friend class RecyclingCloner;
 264
 265    class RecyclingCloner
 266    {
 267       public:
 268       RecyclingCloner(AllocHolder &holder, Icont &irbtree)
 269          :  m_holder(holder), m_icont(irbtree)
 270       {}
 271
 272       NodePtr operator()(const Node &other) const
 273       {
 274 //         if(!m_icont.empty()){
 275          if(NodePtr p = m_icont.unlink_leftmost_without_rebalance()){
 276             //First recycle a node (this can't throw)
 277             //NodePtr p = m_icont.unlink_leftmost_without_rebalance();
 278             try{
 279                //This can throw
 280                *p = other;
 281                return p;
 282             }
 283             catch(...){
 284                //If there is an exception destroy the whole source
 285                m_holder.destroy_node(p);
 286                while((p = m_icont.unlink_leftmost_without_rebalance())){
 287                   m_holder.destroy_node(p);
 288                }
 289                throw;
 290             }
 291          }
 292          else{
 293             return m_holder.create_node(other);
 294          }
 295       }
 296
 297       AllocHolder &m_holder;
 298       Icont &m_icont;
 299    };
 300
 301    public:
 302    BOOST_INTERPROCESS_ENABLE_MOVE_EMULATION(rbtree)
 303
 304    typedef Key                                        key_type;
 305    typedef Value                                      value_type;
 306    typedef A                                          allocator_type;
 307    typedef KeyCompare                                 key_compare;
 308    typedef value_compare_impl< Key, Value
 309                         , KeyCompare, KeyOfValue>     value_compare;
 310    typedef typename A::pointer                        pointer;
 311    typedef typename A::const_pointer                  const_pointer;
 312    typedef typename A::reference                      reference;
 313    typedef typename A::const_reference                const_reference;
 314    typedef typename A::size_type                      size_type;
 315    typedef typename A::difference_type                difference_type;
 316    typedef difference_type                            rbtree_difference_type;
 317    typedef pointer                                    rbtree_pointer;
 318    typedef const_pointer                              rbtree_const_pointer;
 319    typedef reference                                  rbtree_reference;
 320    typedef const_reference                            rbtree_const_reference;
 321    typedef NodeAlloc                                  stored_allocator_type;
 322
 323    private:
 324
 325    template<class KeyValueCompare>
 326    struct key_node_compare
 327       :  private KeyValueCompare
 328    {
 329       key_node_compare(KeyValueCompare comp)
 330          :  KeyValueCompare(comp)
 331       {}
 332
 333       template<class KeyType>
 334       bool operator()(const Node &n, const KeyType &k) const
 335       {  return KeyValueCompare::operator()(n.get_data(), k);  }
 336
 337       template<class KeyType>
 338       bool operator()(const KeyType &k, const Node &n) const
 339       {  return KeyValueCompare::operator()(k, n.get_data());  }
 340    };
 341
 342    typedef key_node_compare<value_compare>  KeyNodeCompare;
 343
 344    public:
 345    //rbtree const_iterator
 346    class const_iterator
 347       : public std::iterator
 348          < std::bidirectional_iterator_tag
 349          , value_type            , rbtree_difference_type
 350          , rbtree_const_pointer  , rbtree_const_reference>
 351    {
 352       protected:
 353       typedef typename Icont::iterator  iiterator;
 354       iiterator m_it;
 355       explicit const_iterator(iiterator it)  : m_it(it){}
 356       void prot_incr() { ++m_it; }
 357       void prot_decr() { --m_it; }
 358
 359       private:
 360       iiterator get()
 361       {  return this->m_it;   }
 362
 363       public:
 364       friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>;
 365       typedef rbtree_difference_type        difference_type;
 366
 367       //Constructors
 368       const_iterator()
 369          :  m_it()
 370       {}
 371
 372       //Pointer like operators
 373       const_reference operator*()  const
 374       { return  m_it->get_data();  }
 375
 376       const_pointer   operator->() const
 377       { return  const_pointer(&m_it->get_data()); }
 378
 379       //Increment / Decrement
 380       const_iterator& operator++()
 381       { prot_incr();  return *this; }
 382
 383       const_iterator operator++(int)
 384       { iiterator tmp = m_it; ++*this; return const_iterator(tmp);  }
 385
 386       const_iterator& operator--()
 387       {   prot_decr(); return *this;   }
 388
 389       const_iterator operator--(int)
 390       {  iiterator tmp = m_it; --*this; return const_iterator(tmp); }
 391
 392       //Comparison operators
 393       bool operator==   (const const_iterator& r)  const
 394       {  return m_it == r.m_it;  }
 395
 396       bool operator!=   (const const_iterator& r)  const
 397       {  return m_it != r.m_it;  }
 398    };
 399
 400    //rbtree iterator
 401    class iterator : public const_iterator
 402    {
 403       private:
 404       explicit iterator(iiterator it)
 405          :  const_iterator(it)
 406       {}
 407
 408       iiterator get()
 409       {  return this->m_it;   }
 410
 411       public:
 412       friend class rbtree <Key, Value, KeyOfValue, KeyCompare, A>;
 413       typedef rbtree_pointer       pointer;
 414       typedef rbtree_reference     reference;
 415
 416       //Constructors
 417       iterator(){}
 418
 419       //Pointer like operators
 420       reference operator*()  const {  return  this->m_it->get_data();  }
 421       pointer   operator->() const {  return  pointer(&this->m_it->get_data());  }
 422
 423       //Increment / Decrement
 424       iterator& operator++()
 425          { this->prot_incr(); return *this;  }
 426
 427       iterator operator++(int)
 428          { iiterator tmp = this->m_it; ++*this; return iterator(tmp); }
 429
 430       iterator& operator--()
 431          {  this->prot_decr(); return *this;  }
 432
 433       iterator operator--(int)
 434          {  iterator tmp = *this; --*this; return tmp; }
 435    };
 436
 437    typedef std::reverse_iterator<iterator>        reverse_iterator;
 438    typedef std::reverse_iterator<const_iterator>  const_reverse_iterator;
 439
 440    rbtree(const key_compare& comp = key_compare(),
 441            const allocator_type& a = allocator_type())
 442       : AllocHolder(a, comp)
 443    {}
 444
 445    template <class InputIterator>
 446    rbtree(InputIterator first, InputIterator last, const key_compare& comp,
 447           const allocator_type& a, bool unique_insertion)
 448       : AllocHolder(a, comp)
 449    {
 450       typedef typename std::iterator_traits<InputIterator>::iterator_category ItCat;
 451       priv_create_and_insert_nodes(first, last, unique_insertion, alloc_version(), ItCat());
 452    }
 453
 454    rbtree(const rbtree& x)
 455       :  AllocHolder(x, x.key_comp())
 456    {
 457       this->icont().clone_from
 458          (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
 459    }
 460
 461    rbtree(BOOST_INTERPROCESS_RV_REF(rbtree) x)
 462       :  AllocHolder(x, x.key_comp())
 463    {  this->swap(x);  }
 464
 465    ~rbtree()
 466    {} //AllocHolder clears the tree
 467
 468    rbtree& operator=(const rbtree& x)
 469    {
 470       if (this != &x) {
 471          //Transfer all the nodes to a temporary tree
 472          //If anything goes wrong, all the nodes will be destroyed
 473          //automatically
 474          Icont other_tree(this->icont().value_comp());
 475          other_tree.swap(this->icont());
 476
 477          //Now recreate the source tree reusing nodes stored by other_tree
 478          this->icont().clone_from
 479             (x.icont()
 480             , RecyclingCloner(*this, other_tree)
 481             //, AllocHolder::cloner(*this)
 482             , Destroyer(this->node_alloc()));
 483
 484          //If there are remaining nodes, destroy them
 485          NodePtr p;
 486          while((p = other_tree.unlink_leftmost_without_rebalance())){
 487             AllocHolder::destroy_node(p);
 488          }
 489       }
 490       return *this;
 491    }
 492
 493    rbtree& operator=(BOOST_INTERPROCESS_RV_REF(rbtree) mx)
 494    {  this->clear(); this->swap(mx);   return *this;  }
 495
 496    public:
 497    // accessors:
 498    value_compare value_comp() const
 499    {  return this->icont().value_comp().value_comp(); }
 500
 501    key_compare key_comp() const
 502    {  return this->icont().value_comp().value_comp().key_comp(); }
 503
 504    allocator_type get_allocator() const
 505    {  return allocator_type(this->node_alloc()); }
 506
 507    const stored_allocator_type &get_stored_allocator() const
 508    {  return this->node_alloc(); }
 509
 510    stored_allocator_type &get_stored_allocator()
 511    {  return this->node_alloc(); }
 512
 513    iterator begin()
 514    { return iterator(this->icont().begin()); }
 515
 516    const_iterator begin() const
 517    {  return this->cbegin();  }
 518
 519    iterator end()
 520    {  return iterator(this->icont().end());  }
 521
 522    const_iterator end() const
 523    {  return this->cend();  }
 524
 525    reverse_iterator rbegin()
 526    {  return reverse_iterator(end());  }
 527
 528    const_reverse_iterator rbegin() const
 529    {  return this->crbegin();  }
 530
 531    reverse_iterator rend()
 532    {  return reverse_iterator(begin());   }
 533
 534    const_reverse_iterator rend() const
 535    {  return this->crend();   }
 536
 537    //! <b>Effects</b>: Returns a const_iterator to the first element contained in the container.
 538    //!
 539    //! <b>Throws</b>: Nothing.
 540    //!
 541    //! <b>Complexity</b>: Constant.
 542    const_iterator cbegin() const
 543    { return const_iterator(this->non_const_icont().begin()); }
 544
 545    //! <b>Effects</b>: Returns a const_iterator to the end of the container.
 546    //!
 547    //! <b>Throws</b>: Nothing.
 548    //!
 549    //! <b>Complexity</b>: Constant.
 550    const_iterator cend() const
 551    { return const_iterator(this->non_const_icont().end()); }
 552
 553    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the beginning
 554    //! of the reversed container.
 555    //!
 556    //! <b>Throws</b>: Nothing.
 557    //!
 558    //! <b>Complexity</b>: Constant.
 559    const_reverse_iterator crbegin() const
 560    { return const_reverse_iterator(cend()); }
 561
 562    //! <b>Effects</b>: Returns a const_reverse_iterator pointing to the end
 563    //! of the reversed container.
 564    //!
 565    //! <b>Throws</b>: Nothing.
 566    //!
 567    //! <b>Complexity</b>: Constant.
 568    const_reverse_iterator crend() const
 569    { return const_reverse_iterator(cbegin()); }
 570
 571    bool empty() const
 572    {  return !this->size();  }
 573
 574    size_type size() const
 575    {  return this->icont().size();   }
 576
 577    size_type max_size() const
 578    {  return AllocHolder::max_size();  }
 579
 580    void swap(ThisType& x)
 581    {  AllocHolder::swap(x);   }
 582
 583    public:
 584
 585    typedef typename Icont::insert_commit_data insert_commit_data;
 586
 587    // insert/erase
 588    std::pair<iterator,bool> insert_unique_check
 589       (const key_type& key, insert_commit_data &data)
 590    {
 591       std::pair<iiterator, bool> ret =
 592          this->icont().insert_unique_check(key, KeyNodeCompare(value_comp()), data);
 593       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
 594    }
 595
 596    std::pair<iterator,bool> insert_unique_check
 597       (const_iterator hint, const key_type& key, insert_commit_data &data)
 598    {
 599       std::pair<iiterator, bool> ret =
 600          this->icont().insert_unique_check(hint.get(), key, KeyNodeCompare(value_comp()), data);
 601       return std::pair<iterator, bool>(iterator(ret.first), ret.second);
 602    }
 603
 604    iterator insert_unique_commit(const value_type& v, insert_commit_data &data)
 605    {
 606       NodePtr tmp = AllocHolder::create_node(v);
 607       iiterator it(this->icont().insert_unique_commit(*tmp, data));
 608       return iterator(it);
 609    }
 610
 611    template<class MovableConvertible>
 612    iterator insert_unique_commit
 613       (BOOST_INTERPROCESS_FWD_REF(MovableConvertible) mv, insert_commit_data &data)
 614    {
 615       NodePtr tmp = AllocHolder::create_node(boost::interprocess::forward<MovableConvertible>(mv));
 616       iiterator it(this->icont().insert_unique_commit(*tmp, data));
 617       return iterator(it);
 618    }
 619
 620    std::pair<iterator,bool> insert_unique(const value_type& v)
 621    {
 622       insert_commit_data data;
 623       std::pair<iterator,bool> ret =
 624          this->insert_unique_check(KeyOfValue()(v), data);
 625       if(!ret.second)
 626          return ret;
 627       return std::pair<iterator,bool>
 628          (this->insert_unique_commit(v, data), true);
 629    }
 630
 631    template<class MovableConvertible>
 632    std::pair<iterator,bool> insert_unique(BOOST_INTERPROCESS_FWD_REF(MovableConvertible) mv)
 633    {
 634       insert_commit_data data;
 635       std::pair<iterator,bool> ret =
 636          this->insert_unique_check(KeyOfValue()(mv), data);
 637       if(!ret.second)
 638          return ret;
 639       return std::pair<iterator,bool>
 640          (this->insert_unique_commit(boost::interprocess::forward<MovableConvertible>(mv), data), true);
 641    }
 642
 643    private:
 644    iterator emplace_unique_impl(NodePtr p)
 645    {
 646       value_type &v = p->get_data();
 647       insert_commit_data data;
 648       std::pair<iterator,bool> ret =
 649          this->insert_unique_check(KeyOfValue()(v), data);
 650       if(!ret.second){
 651          Destroyer(this->node_alloc())(p);
 652          return ret.first;
 653       }
 654       return iterator(iiterator(this->icont().insert_unique_commit(*p, data)));
 655    }
 656
 657    iterator emplace_unique_hint_impl(const_iterator hint, NodePtr p)
 658    {
 659       value_type &v = p->get_data();
 660       insert_commit_data data;
 661       std::pair<iterator,bool> ret =
 662          this->insert_unique_check(hint, KeyOfValue()(v), data);
 663       if(!ret.second){
 664          Destroyer(this->node_alloc())(p);
 665          return ret.first;
 666       }
 667       return iterator(iiterator(this->icont().insert_unique_commit(*p, data)));
 668    }
 669
 670    public:
 671
 672    #ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
 673
 674    template <class... Args>
 675    iterator emplace_unique(Args&&... args)
 676    {  return this->emplace_unique_impl(AllocHolder::create_node(boost::interprocess::forward<Args>(args)...));   }
 677
 678    template <class... Args>
 679    iterator emplace_hint_unique(const_iterator hint, Args&&... args)
 680    {  return this->emplace_unique_hint_impl(hint, AllocHolder::create_node(boost::interprocess::forward<Args>(args)...));   }
 681
 682    template <class... Args>
 683    iterator emplace_equal(Args&&... args)
 684    {
 685       NodePtr p(AllocHolder::create_node(boost::interprocess::forward<Args>(args)...));
 686       return iterator(this->icont().insert_equal(this->icont().end(), *p));
 687    }
 688
 689    template <class... Args>
 690    iterator emplace_hint_equal(const_iterator hint, Args&&... args)
 691    {
 692       NodePtr p(AllocHolder::create_node(boost::interprocess::forward<Args>(args)...));
 693       return iterator(this->icont().insert_equal(hint.get(), *p));
 694    }
 695
 696    #else //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
 697
 698    iterator emplace_unique()
 699    {  return this->emplace_unique_impl(AllocHolder::create_node());   }
 700
 701    iterator emplace_hint_unique(const_iterator hint)
 702    {  return this->emplace_unique_hint_impl(hint, AllocHolder::create_node());   }
 703
 704    iterator emplace_equal()
 705    {
 706       NodePtr p(AllocHolder::create_node());
 707       return iterator(this->icont().insert_equal(this->icont().end(), *p));
 708    }
 709
 710    iterator emplace_hint_equal(const_iterator hint)
 711    {
 712       NodePtr p(AllocHolder::create_node());
 713       return iterator(this->icont().insert_equal(hint.get(), *p));
 714    }
 715
 716    #define BOOST_PP_LOCAL_MACRO(n)                                                                          \
 717    template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                               \
 718    iterator emplace_unique(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _))                           \
 719    {                                                                                                        \
 720       return this->emplace_unique_impl                                                                      \
 721          (AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)));              \
 722    }                                                                                                        \
 723                                                                                                             \
 724    template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                               \
 725    iterator emplace_hint_unique(const_iterator hint, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _)) \
 726    {                                                                                                        \
 727       return this->emplace_unique_hint_impl                                                                 \
 728          (hint, AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)));        \
 729    }                                                                                                        \
 730                                                                                                             \
 731    template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                               \
 732    iterator emplace_equal(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _))                            \
 733    {                                                                                                        \
 734       NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)));        \
 735       return iterator(this->icont().insert_equal(this->icont().end(), *p));                                 \
 736    }                                                                                                        \
 737                                                                                                             \
 738    template<BOOST_PP_ENUM_PARAMS(n, class P)>                                                               \
 739    iterator emplace_hint_equal(const_iterator hint, BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_LIST, _))  \
 740    {                                                                                                        \
 741       NodePtr p(AllocHolder::create_node(BOOST_PP_ENUM(n, BOOST_CONTAINERS_PP_PARAM_FORWARD, _)));        \
 742       return iterator(this->icont().insert_equal(hint.get(), *p));                                          \
 743    }                                                                                                        \
 744    //!
 745    #define BOOST_PP_LOCAL_LIMITS (1, BOOST_CONTAINERS_MAX_CONSTRUCTOR_PARAMETERS)
 746    #include BOOST_PP_LOCAL_ITERATE()
 747
 748    #endif   //#ifdef BOOST_CONTAINERS_PERFECT_FORWARDING
 749
 750    iterator insert_unique(const_iterator hint, const value_type& v)
 751    {
 752       insert_commit_data data;
 753       std::pair<iterator,bool> ret =
 754          this->insert_unique_check(hint, KeyOfValue()(v), data);
 755       if(!ret.second)
 756          return ret.first;
 757       return this->insert_unique_commit(v, data);
 758    }
 759
 760    template<class MovableConvertible>
 761    iterator insert_unique(const_iterator hint, BOOST_INTERPROCESS_FWD_REF(MovableConvertible) mv)
 762    {
 763       insert_commit_data data;
 764       std::pair<iterator,bool> ret =
 765          this->insert_unique_check(hint, KeyOfValue()(mv), data);
 766       if(!ret.second)
 767          return ret.first;
 768       return this->insert_unique_commit(boost::interprocess::forward<MovableConvertible>(mv), data);
 769    }
 770
 771    template <class InputIterator>
 772    void insert_unique(InputIterator first, InputIterator last)
 773    {
 774       if(this->empty()){
 775          //Insert with end hint, to achieve linear
 776          //complexity if [first, last) is ordered
 777          const_iterator end(this->end());
 778          for( ; first != last; ++first)
 779             this->insert_unique(end, *first);
 780       }
 781       else{
 782          for( ; first != last; ++first)
 783             this->insert_unique(*first);
 784       }
 785    }
 786
 787    iterator insert_equal(const value_type& v)
 788    {
 789       NodePtr p(AllocHolder::create_node(v));
 790       return iterator(this->icont().insert_equal(this->icont().end(), *p));
 791    }
 792
 793    template<class MovableConvertible>
 794    iterator insert_equal(BOOST_INTERPROCESS_FWD_REF(MovableConvertible) mv)
 795    {
 796       NodePtr p(AllocHolder::create_node(boost::interprocess::forward<MovableConvertible>(mv)));
 797       return iterator(this->icont().insert_equal(this->icont().end(), *p));
 798    }
 799
 800    iterator insert_equal(const_iterator hint, const value_type& v)
 801    {
 802       NodePtr p(AllocHolder::create_node(v));
 803       return iterator(this->icont().insert_equal(hint.get(), *p));
 804    }
 805
 806    template<class MovableConvertible>
 807    iterator insert_equal(const_iterator hint, BOOST_INTERPROCESS_FWD_REF(MovableConvertible) mv)
 808    {
 809       NodePtr p(AllocHolder::create_node(boost::interprocess::forward<MovableConvertible>(mv)));
 810       return iterator(this->icont().insert_equal(hint.get(), *p));
 811    }
 812
 813    template <class InputIterator>
 814    void insert_equal(InputIterator first, InputIterator last)
 815    {
 816       //Insert with end hint, to achieve linear
 817       //complexity if [first, last) is ordered
 818       const_iterator end(this->cend());
 819       for( ; first != last; ++first)
 820          this->insert_equal(end, *first);
 821    }
 822
 823    iterator erase(const_iterator position)
 824    {  return iterator(this->icont().erase_and_dispose(position.get(), Destroyer(this->node_alloc()))); }
 825
 826    size_type erase(const key_type& k)
 827    {  return AllocHolder::erase_key(k, KeyNodeCompare(value_comp()), alloc_version()); }
 828
 829    iterator erase(const_iterator first, const_iterator last)
 830    {  return iterator(AllocHolder::erase_range(first.get(), last.get(), alloc_version())); }
 831
 832    void clear()
 833    {  AllocHolder::clear(alloc_version());  }
 834
 835    // set operations:
 836    iterator find(const key_type& k)
 837    {  return iterator(this->icont().find(k, KeyNodeCompare(value_comp())));  }
 838
 839    const_iterator find(const key_type& k) const
 840    {  return const_iterator(this->non_const_icont().find(k, KeyNodeCompare(value_comp())));  }
 841
 842    size_type count(const key_type& k) const
 843    {  return size_type(this->icont().count(k, KeyNodeCompare(value_comp()))); }
 844
 845    iterator lower_bound(const key_type& k)
 846    {  return iterator(this->icont().lower_bound(k, KeyNodeCompare(value_comp())));  }
 847
 848    const_iterator lower_bound(const key_type& k) const
 849    {  return const_iterator(this->non_const_icont().lower_bound(k, KeyNodeCompare(value_comp())));  }
 850
 851    iterator upper_bound(const key_type& k)
 852    {  return iterator(this->icont().upper_bound(k, KeyNodeCompare(value_comp())));   }
 853
 854    const_iterator upper_bound(const key_type& k) const
 855    {  return const_iterator(this->non_const_icont().upper_bound(k, KeyNodeCompare(value_comp())));  }
 856
 857    std::pair<iterator,iterator> equal_range(const key_type& k)
 858    {
 859       std::pair<iiterator, iiterator> ret =
 860          this->icont().equal_range(k, KeyNodeCompare(value_comp()));
 861       return std::pair<iterator,iterator>(iterator(ret.first), iterator(ret.second));
 862    }
 863
 864    std::pair<const_iterator, const_iterator> equal_range(const key_type& k) const
 865    {
 866       std::pair<iiterator, iiterator> ret =
 867          this->non_const_icont().equal_range(k, KeyNodeCompare(value_comp()));
 868       return std::pair<const_iterator,const_iterator>
 869          (const_iterator(ret.first), const_iterator(ret.second));
 870    }
 871
 872    private:
 873    //Iterator range version
 874    template<class InpIterator>
 875    void priv_create_and_insert_nodes
 876       (InpIterator beg, InpIterator end, bool unique)
 877    {
 878       typedef typename std::iterator_traits<InpIterator>::iterator_category ItCat;
 879       priv_create_and_insert_nodes(beg, end, unique, alloc_version(), ItCat());
 880    }
 881
 882    template<class InpIterator>
 883    void priv_create_and_insert_nodes
 884       (InpIterator beg, InpIterator end, bool unique, allocator_v1, std::input_iterator_tag)
 885    {
 886       if(unique){
 887          for (; beg != end; ++beg){
 888             this->insert_unique(*beg);
 889          }
 890       }
 891       else{
 892          for (; beg != end; ++beg){
 893             this->insert_equal(*beg);
 894          }
 895       }
 896    }
 897
 898    template<class InpIterator>
 899    void priv_create_and_insert_nodes
 900       (InpIterator beg, InpIterator end, bool unique, allocator_v2, std::input_iterator_tag)
 901    {  //Just forward to the default one
 902       priv_create_and_insert_nodes(beg, end, unique, allocator_v1(), std::input_iterator_tag());
 903    }
 904
 905    class insertion_functor;
 906    friend class insertion_functor;
 907
 908    class insertion_functor
 909    {
 910       Icont &icont_;
 911
 912       public:
 913       insertion_functor(Icont &icont)
 914          :  icont_(icont)
 915       {}
 916
 917       void operator()(Node &n)
 918       {  this->icont_.insert_equal(this->icont_.cend(), n); }
 919    };
 920
 921
 922    template<class FwdIterator>
 923    void priv_create_and_insert_nodes
 924       (FwdIterator beg, FwdIterator end, bool unique, allocator_v2, std::forward_iterator_tag)
 925    {
 926       if(beg != end){
 927          if(unique){
 928             priv_create_and_insert_nodes(beg, end, unique, allocator_v2(), std::input_iterator_tag());
 929          }
 930          else{
 931             //Optimized allocation and construction
 932             this->allocate_many_and_construct
 933                (beg, std::distance(beg, end), insertion_functor(this->icont()));
 934          }
 935       }
 936    }
 937 };
 938
 939 template <class Key, class Value, class KeyOfValue,
 940           class KeyCompare, class A>
 941 inline bool
 942 operator==(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
 943            const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y)
 944 {
 945   return x.size() == y.size() &&
 946          std::equal(x.begin(), x.end(), y.begin());
 947 }
 948
 949 template <class Key, class Value, class KeyOfValue,
 950           class KeyCompare, class A>
 951 inline bool
 952 operator<(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
 953           const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y)
 954 {
 955   return std::lexicographical_compare(x.begin(), x.end(),
 956                                       y.begin(), y.end());
 957 }
 958
 959 template <class Key, class Value, class KeyOfValue,
 960           class KeyCompare, class A>
 961 inline bool
 962 operator!=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
 963            const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
 964   return !(x == y);
 965 }
 966
 967 template <class Key, class Value, class KeyOfValue,
 968           class KeyCompare, class A>
 969 inline bool
 970 operator>(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
 971           const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
 972   return y < x;
 973 }
 974
 975 template <class Key, class Value, class KeyOfValue,
 976           class KeyCompare, class A>
 977 inline bool
 978 operator<=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
 979            const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
 980   return !(y < x);
 981 }
 982
 983 template <class Key, class Value, class KeyOfValue,
 984           class KeyCompare, class A>
 985 inline bool
 986 operator>=(const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
 987            const rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y) {
 988   return !(x < y);
 989 }
 990
 991
 992 template <class Key, class Value, class KeyOfValue,
 993           class KeyCompare, class A>
 994 inline void
 995 swap(rbtree<Key,Value,KeyOfValue,KeyCompare,A>& x,
 996      rbtree<Key,Value,KeyOfValue,KeyCompare,A>& y)
 997 {
 998   x.swap(y);
 999 }
1000
1001 } //namespace containers_detail {
1002 } //namespace interprocess_container {
1003
1004 namespace interprocess {
1005
1006 //!has_trivial_destructor_after_move<> == true_type
1007 //!specialization for optimizations
1008 template <class K, class V, class KOV,
1009 class C, class A>
1010 struct has_trivial_destructor_after_move
1011    <boost::interprocess_container::containers_detail::rbtree<K, V, KOV, C, A> >
1012 {
1013    static const bool value = has_trivial_destructor<A>::value && has_trivial_destructor<C>::value;
1014 };
1015
1016 }  //namespace interprocess {
1017
1018 } //namespace boost  {
1019
1020 #include <boost/interprocess/containers/container/detail/config_end.hpp>
1021
1022 #endif //BOOST_CONTAINERS_TREE_HPP