Imported Upstream version 1.65.0upstream/1.65.0

Change-Id: Icf8400b375482cb11bcf77440a6934ba360d6ba4
Signed-off-by: DongHun Kwak <dh0128.kwak@samsung.com>

1 files changed, 97 insertions, 48 deletions

diff --git a/boost/container/detail/tree.hpp b/boost/container/detail/tree.hpp
index 853d0ad843..99baf3a257 100644
--- a/boost/container/detail/tree.hpp
+++ b/boost/container/detail/tree.hpp
@@ -493,7 +493,7 @@ class tree
    typedef boost::container::reverse_iterator
       <const_iterator>                                const_reverse_iterator;
    typedef node_handle
-      < Node, value_type, allocator_type, void>       node_type;
+      < NodeAlloc, void>                              node_type;
    typedef insert_return_type_base
       <iterator, node_type>                           insert_return_type;
 
@@ -509,7 +509,11 @@ class tree
       : AllocHolder()
    {}
 
-   BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a = allocator_type())
+   BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp)
+      : AllocHolder(ValComp(comp))
+   {}
+
+   BOOST_CONTAINER_FORCEINLINE explicit tree(const key_compare& comp, const allocator_type& a)
       : AllocHolder(ValComp(comp), a)
    {}
 
@@ -518,85 +522,110 @@ class tree
    {}
 
    template <class InputIterator>
-   tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp,
-          const allocator_type& a
-      #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
-      , typename container_detail::enable_if_or
-         < void
-         , container_detail::is_same<alloc_version, version_1>
-         , container_detail::is_input_iterator<InputIterator>
-         >::type * = 0
-      #endif
-         )
+   tree(bool unique_insertion, InputIterator first, InputIterator last)
+      : AllocHolder(value_compare(key_compare()))
+   {
+      this->tree_construct(unique_insertion, first, last);
+      //AllocHolder clears in case of exception
+   }
+
+   template <class InputIterator>
+   tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp)
+      : AllocHolder(value_compare(comp))
+   {
+      this->tree_construct(unique_insertion, first, last);
+      //AllocHolder clears in case of exception
+   }
+
+   template <class InputIterator>
+   tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp, const allocator_type& a)
       : AllocHolder(value_compare(comp), a)
    {
+      this->tree_construct(unique_insertion, first, last);
+      //AllocHolder clears in case of exception
+   }
+
+   //construct with ordered range
+   template <class InputIterator>
+   tree( ordered_range_t, InputIterator first, InputIterator last)
+      : AllocHolder(value_compare(key_compare()))
+   {
+      this->tree_construct(ordered_range_t(), first, last);
+   }
+
+   template <class InputIterator>
+   tree( ordered_range_t, InputIterator first, InputIterator last, const key_compare& comp)
+      : AllocHolder(value_compare(comp))
+   {
+      this->tree_construct(ordered_range_t(), first, last);
+   }
+
+   template <class InputIterator>
+   tree( ordered_range_t, InputIterator first, InputIterator last
+         , const key_compare& comp, const allocator_type& a)
+      : AllocHolder(value_compare(comp), a)
+   {
+      this->tree_construct(ordered_range_t(), first, last);
+   }
+
+   private:
+
+   template <class InputIterator>
+   void tree_construct(bool unique_insertion, InputIterator first, InputIterator last)
+   {
       //Use cend() as hint to achieve linear time for
       //ordered ranges as required by the standard
       //for the constructor
-      const const_iterator end_it(this->cend());
       if(unique_insertion){
+         const const_iterator end_it(this->cend());
          for ( ; first != last; ++first){
             this->insert_unique_convertible(end_it, *first);
          }
       }
       else{
-         for ( ; first != last; ++first){
-            this->insert_equal_convertible(end_it, *first);
-         }
+         this->tree_construct_non_unique(first, last);
       }
    }
 
    template <class InputIterator>
