19720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 29720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1996,1997 39720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Silicon Graphics Computer Systems, Inc. 49720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 59720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Copyright (c) 1999 69720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Boris Fomitchev 79720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 89720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * This material is provided "as is", with absolutely no warranty expressed 99720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * or implied. Any use is at your own risk. 109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to use or copy this software for any purpose is hereby granted 129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * without fee, provided the above notices are retained on all copies. 139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * Permission to modify the code and to distribute modified code is granted, 149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * provided the above notices are retained, and a notice that the code was 159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * modified is included with the above copyright notice. 169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * 179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* NOTE: This is an internal header file, included by other STL headers. 209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block * You should not attempt to use it directly. 219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block */ 229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf 249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// if necessary. Assumes path_end[leaf_index] and leaf_pos are correct. 259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Results in a valid buf_ptr if the iterator can be legitimately 269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// dereferenced. 279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_ROPEIMPL_H 289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#define _STLP_ROPEIMPL_H 299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_ROPE_H 319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_rope.h> 329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_INTERNAL_CSTDIO 359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# include <stl/_cstdio.h> 369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_USE_NO_IOSTREAMS) 39e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# ifndef _STLP_INTERNAL_OSTREAM_H 40e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# include <stl/_ostream.h> 41e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# endif 42e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott 43e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# ifndef _STLP_INTERNAL_ISTREAM 44e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# include <stl/_istream.h> 459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif 469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#include <stl/_range_errors.h> 499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_BEGIN_NAMESPACE 519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 52e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if defined ( _STLP_NESTED_TYPE_PARAM_BUG ) 53e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# define __allocator__ _Alloc 54e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#else 55e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott# define __allocator__ allocator_type 56e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#endif 579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> 599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_Rope_iterator<_CharT, _Alloc>::_Rope_iterator(rope<_CharT,_Alloc>* __r, size_t __pos) 609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _Rope_iterator_base<_CharT,_Alloc>(__r->_M_tree_ptr._M_data, __pos), 619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_root_rope(__r) { _RopeRep::_S_ref(this->_M_root); } 629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> 649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_Rope_iterator<_CharT, _Alloc>::_Rope_iterator(rope<_CharT,_Alloc>& __r, size_t __pos): 659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr._M_data, __pos), 669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_root_rope(&__r) { 679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (__DMC__) 689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep::_S_ref(this->_M_root); if (!(__r.empty()))_S_setcache(*this); 699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#else 709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_iterator_base<_CharT, _Alloc>* __x = this; 719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep::_S_ref(this->_M_root); if (!(__r.empty()))_S_setcache(*__x); 729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> 769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Rope_RopeRep<_CharT, _Alloc>::_M_free_c_string() { 779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __cstr = _M_c_string; 789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != __cstr) { 799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t _p_size = _M_size._M_data + 1; 809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::_Destroy_Range(__cstr, __cstr + _p_size); 819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_size.deallocate(__cstr, _p_size); 829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf 869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct. 879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Results in a valid buf_ptr if the iterator can be legitimately 889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// dereferenced. 899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf( 919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_iterator_base<_CharT,_Alloc>& __x) { 929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _RopeRep* __leaf = __x._M_path_end._M_data[__x._M_leaf_index]; 939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __leaf_pos = __x._M_leaf_pos; 949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __pos = __x._M_current_pos; 959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch(__leaf->_M_tag) { 979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_leaf: 989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf; 999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_buf_start = __STATIC_CAST(const _RopeLeaf*, __leaf)->_M_data; 1009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos); 1019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_buf_end = __x._M_buf_start + __leaf->_M_size._M_data; 1029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 1039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_function: 1049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_substringfn: 1059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 1069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __len = _S_iterator_buf_len; 1079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __buf_start_pos = __leaf_pos; 1089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __leaf_end = __leaf_pos + __leaf->_M_size._M_data; 1099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction; 1109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block char_producer<_CharT>* __fn = __STATIC_CAST(const _RopeFunction*, __leaf)->_M_fn; 1119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__buf_start_pos + __len <= __pos) { 1139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __buf_start_pos = __pos - __len/4; 1149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__buf_start_pos + __len > __leaf_end) { 1159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __buf_start_pos = __leaf_end - __len; 1169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__buf_start_pos + __len > __leaf_end) { 1199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __len = __leaf_end - __buf_start_pos; 1209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf._M_data); 1229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_buf_ptr = __x._M_tmp_buf._M_data + (__pos - __buf_start_pos); 1239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_buf_start = __x._M_tmp_buf._M_data; 1249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_buf_end = __x._M_tmp_buf._M_data + __len; 1259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 1279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block default: 1289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(0) 1299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ; 1309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 1329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Set path and buffer inside a rope iterator. We assume that 1349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// pos and root are already set. 1359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 1369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Rope_iterator_base<_CharT,_Alloc>::_S_setcache( 1379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_iterator_base<_CharT,_Alloc>& __x) { 1389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _RopeRep* __path[_RopeRep::_S_max_rope_depth+1]; 1399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _RopeRep* __curr_rope; 1409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block int __curr_depth = -1; /* index into path */ 1419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __curr_start_pos = 0; 1429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __pos = __x._M_current_pos; 1439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block unsigned char __dirns = 0; // Bit vector marking right turns in the path 1449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__pos <= __x._M_root->_M_size._M_data) 1469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pos >= __x._M_root->_M_size._M_data) { 1479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_buf_ptr = 0; 1489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 1499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __curr_rope = __x._M_root; 1519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != __curr_rope->_M_c_string) { 1529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block /* Treat the root as a leaf. */ 1539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_buf_start = __curr_rope->_M_c_string; 1549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size._M_data; 1559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_buf_ptr = __curr_rope->_M_c_string + __pos; 1569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_path_end._M_data[0] = __curr_rope; 1579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_leaf_index = 0; 1589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_leaf_pos = 0; 1599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 1609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for(;;) { 1629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__curr_depth; 1639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__curr_depth <= _RopeRep::_S_max_rope_depth) 1649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __path[__curr_depth] = __curr_rope; 1659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch(__curr_rope->_M_tag) { 1669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_leaf: 1679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_function: 1689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_substringfn: 1699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_leaf_pos = __curr_start_pos; 1709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block goto done; 1719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_concat: 1729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 1739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _RopeConcat* __c = __STATIC_CAST(const _RopeConcat*, __curr_rope); 1749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __left = __c->_M_left; 1759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __left_len = __left->_M_size._M_data; 1769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __dirns <<= 1; 1789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__pos >= __curr_start_pos + __left_len) { 1799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __dirns |= 1; 1809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __curr_rope = __c->_M_right; 1819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __curr_start_pos += __left_len; 1829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 1839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __curr_rope = __left; 1849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 1879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockdone: 1909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Copy last section of path into _M_path_end. 1919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 1929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block int __i = -1; 1939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block int __j = __curr_depth + 1 - _S_path_cache_len; 1949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__j < 0) __j = 0; 1969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__j <= __curr_depth) { 1979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_path_end._M_data[++__i] = __path[__j++]; 1989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 1999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_leaf_index = __i; 2009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_path_directions = __dirns; 2029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_setbuf(__x); 2039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Specialized version of the above. Assumes that 2069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// the path cache is valid for the previous position. 2079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 2089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr( 2099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_Rope_iterator_base<_CharT,_Alloc>& __x) { 2109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block int __current_index = __x._M_leaf_index; 2119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _RopeRep* __current_node = __x._M_path_end._M_data[__current_index]; 2129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __len = __current_node->_M_size._M_data; 2139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __node_start_pos = __x._M_leaf_pos; 2149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block unsigned char __dirns = __x._M_path_directions; 2159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _RopeConcat* __c; 2169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__x._M_current_pos <= __x._M_root->_M_size._M_data) 2189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__x._M_current_pos - __node_start_pos < __len) { 2199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block /* More stuff in this leaf, we just didn't cache it. */ 2209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_setbuf(__x); 2219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 2229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__node_start_pos + __len == __x._M_current_pos) 2249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // node_start_pos is starting position of last_node. 2259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (--__current_index >= 0) { 2269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!(__dirns & 1) /* Path turned left */) 2279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 2289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __current_node = __x._M_path_end._M_data[__current_index]; 2299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __c = __STATIC_CAST(const _RopeConcat*, __current_node); 2309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Otherwise we were in the right child. Thus we should pop 2319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // the concatenation node. 2329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __node_start_pos -= __c->_M_left->_M_size._M_data; 2339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __dirns >>= 1; 2349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__current_index < 0) { 2369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // We underflowed the cache. Punt. 2379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_setcache(__x); 2389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 2399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __current_node = __x._M_path_end._M_data[__current_index]; 2419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __c = __STATIC_CAST(const _RopeConcat*, __current_node); 2429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // current_node is a concatenation node. We are positioned on the first 2439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // character in its right child. 2449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // node_start_pos is starting position of current_node. 2459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __node_start_pos += __c->_M_left->_M_size._M_data; 2469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __current_node = __c->_M_right; 2479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_path_end._M_data[++__current_index] = __current_node; 2489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __dirns |= 1; 2499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (_RopeRep::_S_concat == __current_node->_M_tag) { 2509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ++__current_index; 2519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_S_path_cache_len == __current_index) { 2529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block int __i; 2539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (__i = 0; __i < _S_path_cache_len-1; ++__i) { 2549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_path_end._M_data[__i] = __x._M_path_end._M_data[__i+1]; 2559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block --__current_index; 2579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __current_node = __STATIC_CAST(const _RopeConcat*, __current_node)->_M_left; 2599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_path_end._M_data[__current_index] = __current_node; 2609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __dirns <<= 1; 2619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // node_start_pos is unchanged. 2629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_leaf_index = __current_index; 2649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_leaf_pos = __node_start_pos; 2659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __x._M_path_directions = __dirns; 2669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_setbuf(__x); 2679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 2709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) { 2719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_current_pos += __n; 2729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != _M_buf_ptr) { 2739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __chars_left = _M_buf_end - _M_buf_ptr; 2749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__chars_left > __n) { 2759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buf_ptr += __n; 2769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else if (__chars_left == __n) { 2779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buf_ptr += __n; 2789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_setcache_for_incr(*this); 2799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 2809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buf_ptr = 0; 2819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 2869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) { 2879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != _M_buf_ptr) { 2889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __chars_left = _M_buf_ptr - _M_buf_start; 2899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__chars_left >= __n) { 2909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buf_ptr -= __n; 2919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 2929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buf_ptr = 0; 2939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 2959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_current_pos -= __n; 2969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 2979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 2989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 2999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Rope_iterator<_CharT,_Alloc>::_M_check() { 3009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_M_root_rope->_M_tree_ptr._M_data != this->_M_root) { 3019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _Rope was modified. Get things fixed up. 3029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep::_S_unref(this->_M_root); 3039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block this->_M_root = _M_root_rope->_M_tree_ptr._M_data; 3049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep::_S_ref(this->_M_root); 3059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block this->_M_buf_ptr = 0; 3069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// There are several reasons for not doing this with virtual destructors 3109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// and a class specific delete operator: 3119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// - A class specific delete operator can't easily get access to 3129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// allocator instances if we need them. 3139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// - Any virtual function would need a 4 or byte vtable pointer; 3149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// this only requires a one byte tag per object. 3159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 3169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree() { 3179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch (_M_tag) { 3189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _S_leaf: 3199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 3209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf; 3219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, this); 3229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::_Destroy(__l); // ->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf(); 3239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size, 3249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf).deallocate(__l, 1); 3259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 3269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _S_concat: 3289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 3299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation; 3309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, this); 3319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::_Destroy(__c); 3329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_size, 3339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation).deallocate(__c, 1); 3349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 3359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _S_function: 3379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 3389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction; 3399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, this); 3409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::_Destroy(__f); 3419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_CREATE_ALLOCATOR(allocator_type, (const allocator_type&)_M_size, 3429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeFunction).deallocate(__f, 1); 3439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 3449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _S_substringfn: 3469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 3479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring; 3489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeSubstring* __rss = __STATIC_CAST(_RopeSubstring*, this); 3499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::_Destroy(__rss); 3509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_CREATE_ALLOCATOR(allocator_type, (const allocator_type&)_M_size, 3519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeSubstring).deallocate(__rss, 1); 3529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 3539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# if defined ( _STLP_NESTED_TYPE_PARAM_BUG ) 3589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __RopeLeaf__ _Rope_RopeLeaf<_CharT,_Alloc> 3599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __RopeRep__ _Rope_RopeRep<_CharT,_Alloc> 3609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define _RopeLeaf _Rope_RopeLeaf<_CharT,_Alloc> 3619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define _RopeRep _Rope_RopeRep<_CharT,_Alloc> 3629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define size_type size_t 3639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# else 3649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __RopeLeaf__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeLeaf 3659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __RopeRep__ _STLP_TYPENAME_ON_RETURN_TYPE rope<_CharT,_Alloc>::_RopeRep 3669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif 3679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 3699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid rope<_CharT, _Alloc>::_M_throw_out_of_range() const { 3709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __stl_throw_out_of_range("rope"); 3719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Concatenate a C string onto a leaf rope by copying the rope data. 3749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Used for short ropes. 3759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 3769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__RopeLeaf__* 3779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_leaf_concat_char_iter ( 3789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __r, const _CharT* __iter, size_t __len) { 3799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __old_len = __r->_M_size._M_data; 3809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __new_data = __r->_M_size.allocate(_S_rounded_up_size(__old_len + __len)); 3819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __result; 3829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __ucopy_n(__r->_M_data, __old_len, __new_data); 3849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __ucopy_n(__iter, __len, __new_data + __old_len); 3859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_construct_null(__new_data + __old_len + __len); 3869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 3879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = _S_new_RopeLeaf(__new_data, __old_len + __len, __r->get_allocator()); 3889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 3899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND(_RopeRep::_S_free_string(__new_data, __old_len + __len, 3909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->get_allocator())) 3919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 3929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 3939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 3949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 3959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Terminate_RopeLeaf(_Rope_RopeLeaf<_CharT,_Alloc> *__r, 3969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __size, const __true_type& /*basic char type*/) { 3979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_construct_null(__r->_M_data + __size); 3989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__r->_M_c_string == __r->_M_data) 3999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 4029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Terminate_RopeLeaf(_Rope_RopeLeaf<_CharT,_Alloc> *__r, 4039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t, const __false_type& /*basic char type*/) { 4049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) { 4059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_free_c_string(); 4069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_c_string = 0; 4079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// As above, but it's OK to clobber original if refcount is 1 4119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 4129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__RopeLeaf__* 4139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter (_RopeLeaf* __r, const _CharT* __iter, size_t __len) { 4149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //_STLP_ASSERT(__r->_M_ref_count >= 1) 4159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if ( /* __r->_M_ref_count > 1 */ __r->_M_incr() > 2 ) { // - ptr 4169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_decr(); // - ptr 4179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_leaf_concat_char_iter(__r, __iter, __len); 4189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_decr(); // - ptr, __r->_M_ref_count == 1 or 0 4209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __old_len = __r->_M_size._M_data; 4219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_S_rounded_up_size(__old_len) == _S_rounded_up_size(__old_len + __len)) { 4229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // The space has been partially initialized for the standard 4239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // character types. But that doesn't matter for those types. 4249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __ucopy_n(__iter, __len, __r->_M_data + __old_len); 4259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Terminate_RopeLeaf(__r, __old_len + __len, _IsBasicCharType()); 4269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_size._M_data = __old_len + __len; 4279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(__r->_M_ref_count == 1) 4289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // __r->_M_ref_count = 2; 4299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_incr(); // i.e. __r->_M_ref_count = 2 4309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __r; 4319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 4329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len); 4339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //_STLP_ASSERT(__result->_M_ref_count == 1) 4349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 4359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Assumes left and right are not 0. 4399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Does not increment (nor decrement on exception) child reference counts. 4409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Result has ref count 1. 4419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 4429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__RopeRep__* 4439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right) { 4449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation* __result = 4459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_new_RopeConcatenation(__left, __right, __left->get_allocator()); 4469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __depth = __result->_M_depth; 4479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__left->get_allocator() == __right->get_allocator()) 4499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__depth > 20 && (__result->_M_size._M_data < 1000 || 4509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __depth > _RopeRep::_S_max_rope_depth)) { 4519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __balanced; 4529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 4549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __balanced = _S_balance(__result); 4559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(__result == __balanced || 4569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // 1 == __result->_M_ref_count && 4579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // 1 == __balanced->_M_ref_count) 4589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result->_M_unref_nonnil(); 4599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND((_STLP_CREATE_ALLOCATOR(allocator_type,(allocator_type&)__left->_M_size, 4619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation).deallocate(__result,1))) 4629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // In case of exception, we need to deallocate 4639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // otherwise dangling result node. But caller 4649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // still owns its children. Thus unref is 4659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // inappropriate. 4669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __balanced; 4679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 4689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 4699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 4719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 4729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 4739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__RopeRep__* 4749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_concat_char_iter (_RopeRep* __r, 4759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _CharT*__s, size_t __slen) { 4769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __result; 4779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __slen) { 4789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_ref(__r); 4799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __r; 4809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __r) 4829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator()); 4839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_leaf == __r->_M_tag && 4849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_size._M_data + __slen <= _S_copy_max) { 4859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); 4869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(1 == __result->_M_ref_count) 4879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 4889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_concat == __r->_M_tag && 4909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) { 4919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __right = (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right); 4929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__right->_M_size._M_data + __slen <= _S_copy_max) { 4939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left; 4949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __nright = _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen); 4959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __left->_M_ref_nonnil(); 4969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 4979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = _S_tree_concat(__left, __nright); 4989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 4999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND(_S_unref(__left); _S_unref(__nright)) 5009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(1 == __result->_M_ref_count) 5019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 5029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __nright = 5059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator()); 5069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 5079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_ref_nonnil(); 5089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = _S_tree_concat(__r, __nright); 5099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND(_S_unref(__r); _S_unref(__nright)) 5119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(1 == __result->_M_ref_count) 5129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 5139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 5169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__RopeRep__* 5179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_destr_concat_char_iter( 5189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __r, const _CharT* __s, size_t __slen) { 5199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __result; 5209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __r) 5219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, 5229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->get_allocator()); 5239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // size_t __count = __r->_M_ref_count; 5249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __orig_size = __r->_M_size._M_data; 5259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(__count >= 1) 5269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if ( /* __count > 1 */ __r->_M_incr() > 2 ) { 5279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_decr(); 5289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_concat_char_iter(__r, __s, __slen); 5299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __slen) { 5319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __r; 5329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_decr(); 5349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__orig_size + __slen <= _S_copy_max && _RopeRep::_S_leaf == __r->_M_tag) { 5359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); 5369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_concat == __r->_M_tag) { 5389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __right = __STATIC_CAST(_RopeLeaf*, __STATIC_CAST(_RopeConcatenation*, __r)->_M_right); 5399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_leaf == __right->_M_tag && 5409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __right->_M_size._M_data + __slen <= _S_copy_max) { 5419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __new_right = _S_destr_leaf_concat_char_iter(__right, __s, __slen); 5429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__right == __new_right) { 5439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(__new_right->_M_ref_count == 2) 5449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // __new_right->_M_ref_count = 1; 5459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __new_right->_M_decr(); 5469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 5479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(__new_right->_M_ref_count >= 1) 5489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __right->_M_unref_nonnil(); 5499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(__r->_M_ref_count == 1) 5519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // __r->_M_ref_count = 2; // One more than before. 5529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_incr(); 5539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __STATIC_CAST(_RopeConcatenation*, __r)->_M_right = __new_right; 5549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // E.Musser : moved below 5559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // __r->_M_size._M_data = __orig_size + __slen; 5569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != __r->_M_c_string) { 5579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_free_c_string(); 5589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_c_string = 0; 5599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_size._M_data = __orig_size + __slen; 5619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __r; 5629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __right = 5659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_RopeLeaf_from_unowned_char_ptr(__s, __slen, __r->get_allocator()); 5669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_ref_nonnil(); 5679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 5689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = _S_tree_concat(__r, __right); 5699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND(_S_unref(__r); _S_unref(__right)) 5719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(1 == __result->_M_ref_count) 5729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 5739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 5749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 5759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 5769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__RopeRep__* 5779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_concat_rep(_RopeRep* __left, _RopeRep* __right) { 5789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __left) { 5799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_ref(__right); 5809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __right; 5819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __right) { 5839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __left->_M_ref_nonnil(); 5849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __left; 5859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_leaf == __right->_M_tag) { 5879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_leaf == __left->_M_tag) { 5889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__right->_M_size._M_data + __left->_M_size._M_data <= _S_copy_max) { 5899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_leaf_concat_char_iter(__STATIC_CAST(_RopeLeaf*, __left), 5909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __STATIC_CAST(_RopeLeaf*, __right)->_M_data, 5919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __right->_M_size._M_data); 5929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 5939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else if (_RopeRep::_S_concat == __left->_M_tag && 5949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep::_S_leaf == __STATIC_CAST(_RopeConcatenation*, __left)->_M_right->_M_tag) { 5959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __leftright = 5969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __STATIC_CAST(_RopeLeaf*, __STATIC_CAST(_RopeConcatenation*, __left)->_M_right); 5979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__leftright->_M_size._M_data + __right->_M_size._M_data <= _S_copy_max) { 5989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __leftleft = __STATIC_CAST(_RopeConcatenation*, __left)->_M_left; 5999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright, 6009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __STATIC_CAST(_RopeLeaf*, __right)->_M_data, 6019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __right->_M_size._M_data); 6029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __leftleft->_M_ref_nonnil(); 6039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 6049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_tree_concat(__leftleft, __rest); 6059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND(_S_unref(__leftleft); _S_unref(__rest)) 6079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __left->_M_ref_nonnil(); 6119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __right->_M_ref_nonnil(); 6129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 6139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_tree_concat(__left, __right); 6149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND(_S_unref(__left); _S_unref(__right)) 6169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_RET_AFTER_THROW(0) 6179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 6189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 6209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__RopeRep__* 6219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_substring(_RopeRep* __base, 6229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __start, size_t __endp1) { 6239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __base) return 0; 6249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __len = __base->_M_size._M_data; 6259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __adj_endp1; 6269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const size_t __lazy_threshold = 128; 6279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__endp1 >= __len) { 6299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __start) { 6309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __base->_M_ref_nonnil(); 6319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __base; 6329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 6339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __adj_endp1 = __len; 6349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 6369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __adj_endp1 = __endp1; 6379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch(__base->_M_tag) { 6399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_concat: 6409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 6419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, __base); 6429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __left = __c->_M_left; 6439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __right = __c->_M_right; 6449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __left_len = __left->_M_size._M_data; 6459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __result; 6469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__adj_endp1 <= __left_len) { 6489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_substring(__left, __start, __endp1); 6499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else if (__start >= __left_len) { 6509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_substring(__right, __start - __left_len, 6519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __adj_endp1 - __left_len); 6529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self_destruct_ptr __left_result(_S_substring(__left, __start, __left_len)); 6549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self_destruct_ptr __right_result(_S_substring(__right, 0, __endp1 - __left_len)); 6559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_MPWFIX_TRY //*TY 06/01/2000 - mpw forgets to call dtor on __left_result and __right_result without this try block 6569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = _S_concat_rep(__left_result, __right_result); 6579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(1 == __result->_M_ref_count) 6589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 6599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_MPWFIX_CATCH //*TY 06/01/2000 - 6609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_leaf: 6629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 6639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __base); 6649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __result; 6659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __result_len; 6669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__start >= __adj_endp1) return 0; 6679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result_len = __adj_endp1 - __start; 6689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__result_len > __lazy_threshold) goto lazy; 6699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _CharT* __section = __l->_M_data + __start; 6709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // We should sometimes create substring node instead. 6719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = _S_RopeLeaf_from_unowned_char_ptr(__section, __result_len, 6729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __base->get_allocator()); 6739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 6749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_substringfn: 6769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Avoid introducing multiple layers of substring nodes. 6779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 6789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeSubstring* __old = __STATIC_CAST(_RopeSubstring*, __base); 6799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __result_len; 6809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__start >= __adj_endp1) return 0; 6819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result_len = __adj_endp1 - __start; 6829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__result_len > __lazy_threshold) { 6839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeSubstring* __result = _S_new_RopeSubstring(__old->_M_base, 6849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __start + __old->_M_start, 6859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __adj_endp1 - __start, 6869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __base->get_allocator()); 6879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 6889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } // *** else fall through: *** 6899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 6909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_function: 6919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 6929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __base); 6939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__start >= __adj_endp1) return 0; 6949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __result_len = __adj_endp1 - __start; 6959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 6969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__result_len > __lazy_threshold) goto lazy; 6979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __section = __base->_M_size.allocate(_S_rounded_up_size(__result_len)); 6989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 6999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block (*(__f->_M_fn))(__start, __result_len, __section); 7009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND(_RopeRep::_S_free_string(__section, 7029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result_len, __base->get_allocator())) 7039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_construct_null(__section + __result_len); 7049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_new_RopeLeaf(__section, __result_len, 7059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __base->get_allocator()); 7069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block /*NOTREACHED*/ 7099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(false) 7109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block lazy: 7119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 7129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Create substring node. 7139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start, 7149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __base->get_allocator()); 7159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 7179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT> 7199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> { 7209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 7219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* _M_buf_ptr; 7229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 7239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_flatten_char_consumer(_CharT* __buffer) { 7249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buf_ptr = __buffer; 7259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ~_Rope_flatten_char_consumer() {} 7279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool operator() (const _CharT* __leaf, size_t __n) { 7289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_PRIV __ucopy_n(__leaf, __n, _M_buf_ptr); 7299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_buf_ptr += __n; 7309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return true; 7319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 7339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT> 7359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rope_find_char_char_consumer : public _Rope_char_consumer<_CharT> { 7369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 7379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT _M_pattern; 7389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 7399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t _M_count; // Number of nonmatching characters 7409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_find_char_char_consumer(_CharT __p) 7419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_pattern(__p), _M_count(0) {} 7429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ~_Rope_find_char_char_consumer() {} 7439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool operator() (const _CharT* __leaf, size_t __n) { 7449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __i; 7459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (__i = 0; __i < __n; ++__i) { 7469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__leaf[__i] == _M_pattern) { 7479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_count += __i; return false; 7489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_count += __n; return true; 7519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 7529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 7539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_USE_NO_IOSTREAMS) 7559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Traits> 7569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Here _CharT is both the stream and rope character type. 7579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockclass _Rope_insert_char_consumer : public _Rope_char_consumer<_CharT> { 7589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockprivate: 7599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef basic_ostream<_CharT,_Traits> _Insert_ostream; 7609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_insert_char_consumer<_CharT,_Traits> _Self; 7619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Insert_ostream& _M_o; 7629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block //explicitely defined as private to avoid warnings: 7649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self& operator = (_Self const&); 7659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockpublic: 7669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_insert_char_consumer(_Insert_ostream& __writer) 7679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block : _M_o(__writer) {} 7689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ~_Rope_insert_char_consumer() {} 7699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Caller is presumed to own the ostream 7709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool operator() (const _CharT* __leaf, size_t __n); 7719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Returns true to continue traversal. 7729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block}; 7739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Traits> 7759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool _Rope_insert_char_consumer<_CharT, _Traits>::operator() 7769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block (const _CharT* __leaf, size_t __n) { 7779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __i; 7789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // We assume that formatting is set up correctly for each element. 7799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (__i = 0; __i < __n; ++__i) _M_o.put(__leaf[__i]); 7809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return true; 7819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 7829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* !_STLP_USE_NO_IOSTREAMS */ 7839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc, class _CharConsumer> 7859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbool _S_apply_to_pieces(_CharConsumer& __c, 7869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_RopeRep<_CharT, _Alloc> * __r, 7879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __begin, size_t __end) { 7889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 7899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_RopeConcatenation<_CharT,_Alloc> _RopeConcatenation; 7909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_RopeLeaf<_CharT,_Alloc> _RopeLeaf; 7919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef _Rope_RopeFunction<_CharT,_Alloc> _RopeFunction; 7929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 7939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __r) return true; 7949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch(__r->_M_tag) { 7959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_concat: 7969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 7979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation* __conc = __STATIC_CAST(_RopeConcatenation*, __r); 7989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __left = __conc->_M_left; 7999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __left_len = __left->_M_size._M_data; 8009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__begin < __left_len) { 8019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __left_end = (min) (__left_len, __end); 8029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!_S_apply_to_pieces(__c, __left, __begin, __left_end)) 8039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 8049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__end > __left_len) { 8069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __right = __conc->_M_right; 8079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __right_start = (max)(__left_len, __begin); 8089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!_S_apply_to_pieces(__c, __right, 8099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __right_start - __left_len, 8109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __end - __left_len)) { 8119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 8129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return true; 8169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_leaf: 8179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 8189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __r); 8199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __c(__l->_M_data + __begin, __end - __begin); 8209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_function: 8229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_substringfn: 8239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 8249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __r); 8259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __len = __end - __begin; 8269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool __result; 8279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __buffer = __r->get_allocator().allocate(__len); 8289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 8299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block (*(__f->_M_fn))(__begin, __len, __buffer); 8309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = __c(__buffer, __len); 8319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->get_allocator().deallocate(__buffer, __len); 8329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND((__r->get_allocator().deallocate(__buffer, __len))) 8349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 8359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block default: 8379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(false) 8389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block /*NOTREACHED*/ 8399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return false; 8409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if !defined (_STLP_USE_NO_IOSTREAMS) 8449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Traits> 8459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, streamsize __n) { 8469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block char __f = __o.fill(); 8479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (streamsize __i = 0; __i < __n; ++__i) __o.put(__f); 8489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Traits, class _Alloc> 8519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbasic_ostream<_CharT, _Traits>& _S_io_get(basic_ostream<_CharT, _Traits>& __o, 8529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const rope<_CharT, _Alloc>& __r, const __true_type& /*_IsBasicCharType*/) { 8539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block streamsize __w = __o.width(); 8549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const bool __left = (__o.flags() & ios::left) != 0; 8559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __rope_len = __r.size(); 8569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_insert_char_consumer<_CharT, _Traits> __c(__o); 8579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const bool __need_pad = (((sizeof(streamsize) > sizeof(size_t)) && (__STATIC_CAST(streamsize, __rope_len) < __w)) || 8599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block ((sizeof(streamsize) <= sizeof(size_t)) && (__rope_len < __STATIC_CAST(size_t, __w)))); 8609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block streamsize __pad_len = __need_pad ? __w - __rope_len : 0; 8619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (!__left && __pad_len > 0) { 8639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_fill(__o, __pad_len); 8649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r.apply_to_pieces(0, __rope_len, __c); 8669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__left && __pad_len > 0) { 8679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_fill(__o, __pad_len); 8689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __o; 8709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Traits, class _Alloc> 8739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbasic_ostream<_CharT, _Traits>& _S_io_get(basic_ostream<_CharT, _Traits>& __o, 8749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const rope<_CharT, _Alloc>& __r, const __false_type& /*_IsBasicCharType*/) { 8759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block streamsize __w = __o.width(); 8769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __rope_len = __r.size(); 8779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_insert_char_consumer<_CharT, _Traits> __c(__o); 8789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __o.width(__w /__rope_len); 8809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 8819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r.apply_to_pieces(0, __rope_len, __c); 8829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __o.width(__w); 8839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 8849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND(__o.width(__w)) 8859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __o; 8869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Traits, class _Alloc> 8899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockbasic_ostream<_CharT, _Traits>& operator<<(basic_ostream<_CharT, _Traits>& __o, 8909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const rope<_CharT, _Alloc>& __r) { 8919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block typedef typename _IsIntegral<_CharT>::_Ret _Char_Is_Integral; 8929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_io_get(__o, __r, _Char_Is_Integral()); 8939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 8949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* NO_IOSTREAMS */ 8959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 8969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 8979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_CharT* rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, 8989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __start, size_t __len, 8999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __buffer) { 9009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_flatten_char_consumer<_CharT> __c(__buffer); 9019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_apply_to_pieces(__c, __r, __start, __start + __len); 9029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return(__buffer + __len); 9039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 9069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocksize_t rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const { 9079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_find_char_char_consumer<_CharT> __c(__pattern); 9089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_apply_to_pieces(__c, _M_tree_ptr._M_data, __start, size()); 9099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_type __result_pos = __start + __c._M_count; 9109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifndef _STLP_OLD_ROPE_SEMANTICS 9119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__result_pos == size()) __result_pos = npos; 9129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 9139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result_pos; 9149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 9179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_CharT* 9189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_flatten(_Rope_RopeRep<_CharT, _Alloc>* __r, _CharT* __buffer) { 9199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __r) return __buffer; 9209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch(__r->_M_tag) { 9219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_concat: 9229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 9239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, __r); 9249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __left = __c->_M_left; 9259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __right = __c->_M_right; 9269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __rest = _S_flatten(__left, __buffer); 9279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_flatten(__right, __rest); 9289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_leaf: 9309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 9319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __l = __STATIC_CAST(_RopeLeaf*, __r); 9329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __ucopy_n(__l->_M_data, __l->_M_size._M_data, __buffer).second; 9339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_function: 9359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_substringfn: 9369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // We dont yet do anything with substring nodes. 9379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // This needs to be fixed before ropefiles will work well. 9389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 9399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeFunction* __f = __STATIC_CAST(_RopeFunction*, __r); 9409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block (*(__f->_M_fn))(0, __f->_M_size._M_data, __buffer); 9419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __buffer + __f->_M_size._M_data; 9429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block default: 9449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(false) 9459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block /*NOTREACHED*/ 9469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return 0; 9479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 9499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#ifdef _STLP_DEBUG 9519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// This needs work for _CharT != char 9529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 9539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent) { 9549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (int __i = 0; __i < __indent; ++__i) putchar(' '); 9559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __r) { 9569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block printf("NULL\n"); return; 9579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_concat == __r->_M_tag) { 9599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation* __c = __STATIC_CAST(_RopeConcatenation*, __r); 9609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __left = __c->_M_left; 9619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __right = __c->_M_right; 9629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block printf("Concatenation %p (rc = %ld, depth = %d, len = %ld, %s balanced)\n", 9639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size._M_data, 9649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_is_balanced? "" : "not"); 9659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_dump(__left, __indent + 2); 9669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_dump(__right, __indent + 2); 9679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 9689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 9709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const char* __kind; 9719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch (__r->_M_tag) { 9739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_leaf: 9749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __kind = "Leaf"; 9759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 9769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_function: 9779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __kind = "Function"; 9789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 9799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_substringfn: 9809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __kind = "Function representing substring"; 9819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 9829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block default: 9839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __kind = "(corrupted kind field!)"; 9849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block printf("%s %p (rc = %ld, depth = %d, len = %ld) ", 9869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size._M_data); 9879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (sizeof(_CharT) == 1) { 9889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const int __max_len = 40; 9899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len)); 9909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT __buffer[__max_len + 1]; 9919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block bool __too_big = __r->_M_size._M_data > __prefix->_M_size._M_data; 9929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 9939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_flatten(__prefix, __buffer); 9949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __buffer[__prefix->_M_size._M_data] = _STLP_DEFAULT_CONSTRUCTED(_CharT); 9959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block printf("%s%s\n", (char*)__buffer, __too_big? "...\n" : "\n"); 9969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 9979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block printf("\n"); 9989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 9999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 10019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_DEBUG */ 10029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# define __ROPE_TABLE_BODY = { \ 10049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, \ 10059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, \ 10069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, \ 10079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 18 */6765ul, /* 19 */10946ul, /* 20 */17711ul, /* 21 */28657ul, /* 22 */46368ul, \ 10089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 23 */75025ul, /* 24 */121393ul, /* 25 */196418ul, /* 26 */317811ul, \ 10099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 27 */514229ul, /* 28 */832040ul, /* 29 */1346269ul, /* 30 */2178309ul, \ 10109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 31 */3524578ul, /* 32 */5702887ul, /* 33 */9227465ul, /* 34 */14930352ul, \ 10119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 35 */24157817ul, /* 36 */39088169ul, /* 37 */63245986ul, /* 38 */102334155ul, \ 10129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 39 */165580141ul, /* 40 */267914296ul, /* 41 */433494437ul, \ 10139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 42 */701408733ul, /* 43 */1134903170ul, /* 44 */1836311903ul, \ 10149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block/* 45 */2971215073ul } 10159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 10179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockconst unsigned long 10189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_min_len[__ROPE_DEPTH_SIZE] __ROPE_TABLE_BODY; 10199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef __ROPE_DEPTH_SIZE 10209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef __ROPE_MAX_DEPTH 10219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef __ROPE_TABLE_BODY 10229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// These are Fibonacci numbers < 2**32. 10249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 10269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block__RopeRep__* rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r) { 10279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __forest[_RopeRep::_S_max_rope_depth + 1] = {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 10289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0, 10299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 0,0,0,0,0,0}; 10309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __result = 0; 10319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block int __i; 10329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Invariant: 10339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // The concatenation of forest in descending order is equal to __r. 10349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // __forest[__i]._M_size._M_data >= _S_min_len[__i] 10359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // __forest[__i]._M_depth = __i 10369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // References from forest are included in refcount. 10379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_TRY { 10399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_add_to_forest(__r, __forest); 10409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i) 10419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != __forest[__i]) { 10429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self_destruct_ptr __old(__result); 10439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result = _S_concat_rep(__forest[__i], __result); 10449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __forest[__i]->_M_unref_nonnil(); 10459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# ifdef _STLP_USE_EXCEPTIONS 10469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __forest[__i] = 0; 10479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif 10489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_UNWIND(for(__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i) 10519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_unref(__forest[__i])) 10529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__result->_M_depth > _RopeRep::_S_max_rope_depth) { 10539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __stl_throw_range_error("rope too long"); 10549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return(__result); 10569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 10579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 10609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 10619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_add_to_forest(_RopeRep* __r, _RopeRep** __forest) 10629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 10639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__r -> _M_is_balanced) { 10649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_add_leaf_to_forest(__r, __forest); 10659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 10669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__r->_M_tag == _RopeRep::_S_concat) 10689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 10699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation* __c = (_RopeConcatenation*)__r; 10709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_add_to_forest(__c->_M_left, __forest); 10729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_add_to_forest(__c->_M_right, __forest); 10739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 10759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 10789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid 10799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest) 10809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 10819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __insertee; // included in refcount 10829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __too_tiny = 0; // included in refcount 10839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block int __i; // forest[0..__i-1] is empty 10849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __s = __r->_M_size._M_data; 10859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 10869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) { 10879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != __forest[__i]) { 10889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self_destruct_ptr __old(__too_tiny); 10899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny); 10909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __forest[__i]->_M_unref_nonnil(); 10919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __forest[__i] = 0; 10929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 10959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self_destruct_ptr __old(__too_tiny); 10969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __insertee = _S_concat_and_set_balanced(__too_tiny, __r); 10979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 10989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Too_tiny dead, and no longer included in refcount. 10999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Insertee is live and included. 11009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(_S_is_almost_balanced(__insertee)) 11019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__insertee->_M_depth <= __r->_M_depth + 1) 11029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for (;; ++__i) { 11039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != __forest[__i]) { 11049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self_destruct_ptr __old(__insertee); 11059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __insertee = _S_concat_and_set_balanced(__forest[__i], __insertee); 11069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __forest[__i]->_M_unref_nonnil(); 11079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __forest[__i] = 0; 11089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(_S_is_almost_balanced(__insertee)) 11099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(_S_min_len[__i] <= __insertee->_M_size._M_data) 11119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__forest[__i] == 0) 11129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__i == _RopeRep::_S_max_rope_depth || 11139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __insertee->_M_size._M_data < _S_min_len[__i+1]) { 11149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __forest[__i] = __insertee; 11159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // refcount is OK since __insertee is now dead. 11169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return; 11179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 11209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 11229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_CharT 11239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_fetch(_RopeRep* __r, size_type __i) 11249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 11259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __cstr = __r->_M_c_string; 11269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__i < __r->_M_size._M_data) 11289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != __cstr) return __cstr[__i]; 11299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for(;;) { 11309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch(__r->_M_tag) { 11319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_concat: 11329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 11339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation* __c = (_RopeConcatenation*)__r; 11349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __left = __c->_M_left; 11359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __left_len = __left->_M_size._M_data; 11369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__i >= __left_len) { 11389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __i -= __left_len; 11399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r = __c->_M_right; 11409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 11419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r = __left; 11429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 11459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_leaf: 11469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 11479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __l = (_RopeLeaf*)__r; 11489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __l->_M_data[__i]; 11499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_function: 11519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_substringfn: 11529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 11539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeFunction* __f = (_RopeFunction*)__r; 11549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT __result; 11559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block (*(__f->_M_fn))(__i, 1, &__result); 11579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 11589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined(_STLP_NEED_UNREACHABLE_RETURN) 11629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return 0; 11639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 11649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 11659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Return a uniquely referenced character slot for the given 11679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// position, or 0 if that's not possible. 11689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 11699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_CharT* 11709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_fetch_ptr(_RopeRep* __r, size_type __i) 11719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block{ 11729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __clrstack[_RopeRep::_S_max_rope_depth]; 11739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __csptr = 0; 11749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block for(;;) { 11769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // if (__r->_M_ref_count > 1) return 0; 11779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if ( __r->_M_incr() > 2 ) { 11789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_decr(); 11799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return 0; 11809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block switch(__r->_M_tag) { 11829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_concat: 11839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 11849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeConcatenation* __c = (_RopeConcatenation*)__r; 11859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __left = __c->_M_left; 11869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __left_len = __left->_M_size._M_data; 11879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 11889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c; 11899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__i >= __left_len) { 11909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __i -= __left_len; 11919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r = __c->_M_right; 11929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } else { 11939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r = __left; 11949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 11969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block break; 11979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_leaf: 11989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block { 11999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeLeaf* __l = (_RopeLeaf*)__r; 12009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0) 12019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __clrstack[__csptr++] = __l; 12029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block while (__csptr > 0) { 12039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block -- __csptr; 12049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __d = __clrstack[__csptr]; 12059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __d->_M_free_c_string(); 12069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __d->_M_c_string = 0; 12079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __l->_M_data + __i; 12099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_function: 12119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block case _RopeRep::_S_substringfn: 12129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return 0; 12139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#if defined(_STLP_NEED_UNREACHABLE_RETURN) 12169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return 0; 12179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 12189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// The following could be implemented trivially using 12229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// lexicographical_compare_3way. 12239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// We do a little more work to avoid dealing with rope iterators for 12249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// flat strings. 12259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 12269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockint 12279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockrope<_CharT,_Alloc>::_S_compare (const _RopeRep* __left, 12289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _RopeRep* __right) { 12299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __left_len; 12309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __right_len; 12319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __right) return 0 != __left; 12339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == __left) return -1; 12349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __left_len = __left->_M_size._M_data; 12359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __right_len = __right->_M_size._M_data; 12369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_leaf == __left->_M_tag) { 12379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _RopeLeaf* __l = __STATIC_CAST(const _RopeLeaf*, __left); 12389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_leaf == __right->_M_tag) { 12399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _RopeLeaf* __r = __STATIC_CAST(const _RopeLeaf*, __right); 12409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __lexicographical_compare_3way(__l->_M_data, __l->_M_data + __left_len, 12419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_data, __r->_M_data + __right_len); 12429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 12449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator __rstart(__right, 0); 12459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator __rend(__right, __right_len); 12469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __lexicographical_compare_3way(__l->_M_data, __l->_M_data + __left_len, 12479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __rstart, __rend); 12489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 12519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator __lstart(__left, 0); 12529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator __lend(__left, __left_len); 12539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_leaf == __right->_M_tag) { 12549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const _RopeLeaf* __r = __STATIC_CAST(const _RopeLeaf*, __right); 12559720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __lexicographical_compare_3way(__lstart, __lend, 12569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r->_M_data, __r->_M_data + __right_len); 12579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block else { 12599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator __rstart(__right, 0); 12609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block const_iterator __rend(__right, __right_len); 12619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _STLP_PRIV __lexicographical_compare_3way(__lstart, __lend, __rstart, __rend); 12629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Assignment to reference proxies. 12679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 12689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_Rope_char_ref_proxy<_CharT, _Alloc>& 12699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) { 12709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __old = _M_root->_M_tree_ptr._M_data; 12719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // First check for the case in which everything is uniquely 12729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // referenced. In that case we can do this destructively. 12739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos); 12749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != __ptr) { 12759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block *__ptr = __c; 12769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return *this; 12779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 12789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self_destruct_ptr __left( 12799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _My_rope::_S_substring(__old, 0, _M_pos)); 12809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self_destruct_ptr __right( 12819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _My_rope::_S_substring(__old, _M_pos+1, __old->_M_size._M_data)); 12829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Self_destruct_ptr __result_left( 12839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _My_rope::_S_destr_concat_char_iter(__left, &__c, 1)); 12849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(__left == __result_left || 1 == __result_left->_M_ref_count) 12869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep* __result = 12879720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _My_rope::_S_concat_rep(__result_left, __right); 12889720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // _STLP_ASSERT(1 <= __result->_M_ref_count) 12899720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _RopeRep::_S_unref(__old); 12909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_root->_M_tree_ptr._M_data = __result; 12919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return *this; 12929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 12949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 12959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_Rope_char_ptr_proxy<_CharT, _Alloc> 12969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const { 12979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); 12989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 12999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> 13019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_CharT rope<_CharT,_Alloc>::_S_empty_c_str[1] = { _CharT() }; 13029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// # endif 13039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1304e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if !defined (_STLP_STATIC_CONST_INIT_BUG) && !defined (_STLP_NO_STATIC_CONST_DEFINITION) 13059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate <class _CharT, class _Alloc> 13069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockconst size_t rope<_CharT, _Alloc>::npos; 13079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif 13089720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13099720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> 13109720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockconst _CharT* rope<_CharT,_Alloc>::c_str() const { 13119720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == _M_tree_ptr._M_data) { 13129720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // Possibly redundant, but probably fast. 13139720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_empty_c_str[0] = _STLP_DEFAULT_CONSTRUCTED(_CharT); 13149720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_empty_c_str; 13159720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 13169720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string; 13179720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != __old_c_string) return __old_c_string; 13189720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __s = size(); 13199720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __result = _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_tree_ptr, _CharT).allocate(__s + 1); 13209720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_flatten(_M_tree_ptr._M_data, __result); 13219720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_construct_null(__result + __s); 13229720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __old_c_string = __STATIC_CAST(_CharT*, _Atomic_swap_ptr(__REINTERPRET_CAST(void* _STLP_VOLATILE*, &(_M_tree_ptr._M_data->_M_c_string)), 13239720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __result)); 13249720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 != __old_c_string) { 13259720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // It must have been added in the interim. Hence it had to have been 13269720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // separately allocated. Deallocate the old copy, since we just 13279720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block // replaced it. 13289720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_STD::_Destroy_Range(__old_c_string, __old_c_string + __s + 1); 13299720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_CREATE_ALLOCATOR(allocator_type,(const allocator_type&)_M_tree_ptr, _CharT).deallocate(__old_c_string, __s + 1); 13309720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 13319720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 13329720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 13339720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13349720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT, class _Alloc> 13359720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockconst _CharT* rope<_CharT,_Alloc>::replace_with_c_str() { 13369720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (0 == _M_tree_ptr._M_data) { 13379720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_empty_c_str[0] = _STLP_DEFAULT_CONSTRUCTED(_CharT); 13389720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return _S_empty_c_str; 13399720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 13409720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __old_c_string = _M_tree_ptr._M_data->_M_c_string; 13419720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block if (_RopeRep::_S_leaf == _M_tree_ptr._M_data->_M_tag && 0 != __old_c_string) { 13429720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __old_c_string; 13439720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block } 13449720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block size_t __s = size(); 13459720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _CharT* __result = _M_tree_ptr.allocate(_S_rounded_up_size(__s)); 13469720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_flatten(_M_tree_ptr._M_data, __result); 13479720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _S_construct_null(__result + __s); 13489720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_tree_ptr._M_data->_M_unref_nonnil(); 13499720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _M_tree_ptr._M_data = _S_new_RopeLeaf(__result, __s, _M_tree_ptr); 13509720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block return __result; 13519720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 13529720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13539720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Algorithm specializations. More should be added. 13549720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 1355e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott#if (!defined (_STLP_MSVC) || (_STLP_MSVC >= 1310)) && !defined (__DMC__) 13569720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// I couldn't get this to work with VC++ 13579720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blocktemplate<class _CharT,class _Alloc> 13589720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockvoid _Rope_rotate(_Rope_iterator<_CharT,_Alloc> __first, 13599720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_iterator<_CharT,_Alloc> __middle, 13609720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_iterator<_CharT,_Alloc> __last) { 13619720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _STLP_ASSERT(__first.container() == __middle.container() && 13629720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __middle.container() == __last.container()) 13639720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block rope<_CharT,_Alloc>& __r(__first.container()); 13649720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index()); 13659720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block rope<_CharT,_Alloc> __suffix = 13669720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r.substr(__last.index(), __r.size() - __last.index()); 13679720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block rope<_CharT,_Alloc> __part1 = 13689720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r.substr(__middle.index(), __last.index() - __middle.index()); 13699720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block rope<_CharT,_Alloc> __part2 = 13709720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r.substr(__first.index(), __middle.index() - __first.index()); 13719720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r = __prefix; 13729720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r += __part1; 13739720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r += __part2; 13749720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block __r += __suffix; 13759720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 13769720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13779720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13789720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# if 0 13799720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Probably not useful for several reasons: 13809720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// - for SGIs 7.1 compiler and probably some others, 13819720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// this forces lots of rope<wchar_t, ...> instantiations, creating a 13829720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// code bloat and compile time problem. (Fixed in 7.2.) 13839720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive 13849720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// for unicode strings. Unsigned short may be a better character 13859720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// type. 13869720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Blockinline void rotate( 1387e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Rope_iterator<wchar_t, allocator<char> > __first, 1388e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Rope_iterator<wchar_t, allocator<char> > __middle, 1389e46c9386c4f79aa40185f79a19fc5b2a7ef528b3Patrick Scott _Rope_iterator<wchar_t, allocator<char> > __last) { 13909720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block _Rope_rotate(__first, __middle, __last); 13919720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block} 13929720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif 13939720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block#endif /* _STLP_MSVC */ 13949720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 13959720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef __RopeLeaf__ 13969720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef __RopeRep__ 13979720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef __RopeLeaf 13989720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef __RopeRep 13999720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# undef size_type 14009720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 14019720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block_STLP_END_NAMESPACE 14029720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 14039720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block# endif /* ROPEIMPL_H */ 14049720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block 14059720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// Local Variables: 14069720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// mode:C++ 14079720d5f59b9c1f5d1b9ecbc9173dbcb71bd557beSteve Block// End: 1408