ropeimpl.h

linux下编程用 编译软件

	      _Self_destruct_ptr __old(__too_tiny);
#endif
	      __too_tiny = _S_concat_and_set_balanced(__forest[__i],
						      __too_tiny);
	      __forest[__i]->_M_unref_nonnil();
	      __forest[__i] = 0;
	    }
	}
      {
#ifndef __GC
	_Self_destruct_ptr __old(__too_tiny);
#endif
	__insertee = _S_concat_and_set_balanced(__too_tiny, __r);
      }
      // Too_tiny dead, and no longer included in refcount.
      // Insertee is live and included.
      for (;; ++__i)
	{
	  if (0 != __forest[__i])
	    {
#ifndef __GC
	      _Self_destruct_ptr __old(__insertee);
#endif
	      __insertee = _S_concat_and_set_balanced(__forest[__i],
						      __insertee);
	      __forest[__i]->_M_unref_nonnil();
	      __forest[__i] = 0;
	    }
	  if (__i == int(_Rope_constants::_S_max_rope_depth)
	      || __insertee->_M_size < _S_min_len[__i+1])
	    {
	      __forest[__i] = __insertee;
	      // refcount is OK since __insertee is now dead.
	      return;
	    }
	}
    }

  template <class _CharT, class _Alloc>
    _CharT
    rope<_CharT, _Alloc>::
    _S_fetch(_RopeRep* __r, size_type __i)
    {
      __GC_CONST _CharT* __cstr = __r->_M_c_string;
      
      if (0 != __cstr)
	return __cstr[__i];
      for(;;)
	{
	  switch(__r->_M_tag)
	    {
	    case _Rope_constants::_S_concat:
	      {
		_RopeConcatenation* __c = (_RopeConcatenation*)__r;
		_RopeRep* __left = __c->_M_left;
		size_t __left_len = __left->_M_size;
		
		if (__i >= __left_len)
		  {
		    __i -= __left_len;
		    __r = __c->_M_right;
		  } 
		else
		  __r = __left;
	      }
	      break;
	    case _Rope_constants::_S_leaf:
	      {
		_RopeLeaf* __l = (_RopeLeaf*)__r;
		return __l->_M_data[__i];
	      }
	    case _Rope_constants::_S_function:
	    case _Rope_constants::_S_substringfn:
	      {
		_RopeFunction* __f = (_RopeFunction*)__r;
		_CharT __result;
		
		(*(__f->_M_fn))(__i, 1, &__result);
		return __result;
	      }
	    }
	}
    }
  
#ifndef __GC
  // Return a uniquely referenced character slot for the given
  // position, or 0 if that's not possible.
  template <class _CharT, class _Alloc>
    _CharT*
    rope<_CharT, _Alloc>::
    _S_fetch_ptr(_RopeRep* __r, size_type __i)
    {
      _RopeRep* __clrstack[_Rope_constants::_S_max_rope_depth];
      size_t __csptr = 0;
      
      for(;;)
	{
	  if (__r->_M_ref_count > 1)
	    return 0;
	  switch(__r->_M_tag)
	    {
	    case _Rope_constants::_S_concat:
	      {
		_RopeConcatenation* __c = (_RopeConcatenation*)__r;
		_RopeRep* __left = __c->_M_left;
		size_t __left_len = __left->_M_size;
		
		if (__c->_M_c_string != 0)
		  __clrstack[__csptr++] = __c;
		if (__i >= __left_len)
		  {
		    __i -= __left_len;
		    __r = __c->_M_right;
		  } 
		else
		  __r = __left;
	      }
	      break;
	    case _Rope_constants::_S_leaf:
	      {
		_RopeLeaf* __l = (_RopeLeaf*)__r;
		if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0)
		  __clrstack[__csptr++] = __l;
		while (__csptr > 0)
		  {
		    -- __csptr;
		    _RopeRep* __d = __clrstack[__csptr];
		    __d->_M_free_c_string();
		    __d->_M_c_string = 0;
		  }
		return __l->_M_data + __i;
	      }
	    case _Rope_constants::_S_function:
	    case _Rope_constants::_S_substringfn:
	      return 0;
	    }
	}
    }
