ropeimpl.h

linux下的gcc编译器

    }
}
#else

template <class _CharT, class _Alloc>
  inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string
		(const _CharT*, size_t, allocator_type)
{}

#endif


// Concatenate a C string onto a leaf rope by copying the rope data.
// Used for short ropes.
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 > _RopeRep::_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 (_RopeRep::_S_leaf == __r->_M_tag && 
          __r->_M_size + __slen <= _S_copy_max) {
	__result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
	return __result;
    }
    if (_RopeRep::_S_concat == __r->_M_tag
	&& _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) {
	_RopeLeaf* __right = 
	  (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right);
	if (__right->_M_size + __slen <= _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 <= _S_copy_max && 
          _RopeRep::_S_leaf == __r->_M_tag) {
	__result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen);
	return __result;
    }
    if (_RopeRep::_S_concat == __r->_M_tag) {
	_RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)__r)->_M_right);
	if (_RopeRep::_S_leaf == __right->_M_tag
	    && __right->_M_size + __slen <= _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 (_RopeRep::_S_leaf == __right->_M_tag) {
	if (_RopeRep::_S_leaf == __left->_M_tag) {
	  if (__right->_M_size + __left->_M_size <= _S_copy_max) {
	    return _S_leaf_concat_char_iter((_RopeLeaf*)__left,
					 ((_RopeLeaf*)__right)->_M_data,
					 __right->_M_size);
	  }
	} else if (_RopeRep::_S_concat == __left->_M_tag
		   && _RopeRep::_S_leaf ==
		      ((_RopeConcatenation*)__left)->_M_right->_M_tag) {
	  _RopeLeaf* __leftright =
		    (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); 
	  if (__leftright->_M_size + __right->_M_size <= _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 _RopeRep::_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 _RopeRep::_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 _RopeRep::_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 _RopeRep::_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> {