stl_rope.c

粗糙集应用软件

/*
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Copyright (c) 1999 
 * Boris Fomitchev
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted 
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 */

/* NOTE: This is an internal header file, included by other STL headers.
 *   You should not attempt to use it directly.
 */

// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
// if necessary.  Assumes path_end[leaf_index] and leaf_pos are correct.
// Results in a valid buf_ptr if the iterator can be legitimately
// dereferenced.
# ifndef __SGI_STL_ROPEIMPL_H
# define __SGI_STL_ROPEIMPL_H

# ifndef __STLPORT_CSTDIO
#  include <cstdio>
# endif

#ifndef __STLPORT_IOSTREAM
# include <iostream>
#endif

#if defined (__STL_USE_EXCEPTIONS)
# include <stdexcept>
#endif

// #include <string>

__STL_BEGIN_NAMESPACE

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

# if defined ( __STL_NESTED_TYPE_PARAM_BUG )
# define __size_type__ size_t
# define __allocator__ _Alloc
# else
# define __allocator__ allocator_type
# define __size_type__ __STL_TYPENAME_ON_RETURN_TYPE rope<_CharT, _Alloc>::size_type
# endif

# if(__STL_STATIC_TEMPLATE_DATA >0 )
template <class _CharT, class _Alloc>
const __size_type__ rope<_CharT, _Alloc>::npos =
			(__size_type__)(-1);
# else
const __size_type__ rope<char, __STL_DEFAULT_ALLOCATOR(char) >::npos __STL_WEAK = (__size_type__)(-1);
#  if defined (__STL_HAS_WCHAR_T)
const __size_type__ rope<wchar_t, __STL_DEFAULT_ALLOCATOR(wchar_t) >::npos __STL_WEAK = (__size_type__)(-1);
#  endif
# endif

#undef __size_type__

template<class _CharT, class _Alloc>
void 
_Rope_RopeRep<_CharT, _Alloc>::_M_free_c_string()
{
  _CharT* __cstr = _M_c_string;
  if (0 != __cstr) {
    size_t _p_size = _M_size._M_data + 1;
    destroy(__cstr, __cstr + _p_size);
    _M_size.deallocate(__cstr, _p_size);
  }
}


// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf
// if necessary.  Assumes _M_path_end[leaf_index] and leaf_pos are correct.
// Results in a valid buf_ptr if the iterator can be legitimately
// dereferenced.
template <class _CharT, class _Alloc>
void _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf( 
  _Rope_iterator_base<_CharT,_Alloc>& __x)
{
    const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index];
    size_t __leaf_pos = __x._M_leaf_pos;
    size_t __pos = __x._M_current_pos;

    switch(__leaf->_M_tag) {
	case _RopeRep::_S_leaf:
	    __x._M_buf_start = 
	      ((_Rope_RopeLeaf<_CharT,_Alloc>*)__leaf)->_M_data;
	    __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos);
	    __x._M_buf_end = __x._M_buf_start + __leaf->_M_size._M_data;
	    break;
	case _RopeRep::_S_function:
	case _RopeRep::_S_substringfn:
	    {
		size_t __len = _S_iterator_buf_len;
		size_t __buf_start_pos = __leaf_pos;
		size_t __leaf_end = __leaf_pos + __leaf->_M_size._M_data;
		char_producer<_CharT>* __fn =
			((_Rope_RopeFunction<_CharT,_Alloc>*)__leaf)->_M_fn;

		if (__buf_start_pos + __len <= __pos) {
		    __buf_start_pos = __pos - __len/4;
		    if (__buf_start_pos + __len > __leaf_end) {
			__buf_start_pos = __leaf_end - __len;
		    }
		}
		if (__buf_start_pos + __len > __leaf_end) {
		    __len = __leaf_end - __buf_start_pos;
		}
		(*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf);
		__x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos);
		__x._M_buf_start = __x._M_tmp_buf;
		__x._M_buf_end = __x._M_tmp_buf + __len;
	    }
	    break;
	default:
	    __stl_assert(0);
    }
}