#endif /* __GC */

  // The following could be implemented trivially using
  // lexicographical_compare_3way.
  // We do a little more work to avoid dealing with rope iterators for
  // flat strings.
  template <class _CharT, class _Alloc>
    int
    rope<_CharT, _Alloc>::
    _S_compare (const _RopeRep* __left, const _RopeRep* __right)
    {
      size_t __left_len;
      size_t __right_len;
      
      if (0 == __right)
	return 0 != __left;
      if (0 == __left)
	return -1;
      __left_len = __left->_M_size;
      __right_len = __right->_M_size;
      if (_Rope_constants::_S_leaf == __left->_M_tag)
	{
	  _RopeLeaf* __l = (_RopeLeaf*) __left;
	  if (_Rope_constants::_S_leaf == __right->_M_tag)
	    {
	      _RopeLeaf* __r = (_RopeLeaf*) __right;
	      return lexicographical_compare_3way(__l->_M_data,
						  __l->_M_data + __left_len,
						  __r->_M_data, __r->_M_data
						  + __right_len);
	    }
	  else
	    {
	      const_iterator __rstart(__right, 0);
	      const_iterator __rend(__right, __right_len);
	      return lexicographical_compare_3way(__l->_M_data, __l->_M_data
						  + __left_len,
						  __rstart, __rend);
	    }
	}
      else
	{
	  const_iterator __lstart(__left, 0);
	  const_iterator __lend(__left, __left_len);
	  if (_Rope_constants::_S_leaf == __right->_M_tag)
	    {
	      _RopeLeaf* __r = (_RopeLeaf*) __right;
	      return lexicographical_compare_3way(__lstart, __lend,
						  __r->_M_data, __r->_M_data
						  + __right_len);
	    }
	  else
	    {
	      const_iterator __rstart(__right, 0);
	      const_iterator __rend(__right, __right_len);
	      return lexicographical_compare_3way(__lstart, __lend,
						  __rstart, __rend);
	    }
	}
    }

  // Assignment to reference proxies.
  template <class _CharT, class _Alloc>
    _Rope_char_ref_proxy<_CharT, _Alloc>&
    _Rope_char_ref_proxy<_CharT, _Alloc>::
    operator=(_CharT __c)
    {
      _RopeRep* __old = _M_root->_M_tree_ptr;
#ifndef __GC
      // First check for the case in which everything is uniquely
      // referenced.  In that case we can do this destructively.
      _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos);
      if (0 != __ptr)
	{
	  *__ptr = __c;
	  return *this;
	}
#endif
      _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos));
      _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1,
							__old->_M_size));
      _Self_destruct_ptr __result_left(_My_rope::
				       _S_destr_concat_char_iter(__left,
								 &__c, 1));

      _RopeRep* __result = _My_rope::_S_concat(__result_left, __right);
#ifndef __GC
      _RopeRep::_S_unref(__old);
