Re: [Patch] Second half of 29385 + improving operator=() in tree containers

[Ion Gaztañaga <igaztanaga at gmail dot com>]

Paolo Carlini wrote:
> Hi again,
>
> the second half, basically Ion's idea (can you have a look? Thanks in 
> advance!), tested x86-linux. I'll wait until tomorrow...
>
> Paolo.
>
> ///////////////////

Seems correct. Nice _M_lower_bound / _M_upper_bound refactoring!

If you want another idea (much more complicated than the equal_range 
trick, I'm afraid) I found the way to improve operator=() in tree 
containers. The idea is to reuse old nodes instead of destroying the old 
tree and creating a new one:

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    operator=(const _Rb_tree<_Key, _Val,
              _KeyOfValue, _Compare, _Alloc>& __x)
    {
      if (this != &__x)
	{
	  // Note that _Key may be a constant type.
	  clear();
	  _M_impl._M_key_compare() = __x._M_impl._M_key_compare();
	  if (__x._M_root() != 0)
	    {
	      _M_root() = _M_copy(__x._M_begin(), _M_end());
	      _M_leftmost() = _S_minimum(_M_root());
	      _M_rightmost() = _S_maximum(_M_root());
	      _M_impl._M_node_count = __x._M_impl._M_node_count;
	    }
	}
      return *this;
    }

The trick is to add another version of _M_clone recycling nodes 
(pseudo_code):

  template<typename _Key, typename _Val, typename _KoV,
           typename _Compare, typename _Alloc>
    typename _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::_Link_type
    _Rb_tree<_Key, _Val, _KoV, _Compare, _Alloc>::
    _M_reycling_copy(_Const_Link_type __x, _Link_type __p)
    {
      // Structural copy.  __x and __p must be non-null.
      _Link_type __top = _M_clone_node(__x);
      __top->_M_parent = __p;

      try
	{
	  if (__x->_M_right)
	    __top->_M_right = _M_recycling_copy(_S_right(__x), __top);
	  __p = __top;
	  __x = _S_left(__x);

	  while (__x != 0)
	    {
	      _Link_type __y = _M_recycling_clone(__x);
	      __p->_M_left = __y;
	      __y->_M_parent = __p;
	      if (__x->_M_right)
		__y->_M_right = _M_copy(_S_right(__x), __y);
	      __p = __y;
	      __x = _S_left(__x);
	    }
	}
      catch(...)
	{
	  _M_erase(__top);
           while((p = unlink_leftmost_without_rebalance())){
              _M_destroy(p);
           }
	  __throw_exception_again;
	}
      return __top;
    }

Now _M_recycling_clone would be something like this (pseudo-code):

if(!empty()){
   NodePtr p;
   try{
      //First recycle a node (this can't throw)
      NodePtr p = unlink_leftmost_without_rebalance();

      //Destroy node (this can't throw)
      allocator._destroy(p);

      //Now call the copy constructor (this can throw)
      rbtree_alloc::construct(p, other);

      //Maybe we can just use assignment
      //instead of destruction + construction?

      return p;
   }
   catch(...){
      //If there is an exception destroy the whole source
      allocator.deallocate(p, 1);
      while((p = unlink_leftmost_without_rebalance())){
         _M_destroy(p);
      }
      throw;
   }
}
else{
  return _M_clone_node(other);
}


and "unlink_leftmost_without_rebalance()" would be a function taking the 
leftmost node and fixing the begin() pointer. This function is an step 
in the destruction of the tree (something like a 1 step _M_erase()). 
This code is taking from my own tree container, but I think it's easy to 
follow:

-> it takes the leftmost node
-> unlinks it from the tree
-> finds the new leftmost
-> fixes the header->left pointer to point to it.:

   node_ptr unlink_leftmost_without_rebalance(node_ptr header)
   {
      node_ptr leftmost = NodeTraits::get_left(header);
      if (leftmost == header)
         return 0;
      node_ptr leftmost_parent(NodeTraits::get_parent(leftmost));
      node_ptr leftmost_right (NodeTraits::get_right(leftmost));
      bool is_root = leftmost_parent == header;

      if (leftmost_right){
         NodeTraits::set_parent(leftmost_right, leftmost_parent);
         NodeTraits::set_left(header, minimum(leftmost_right));

         if (is_root)
            NodeTraits::set_parent(header, leftmost_right);
         else
            NodeTraits::set_left
                (NodeTraits::get_parent(header), leftmost_right);
      }
      else if (is_root){
         NodeTraits::set_parent(header, 0);
         NodeTraits::set_left(header,  header);
         NodeTraits::set_right(header, header);
      }
      else{
         NodeTraits::set_left(leftmost_parent, 0);
         NodeTraits::set_left(header, leftmost_parent);
      }
      return leftmost;
   }

The operator= should look like (pseudo-code):

  template<typename _Key, typename _Val, typename _KeyOfValue,
           typename _Compare, typename _Alloc>
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>&
    _Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::
    operator=(const _Rb_tree<_Key, _Val,
              _KeyOfValue, _Compare, _Alloc>& __x)
    {
      if (this != &__x)
	{
	  // Note that _Key may be a constant type.
	  clear();
	  _M_impl._M_key_compare() = __x._M_impl._M_key_compare();
	  if (__x._M_root() != 0)
	    {
              _M_impl._M_node_count = 0;
	      NodePtr new_root =
                 _M_recycling_copy(__x._M_begin(), _M_end());

              //If there are remaining nodes, destroy them (nothrow)
              NodePtr p;
              while((p =
                 unlink_leftmost_without_rebalance())){
                 allocator.destroy_node(p);
              }

              _M_root() = new_root;
	      _M_leftmost() = _S_minimum(_M_root());
	      _M_rightmost() = _S_maximum(_M_root());
	      _M_impl._M_node_count = __x._M_impl._M_node_count;
	    }
	}
      return *this;
    }

////////////////////////////////////////////////////////////////////

This new operator() has no strong guarantee, and the old tree is 
completely destroyed if an exception is thrown. So if we want to achieve 
strong guarantee in operator=(), this recycling trick should be used 
only with non-throwing copy-constructor value_types (or non throwing 
assignment if that's used to clone). I've suggested 
"unlink_leftmost_without_rebalance" as node picking function but we can 
use any other that guarantees a fast partial tree destruction.

To sum up:

-> Reuse _M_clone for _M_reclycing_clone but change _M_clone_node with a 
recycling cloner.

-> The cloner picks an old node and constructs the new value. If the old 
tree has no more nodes to recycle, _M_clone_node is used.

-> To pick a node from the old tree, a "erase without rebalancing" 
function is used.

-> operator=() should destroy remaining nodes that the recycling cloner 
have not used.

A bit complicated, but this should really help if we copy trees. It just 
a shame that we are wasting previously allocated nodes. For example, in 
std::list, nodes are reused in operator=.

Regards,

Ion