// Set path and buffer inside a rope iterator.  We assume that 
// pos and root are already set.
template <class _CharT, class _Alloc>
void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache
(_Rope_iterator_base<_CharT,_Alloc>& __x)
{
    const _RopeRep* __path[_RopeRep::_S_max_rope_depth+1];
    const _RopeRep* __curr_rope;
    int __curr_depth = -1;  /* index into path    */
    size_t __curr_start_pos = 0;
    size_t __pos = __x._M_current_pos;
    unsigned char __dirns = 0; // Bit vector marking right turns in the path

    __stl_assert(__pos <= __x._M_root->_M_size._M_data);
    if (__pos >= __x._M_root->_M_size._M_data) {
	__x._M_buf_ptr = 0;
	return;
    }
    __curr_rope = __x._M_root;
    if (0 != __curr_rope->_M_c_string) {
	/* Treat the root as a leaf. */
	__x._M_buf_start = __curr_rope->_M_c_string;
	__x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size._M_data;
	__x._M_buf_ptr = __curr_rope->_M_c_string + __pos;
	__x._M_path_end[0] = __curr_rope;
	__x._M_leaf_index = 0;
	__x._M_leaf_pos = 0;
	return;
    }
    for(;;) {
	++__curr_depth;
	__stl_assert(__curr_depth <= _RopeRep::_S_max_rope_depth);
	__path[__curr_depth] = __curr_rope;
	switch(__curr_rope->_M_tag) {
	  case _RopeRep::_S_leaf:
	  case _RopeRep::_S_function:
	  case _RopeRep::_S_substringfn:
	    __x._M_leaf_pos = __curr_start_pos;
	    goto done;
	  case _RopeRep::_S_concat:
	    {
		_Rope_RopeConcatenation<_CharT,_Alloc>* __c =
			(_Rope_RopeConcatenation<_CharT,_Alloc>*)__curr_rope;
		_RopeRep* __left = __c->_M_left;
		size_t __left_len = __left->_M_size._M_data;
		
		__dirns <<= 1;
		if (__pos >= __curr_start_pos + __left_len) {
		    __dirns |= 1;
		    __curr_rope = __c->_M_right;
		    __curr_start_pos += __left_len;
		} else {
		    __curr_rope = __left;
		}
	    }
	    break;
	}
    }
  done:
    // Copy last section of path into _M_path_end.
      {
	int __i = -1;
	int __j = __curr_depth + 1 - _S_path_cache_len;

	if (__j < 0) __j = 0;
	while (__j <= __curr_depth) {
	    __x._M_path_end[++__i] = __path[__j++];
	}
	__x._M_leaf_index = __i;
      }
      __x._M_path_directions = __dirns;
      _S_setbuf(__x);
}

// Specialized version of the above.  Assumes that
// the path cache is valid for the previous position.
template <class _CharT, class _Alloc>
void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr
(_Rope_iterator_base<_CharT,_Alloc>& __x)
{
    int __current_index = __x._M_leaf_index;
    const _RopeRep* __current_node = __x._M_path_end[__current_index];
    size_t __len = __current_node->_M_size._M_data;
    size_t __node_start_pos = __x._M_leaf_pos;
    unsigned char __dirns = __x._M_path_directions;
    _Rope_RopeConcatenation<_CharT,_Alloc>* __c;

    __stl_assert(__x._M_current_pos <= __x._M_root->_M_size._M_data);
    if (__x._M_current_pos - __node_start_pos < __len) {
	/* More stuff in this leaf, we just didn't cache it. */
	_S_setbuf(__x);
	return;
    }
    __stl_assert(__node_start_pos + __len == __x._M_current_pos);
    //  node_start_pos is starting position of last_node.
    while (--__current_index >= 0) {
	if (!(__dirns & 1) /* Path turned left */) 
	  break;
	__current_node = __x._M_path_end[__current_index];
	__c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
	// Otherwise we were in the right child.  Thus we should pop
	// the concatenation node.
	__node_start_pos -= __c->_M_left->_M_size._M_data;
	__dirns >>= 1;
    }
    if (__current_index < 0) {
	// We underflowed the cache. Punt.
	_S_setcache(__x);
	return;
    }
    __current_node = __x._M_path_end[__current_index];
    __c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node;
    // current_node is a concatenation node.  We are positioned on the first
    // character in its right child.
    // node_start_pos is starting position of current_node.
    __node_start_pos += __c->_M_left->_M_size._M_data;
    __current_node = __c->_M_right;
    __x._M_path_end[++__current_index] = __current_node;
    __dirns |= 1;
    while (_RopeRep::_S_concat == __current_node->_M_tag) {
	++__current_index;
	if (_S_path_cache_len == __current_index) {
	    int __i;
	    for (__i = 0; __i < _S_path_cache_len-1; __i++) {
		__x._M_path_end[__i] = __x._M_path_end[__i+1];
	    }
	    --__current_index;
	}
	__current_node =
	    ((_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node)->_M_left;
	__x._M_path_end[__current_index] = __current_node;
	__dirns <<= 1;
	// node_start_pos is unchanged.
    }
    __x._M_leaf_index = __current_index;
    __x._M_leaf_pos = __node_start_pos;
    __x._M_path_directions = __dirns;
    _S_setbuf(__x);
}

template <class _CharT, class _Alloc>
void _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) {
    _M_current_pos += __n;
    if (0 != _M_buf_ptr) {
        size_t __chars_left = _M_buf_end - _M_buf_ptr;
        if (__chars_left > __n) {
            _M_buf_ptr += __n;
        } else if (__chars_left == __n) {
            _M_buf_ptr += __n;
            _S_setcache_for_incr(*this);
        } else {
            _M_buf_ptr = 0;
        }
    }
}

