ropeimpl.h

linux下编程用 编译软件

  template <class _CharT, class _Alloc>
    typename rope<_CharT, _Alloc>::_RopeLeaf*
    rope<_CharT, _Alloc>::
    _S_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, size_t __len)
    {
      size_t __old_len = __r->_M_size;
      _CharT* __new_data = (_CharT*)
	_Data_allocate(_S_rounded_up_size(__old_len + __len));
      _RopeLeaf* __result;

      uninitialized_copy_n(__r->_M_data, __old_len, __new_data);
      uninitialized_copy_n(__iter, __len, __new_data + __old_len);
      _S_cond_store_eos(__new_data[__old_len + __len]);
      try
	{
	  __result = _S_new_RopeLeaf(__new_data, __old_len + __len,
				     __r->get_allocator());
	}
      catch(...)
	{
	  _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len,
				      __r->get_allocator());
	  __throw_exception_again;
	}
      return __result;
    }

#ifndef __GC
  // As above, but it's OK to clobber original if refcount is 1
  template <class _CharT, class _Alloc>
    typename rope<_CharT,_Alloc>::_RopeLeaf*
    rope<_CharT, _Alloc>::
    _S_destr_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter,
				   size_t __len)
    {
      if (__r->_M_ref_count > 1)
	return _S_leaf_concat_char_iter(__r, __iter, __len);
      size_t __old_len = __r->_M_size;
      if (_S_allocated_capacity(__old_len) >= __old_len + __len)
	{
	  // The space has been partially initialized for the standard
	  // character types.  But that doesn't matter for those types.
	  uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len);
	  if (_S_is_basic_char_type((_CharT*)0))
	    _S_cond_store_eos(__r->_M_data[__old_len + __len]);
	  else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string)
	    {
	      __r->_M_free_c_string();
	      __r->_M_c_string = 0;
	    }
	  __r->_M_size = __old_len + __len;
	  __r->_M_ref_count = 2;
	  return __r;
	}
      else
	{
	  _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len);
	  return __result;
	}
    }
#endif

  // Assumes left and right are not 0.
  // Does not increment (nor decrement on exception) child reference counts.
  // Result has ref count 1.
  template <class _CharT, class _Alloc>
    typename rope<_CharT, _Alloc>::_RopeRep*
    rope<_CharT, _Alloc>::
    _S_tree_concat(_RopeRep* __left, _RopeRep* __right)
    {
      _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right,
							      __left->
							      get_allocator());
      size_t __depth = __result->_M_depth;
      
      if (__depth > 20
	  && (__result->_M_size < 1000
	      || __depth > size_t(_Rope_constants::_S_max_rope_depth)))
	{
	  _RopeRep* __balanced;

	  try
	    {
	      __balanced = _S_balance(__result);
	      __result->_M_unref_nonnil();
	    }
	  catch(...)
	    {
	      _C_deallocate(__result,1);
	      __throw_exception_again;
	    }
	  // In case of exception, we need to deallocate
	  // otherwise dangling result node.  But caller
	  // still owns its children.  Thus unref is
	  // inappropriate.
	  return __balanced;
	}
      else
	return __result;
    }

  template <class _CharT, class _Alloc>
    typename rope<_CharT, _Alloc>::_RopeRep*
    rope<_CharT, _Alloc>::
    _S_concat_char_iter(_RopeRep* __r, const _CharT*__s, size_t __slen)
    {
      _RopeRep* __result;
      if (0 == __slen)
	{
	  _S_ref(__r);
	  return __r;
	}
      if (0 == __r)
	return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
						__r->get_allocator());
      if (_Rope_constants::_S_leaf == __r->_M_tag
	  && __r->_M_size + __slen <= size_t(_S_copy_max))
	{
	  __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
	  return __result;
	}
      if (_Rope_constants::_S_concat == __r->_M_tag
	  && _Rope_constants::_S_leaf == ((_RopeConcatenation*)
					  __r)->_M_right->_M_tag)
	{
	  _RopeLeaf* __right =
	    (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
	  if (__right->_M_size + __slen <= size_t(_S_copy_max))
	    {
	      _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left;
	      _RopeRep* __nright =
		_S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen);
	      __left->_M_ref_nonnil();
	      try
		{ __result = _S_tree_concat(__left, __nright); }
	      catch(...)
		{
		  _S_unref(__left);
		  _S_unref(__nright);
		  __throw_exception_again;
		}
	      return __result;
	    }
	}
      _RopeRep* __nright =
	__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
      try
	{
	  __r->_M_ref_nonnil();
	  __result = _S_tree_concat(__r, __nright);
	}
      catch(...)
	{
	  _S_unref(__r);
	  _S_unref(__nright);
	  __throw_exception_again;
	}
      return __result;
    }