-   tree(bool unique_insertion, InputIterator first, InputIterator last, const key_compare& comp,
-          const allocator_type& a
+   void tree_construct_non_unique(InputIterator first, InputIterator last
       #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
-      , typename container_detail::disable_if_or
+      , typename container_detail::enable_if_or
          < void
          , container_detail::is_same<alloc_version, version_1>
          , container_detail::is_input_iterator<InputIterator>
          >::type * = 0
       #endif
          )
-      : AllocHolder(value_compare(comp), a)
    {
-      if(unique_insertion){
-         //Use cend() as hint to achieve linear time for
-         //ordered ranges as required by the standard
-         //for the constructor
-         const const_iterator end_it(this->cend());
-         for ( ; first != last; ++first){
-            this->insert_unique_convertible(end_it, *first);
-         }
-      }
-      else{
-         //Optimized allocation and construction
-         this->allocate_many_and_construct
-            ( first, boost::container::iterator_distance(first, last)
-            , insert_equal_end_hint_functor<Node, Icont>(this->icont()));
+      //Use cend() as hint to achieve linear time for
+      //ordered ranges as required by the standard
+      //for the constructor
+      const const_iterator end_it(this->cend());
+      for ( ; first != last; ++first){
+         this->insert_equal_convertible(end_it, *first);
       }
    }
 
    template <class InputIterator>
-   tree( ordered_range_t, InputIterator first, InputIterator last
-         , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type()
-         #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
-      , typename container_detail::enable_if_or
+   void tree_construct_non_unique(InputIterator first, InputIterator last
+      #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+      , typename container_detail::disable_if_or
          < void
          , container_detail::is_same<alloc_version, version_1>
          , container_detail::is_input_iterator<InputIterator>
          >::type * = 0
-         #endif
+      #endif
          )
-      : AllocHolder(value_compare(comp), a)
    {
-      for ( ; first != last; ++first){
-         this->push_back_impl(*first);
-      }
+      //Optimized allocation and construction
+      this->allocate_many_and_construct
+         ( first, boost::container::iterator_distance(first, last)
+         , insert_equal_end_hint_functor<Node, Icont>(this->icont()));
    }
 
    template <class InputIterator>
-   tree( ordered_range_t, InputIterator first, InputIterator last
-         , const key_compare& comp = key_compare(), const allocator_type& a = allocator_type()
+   void tree_construct( ordered_range_t, InputIterator first, InputIterator last
          #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
       , typename container_detail::disable_if_or
          < void
@@ -605,16 +634,34 @@ class tree
          >::type * = 0
          #endif
          )
-      : AllocHolder(value_compare(comp), a)
    {
       //Optimized allocation and construction
       this->allocate_many_and_construct
          ( first, boost::container::iterator_distance(first, last)
          , container_detail::push_back_functor<Node, Icont>(this->icont()));
+      //AllocHolder clears in case of exception
+   }
+
+   template <class InputIterator>
+   void tree_construct( ordered_range_t, InputIterator first, InputIterator last
+         #if !defined(BOOST_CONTAINER_DOXYGEN_INVOKED)
+      , typename container_detail::enable_if_or
+         < void
+         , container_detail::is_same<alloc_version, version_1>
+         , container_detail::is_input_iterator<InputIterator>
+         >::type * = 0
+         #endif
+         )
+   {
+      for ( ; first != last; ++first){
+         this->push_back_impl(*first);
+      }
    }
 
+   public:
+
    BOOST_CONTAINER_FORCEINLINE tree(const tree& x)
-      :  AllocHolder(x.value_comp(), x)
+      :  AllocHolder(x, x.value_comp())
    {
       this->icont().clone_from
          (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
@@ -630,6 +677,7 @@ class tree
    {
       this->icont().clone_from
          (x.icont(), typename AllocHolder::cloner(*this), Destroyer(this->node_alloc()));
+      //AllocHolder clears in case of exception
    }
 
    tree(BOOST_RV_REF(tree) x, const allocator_type &a)
@@ -642,6 +690,7 @@ class tree
          this->icont().clone_from
             (boost::move(x.icont()), typename AllocHolder::move_cloner(*this), Destroyer(this->node_alloc()));
       }
+      //AllocHolder clears in case of exception
    }
 
    BOOST_CONTAINER_FORCEINLINE ~tree()
@@ -1142,7 +1191,7 @@ class tree
             this->insert_unique_check(hint, KeyOfValue()(nh.value()), data);
          if(ret.second){
             irt.inserted = true;
-            irt.position = iterator(this->icont().insert_unique_commit(*nh.get_node_pointer(), data));
+            irt.position = iterator(this->icont().insert_unique_commit(*nh.get(), data));
             nh.release();
          }
          else{