template <class _CharT, class _Alloc>
void _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) {
    if (0 != _M_buf_ptr) {
        size_t __chars_left = _M_buf_ptr - _M_buf_start;
        if (__chars_left >= __n) {
            _M_buf_ptr -= __n;
        } else {
            _M_buf_ptr = 0;
        }
    }
    _M_current_pos -= __n;
}

template <class _CharT, class _Alloc>
void _Rope_iterator<_CharT,_Alloc>::_M_check() {
    if (_M_root_rope->_M_tree_ptr._M_data != _M_root) {
        // _Rope was modified.  Get things fixed up.
        _RopeRep::_S_unref(_M_root);
        _M_root = _M_root_rope->_M_tree_ptr._M_data;
        _RopeRep::_S_ref(_M_root);
        _M_buf_ptr = 0;
    }
}

# ifndef _GC
//  There are several reasons for not doing this with virtual destructors
//  and a class specific delete operator:
//  - A class specific delete operator can't easily get access to
//    allocator instances if we need them.
//  - Any virtual function would need a 4 or byte vtable pointer;
//    this only requires a one byte tag per object.
template <class _CharT, class _Alloc>
void _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree()
{
    switch(_M_tag) {
	case _S_leaf:
	    {
	        _Rope_RopeLeaf<_CharT,_Alloc>* __l
			= (_Rope_RopeLeaf<_CharT,_Alloc>*)this;
	        __l->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf();
	        __stl_alloc_create((const allocator_type&)_M_size, 
				   (_Rope_RopeLeaf<_CharT,_Alloc>*)0).deallocate(__l, 1);
	        break;
	    }
	case _S_concat:
	    {
	        _Rope_RopeConcatenation<_CharT,_Alloc>* __c
		    = (_Rope_RopeConcatenation<_CharT,_Alloc>*)this;
	        __c->_Rope_RopeConcatenation<_CharT,_Alloc>::
		       ~_Rope_RopeConcatenation();
	        __stl_alloc_create((const allocator_type&)_M_size, 
				(_Rope_RopeConcatenation<_CharT,_Alloc>*)0).deallocate(__c, 1);
	        break;
	    }
	case _S_function:
	    {
	        _Rope_RopeFunction<_CharT,_Alloc>* __f
		    = (_Rope_RopeFunction<_CharT,_Alloc>*)this;
	        __f->_Rope_RopeFunction<_CharT,_Alloc>::~_Rope_RopeFunction();
	        __stl_alloc_create((const allocator_type&)_M_size, 
				   (_Rope_RopeFunction<_CharT,_Alloc>*)0).deallocate(__f, 1);
	        break;
	    }
	case _S_substringfn:
	    {
	        _Rope_RopeSubstring<_CharT,_Alloc>* __ss =
			(_Rope_RopeSubstring<_CharT,_Alloc>*)this;
		__ss->_Rope_RopeSubstring<_CharT,_Alloc>::
		        ~_Rope_RopeSubstring();
	        __stl_alloc_create((const allocator_type&)_M_size, 
				(_Rope_RopeSubstring<_CharT,_Alloc>*)0).deallocate(__ss, 1);
		break;
	    }
    }
}
#endif

# if defined ( __STL_NESTED_TYPE_PARAM_BUG )
#   define __RopeLeaf__ _Rope_RopeLeaf<_CharT,_Alloc>
#   define __RopeRep__ _Rope_RopeRep<_CharT,_Alloc>
#   define size_type size_t
# else
#   define __RopeLeaf__ __STL_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeLeaf
#   define __RopeRep__ __STL_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeRep
# endif

// Concatenate a C string onto a leaf rope by copying the rope data.
// Used for short ropes.
template <class _CharT, class _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._M_data;
    _CharT* __new_data = __r->_M_size.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);