#ifndef __GC
  template <class _CharT, class _Alloc>
    typename rope<_CharT,_Alloc>::_RopeRep*
    rope<_CharT,_Alloc>::
    _S_destr_concat_char_iter(_RopeRep* __r, const _CharT* __s, size_t __slen)
    {
      _RopeRep* __result;
      if (0 == __r)
	return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen,
						__r->get_allocator());
      size_t __count = __r->_M_ref_count;
      size_t __orig_size = __r->_M_size;
      if (__count > 1)
	return _S_concat_char_iter(__r, __s, __slen);
      if (0 == __slen)
	{
	  __r->_M_ref_count = 2;      // One more than before
	  return __r;
	}
      if (__orig_size + __slen <= size_t(_S_copy_max)
	  && _Rope_constants::_S_leaf == __r->_M_tag)
	{
	  __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, 
						    __slen);
	  return __result;
	}
      if (_Rope_constants::_S_concat == __r->_M_tag)
	{
	  _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)
					     __r)->_M_right);
	  if (_Rope_constants::_S_leaf == __right->_M_tag
	      && __right->_M_size + __slen <= size_t(_S_copy_max))
	    {
	      _RopeRep* __new_right =
		_S_destr_leaf_concat_char_iter(__right, __s, __slen);
	      if (__right == __new_right)
		__new_right->_M_ref_count = 1;
	      else
		__right->_M_unref_nonnil();
	      __r->_M_ref_count = 2;    // One more than before.
	      ((_RopeConcatenation*)__r)->_M_right = __new_right;
	      __r->_M_size = __orig_size + __slen;
	      if (0 != __r->_M_c_string)
		{
		  __r->_M_free_c_string();
		  __r->_M_c_string = 0;
		}
	      return __r;
	    }
	}
      _RopeRep* __right =
	__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator());
      __r->_M_ref_nonnil();
      try
	{ __result = _S_tree_concat(__r, __right); }
      catch(...)
	{
	  _S_unref(__r);
	  _S_unref(__right);
	  __throw_exception_again;
	}
      return __result;
    }
