111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// SGI's rope class implementation -*- C++ -*- 211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Copyright (C) 2001-2014 Free Software Foundation, Inc. 411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This file is part of the GNU ISO C++ Library. This library is free 611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// software; you can redistribute it and/or modify it under the 711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// terms of the GNU General Public License as published by the 811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Free Software Foundation; either version 3, or (at your option) 911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// any later version. 1011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// This library is distributed in the hope that it will be useful, 1211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// but WITHOUT ANY WARRANTY; without even the implied warranty of 1311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// GNU General Public License for more details. 1511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 1611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// Under Section 7 of GPL version 3, you are granted additional 1711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// permissions described in the GCC Runtime Library Exception, version 1811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// 3.1, as published by the Free Software Foundation. 1911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// You should have received a copy of the GNU General Public License and 2111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// a copy of the GCC Runtime Library Exception along with this program; 2211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 2311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert// <http://www.gnu.org/licenses/>. 2411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 2511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/* 2611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Copyright (c) 1997 2711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Silicon Graphics Computer Systems, Inc. 2811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * 2911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Permission to use, copy, modify, distribute and sell this software 3011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * and its documentation for any purpose is hereby granted without fee, 3111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * provided that the above copyright notice appear in all copies and 3211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * that both that copyright notice and this permission notice appear 3311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * in supporting documentation. Silicon Graphics makes no 3411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * representations about the suitability of this software for any 3511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * purpose. It is provided "as is" without express or implied warranty. 3611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 3711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 3811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert/** @file ropeimpl.h 3911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * This is an internal header file, included by other library headers. 4011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert * Do not attempt to use it directly. @headername{ext/rope} 4111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert */ 4211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <cstdio> 4411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ostream> 4511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <bits/functexcept.h> 4611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 4711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/algorithm> // For copy_n and lexicographical_compare_3way 4811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/memory> // For uninitialized_copy_n 4911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#include <ext/numeric> // For power 5011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5111cd02dfb91661c65134cac258cf5924270e9d2Dan Albertnamespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 5211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert{ 5311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_GLIBCXX_BEGIN_NAMESPACE_VERSION 5411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 5511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert using std::size_t; 5611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert using std::printf; 5711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert using std::basic_ostream; 5811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert using std::__throw_length_error; 5911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert using std::_Destroy; 6011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert using std::__uninitialized_fill_n_a; 6111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 6211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf 6311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct. 6411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Results in a valid buf_ptr if the iterator can be legitimately 6511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // dereferenced. 6611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 6711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 6811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator_base<_CharT, _Alloc>:: 6911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x) 7011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 7111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index]; 7211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __leaf_pos = __x._M_leaf_pos; 7311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __pos = __x._M_current_pos; 7411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 7511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert switch(__leaf->_M_tag) 7611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 7711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_leaf: 7811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data; 7911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos); 8011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_buf_end = __x._M_buf_start + __leaf->_M_size; 8111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 8211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_function: 8311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_substringfn: 8411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 8511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __len = _S_iterator_buf_len; 8611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __buf_start_pos = __leaf_pos; 8711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __leaf_end = __leaf_pos + __leaf->_M_size; 8811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT, 8911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Alloc>*)__leaf)->_M_fn; 9011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__buf_start_pos + __len <= __pos) 9111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 9211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __buf_start_pos = __pos - __len / 4; 9311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__buf_start_pos + __len > __leaf_end) 9411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __buf_start_pos = __leaf_end - __len; 9511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 9611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__buf_start_pos + __len > __leaf_end) 9711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __len = __leaf_end - __buf_start_pos; 9811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf); 9911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos); 10011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_buf_start = __x._M_tmp_buf; 10111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_buf_end = __x._M_tmp_buf + __len; 10211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 10311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 10411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert default: 10511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 10611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 10711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 10811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 10911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Set path and buffer inside a rope iterator. We assume that 11011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // pos and root are already set. 11111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 11211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 11311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator_base<_CharT, _Alloc>:: 11411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x) 11511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 11611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _RopeRep* __path[int(__detail::_S_max_rope_depth) + 1]; 11711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _RopeRep* __curr_rope; 11811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int __curr_depth = -1; /* index into path */ 11911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __curr_start_pos = 0; 12011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __pos = __x._M_current_pos; 12111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert unsigned char __dirns = 0; // Bit vector marking right turns in the path 12211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 12311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__pos >= __x._M_root->_M_size) 12411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 12511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_buf_ptr = 0; 12611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 12711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 12811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __curr_rope = __x._M_root; 12911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != __curr_rope->_M_c_string) 13011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 13111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* Treat the root as a leaf. */ 13211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_buf_start = __curr_rope->_M_c_string; 13311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size; 13411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_buf_ptr = __curr_rope->_M_c_string + __pos; 13511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_path_end[0] = __curr_rope; 13611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_leaf_index = 0; 13711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_leaf_pos = 0; 13811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 13911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 14011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for(;;) 14111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 14211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__curr_depth; 14311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __path[__curr_depth] = __curr_rope; 14411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert switch(__curr_rope->_M_tag) 14511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 14611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_leaf: 14711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_function: 14811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_substringfn: 14911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_leaf_pos = __curr_start_pos; 15011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert goto done; 15111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_concat: 15211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 15311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeConcatenation<_CharT, _Alloc>* __c = 15411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope; 15511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __left = __c->_M_left; 15611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __left_len = __left->_M_size; 15711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 15811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __dirns <<= 1; 15911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__pos >= __curr_start_pos + __left_len) 16011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 16111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __dirns |= 1; 16211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __curr_rope = __c->_M_right; 16311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __curr_start_pos += __left_len; 16411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 16511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 16611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __curr_rope = __left; 16711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 16811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 16911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 17011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 17111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert done: 17211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Copy last section of path into _M_path_end. 17311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 17411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int __i = -1; 17511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int __j = __curr_depth + 1 - int(_S_path_cache_len); 17611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 17711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__j < 0) __j = 0; 17811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__j <= __curr_depth) 17911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_path_end[++__i] = __path[__j++]; 18011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_leaf_index = __i; 18111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 18211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_path_directions = __dirns; 18311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_setbuf(__x); 18411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 18511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 18611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Specialized version of the above. Assumes that 18711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // the path cache is valid for the previous position. 18811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 18911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 19011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator_base<_CharT, _Alloc>:: 19111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x) 19211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 19311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int __current_index = __x._M_leaf_index; 19411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _RopeRep* __current_node = __x._M_path_end[__current_index]; 19511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __len = __current_node->_M_size; 19611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __node_start_pos = __x._M_leaf_pos; 19711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert unsigned char __dirns = __x._M_path_directions; 19811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeConcatenation<_CharT, _Alloc>* __c; 19911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 20011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__x._M_current_pos - __node_start_pos < __len) 20111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 20211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* More stuff in this leaf, we just didn't cache it. */ 20311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_setbuf(__x); 20411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 20511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 20611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // node_start_pos is starting position of last_node. 20711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (--__current_index >= 0) 20811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 20911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!(__dirns & 1) /* Path turned left */) 21011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 21111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __current_node = __x._M_path_end[__current_index]; 21211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node; 21311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Otherwise we were in the right child. Thus we should pop 21411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // the concatenation node. 21511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __node_start_pos -= __c->_M_left->_M_size; 21611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __dirns >>= 1; 21711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 21811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__current_index < 0) 21911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 22011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // We underflowed the cache. Punt. 22111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_setcache(__x); 22211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 22311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 22411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __current_node = __x._M_path_end[__current_index]; 22511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node; 22611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // current_node is a concatenation node. We are positioned on the first 22711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // character in its right child. 22811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // node_start_pos is starting position of current_node. 22911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __node_start_pos += __c->_M_left->_M_size; 23011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __current_node = __c->_M_right; 23111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_path_end[++__current_index] = __current_node; 23211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __dirns |= 1; 23311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__detail::_S_concat == __current_node->_M_tag) 23411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 23511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__current_index; 23611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (int(_S_path_cache_len) == __current_index) 23711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 23811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int __i; 23911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__i = 0; __i < int(_S_path_cache_len) - 1; __i++) 24011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_path_end[__i] = __x._M_path_end[__i+1]; 24111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert --__current_index; 24211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 24311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __current_node = 24411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left; 24511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_path_end[__current_index] = __current_node; 24611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __dirns <<= 1; 24711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // node_start_pos is unchanged. 24811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 24911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_leaf_index = __current_index; 25011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_leaf_pos = __node_start_pos; 25111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __x._M_path_directions = __dirns; 25211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_setbuf(__x); 25311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 25411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 25511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 25611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 25711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator_base<_CharT, _Alloc>:: 25811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_incr(size_t __n) 25911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 26011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_current_pos += __n; 26111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != _M_buf_ptr) 26211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 26311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __chars_left = _M_buf_end - _M_buf_ptr; 26411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__chars_left > __n) 26511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buf_ptr += __n; 26611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else if (__chars_left == __n) 26711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 26811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buf_ptr += __n; 26911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_setcache_for_incr(*this); 27011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 27111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 27211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buf_ptr = 0; 27311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 27411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 27511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 27611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 27711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 27811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator_base<_CharT, _Alloc>:: 27911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_decr(size_t __n) 28011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 28111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != _M_buf_ptr) 28211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 28311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __chars_left = _M_buf_ptr - _M_buf_start; 28411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__chars_left >= __n) 28511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buf_ptr -= __n; 28611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 28711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buf_ptr = 0; 28811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 28911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_current_pos -= __n; 29011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 29111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 29211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 29311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 29411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator<_CharT, _Alloc>:: 29511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_check() 29611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 29711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_M_root_rope->_M_tree_ptr != this->_M_root) 29811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 29911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // _Rope was modified. Get things fixed up. 30011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep::_S_unref(this->_M_root); 30111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_root = _M_root_rope->_M_tree_ptr; 30211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep::_S_ref(this->_M_root); 30311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_buf_ptr = 0; 30411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 30511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 30611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 30711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 30811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline 30911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_const_iterator<_CharT, _Alloc>:: 31011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_const_iterator(const _Rope_iterator<_CharT, _Alloc>& __x) 31111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _Rope_iterator_base<_CharT, _Alloc>(__x) 31211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { } 31311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 31411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 31511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline 31611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator<_CharT, _Alloc>:: 31711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos) 31811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos), 31911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_root_rope(&__r) 32011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _RopeRep::_S_ref(this->_M_root); } 32111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 32311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline size_t 32411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 32511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_char_ptr_len(const _CharT* __s) 32611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 32711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _CharT* __p = __s; 32811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 32911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (!_S_is0(*__p)) 33011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ++__p; 33111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return (__p - __s); 33211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 33311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __GC 33611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 33711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 33811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 33911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeRep<_CharT, _Alloc>:: 34011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_free_c_string() 34111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 34211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* __cstr = _M_c_string; 34311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != __cstr) 34411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 34511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __size = this->_M_size + 1; 34611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Destroy(__cstr, __cstr + __size, _M_get_allocator()); 34711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_Data_deallocate(__cstr, __size); 34811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 34911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 35011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 35211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 35311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeRep<_CharT, _Alloc>:: 35411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_free_string(_CharT* __s, size_t __n, allocator_type& __a) 35511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 35611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!_S_is_basic_char_type((_CharT*)0)) 35711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Destroy(__s, __s + __n, __a); 35811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 35911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // This has to be a static member, so this gets a bit messy 36011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __a.deallocate(__s, 36111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n)); 36211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 36311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 36411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // There are several reasons for not doing this with virtual destructors 36511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // and a class specific delete operator: 36611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // - A class specific delete operator can't easily get access to 36711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // allocator instances if we need them. 36811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // - Any virtual function would need a 4 or byte vtable pointer; 36911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // this only requires a one byte tag per object. 37011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 37111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 37211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeRep<_CharT, _Alloc>:: 37311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_free_tree() 37411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 37511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert switch(_M_tag) 37611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 37711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_leaf: 37811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 37911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeLeaf<_CharT, _Alloc>* __l 38011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = (_Rope_RopeLeaf<_CharT, _Alloc>*)this; 38111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __l->_Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf(); 38211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_L_deallocate(__l, 1); 38311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 38411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 38511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_concat: 38611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 38711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeConcatenation<_CharT,_Alloc>* __c 38811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = (_Rope_RopeConcatenation<_CharT, _Alloc>*)this; 38911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __c->_Rope_RopeConcatenation<_CharT, _Alloc>:: 39011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Rope_RopeConcatenation(); 39111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_C_deallocate(__c, 1); 39211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 39311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 39411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_function: 39511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 39611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeFunction<_CharT, _Alloc>* __f 39711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert = (_Rope_RopeFunction<_CharT, _Alloc>*)this; 39811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction(); 39911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_F_deallocate(__f, 1); 40011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 40111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 40211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_substringfn: 40311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 40411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeSubstring<_CharT, _Alloc>* __ss = 40511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (_Rope_RopeSubstring<_CharT, _Alloc>*)this; 40611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __ss->_Rope_RopeSubstring<_CharT, _Alloc>:: 40711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Rope_RopeSubstring(); 40811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_S_deallocate(__ss, 1); 40911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 41011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 41111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 41211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 41311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 41411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 41511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 41611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 41711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_RopeRep<_CharT, _Alloc>:: 41811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_free_string(const _CharT*, size_t, allocator_type) 41911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { } 42011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 42211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 42311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Concatenate a C string onto a leaf rope by copying the rope data. 42411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Used for short ropes. 42511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 42611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename rope<_CharT, _Alloc>::_RopeLeaf* 42711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 42811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, size_t __len) 42911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 43011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __old_len = __r->_M_size; 43111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* __new_data = (_CharT*) 43211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope::_Data_allocate(_S_rounded_up_size(__old_len + __len)); 43311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __result; 43411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 43511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert uninitialized_copy_n(__r->_M_data, __old_len, __new_data); 43611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert uninitialized_copy_n(__iter, __len, __new_data + __old_len); 43711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_cond_store_eos(__new_data[__old_len + __len]); 43811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 43911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 44011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = _S_new_RopeLeaf(__new_data, __old_len + __len, 44111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_get_allocator()); 44211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 44311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 44411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 44511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len, 44611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_get_allocator()); 44711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 44811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 44911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 45011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 45111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 45211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __GC 45311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // As above, but it's OK to clobber original if refcount is 1 45411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 45511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename rope<_CharT,_Alloc>::_RopeLeaf* 45611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 45711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_destr_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, 45811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __len) 45911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 46011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__r->_M_ref_count > 1) 46111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _S_leaf_concat_char_iter(__r, __iter, __len); 46211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __old_len = __r->_M_size; 46311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_S_allocated_capacity(__old_len) >= __old_len + __len) 46411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 46511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // The space has been partially initialized for the standard 46611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // character types. But that doesn't matter for those types. 46711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len); 46811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_S_is_basic_char_type((_CharT*)0)) 46911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_cond_store_eos(__r->_M_data[__old_len + __len]); 47011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) 47111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 47211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_free_c_string(); 47311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_c_string = 0; 47411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 47511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_size = __old_len + __len; 47611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_ref_count = 2; 47711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __r; 47811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 47911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 48011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 48111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len); 48211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 48311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 48411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 48511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 48611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 48711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Assumes left and right are not 0. 48811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Does not increment (nor decrement on exception) child reference counts. 48911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Result has ref count 1. 49011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 49111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename rope<_CharT, _Alloc>::_RopeRep* 49211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 49311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_tree_concat(_RopeRep* __left, _RopeRep* __right) 49411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 49511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right, 49611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __left-> 49711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_allocator()); 49811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __depth = __result->_M_depth; 49911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 50011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__depth > 20 50111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert && (__result->_M_size < 1000 50211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert || __depth > size_t(__detail::_S_max_rope_depth))) 50311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 50411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __balanced; 50511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 50611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 50711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 50811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __balanced = _S_balance(__result); 50911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result->_M_unref_nonnil(); 51011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 51111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 51211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 51311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope::_C_deallocate(__result,1); 51411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 51511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 51611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // In case of exception, we need to deallocate 51711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // otherwise dangling result node. But caller 51811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // still owns its children. Thus unref is 51911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // inappropriate. 52011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __balanced; 52111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 52211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 52311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 52411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 52511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 52611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 52711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename rope<_CharT, _Alloc>::_RopeRep* 52811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 52911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_concat_char_iter(_RopeRep* __r, const _CharT*__s, size_t __slen) 53011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 53111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __result; 53211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __slen) 53311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 53411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_ref(__r); 53511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __r; 53611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 53711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __r) 53811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, 53911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_get_allocator()); 54011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__r->_M_tag == __detail::_S_leaf 54111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert && __r->_M_size + __slen <= size_t(_S_copy_max)) 54211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 54311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); 54411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 54511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 54611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__detail::_S_concat == __r->_M_tag 54711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert && __detail::_S_leaf == ((_RopeConcatenation*) __r)->_M_right->_M_tag) 54811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 54911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __right = 55011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right); 55111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__right->_M_size + __slen <= size_t(_S_copy_max)) 55211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 55311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left; 55411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __nright = 55511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen); 55611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __left->_M_ref_nonnil(); 55711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 55811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { __result = _S_tree_concat(__left, __nright); } 55911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 56011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 56111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__left); 56211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__nright); 56311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 56411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 56511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 56611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 56711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 56811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __nright = 56911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->_M_get_allocator()); 57011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 57111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 57211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_ref_nonnil(); 57311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = _S_tree_concat(__r, __nright); 57411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 57511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 57611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 57711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__r); 57811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__nright); 57911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 58011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 58111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 58211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 58311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 58411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __GC 58511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 58611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename rope<_CharT,_Alloc>::_RopeRep* 58711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT,_Alloc>:: 58811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_destr_concat_char_iter(_RopeRep* __r, const _CharT* __s, size_t __slen) 58911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 59011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __result; 59111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __r) 59211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, 59311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_get_allocator()); 59411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __count = __r->_M_ref_count; 59511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __orig_size = __r->_M_size; 59611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__count > 1) 59711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _S_concat_char_iter(__r, __s, __slen); 59811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __slen) 59911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 60011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_ref_count = 2; // One more than before 60111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __r; 60211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 60311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__orig_size + __slen <= size_t(_S_copy_max) 60411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert && __detail::_S_leaf == __r->_M_tag) 60511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 60611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, 60711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __slen); 60811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 60911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 61011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__detail::_S_concat == __r->_M_tag) 61111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 61211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*) 61311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r)->_M_right); 61411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__detail::_S_leaf == __right->_M_tag 61511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert && __right->_M_size + __slen <= size_t(_S_copy_max)) 61611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 61711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __new_right = 61811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_destr_leaf_concat_char_iter(__right, __s, __slen); 61911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__right == __new_right) 62011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __new_right->_M_ref_count = 1; 62111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 62211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __right->_M_unref_nonnil(); 62311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_ref_count = 2; // One more than before. 62411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ((_RopeConcatenation*)__r)->_M_right = __new_right; 62511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_size = __orig_size + __slen; 62611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != __r->_M_c_string) 62711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 62811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_free_c_string(); 62911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_c_string = 0; 63011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 63111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __r; 63211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 63311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 63411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __right = 63511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->_M_get_allocator()); 63611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_ref_nonnil(); 63711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 63811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { __result = _S_tree_concat(__r, __right); } 63911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 64011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 64111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__r); 64211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__right); 64311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 64411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 64511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 64611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 64711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* !__GC */ 64811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 64911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 65011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename rope<_CharT, _Alloc>::_RopeRep* 65111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 65211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_concat(_RopeRep* __left, _RopeRep* __right) 65311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 65411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __left) 65511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 65611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_ref(__right); 65711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __right; 65811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 65911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __right) 66011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 66111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __left->_M_ref_nonnil(); 66211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __left; 66311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 66411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__detail::_S_leaf == __right->_M_tag) 66511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 66611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__detail::_S_leaf == __left->_M_tag) 66711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 66811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__right->_M_size + __left->_M_size <= size_t(_S_copy_max)) 66911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _S_leaf_concat_char_iter((_RopeLeaf*)__left, 67011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ((_RopeLeaf*)__right)->_M_data, 67111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __right->_M_size); 67211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 67311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else if (__detail::_S_concat == __left->_M_tag 67411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert && __detail::_S_leaf == ((_RopeConcatenation*) 67511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __left)->_M_right->_M_tag) 67611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 67711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __leftright = 67811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); 67911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__leftright->_M_size 68011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert + __right->_M_size <= size_t(_S_copy_max)) 68111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 68211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left; 68311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright, 68411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ((_RopeLeaf*) 68511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __right)-> 68611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_data, 68711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __right->_M_size); 68811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __leftleft->_M_ref_nonnil(); 68911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 69011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return(_S_tree_concat(__leftleft, __rest)); } 69111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 69211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 69311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__leftleft); 69411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__rest); 69511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 69611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 69711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 69811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 69911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 70011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __left->_M_ref_nonnil(); 70111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __right->_M_ref_nonnil(); 70211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 70311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return(_S_tree_concat(__left, __right)); } 70411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 70511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 70611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__left); 70711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__right); 70811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 70911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 71011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 71111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 71211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 71311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename rope<_CharT, _Alloc>::_RopeRep* 71411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 71511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_substring(_RopeRep* __base, size_t __start, size_t __endp1) 71611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 71711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __base) 71811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 0; 71911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __len = __base->_M_size; 72011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __adj_endp1; 72111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const size_t __lazy_threshold = 128; 72211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 72311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__endp1 >= __len) 72411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 72511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __start) 72611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 72711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __base->_M_ref_nonnil(); 72811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __base; 72911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 73011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 73111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __adj_endp1 = __len; 73211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 73311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 73411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 73511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __adj_endp1 = __endp1; 73611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 73711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert switch(__base->_M_tag) 73811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 73911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_concat: 74011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 74111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeConcatenation* __c = (_RopeConcatenation*)__base; 74211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __left = __c->_M_left; 74311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __right = __c->_M_right; 74411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __left_len = __left->_M_size; 74511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __result; 74611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 74711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__adj_endp1 <= __left_len) 74811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _S_substring(__left, __start, __endp1); 74911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else if (__start >= __left_len) 75011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _S_substring(__right, __start - __left_len, 75111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __adj_endp1 - __left_len); 75211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self_destruct_ptr __left_result(_S_substring(__left, 75311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __start, 75411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __left_len)); 75511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self_destruct_ptr __right_result(_S_substring(__right, 0, 75611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __endp1 75711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert - __left_len)); 75811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = _S_concat(__left_result, __right_result); 75911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 76011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 76111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_leaf: 76211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 76311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __l = (_RopeLeaf*)__base; 76411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __result; 76511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __result_len; 76611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__start >= __adj_endp1) 76711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 0; 76811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result_len = __adj_endp1 - __start; 76911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__result_len > __lazy_threshold) 77011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert goto lazy; 77111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef __GC 77211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _CharT* __section = __l->_M_data + __start; 77311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = _S_new_RopeLeaf(__section, __result_len, 77411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __base->_M_get_allocator()); 77511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result->_M_c_string = 0; // Not eos terminated. 77611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 77711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // We should sometimes create substring node instead. 77811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start, 77911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result_len, 78011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __base-> 78111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_allocator()); 78211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 78311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 78411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 78511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_substringfn: 78611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Avoid introducing multiple layers of substring nodes. 78711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 78811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeSubstring* __old = (_RopeSubstring*)__base; 78911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __result_len; 79011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__start >= __adj_endp1) 79111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 0; 79211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result_len = __adj_endp1 - __start; 79311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__result_len > __lazy_threshold) 79411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 79511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeSubstring* __result = 79611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_new_RopeSubstring(__old->_M_base, 79711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __start + __old->_M_start, 79811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __adj_endp1 - __start, 79911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __base->_M_get_allocator()); 80011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 80111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 80211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } // *** else fall through: *** 80311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 80411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_function: 80511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 80611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeFunction* __f = (_RopeFunction*)__base; 80711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* __section; 80811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __result_len; 80911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__start >= __adj_endp1) 81011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 0; 81111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result_len = __adj_endp1 - __start; 81211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 81311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__result_len > __lazy_threshold) 81411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert goto lazy; 81511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __section = (_CharT*) 81611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope::_Data_allocate(_S_rounded_up_size(__result_len)); 81711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 81811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { (*(__f->_M_fn))(__start, __result_len, __section); } 81911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 82011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 82111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep::__STL_FREE_STRING(__section, __result_len, 82211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __base->_M_get_allocator()); 82311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 82411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 82511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_cond_store_eos(__section[__result_len]); 82611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _S_new_RopeLeaf(__section, __result_len, 82711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __base->_M_get_allocator()); 82811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 82911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 83011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert lazy: 83111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 83211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Create substring node. 83311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start, 83411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __base->_M_get_allocator()); 83511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 83611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 83711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 83811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _CharT> 83911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Rope_flatten_char_consumer 84011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : public _Rope_char_consumer<_CharT> 84111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 84211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 84311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* _M_buf_ptr; 84411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 84511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 84611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_flatten_char_consumer(_CharT* __buffer) 84711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _M_buf_ptr = __buffer; }; 84811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 84911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Rope_flatten_char_consumer() {} 85011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 85111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 85211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(const _CharT* __leaf, size_t __n) 85311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 85411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert uninitialized_copy_n(__leaf, __n, _M_buf_ptr); 85511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_buf_ptr += __n; 85611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return true; 85711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 85811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 85911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 86011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _CharT> 86111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Rope_find_char_char_consumer 86211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : public _Rope_char_consumer<_CharT> 86311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 86411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 86511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT _M_pattern; 86611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 86711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t _M_count; // Number of nonmatching characters 86811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 86911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_find_char_char_consumer(_CharT __p) 87011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_pattern(__p), _M_count(0) {} 87111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 87211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Rope_find_char_char_consumer() {} 87311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 87411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 87511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(const _CharT* __leaf, size_t __n) 87611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 87711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __i; 87811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__i = 0; __i < __n; __i++) 87911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 88011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__leaf[__i] == _M_pattern) 88111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 88211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_count += __i; 88311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 88411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 88511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 88611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_count += __n; return true; 88711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 88811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 88911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 89011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _CharT, class _Traits> 89111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Here _CharT is both the stream and rope character type. 89211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert class _Rope_insert_char_consumer 89311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : public _Rope_char_consumer<_CharT> 89411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 89511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert private: 89611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef basic_ostream<_CharT,_Traits> _Insert_ostream; 89711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Insert_ostream& _M_o; 89811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert public: 89911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_insert_char_consumer(_Insert_ostream& __writer) 90011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _M_o(__writer) {}; 90111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert ~_Rope_insert_char_consumer() { }; 90211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Caller is presumed to own the ostream 90311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool operator() (const _CharT* __leaf, size_t __n); 90411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Returns true to continue traversal. 90511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert }; 90611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 90711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _CharT, class _Traits> 90811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 90911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_insert_char_consumer<_CharT, _Traits>:: 91011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator()(const _CharT* __leaf, size_t __n) 91111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 91211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __i; 91311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // We assume that formatting is set up correctly for each element. 91411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__i = 0; __i < __n; __i++) 91511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_o.put(__leaf[__i]); 91611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return true; 91711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 91811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 91911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 92011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool 92111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 92211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c, 92311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _RopeRep* __r, size_t __begin, size_t __end) 92411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 92511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __r) 92611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return true; 92711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert switch(__r->_M_tag) 92811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 92911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_concat: 93011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 93111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeConcatenation* __conc = (_RopeConcatenation*)__r; 93211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __left = __conc->_M_left; 93311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __left_len = __left->_M_size; 93411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__begin < __left_len) 93511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 93611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __left_end = std::min(__left_len, __end); 93711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!_S_apply_to_pieces(__c, __left, __begin, __left_end)) 93811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 93911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 94011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__end > __left_len) 94111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 94211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __right = __conc->_M_right; 94311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __right_start = std::max(__left_len, __begin); 94411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!_S_apply_to_pieces(__c, __right, 94511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __right_start - __left_len, 94611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __end - __left_len)) 94711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 94811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 94911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 95011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return true; 95111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_leaf: 95211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 95311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __l = (_RopeLeaf*)__r; 95411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __c(__l->_M_data + __begin, __end - __begin); 95511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 95611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_function: 95711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_substringfn: 95811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 95911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeFunction* __f = (_RopeFunction*)__r; 96011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __len = __end - __begin; 96111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __result; 96211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* __buffer = 96311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (_CharT*)_Alloc().allocate(__len * sizeof(_CharT)); 96411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 96511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 96611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (*(__f->_M_fn))(__begin, __len, __buffer); 96711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = __c(__buffer, __len); 96811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); 96911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 97011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 97111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 97211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); 97311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 97411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 97511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 97611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 97711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert default: 97811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return false; 97911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 98011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 98111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 98211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _CharT, class _Traits> 98311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 98411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n) 98511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 98611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert char __f = __o.fill(); 98711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __i; 98811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 98911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__i = 0; __i < __n; __i++) 99011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __o.put(__f); 99111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 99211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 99311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 99411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT> 99511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 99611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_is_simple(_CharT*) 99711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return false; } 99811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 99911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 100011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_is_simple(char*) 100111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return true; } 100211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 100311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline bool 100411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_is_simple(wchar_t*) 100511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return true; } 100611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 100711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _CharT, class _Traits, class _Alloc> 100811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert basic_ostream<_CharT, _Traits>& 100911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator<<(basic_ostream<_CharT, _Traits>& __o, 101011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const rope<_CharT, _Alloc>& __r) 101111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 101211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __w = __o.width(); 101311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __left = bool(__o.flags() & std::ios::left); 101411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __pad_len; 101511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __rope_len = __r.size(); 101611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_insert_char_consumer<_CharT, _Traits> __c(__o); 101711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __is_simple = _Rope_is_simple((_CharT*)0); 101811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 101911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__rope_len < __w) 102011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pad_len = __w - __rope_len; 102111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 102211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __pad_len = 0; 102311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 102411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__is_simple) 102511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __o.width(__w / __rope_len); 102611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 102711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 102811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__is_simple && !__left && __pad_len > 0) 102911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_fill(__o, __pad_len); 103011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r.apply_to_pieces(0, __r.size(), __c); 103111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__is_simple && __left && __pad_len > 0) 103211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_fill(__o, __pad_len); 103311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__is_simple) 103411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __o.width(__w); 103511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 103611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 103711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 103811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (!__is_simple) 103911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __o.width(__w); 104011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 104111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 104211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __o; 104311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 104411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 104511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 104611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* 104711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 104811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_flatten(_RopeRep* __r, size_t __start, size_t __len, 104911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* __buffer) 105011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 105111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_flatten_char_consumer<_CharT> __c(__buffer); 105211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_apply_to_pieces(__c, __r, __start, __start + __len); 105311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return(__buffer + __len); 105411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 105511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 105611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 105711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t 105811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 105911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert find(_CharT __pattern, size_t __start) const 106011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 106111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_find_char_char_consumer<_CharT> __c(__pattern); 106211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size()); 106311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_type __result_pos = __start + __c._M_count; 106411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __STL_OLD_ROPE_SEMANTICS 106511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__result_pos == size()) 106611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result_pos = npos; 106711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 106811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result_pos; 106911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 107011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 107111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 107211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* 107311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 107411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_flatten(_RopeRep* __r, _CharT* __buffer) 107511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 107611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __r) 107711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __buffer; 107811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert switch(__r->_M_tag) 107911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 108011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_concat: 108111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 108211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeConcatenation* __c = (_RopeConcatenation*)__r; 108311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __left = __c->_M_left; 108411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __right = __c->_M_right; 108511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* __rest = _S_flatten(__left, __buffer); 108611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _S_flatten(__right, __rest); 108711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 108811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_leaf: 108911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 109011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __l = (_RopeLeaf*)__r; 109111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return copy_n(__l->_M_data, __l->_M_size, __buffer).second; 109211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 109311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_function: 109411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_substringfn: 109511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // We don't yet do anything with substring nodes. 109611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // This needs to be fixed before ropefiles will work well. 109711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 109811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeFunction* __f = (_RopeFunction*)__r; 109911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (*(__f->_M_fn))(0, __f->_M_size, __buffer); 110011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __buffer + __f->_M_size; 110111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 110211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert default: 110311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 0; 110411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 110511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 110611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 110711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // This needs work for _CharT != char 110811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 110911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 111011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 111111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_dump(_RopeRep* __r, int __indent) 111211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 111311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (int __i = 0; __i < __indent; __i++) 111411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert putchar(' '); 111511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __r) 111611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 111711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert printf("NULL\n"); 111811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 111911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 112011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_S_concat == __r->_M_tag) 112111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 112211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeConcatenation* __c = (_RopeConcatenation*)__r; 112311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __left = __c->_M_left; 112411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __right = __c->_M_right; 112511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 112611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef __GC 112711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n", 112811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r, __r->_M_depth, __r->_M_size, 112911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_is_balanced? "" : "not"); 113011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 113111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert printf("Concatenation %p (rc = %ld, depth = %d, " 113211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert "len = %ld, %s balanced)\n", 113311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size, 113411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_is_balanced? "" : "not"); 113511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 113611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_dump(__left, __indent + 2); 113711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_dump(__right, __indent + 2); 113811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 113911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 114011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 114111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 114211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert char* __kind; 114311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 114411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert switch (__r->_M_tag) 114511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 114611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_leaf: 114711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __kind = "Leaf"; 114811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 114911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_function: 115011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __kind = "Function"; 115111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 115211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_substringfn: 115311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __kind = "Function representing substring"; 115411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 115511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert default: 115611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __kind = "(corrupted kind field!)"; 115711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 115811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifdef __GC 115911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert printf("%s %p (depth = %d, len = %ld) ", 116011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __kind, __r, __r->_M_depth, __r->_M_size); 116111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#else 116211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert printf("%s %p (rc = %ld, depth = %d, len = %ld) ", 116311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size); 116411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 116511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_S_is_one_byte_char_type((_CharT*)0)) 116611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 116711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const int __max_len = 40; 116811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len)); 116911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT __buffer[__max_len + 1]; 117011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert bool __too_big = __r->_M_size > __prefix->_M_size; 117111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 117211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_flatten(__prefix, __buffer); 117311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __buffer[__prefix->_M_size] = _S_eos((_CharT*)0); 117411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert printf("%s%s\n", (char*)__buffer, 117511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __too_big? "...\n" : "\n"); 117611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 117711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 117811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert printf("\n"); 117911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 118011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 118111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 118211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 118311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const unsigned long 118411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 118511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_min_len[int(__detail::_S_max_rope_depth) + 1] = { 118611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, 118711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, 118811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, 118911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368, 119011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811, 119111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309, 119211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352, 119311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155, 119411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 39 */165580141, /* 40 */267914296, /* 41 */433494437, 119511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903, 119611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert /* 45 */2971215073u }; 119711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // These are Fibonacci numbers < 2**32. 119811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 119911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 120011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typename rope<_CharT, _Alloc>::_RopeRep* 120111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 120211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_balance(_RopeRep* __r) 120311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 120411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __forest[int(__detail::_S_max_rope_depth) + 1]; 120511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __result = 0; 120611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int __i; 120711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Invariant: 120811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // The concatenation of forest in descending order is equal to __r. 120911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // __forest[__i]._M_size >= _S_min_len[__i] 121011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // __forest[__i]._M_depth = __i 121111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // References from forest are included in refcount. 121211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 121311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i) 121411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __forest[__i] = 0; 121511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 121611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 121711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_add_to_forest(__r, __forest); 121811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i) 121911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != __forest[__i]) 122011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 122111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __GC 122211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self_destruct_ptr __old(__result); 122311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 122411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = _S_concat(__forest[__i], __result); 122511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __forest[__i]->_M_unref_nonnil(); 122611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if !defined(__GC) && defined(__EXCEPTIONS) 122711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __forest[__i] = 0; 122811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 122911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 123011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 123111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 123211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 123311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for(__i = 0; __i <= int(__detail::_S_max_rope_depth); __i++) 123411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_unref(__forest[__i]); 123511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 123611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 123711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 123811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__result->_M_depth > int(__detail::_S_max_rope_depth)) 123911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_length_error(__N("rope::_S_balance")); 124011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return(__result); 124111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 124211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 124311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 124411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 124511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 124611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest) 124711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 124811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__r->_M_is_balanced) 124911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 125011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_add_leaf_to_forest(__r, __forest); 125111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 125211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 125311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 125411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 125511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeConcatenation* __c = (_RopeConcatenation*)__r; 125611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 125711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_add_to_forest(__c->_M_left, __forest); 125811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_add_to_forest(__c->_M_right, __forest); 125911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 126011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 126111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 126211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 126311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 126411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void 126511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 126611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest) 126711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 126811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __insertee; // included in refcount 126911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __too_tiny = 0; // included in refcount 127011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int __i; // forest[0..__i-1] is empty 127111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __s = __r->_M_size; 127211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 127311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) 127411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 127511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != __forest[__i]) 127611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 127711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __GC 127811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self_destruct_ptr __old(__too_tiny); 127911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 128011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __too_tiny = _S_concat_and_set_balanced(__forest[__i], 128111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __too_tiny); 128211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __forest[__i]->_M_unref_nonnil(); 128311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __forest[__i] = 0; 128411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 128511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 128611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 128711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __GC 128811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self_destruct_ptr __old(__too_tiny); 128911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 129011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __insertee = _S_concat_and_set_balanced(__too_tiny, __r); 129111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 129211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Too_tiny dead, and no longer included in refcount. 129311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Insertee is live and included. 129411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for (;; ++__i) 129511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 129611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != __forest[__i]) 129711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 129811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __GC 129911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self_destruct_ptr __old(__insertee); 130011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 130111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __insertee = _S_concat_and_set_balanced(__forest[__i], 130211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __insertee); 130311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __forest[__i]->_M_unref_nonnil(); 130411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __forest[__i] = 0; 130511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 130611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__i == int(__detail::_S_max_rope_depth) 130711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert || __insertee->_M_size < _S_min_len[__i+1]) 130811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 130911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __forest[__i] = __insertee; 131011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // refcount is OK since __insertee is now dead. 131111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 131211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 131311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 131411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 131511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 131611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 131711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT 131811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 131911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_fetch(_RopeRep* __r, size_type __i) 132011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 132111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __GC_CONST _CharT* __cstr = __r->_M_c_string; 132211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 132311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != __cstr) 132411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __cstr[__i]; 132511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for(;;) 132611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 132711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert switch(__r->_M_tag) 132811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 132911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_concat: 133011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 133111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeConcatenation* __c = (_RopeConcatenation*)__r; 133211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __left = __c->_M_left; 133311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __left_len = __left->_M_size; 133411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 133511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__i >= __left_len) 133611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 133711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __i -= __left_len; 133811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r = __c->_M_right; 133911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 134011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 134111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r = __left; 134211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 134311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 134411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_leaf: 134511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 134611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __l = (_RopeLeaf*)__r; 134711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __l->_M_data[__i]; 134811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 134911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_function: 135011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_substringfn: 135111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 135211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeFunction* __f = (_RopeFunction*)__r; 135311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT __result; 135411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 135511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert (*(__f->_M_fn))(__i, 1, &__result); 135611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __result; 135711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 135811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 135911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 136011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 136111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 136211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __GC 136311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Return a uniquely referenced character slot for the given 136411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // position, or 0 if that's not possible. 136511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 136611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* 136711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 136811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_fetch_ptr(_RopeRep* __r, size_type __i) 136911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 137011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __clrstack[__detail::_S_max_rope_depth]; 137111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __csptr = 0; 137211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 137311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert for(;;) 137411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 137511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__r->_M_ref_count > 1) 137611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 0; 137711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert switch(__r->_M_tag) 137811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 137911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_concat: 138011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 138111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeConcatenation* __c = (_RopeConcatenation*)__r; 138211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __left = __c->_M_left; 138311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __left_len = __left->_M_size; 138411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 138511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__c->_M_c_string != 0) 138611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __clrstack[__csptr++] = __c; 138711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__i >= __left_len) 138811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 138911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __i -= __left_len; 139011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r = __c->_M_right; 139111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 139211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 139311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r = __left; 139411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 139511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert break; 139611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_leaf: 139711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 139811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __l = (_RopeLeaf*)__r; 139911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0) 140011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __clrstack[__csptr++] = __l; 140111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert while (__csptr > 0) 140211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 140311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert -- __csptr; 140411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __d = __clrstack[__csptr]; 140511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __d->_M_free_c_string(); 140611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __d->_M_c_string = 0; 140711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 140811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return __l->_M_data + __i; 140911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 141011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_function: 141111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert case __detail::_S_substringfn: 141211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 0; 141311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 141411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 141511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 141611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif /* __GC */ 141711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 141811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // The following could be implemented trivially using 141911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // lexicographical_compare_3way. 142011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // We do a little more work to avoid dealing with rope iterators for 142111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // flat strings. 142211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 142311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert int 142411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 142511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_compare (const _RopeRep* __left, const _RopeRep* __right) 142611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 142711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __left_len; 142811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __right_len; 142911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 143011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __right) 143111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return 0 != __left; 143211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __left) 143311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return -1; 143411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __left_len = __left->_M_size; 143511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __right_len = __right->_M_size; 143611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__detail::_S_leaf == __left->_M_tag) 143711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 143811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __l = (_RopeLeaf*) __left; 143911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__detail::_S_leaf == __right->_M_tag) 144011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 144111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __r = (_RopeLeaf*) __right; 144211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return lexicographical_compare_3way(__l->_M_data, 144311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __l->_M_data + __left_len, 144411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_data, __r->_M_data 144511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert + __right_len); 144611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 144711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 144811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 144911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator __rstart(__right, 0); 145011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator __rend(__right, __right_len); 145111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return lexicographical_compare_3way(__l->_M_data, __l->_M_data 145211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert + __left_len, 145311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __rstart, __rend); 145411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 145511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 145611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 145711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 145811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator __lstart(__left, 0); 145911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator __lend(__left, __left_len); 146011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__detail::_S_leaf == __right->_M_tag) 146111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 146211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __r = (_RopeLeaf*) __right; 146311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return lexicographical_compare_3way(__lstart, __lend, 146411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r->_M_data, __r->_M_data 146511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert + __right_len); 146611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 146711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 146811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 146911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator __rstart(__right, 0); 147011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const_iterator __rend(__right, __right_len); 147111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return lexicographical_compare_3way(__lstart, __lend, 147211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __rstart, __rend); 147311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 147411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 147511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 147611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 147711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Assignment to reference proxies. 147811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 147911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_char_ref_proxy<_CharT, _Alloc>& 148011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_char_ref_proxy<_CharT, _Alloc>:: 148111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator=(_CharT __c) 148211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 148311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __old = _M_root->_M_tree_ptr; 148411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __GC 148511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // First check for the case in which everything is uniquely 148611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // referenced. In that case we can do this destructively. 148711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos); 148811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != __ptr) 148911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 149011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert *__ptr = __c; 149111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return *this; 149211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 149311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 149411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos)); 149511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1, 149611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __old->_M_size)); 149711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Self_destruct_ptr __result_left(_My_rope:: 149811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_destr_concat_char_iter(__left, 149911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert &__c, 1)); 150011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 150111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __result = _My_rope::_S_concat(__result_left, __right); 150211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#ifndef __GC 150311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep::_S_unref(__old); 150411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 150511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_root->_M_tree_ptr = __result; 150611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return *this; 150711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 150811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 150911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 151011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline _Rope_char_ref_proxy<_CharT, _Alloc>:: 151111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator _CharT() const 151211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 151311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (_M_current_valid) 151411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _M_current; 151511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 151611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos); 151711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 151811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 151911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 152011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_char_ptr_proxy<_CharT, _Alloc> 152111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_char_ref_proxy<_CharT, _Alloc>:: 152211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert operator&() const 152311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); } 152411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 152511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template <class _CharT, class _Alloc> 152611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 152711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope(size_t __n, _CharT __c, const allocator_type& __a) 152811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert : _Base(__a) 152911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 153011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT,_Alloc> __result; 153111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const size_t __exponentiate_threshold = 32; 153211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __exponent; 153311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __rest; 153411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* __rest_buffer; 153511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep* __remainder; 153611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc> __remainder_rope; 153711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 153811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __n) 153911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return; 154011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 154111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __exponent = __n / __exponentiate_threshold; 154211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __rest = __n % __exponentiate_threshold; 154311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __rest) 154411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __remainder = 0; 154511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 154611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 154711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest)); 154811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __uninitialized_fill_n_a(__rest_buffer, __rest, __c, 154911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_allocator()); 155011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_cond_store_eos(__rest_buffer[__rest]); 155111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 155211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, 155311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_allocator()); } 155411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 155511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 155611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, 155711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_allocator()); 155811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 155911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 156011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 156111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __remainder_rope._M_tree_ptr = __remainder; 156211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__exponent != 0) 156311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 156411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* __base_buffer = 156511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold)); 156611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeLeaf* __base_leaf; 156711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope __base_rope; 156811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c, 156911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_allocator()); 157011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_cond_store_eos(__base_buffer[__exponentiate_threshold]); 157111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __try 157211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 157311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __base_leaf = _S_new_RopeLeaf(__base_buffer, 157411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __exponentiate_threshold, 157511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_allocator()); 157611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 157711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __catch(...) 157811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 157911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _RopeRep::__STL_FREE_STRING(__base_buffer, 158011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __exponentiate_threshold, 158111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _M_get_allocator()); 158211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __throw_exception_again; 158311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 158411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __base_rope._M_tree_ptr = __base_leaf; 158511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (1 == __exponent) 158611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = __base_rope; 158711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 158811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = power(__base_rope, __exponent, 158911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_Concat_fn<_CharT, _Alloc>()); 159011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 159111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 != __remainder) 159211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result += __remainder_rope; 159311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 159411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert else 159511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = __remainder_rope; 159611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 159711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_tree_ptr = __result._M_tree_ptr; 159811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_tree_ptr->_M_ref_nonnil(); 159911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 160011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 160111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _CharT, class _Alloc> 160211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT 160311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>::_S_empty_c_str[1]; 160411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 160511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _CharT, class _Alloc> 160611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _CharT* 160711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>:: 160811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert c_str() const 160911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 161011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == this->_M_tree_ptr) 161111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 161211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_empty_c_str[0] = _S_eos((_CharT*)0); // Possibly redundant, 161311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // but probably fast. 161411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _S_empty_c_str; 161511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 161611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock); 161711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string; 161811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == __result) 161911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 162011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __s = size(); 162111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result = this->_Data_allocate(__s + 1); 162211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_flatten(this->_M_tree_ptr, __result); 162311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result[__s] = _S_eos((_CharT*)0); 162411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_tree_ptr->_M_c_string = __result; 162511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 162611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock); 162711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return(__result); 162811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 162911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 163011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _CharT, class _Alloc> 163111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert const _CharT* rope<_CharT, _Alloc>:: 163211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert replace_with_c_str() 163311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 163411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (0 == this->_M_tree_ptr) 163511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 163611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_empty_c_str[0] = _S_eos((_CharT*)0); 163711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return _S_empty_c_str; 163811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 163911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string; 164011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag 164111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert && 0 != __old_c_string) 164211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return(__old_c_string); 164311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert size_t __s = size(); 164411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s)); 164511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _S_flatten(this->_M_tree_ptr, __result); 164611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __result[__s] = _S_eos((_CharT*)0); 164711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_tree_ptr->_M_unref_nonnil(); 164811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s, 164911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert this->_M_get_allocator()); 165011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert return(__result); 165111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 165211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 165311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Algorithm specializations. More should be added. 165411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 165511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert template<class _Rope_iterator> // was templated on CharT and Alloc 165611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert void // VC++ workaround 165711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_rotate(_Rope_iterator __first, 165811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator __middle, 165911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator __last) 166011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { 166111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rope_iterator::value_type _CharT; 166211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert typedef typename _Rope_iterator::_allocator_type _Alloc; 166311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 166411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc>& __r(__first.container()); 166511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index()); 166611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc> __suffix = 166711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r.substr(__last.index(), __r.size() - __last.index()); 166811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc> __part1 = 166911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r.substr(__middle.index(), __last.index() - __middle.index()); 167011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rope<_CharT, _Alloc> __part2 = 167111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r.substr(__first.index(), __middle.index() - __first.index()); 167211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r = __prefix; 167311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r += __part1; 167411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r += __part2; 167511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert __r += __suffix; 167611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert } 167711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 167811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#if !defined(__GNUC__) 167911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Appears to confuse g++ 168011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 168111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rotate(_Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __first, 168211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __middle, 168311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __last) 168411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _Rope_rotate(__first, __middle, __last); } 168511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert#endif 168611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 168711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# if 0 168811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // Probably not useful for several reasons: 168911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // - for SGIs 7.1 compiler and probably some others, 169011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // this forces lots of rope<wchar_t, ...> instantiations, creating a 169111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // code bloat and compile time problem. (Fixed in 7.2.) 169211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // - wchar_t is 4 bytes wide on most UNIX platforms, making it 169311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // unattractive for unicode strings. Unsigned short may be a better 169411cd02dfb91661c65134cac258cf5924270e9d2Dan Albert // character type. 169511cd02dfb91661c65134cac258cf5924270e9d2Dan Albert inline void 169611cd02dfb91661c65134cac258cf5924270e9d2Dan Albert rotate(_Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first, 169711cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle, 169811cd02dfb91661c65134cac258cf5924270e9d2Dan Albert _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last) 169911cd02dfb91661c65134cac258cf5924270e9d2Dan Albert { _Rope_rotate(__first, __middle, __last); } 170011cd02dfb91661c65134cac258cf5924270e9d2Dan Albert# endif 170111cd02dfb91661c65134cac258cf5924270e9d2Dan Albert 170211cd02dfb91661c65134cac258cf5924270e9d2Dan Albert_GLIBCXX_END_NAMESPACE_VERSION 170311cd02dfb91661c65134cac258cf5924270e9d2Dan Albert} // namespace 1704