stl_rope.c

粗糙集应用软件

template <class _CharT, class _Alloc>
void
rope<_CharT,_Alloc>::_S_add_to_forest(__RopeRep__* __r, __RopeRep__** __forest)
{
    if (__r -> _M_is_balanced) {
	_S_add_leaf_to_forest(__r, __forest);
	return;
    }
    __stl_assert(__r->_M_tag == _RopeRep::_S_concat);
    {
	_RopeConcatenation* __c = (_RopeConcatenation*)__r;

	_S_add_to_forest(__c->_M_left, __forest);
	_S_add_to_forest(__c->_M_right, __forest);
    }
}


template <class _CharT, class _Alloc>
void
rope<_CharT,_Alloc>::_S_add_leaf_to_forest(__RopeRep__* __r, __RopeRep__** __forest)
{
    _RopeRep* __insertee;   		// included in refcount
    _RopeRep* __too_tiny = 0;    	// included in refcount
    int __i;  				// forest[0..__i-1] is empty
    size_t __s = __r->_M_size._M_data;

    for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) {
	if (0 != __forest[__i]) {
#	    ifndef __GC
	      _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.
    __stl_assert(_S_is_almost_balanced(__insertee));
    __stl_assert(__insertee->_M_depth <= __r->_M_depth + 1);
    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;
	    __stl_assert(_S_is_almost_balanced(__insertee));
	}
	__stl_assert(_S_min_len[__i] <= __insertee->_M_size._M_data);
	__stl_assert(__forest[__i] == 0);
	if (__i == _RopeRep::_S_max_rope_depth || 
	      __insertee->_M_size._M_data < _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;

    __stl_assert(__i < __r->_M_size._M_data);
    if (0 != __cstr) return __cstr[__i]; 
    for(;;) {
      switch(__r->_M_tag) {
	case _RopeRep::_S_concat:
	    {
		_RopeConcatenation* __c = (_RopeConcatenation*)__r;
		_RopeRep* __left = __c->_M_left;
		size_t __left_len = __left->_M_size._M_data;

		if (__i >= __left_len) {
		    __i -= __left_len;
		    __r = __c->_M_right;
		} else {
		    __r = __left;
		}
	    }
	    break;
	case _RopeRep::_S_leaf:
	    {
		_RopeLeaf* __l = (_RopeLeaf*)__r;
		return __l->_M_data[__i];
	    }
	case _RopeRep::_S_function:
	case _RopeRep::_S_substringfn:
	    {
		_RopeFunction* __f = (_RopeFunction*)__r;
		_CharT __result;

		(*(__f->_M_fn))(__i, 1, &__result);
		return __result;
	    }
      }
    }
#if defined(__STL_NEED_UNREACHABLE_RETURN)
    return 0;
#endif
}

# 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[_RopeRep::_S_max_rope_depth];
    size_t __csptr = 0;

    for(;;) {
      if (__r->_M_ref_count > 1) return 0;
      switch(__r->_M_tag) {
	case _RopeRep::_S_concat:
	    {
		_RopeConcatenation* __c = (_RopeConcatenation*)__r;
		_RopeRep* __left = __c->_M_left;
		size_t __left_len = __left->_M_size._M_data;

		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 _RopeRep::_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 _RopeRep::_S_function:
	case _RopeRep::_S_substringfn:
	    return 0;
      }
    }
#if defined(__STL_NEED_UNREACHABLE_RETURN)
    return 0;
#endif

}
# 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._M_data;
    __right_len = __right->_M_size._M_data;
    if (_RopeRep::_S_leaf == __left->_M_tag) {
	_RopeLeaf* __l = (_RopeLeaf*) __left;
	if (_RopeRep::_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 (_RopeRep::_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._M_data;
#   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._M_data));
    _Self_destruct_ptr __result_left(
      _My_rope::_S_destr_concat_char_iter(__left, &__c, 1));

#   ifndef __GC
      __stl_assert(__left == __result_left || 1 == __result_left->_M_ref_count);
#   endif
    _RopeRep* __result =
      _My_rope::_S_concat_rep(__result_left, __right);
#   ifndef __GC
      __stl_assert(1 <= __result->_M_ref_count);
      _RopeRep::_S_unref(__old);
#   endif
    _M_root->_M_tree_ptr._M_data = __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_data, _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);
}

# if ( __STL_STATIC_TEMPLATE_DATA > 0 )
template<class _CharT, class _Alloc>
_CharT rope<_CharT,_Alloc>::_S_empty_c_str[1] = { _CharT() };
# else
__DECLARE_INSTANCE(char, crope::_S_empty_c_str[1], ={0});
# ifdef __STL_HAS_WCHAR_T
__DECLARE_INSTANCE(wchar_t, wrope::_S_empty_c_str[1], ={0});
# endif /* __STL_HAS_WCHAR_T */
# endif /* __STL_STATIC_TEMPLATE_DATA */
// # endif

template<class _CharT, class _Alloc>
const _CharT* rope<_CharT,_Alloc>::c_str() const {
    if (0 == _M_tree_ptr._M_data) {
        _S_empty_c_str[0] = _S_eos((_CharT*)0);  // Possibly redundant,
					     // but probably fast.
        return _S_empty_c_str;
    }
    __GC_CONST _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string;
    if (0 != __old_c_string) return(__old_c_string);
    size_t __s = size();
    _CharT* __result = __stl_alloc_create((const allocator_type&)_M_tree_ptr, (_CharT*)0).allocate(__s + 1);
    _S_flatten(_M_tree_ptr._M_data, __result);
    __result[__s] = _S_eos((_CharT*)0);
#   ifdef __GC
	_M_tree_ptr._M_data->_M_c_string = __result;
#   else
      if ((__old_c_string = (__GC_CONST _CharT*)
             _Atomic_swap((unsigned long *)(&(_M_tree_ptr._M_data->_M_c_string)),
			  (unsigned long)__result)) != 0) {
	// It must have been added in the interim.  Hence it had to have been
	// separately allocated.  Deallocate the old copy, since we just
	// replaced it.
	destroy(__old_c_string, __old_c_string + __s + 1);
	__stl_alloc_create((const allocator_type&)_M_tree_ptr, (_CharT*)0).deallocate(__old_c_string, __s + 1);
      }
#   endif
    return(__result);
}

template<class _CharT, class _Alloc>
const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() {
    if (0 == _M_tree_ptr._M_data) {
        _S_empty_c_str[0] = _S_eos((_CharT*)0);
        return _S_empty_c_str;
    }
    __GC_CONST _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string;
    if (_RopeRep::_S_leaf == _M_tree_ptr._M_data->_M_tag && 0 != __old_c_string) {
	return(__old_c_string);
    }
    size_t __s = size();
    _CharT* __result = _M_tree_ptr.allocate(_S_rounded_up_size(__s));
    _S_flatten(_M_tree_ptr._M_data, __result);
    __result[__s] = _S_eos((_CharT*)0);
    _M_tree_ptr._M_data->_M_unref_nonnil();
    _M_tree_ptr._M_data = _S_new_RopeLeaf(__result, __s, get_allocator());
    return(__result);
}

// Algorithm specializations.  More should be added.

#ifndef __STL_MSVC
// I couldn't get this to work with VC++
template<class _CharT,class _Alloc>
void
_Rope_rotate(_Rope_iterator<_CharT,_Alloc> __first,
              _Rope_iterator<_CharT,_Alloc> __middle,
              _Rope_iterator<_CharT,_Alloc> __last)
{
    __stl_assert(__first.container() == __middle.container()
                 && __middle.container() == __last.container());
    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 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
#endif /* __STL_MSVC */

#   undef __RopeLeaf__ 
#   undef __RopeRep__ 
#   undef size_type

__STL_END_NAMESPACE
#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
#pragma reset woff 1174
#endif

# endif /* ROPEIMPL_H */

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