#endif /* !__GC */
  
  template <class _CharT, class _Alloc>
    typename rope<_CharT, _Alloc>::_RopeRep*
    rope<_CharT, _Alloc>::
    _S_concat(_RopeRep* __left, _RopeRep* __right)
    {
      if (0 == __left)
	{
	  _S_ref(__right);
	  return __right;
	}
      if (0 == __right)
	{
	  __left->_M_ref_nonnil();
	  return __left;
	}
      if (_Rope_constants::_S_leaf == __right->_M_tag)
	{
	  if (_Rope_constants::_S_leaf == __left->_M_tag)
	    {
	      if (__right->_M_size + __left->_M_size <= size_t(_S_copy_max))
		return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
						((_RopeLeaf*)__right)->_M_data,
						__right->_M_size);
	    }
	  else if (_Rope_constants::_S_concat == __left->_M_tag
		   && _Rope_constants::_S_leaf == ((_RopeConcatenation*)
						   __left)->_M_right->_M_tag)
	    {
	      _RopeLeaf* __leftright =
		(_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right);
	      if (__leftright->_M_size
		  + __right->_M_size <= size_t(_S_copy_max))
		{
		  _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left;
		  _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright,
							      ((_RopeLeaf*)
							       __right)->
							      _M_data,
							      __right->_M_size);
		  __leftleft->_M_ref_nonnil();
		  try
		    { return(_S_tree_concat(__leftleft, __rest)); }
		  catch(...)
		    {
		      _S_unref(__leftleft);
		      _S_unref(__rest);
		      __throw_exception_again;
		    }
		}
	    }
	}
      __left->_M_ref_nonnil();
      __right->_M_ref_nonnil();
      try
	{ return(_S_tree_concat(__left, __right)); }
      catch(...)
	{
	  _S_unref(__left);
	  _S_unref(__right);
	  __throw_exception_again;
	}
    }

  template <class _CharT, class _Alloc>
    typename rope<_CharT, _Alloc>::_RopeRep*
    rope<_CharT, _Alloc>::
    _S_substring(_RopeRep* __base, size_t __start, size_t __endp1)
    {
      if (0 == __base)
	return 0;
      size_t __len = __base->_M_size;
      size_t __adj_endp1;
      const size_t __lazy_threshold = 128;
      
      if (__endp1 >= __len)
	{
	  if (0 == __start)
	    {
	      __base->_M_ref_nonnil();
	      return __base;
	    }
	  else
	    __adj_endp1 = __len;
	  
	}
      else
	__adj_endp1 = __endp1;

      switch(__base->_M_tag)
	{
	case _Rope_constants::_S_concat:
	    {
	      _RopeConcatenation* __c = (_RopeConcatenation*)__base;
	      _RopeRep* __left = __c->_M_left;
	      _RopeRep* __right = __c->_M_right;
	      size_t __left_len = __left->_M_size;
	      _RopeRep* __result;
	      
	      if (__adj_endp1 <= __left_len)
		return _S_substring(__left, __start, __endp1);
	      else if (__start >= __left_len)
		return _S_substring(__right, __start - __left_len,
				    __adj_endp1 - __left_len);
	      _Self_destruct_ptr __left_result(_S_substring(__left,
							    __start,
							    __left_len));
	      _Self_destruct_ptr __right_result(_S_substring(__right, 0,
							     __endp1 
							     - __left_len));
	      __result = _S_concat(__left_result, __right_result);
	      return __result;
	    }
	case _Rope_constants::_S_leaf:
	  {
	    _RopeLeaf* __l = (_RopeLeaf*)__base;
	    _RopeLeaf* __result;
	    size_t __result_len;
	    if (__start >= __adj_endp1)
	      return 0;
	    __result_len = __adj_endp1 - __start;
	    if (__result_len > __lazy_threshold)
	      goto lazy;
#ifdef __GC
	    const _CharT* __section = __l->_M_data + __start;
	    __result = _S_new_RopeLeaf(__section, __result_len,
				       __base->get_allocator());
	    __result->_M_c_string = 0;  // Not eos terminated.
#else
	    // We should sometimes create substring node instead.
	    __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start,
							__result_len,
							__base->
							get_allocator());
#endif
	    return __result;
	  }
	case _Rope_constants::_S_substringfn:
	  // Avoid introducing multiple layers of substring nodes.
	  {
	    _RopeSubstring* __old = (_RopeSubstring*)__base;
	    size_t __result_len;
	    if (__start >= __adj_endp1)
	      return 0;
	    __result_len = __adj_endp1 - __start;
	    if (__result_len > __lazy_threshold)
	      {
		_RopeSubstring* __result =
		  _S_new_RopeSubstring(__old->_M_base,
				       __start + __old->_M_start,
				       __adj_endp1 - __start,
				       __base->get_allocator());
		return __result;
		
	      } // *** else fall through: ***
	  }
	case _Rope_constants::_S_function:
	  {
	    _RopeFunction* __f = (_RopeFunction*)__base;
	    _CharT* __section;
	    size_t __result_len;
	    if (__start >= __adj_endp1)
	      return 0;
	    __result_len = __adj_endp1 - __start;
	    
	    if (__result_len > __lazy_threshold)
	      goto lazy;
	    __section = (_CharT*)
	      _Data_allocate(_S_rounded_up_size(__result_len));
	    try
	      {	(*(__f->_M_fn))(__start, __result_len, __section); }
	    catch(...)
	      {
		_RopeRep::__STL_FREE_STRING(__section, __result_len,
					    __base->get_allocator());
		__throw_exception_again;
	      }
	    _S_cond_store_eos(__section[__result_len]);
	    return _S_new_RopeLeaf(__section, __result_len,
				   __base->get_allocator());
	  }
	}
    lazy:
      {
	// Create substring node.
	return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start,
				    __base->get_allocator());
      }
    }

  template<class _CharT>
    class _Rope_flatten_char_consumer
    : public _Rope_char_consumer<_CharT>
    {
    private:
      _CharT* _M_buf_ptr;
    public:
      
      _Rope_flatten_char_consumer(_CharT* __buffer)
      { _M_buf_ptr = __buffer; };

      ~_Rope_flatten_char_consumer() {}