/* * Copyright (c) 1997 * Silicon Graphics Computer Systems, Inc. * * Permission to use, copy, modify, distribute and sell this software * and its documentation for any purpose is hereby granted without fee, * provided that the above copyright notice appear in all copies and * that both that copyright notice and this permission notice appear * in supporting documentation.  Silicon Graphics makes no * representations about the suitability of this software for any * purpose.  It is provided "as is" without express or implied warranty. *//* NOTE: This is an internal header file, included by other STL headers. *   You should not attempt to use it directly. */# include <stdio.h>     #ifdef __STL_USE_NEW_IOSTREAMS # include <iostream>#else /* __STL_USE_NEW_IOSTREAMS */# include <iostream.h>#endif /* __STL_USE_NEW_IOSTREAMS */#ifdef __STL_USE_EXCEPTIONS# include <stdexcept>#endif__STL_BEGIN_NAMESPACE#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)#pragma set woff 1174#endif// 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;	    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;		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);    if (__pos >= __x._M_root->_M_size) {	__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;	__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;				__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;    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);    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;	__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;    __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_root) {        // _Rope was modified.  Get things fixed up.        _RopeRep::_S_unref(_M_root);        _M_root = _M_root_rope->_M_tree_ptr;        _RopeRep::_S_ref(_M_root);        _M_buf_ptr = 0;    }}template <class _CharT, class _Alloc>inline _Rope_const_iterator<_CharT, _Alloc>::_Rope_const_iterator(  const _Rope_iterator<_CharT,_Alloc>& __x): _Rope_iterator_base<_CharT,_Alloc>(__x) { }template <class _CharT, class _Alloc>inline _Rope_iterator<_CharT,_Alloc>::_Rope_iterator(  rope<_CharT,_Alloc>& __r, size_t __pos): _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos),   _M_root_rope(&__r){    _RopeRep::_S_ref(_M_root);}template <class _CharT, class _Alloc>inline size_t rope<_CharT,_Alloc>::_S_char_ptr_len(const _CharT* __s){    const _CharT* __p = __s;    while (!_S_is0(*__p)) { ++__p; }    return (__p - __s);}#ifndef __GCtemplate <class _CharT, class _Alloc>inline void _Rope_RopeRep<_CharT,_Alloc>::_M_free_c_string(){    _CharT* __cstr = _M_c_string;    if (0 != __cstr) {	size_t __size = _M_size + 1;	destroy(__cstr, __cstr + __size);	_Data_deallocate(__cstr, __size);    }}template <class _CharT, class _Alloc>#ifdef __STL_USE_STD_ALLOCATORS  inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s,							   size_t __n,						           allocator_type __a)#else  inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s,							   size_t __n)#endif{    if (!_S_is_basic_char_type((_CharT*)0)) {	destroy(__s, __s + __n);    }//  This has to be a static member, so this gets a bit messy#   ifdef __STL_USE_STD_ALLOCATORS        __a.deallocate(	    __s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n));#   else	_Data_deallocate(	    __s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n));#   endif}//  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();	        _L_deallocate(__l, 1);	        break;	    }	case _S_concat:	    {	        _Rope_RopeConcatenation<_CharT,_Alloc>* __c		    = (_Rope_RopeConcatenation<_CharT,_Alloc>*)this;	        __c->_Rope_RopeConcatenation<_CharT,_Alloc>::		       ~_Rope_RopeConcatenation();	        _C_deallocate(__c, 1);	        break;	    }	case _S_function:	    {	        _Rope_RopeFunction<_CharT,_Alloc>* __f		    = (_Rope_RopeFunction<_CharT,_Alloc>*)this;	        __f->_Rope_RopeFunction<_CharT,_Alloc>::~_Rope_RopeFunction();	        _F_deallocate(__f, 1);	        break;	    }	case _S_substringfn:	    {	        _Rope_RopeSubstring<_CharT,_Alloc>* __ss =			(_Rope_RopeSubstring<_CharT,_Alloc>*)this;		__ss->_Rope_RopeSubstring<_CharT,_Alloc>::		        ~_Rope_RopeSubstring();		_S_deallocate(__ss, 1);		break;	    }    }}#elsetemplate <class _CharT, class _Alloc>#ifdef __STL_USE_STD_ALLOCATORS  inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string		(const _CharT*, size_t, allocator_type)#else  inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string		(const _CharT*, size_t)#endif{}#endif// Concatenate a C string onto a leaf rope by copying the rope data.// Used for short ropes.template <class _CharT, class _Alloc>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;