#endif
      _M_root->_M_tree_ptr = __result;
      return *this;
    }

  template <class _CharT, class _Alloc>
    inline _Rope_char_ref_proxy<_CharT, _Alloc>::
    operator _CharT() const
    {
      if (_M_current_valid)
	return _M_current;
      else
	return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos);
    }

  template <class _CharT, class _Alloc>
    _Rope_char_ptr_proxy<_CharT, _Alloc>
    _Rope_char_ref_proxy<_CharT, _Alloc>::
    operator&() const
    { return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); }

  template <class _CharT, class _Alloc>
    rope<_CharT, _Alloc>::
    rope(size_t __n, _CharT __c, const allocator_type& __a)
    : _Base(__a)
    {
      rope<_CharT,_Alloc> __result;
      const size_t __exponentiate_threshold = 32;
      size_t __exponent;
      size_t __rest;
      _CharT* __rest_buffer;
      _RopeRep* __remainder;
      rope<_CharT, _Alloc> __remainder_rope;

      if (0 == __n)
	return;

      __exponent = __n / __exponentiate_threshold;
      __rest = __n % __exponentiate_threshold;
      if (0 == __rest)
	__remainder = 0;
      else
	{
	  __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest));
	  __uninitialized_fill_n_a(__rest_buffer, __rest, __c,
				   get_allocator());
	  _S_cond_store_eos(__rest_buffer[__rest]);
	  try
	    { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a); }
	  catch(...)
	    {
	      _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a);
	      __throw_exception_again;
	    }
	}
      __remainder_rope._M_tree_ptr = __remainder;
      if (__exponent != 0)
	{
	  _CharT* __base_buffer =
	    this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold));
	  _RopeLeaf* __base_leaf;
	  rope __base_rope;
	  __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c,
				   get_allocator());
	  _S_cond_store_eos(__base_buffer[__exponentiate_threshold]);
	  try
	    {
	      __base_leaf = _S_new_RopeLeaf(__base_buffer,
					    __exponentiate_threshold, __a);
	    }
	  catch(...)
	    {
	      _RopeRep::__STL_FREE_STRING(__base_buffer,
					  __exponentiate_threshold, __a);
	      __throw_exception_again;
	    }
	  __base_rope._M_tree_ptr = __base_leaf;
	  if (1 == __exponent)
	    __result = __base_rope;
	  else
	    __result = power(__base_rope, __exponent,
			     _Rope_Concat_fn<_CharT, _Alloc>());
	    
	  if (0 != __remainder)
	    __result += __remainder_rope;
	}
      else
	__result = __remainder_rope;
	  
      this->_M_tree_ptr = __result._M_tree_ptr;
      this->_M_tree_ptr->_M_ref_nonnil();
    }
      
  template<class _CharT, class _Alloc>
    _CharT
    rope<_CharT, _Alloc>::_S_empty_c_str[1];
      
  template<class _CharT, class _Alloc>
    const _CharT*
    rope<_CharT, _Alloc>::
    c_str() const
    {
      if (0 == this->_M_tree_ptr)
	{
	  _S_empty_c_str[0] = _S_eos((_CharT*)0);  // Possibly redundant,
	                                           // but probably fast.
	  return _S_empty_c_str;
	}
      __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock);
      __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string;
      if (0 == __result)
	{
	  size_t __s = size();
	  __result = this->_Data_allocate(__s + 1);
	  _S_flatten(this->_M_tree_ptr, __result);
	  __result[__s] = _S_eos((_CharT*)0);
	  this->_M_tree_ptr->_M_c_string = __result;
	}
      __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock);
      return(__result);
    }
  
  template<class _CharT, class _Alloc>
    const _CharT* rope<_CharT, _Alloc>::
    replace_with_c_str()
    {
      if (0 == this->_M_tree_ptr)
	{
	  _S_empty_c_str[0] = _S_eos((_CharT*)0);
	  return _S_empty_c_str;
	}
      __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string;
      if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag
	  && 0 != __old_c_string)
	return(__old_c_string);
      size_t __s = size();
      _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s));
      _S_flatten(this->_M_tree_ptr, __result);
      __result[__s] = _S_eos((_CharT*)0);
      this->_M_tree_ptr->_M_unref_nonnil();
      this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s,
					  this->get_allocator());
      return(__result);
    }

  // Algorithm specializations.  More should be added.
  
  template<class _Rope_iterator>  // was templated on CharT and Alloc
    void		          // VC++ workaround
    _Rope_rotate(_Rope_iterator __first,
		 _Rope_iterator __middle,
		 _Rope_iterator __last)
    {
      typedef typename _Rope_iterator::value_type _CharT;
      typedef typename _Rope_iterator::_allocator_type _Alloc;
      
      rope<_CharT, _Alloc>& __r(__first.container());
      rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index());
      rope<_CharT, _Alloc> __suffix =
	__r.substr(__last.index(), __r.size() - __last.index());
      rope<_CharT, _Alloc> __part1 =
	__r.substr(__middle.index(), __last.index() - __middle.index());
      rope<_CharT, _Alloc> __part2 =
	__r.substr(__first.index(), __middle.index() - __first.index());
      __r = __prefix;
      __r += __part1;
      __r += __part2;
      __r += __suffix;
    }

#if !defined(__GNUC__)
  // Appears to confuse g++
  inline void
  rotate(_Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __first,
	 _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __middle,
	 _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __last)
  { _Rope_rotate(__first, __middle, __last); }
#endif

# if 0
  // Probably not useful for several reasons:
  // - for SGIs 7.1 compiler and probably some others,
  //   this forces lots of rope<wchar_t, ...> instantiations, creating a
  //   code bloat and compile time problem.  (Fixed in 7.2.)
  // - wchar_t is 4 bytes wide on most UNIX platforms, making it
  //   unattractive for unicode strings.  Unsigned short may be a better
  //   character type.
  inline void
  rotate(_Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first,
	 _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle,
	 _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last)
  { _Rope_rotate(__first, __middle, __last); }
# endif

} // namespace __gnu_cxx

// Local Variables:
// mode:C++
// End: