197403Sobrien// SGI's rope class implementation -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 597403Sobrien// 697403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 797403Sobrien// software; you can redistribute it and/or modify it under the 897403Sobrien// terms of the GNU General Public License as published by the 997403Sobrien// Free Software Foundation; either version 2, or (at your option) 1097403Sobrien// any later version. 1197403Sobrien 1297403Sobrien// This library is distributed in the hope that it will be useful, 1397403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1497403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1597403Sobrien// GNU General Public License for more details. 1697403Sobrien 1797403Sobrien// You should have received a copy of the GNU General Public License along 1897403Sobrien// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 2097403Sobrien// USA. 2197403Sobrien 2297403Sobrien// As a special exception, you may use this file as part of a free software 2397403Sobrien// library without restriction. Specifically, if other files instantiate 2497403Sobrien// templates or use macros or inline functions from this file, or you compile 2597403Sobrien// this file and link it with other files to produce an executable, this 2697403Sobrien// file does not by itself cause the resulting executable to be covered by 2797403Sobrien// the GNU General Public License. This exception does not however 2897403Sobrien// invalidate any other reasons why the executable file might be covered by 2997403Sobrien// the GNU General Public License. 3097403Sobrien 3197403Sobrien/* 3297403Sobrien * Copyright (c) 1997 3397403Sobrien * Silicon Graphics Computer Systems, Inc. 3497403Sobrien * 3597403Sobrien * Permission to use, copy, modify, distribute and sell this software 3697403Sobrien * and its documentation for any purpose is hereby granted without fee, 3797403Sobrien * provided that the above copyright notice appear in all copies and 3897403Sobrien * that both that copyright notice and this permission notice appear 3997403Sobrien * in supporting documentation. Silicon Graphics makes no 4097403Sobrien * representations about the suitability of this software for any 4197403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4297403Sobrien */ 4397403Sobrien 4497403Sobrien/** @file ropeimpl.h 4597403Sobrien * This is an internal header file, included by other library headers. 4697403Sobrien * You should not attempt to use it directly. 4797403Sobrien */ 4897403Sobrien 49132720Skan#include <cstdio> 50132720Skan#include <ostream> 5197403Sobrien#include <bits/functexcept.h> 5297403Sobrien 5397403Sobrien#include <ext/algorithm> // For copy_n and lexicographical_compare_3way 5497403Sobrien#include <ext/memory> // For uninitialized_copy_n 5597403Sobrien#include <ext/numeric> // For power 5697403Sobrien 57169691Skan_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 58169691Skan 59132720Skan using std::size_t; 60132720Skan using std::printf; 61132720Skan using std::basic_ostream; 62132720Skan using std::__throw_length_error; 63132720Skan using std::_Destroy; 64132720Skan using std::uninitialized_fill_n; 6597403Sobrien 66169691Skan // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf 67169691Skan // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct. 68169691Skan // Results in a valid buf_ptr if the iterator can be legitimately 69169691Skan // dereferenced. 70169691Skan template <class _CharT, class _Alloc> 71169691Skan void 72169691Skan _Rope_iterator_base<_CharT, _Alloc>:: 73169691Skan _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x) 74169691Skan { 75169691Skan const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index]; 76169691Skan size_t __leaf_pos = __x._M_leaf_pos; 77169691Skan size_t __pos = __x._M_current_pos; 7897403Sobrien 79169691Skan switch(__leaf->_M_tag) 80169691Skan { 81169691Skan case __detail::_S_leaf: 82169691Skan __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data; 83169691Skan __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos); 84169691Skan __x._M_buf_end = __x._M_buf_start + __leaf->_M_size; 85169691Skan break; 86169691Skan case __detail::_S_function: 87169691Skan case __detail::_S_substringfn: 88169691Skan { 89169691Skan size_t __len = _S_iterator_buf_len; 90169691Skan size_t __buf_start_pos = __leaf_pos; 91169691Skan size_t __leaf_end = __leaf_pos + __leaf->_M_size; 92169691Skan char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT, 93169691Skan _Alloc>*)__leaf)->_M_fn; 94169691Skan if (__buf_start_pos + __len <= __pos) 95169691Skan { 96169691Skan __buf_start_pos = __pos - __len / 4; 97169691Skan if (__buf_start_pos + __len > __leaf_end) 98169691Skan __buf_start_pos = __leaf_end - __len; 99169691Skan } 100169691Skan if (__buf_start_pos + __len > __leaf_end) 101169691Skan __len = __leaf_end - __buf_start_pos; 102169691Skan (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf); 103169691Skan __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos); 104169691Skan __x._M_buf_start = __x._M_tmp_buf; 105169691Skan __x._M_buf_end = __x._M_tmp_buf + __len; 106169691Skan } 107169691Skan break; 10897403Sobrien default: 10997403Sobrien break; 110169691Skan } 11197403Sobrien } 11297403Sobrien 113169691Skan // Set path and buffer inside a rope iterator. We assume that 114169691Skan // pos and root are already set. 115169691Skan template <class _CharT, class _Alloc> 116169691Skan void 117169691Skan _Rope_iterator_base<_CharT, _Alloc>:: 118169691Skan _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x) 119169691Skan { 120169691Skan const _RopeRep* __path[int(__detail::_S_max_rope_depth) + 1]; 121169691Skan const _RopeRep* __curr_rope; 122169691Skan int __curr_depth = -1; /* index into path */ 123169691Skan size_t __curr_start_pos = 0; 124169691Skan size_t __pos = __x._M_current_pos; 125169691Skan unsigned char __dirns = 0; // Bit vector marking right turns in the path 12697403Sobrien 127169691Skan if (__pos >= __x._M_root->_M_size) 128169691Skan { 129169691Skan __x._M_buf_ptr = 0; 130169691Skan return; 131169691Skan } 132169691Skan __curr_rope = __x._M_root; 133169691Skan if (0 != __curr_rope->_M_c_string) 134169691Skan { 135169691Skan /* Treat the root as a leaf. */ 136169691Skan __x._M_buf_start = __curr_rope->_M_c_string; 137169691Skan __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size; 138169691Skan __x._M_buf_ptr = __curr_rope->_M_c_string + __pos; 139169691Skan __x._M_path_end[0] = __curr_rope; 140169691Skan __x._M_leaf_index = 0; 141169691Skan __x._M_leaf_pos = 0; 142169691Skan return; 143169691Skan } 144169691Skan for(;;) 145169691Skan { 146169691Skan ++__curr_depth; 147169691Skan __path[__curr_depth] = __curr_rope; 148169691Skan switch(__curr_rope->_M_tag) 14997403Sobrien { 150169691Skan case __detail::_S_leaf: 151169691Skan case __detail::_S_function: 152169691Skan case __detail::_S_substringfn: 153169691Skan __x._M_leaf_pos = __curr_start_pos; 154169691Skan goto done; 155169691Skan case __detail::_S_concat: 156169691Skan { 157169691Skan _Rope_RopeConcatenation<_CharT, _Alloc>* __c = 158169691Skan (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope; 15997403Sobrien _RopeRep* __left = __c->_M_left; 16097403Sobrien size_t __left_len = __left->_M_size; 161132720Skan 16297403Sobrien __dirns <<= 1; 163169691Skan if (__pos >= __curr_start_pos + __left_len) 164169691Skan { 16597403Sobrien __dirns |= 1; 16697403Sobrien __curr_rope = __c->_M_right; 16797403Sobrien __curr_start_pos += __left_len; 168169691Skan } 169169691Skan else 170169691Skan __curr_rope = __left; 171169691Skan } 172169691Skan break; 17397403Sobrien } 17497403Sobrien } 175169691Skan done: 176169691Skan // Copy last section of path into _M_path_end. 17797403Sobrien { 17897403Sobrien int __i = -1; 179169691Skan int __j = __curr_depth + 1 - int(_S_path_cache_len); 18097403Sobrien 18197403Sobrien if (__j < 0) __j = 0; 182169691Skan while (__j <= __curr_depth) 183169691Skan __x._M_path_end[++__i] = __path[__j++]; 18497403Sobrien __x._M_leaf_index = __i; 18597403Sobrien } 18697403Sobrien __x._M_path_directions = __dirns; 18797403Sobrien _S_setbuf(__x); 188169691Skan } 18997403Sobrien 190169691Skan // Specialized version of the above. Assumes that 191169691Skan // the path cache is valid for the previous position. 192169691Skan template <class _CharT, class _Alloc> 193169691Skan void 194169691Skan _Rope_iterator_base<_CharT, _Alloc>:: 195169691Skan _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x) 196169691Skan { 197169691Skan int __current_index = __x._M_leaf_index; 198169691Skan const _RopeRep* __current_node = __x._M_path_end[__current_index]; 199169691Skan size_t __len = __current_node->_M_size; 200169691Skan size_t __node_start_pos = __x._M_leaf_pos; 201169691Skan unsigned char __dirns = __x._M_path_directions; 202169691Skan _Rope_RopeConcatenation<_CharT, _Alloc>* __c; 20397403Sobrien 204169691Skan if (__x._M_current_pos - __node_start_pos < __len) 205169691Skan { 206169691Skan /* More stuff in this leaf, we just didn't cache it. */ 207169691Skan _S_setbuf(__x); 208169691Skan return; 209169691Skan } 210169691Skan // node_start_pos is starting position of last_node. 211169691Skan while (--__current_index >= 0) 212169691Skan { 213169691Skan if (!(__dirns & 1) /* Path turned left */) 214169691Skan break; 215169691Skan __current_node = __x._M_path_end[__current_index]; 216169691Skan __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node; 217169691Skan // Otherwise we were in the right child. Thus we should pop 218169691Skan // the concatenation node. 219169691Skan __node_start_pos -= __c->_M_left->_M_size; 220169691Skan __dirns >>= 1; 221169691Skan } 222169691Skan if (__current_index < 0) 223169691Skan { 224169691Skan // We underflowed the cache. Punt. 225169691Skan _S_setcache(__x); 226169691Skan return; 227169691Skan } 228169691Skan __current_node = __x._M_path_end[__current_index]; 229169691Skan __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node; 230169691Skan // current_node is a concatenation node. We are positioned on the first 231169691Skan // character in its right child. 232169691Skan // node_start_pos is starting position of current_node. 233169691Skan __node_start_pos += __c->_M_left->_M_size; 234169691Skan __current_node = __c->_M_right; 235169691Skan __x._M_path_end[++__current_index] = __current_node; 236169691Skan __dirns |= 1; 237169691Skan while (__detail::_S_concat == __current_node->_M_tag) 238169691Skan { 239169691Skan ++__current_index; 240169691Skan if (int(_S_path_cache_len) == __current_index) 241169691Skan { 242169691Skan int __i; 243169691Skan for (__i = 0; __i < int(_S_path_cache_len) - 1; __i++) 24497403Sobrien __x._M_path_end[__i] = __x._M_path_end[__i+1]; 245169691Skan --__current_index; 24697403Sobrien } 247169691Skan __current_node = 248169691Skan ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left; 249169691Skan __x._M_path_end[__current_index] = __current_node; 250169691Skan __dirns <<= 1; 251169691Skan // node_start_pos is unchanged. 25297403Sobrien } 253169691Skan __x._M_leaf_index = __current_index; 254169691Skan __x._M_leaf_pos = __node_start_pos; 255169691Skan __x._M_path_directions = __dirns; 256169691Skan _S_setbuf(__x); 25797403Sobrien } 25897403Sobrien 259169691Skan template <class _CharT, class _Alloc> 260169691Skan void 261169691Skan _Rope_iterator_base<_CharT, _Alloc>:: 262169691Skan _M_incr(size_t __n) 263169691Skan { 264169691Skan _M_current_pos += __n; 265169691Skan if (0 != _M_buf_ptr) 266169691Skan { 267169691Skan size_t __chars_left = _M_buf_end - _M_buf_ptr; 268169691Skan if (__chars_left > __n) 269169691Skan _M_buf_ptr += __n; 270169691Skan else if (__chars_left == __n) 271169691Skan { 272169691Skan _M_buf_ptr += __n; 273169691Skan _S_setcache_for_incr(*this); 274169691Skan } 275169691Skan else 276169691Skan _M_buf_ptr = 0; 277169691Skan } 27897403Sobrien } 27997403Sobrien 280169691Skan template <class _CharT, class _Alloc> 281169691Skan void 282169691Skan _Rope_iterator_base<_CharT, _Alloc>:: 283169691Skan _M_decr(size_t __n) 284169691Skan { 285169691Skan if (0 != _M_buf_ptr) 286169691Skan { 287169691Skan size_t __chars_left = _M_buf_ptr - _M_buf_start; 288169691Skan if (__chars_left >= __n) 289169691Skan _M_buf_ptr -= __n; 290169691Skan else 291169691Skan _M_buf_ptr = 0; 292169691Skan } 293169691Skan _M_current_pos -= __n; 29497403Sobrien } 29597403Sobrien 296169691Skan template <class _CharT, class _Alloc> 297169691Skan void 298169691Skan _Rope_iterator<_CharT, _Alloc>:: 299169691Skan _M_check() 300169691Skan { 301169691Skan if (_M_root_rope->_M_tree_ptr != this->_M_root) 302169691Skan { 303169691Skan // _Rope was modified. Get things fixed up. 304169691Skan _RopeRep::_S_unref(this->_M_root); 305169691Skan this->_M_root = _M_root_rope->_M_tree_ptr; 306169691Skan _RopeRep::_S_ref(this->_M_root); 307169691Skan this->_M_buf_ptr = 0; 308169691Skan } 30997403Sobrien } 31097403Sobrien 311169691Skan template <class _CharT, class _Alloc> 312169691Skan inline 313169691Skan _Rope_const_iterator<_CharT, _Alloc>:: 314169691Skan _Rope_const_iterator(const _Rope_iterator<_CharT, _Alloc>& __x) 315169691Skan : _Rope_iterator_base<_CharT, _Alloc>(__x) 316169691Skan { } 31797403Sobrien 318169691Skan template <class _CharT, class _Alloc> 319169691Skan inline 320169691Skan _Rope_iterator<_CharT, _Alloc>:: 321169691Skan _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos) 322169691Skan : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos), 323169691Skan _M_root_rope(&__r) 324169691Skan { _RopeRep::_S_ref(this->_M_root); } 32597403Sobrien 326169691Skan template <class _CharT, class _Alloc> 327169691Skan inline size_t 328169691Skan rope<_CharT, _Alloc>:: 329169691Skan _S_char_ptr_len(const _CharT* __s) 330169691Skan { 331169691Skan const _CharT* __p = __s; 332169691Skan 333169691Skan while (!_S_is0(*__p)) 334169691Skan ++__p; 335169691Skan return (__p - __s); 336169691Skan } 33797403Sobrien 33897403Sobrien 33997403Sobrien#ifndef __GC 34097403Sobrien 341169691Skan template <class _CharT, class _Alloc> 342169691Skan inline void 343169691Skan _Rope_RopeRep<_CharT, _Alloc>:: 344169691Skan _M_free_c_string() 345169691Skan { 346169691Skan _CharT* __cstr = _M_c_string; 347169691Skan if (0 != __cstr) 348169691Skan { 349169691Skan size_t __size = this->_M_size + 1; 350169691Skan _Destroy(__cstr, __cstr + __size, get_allocator()); 351169691Skan this->_Data_deallocate(__cstr, __size); 352169691Skan } 35397403Sobrien } 35497403Sobrien 355169691Skan template <class _CharT, class _Alloc> 356169691Skan inline void 357169691Skan _Rope_RopeRep<_CharT, _Alloc>:: 358169691Skan _S_free_string(_CharT* __s, size_t __n, allocator_type __a) 359169691Skan { 360169691Skan if (!_S_is_basic_char_type((_CharT*)0)) 361169691Skan _Destroy(__s, __s + __n, __a); 362169691Skan 363169691Skan // This has to be a static member, so this gets a bit messy 364169691Skan __a.deallocate(__s, 365169691Skan _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n)); 36697403Sobrien } 36797403Sobrien 368169691Skan // There are several reasons for not doing this with virtual destructors 369169691Skan // and a class specific delete operator: 370169691Skan // - A class specific delete operator can't easily get access to 371169691Skan // allocator instances if we need them. 372169691Skan // - Any virtual function would need a 4 or byte vtable pointer; 373169691Skan // this only requires a one byte tag per object. 374169691Skan template <class _CharT, class _Alloc> 375169691Skan void 376169691Skan _Rope_RopeRep<_CharT, _Alloc>:: 377169691Skan _M_free_tree() 378169691Skan { 379169691Skan switch(_M_tag) 380169691Skan { 381169691Skan case __detail::_S_leaf: 382169691Skan { 383169691Skan _Rope_RopeLeaf<_CharT, _Alloc>* __l 384169691Skan = (_Rope_RopeLeaf<_CharT, _Alloc>*)this; 385211755Srpaulo __l->template _Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf(); 386169691Skan _L_deallocate(__l, 1); 387169691Skan break; 388169691Skan } 389169691Skan case __detail::_S_concat: 390169691Skan { 391169691Skan _Rope_RopeConcatenation<_CharT,_Alloc>* __c 392169691Skan = (_Rope_RopeConcatenation<_CharT, _Alloc>*)this; 393211755Srpaulo __c->template _Rope_RopeConcatenation<_CharT, _Alloc>:: 394169691Skan ~_Rope_RopeConcatenation(); 395169691Skan _C_deallocate(__c, 1); 396169691Skan break; 397169691Skan } 398169691Skan case __detail::_S_function: 399169691Skan { 400169691Skan _Rope_RopeFunction<_CharT, _Alloc>* __f 401169691Skan = (_Rope_RopeFunction<_CharT, _Alloc>*)this; 402211755Srpaulo __f->template _Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction(); 403169691Skan _F_deallocate(__f, 1); 404169691Skan break; 405169691Skan } 406169691Skan case __detail::_S_substringfn: 407169691Skan { 408169691Skan _Rope_RopeSubstring<_CharT, _Alloc>* __ss = 409169691Skan (_Rope_RopeSubstring<_CharT, _Alloc>*)this; 410211755Srpaulo __ss->template _Rope_RopeSubstring<_CharT, _Alloc>:: 411169691Skan ~_Rope_RopeSubstring(); 412169691Skan _S_deallocate(__ss, 1); 413169691Skan break; 414169691Skan } 415169691Skan } 41697403Sobrien } 41797403Sobrien#else 41897403Sobrien 419169691Skan template <class _CharT, class _Alloc> 420169691Skan inline void 421169691Skan _Rope_RopeRep<_CharT, _Alloc>:: 422169691Skan _S_free_string(const _CharT*, size_t, allocator_type) 423169691Skan { } 42497403Sobrien 42597403Sobrien#endif 42697403Sobrien 427169691Skan // Concatenate a C string onto a leaf rope by copying the rope data. 428169691Skan // Used for short ropes. 429169691Skan template <class _CharT, class _Alloc> 430169691Skan typename rope<_CharT, _Alloc>::_RopeLeaf* 431169691Skan rope<_CharT, _Alloc>:: 432169691Skan _S_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, size_t __len) 433169691Skan { 434169691Skan size_t __old_len = __r->_M_size; 435169691Skan _CharT* __new_data = (_CharT*) 436211755Srpaulo _Rope_rep_base<_CharT, _Alloc>::_Data_allocate(_S_rounded_up_size(__old_len + __len)); 437169691Skan _RopeLeaf* __result; 43897403Sobrien 439169691Skan uninitialized_copy_n(__r->_M_data, __old_len, __new_data); 440169691Skan uninitialized_copy_n(__iter, __len, __new_data + __old_len); 441169691Skan _S_cond_store_eos(__new_data[__old_len + __len]); 442169691Skan try 443169691Skan { 444169691Skan __result = _S_new_RopeLeaf(__new_data, __old_len + __len, 445169691Skan __r->get_allocator()); 446169691Skan } 447169691Skan catch(...) 448169691Skan { 449169691Skan _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len, 450169691Skan __r->get_allocator()); 451169691Skan __throw_exception_again; 452169691Skan } 453169691Skan return __result; 45497403Sobrien } 45597403Sobrien 45697403Sobrien#ifndef __GC 457169691Skan // As above, but it's OK to clobber original if refcount is 1 458169691Skan template <class _CharT, class _Alloc> 459169691Skan typename rope<_CharT,_Alloc>::_RopeLeaf* 460169691Skan rope<_CharT, _Alloc>:: 461169691Skan _S_destr_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, 462169691Skan size_t __len) 463169691Skan { 464169691Skan if (__r->_M_ref_count > 1) 465169691Skan return _S_leaf_concat_char_iter(__r, __iter, __len); 466169691Skan size_t __old_len = __r->_M_size; 467169691Skan if (_S_allocated_capacity(__old_len) >= __old_len + __len) 468169691Skan { 469169691Skan // The space has been partially initialized for the standard 470169691Skan // character types. But that doesn't matter for those types. 471169691Skan uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len); 472169691Skan if (_S_is_basic_char_type((_CharT*)0)) 47397403Sobrien _S_cond_store_eos(__r->_M_data[__old_len + __len]); 474169691Skan else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) 475169691Skan { 476169691Skan __r->_M_free_c_string(); 477169691Skan __r->_M_c_string = 0; 478169691Skan } 479169691Skan __r->_M_size = __old_len + __len; 480169691Skan __r->_M_ref_count = 2; 481169691Skan return __r; 48297403Sobrien } 483169691Skan else 484169691Skan { 485169691Skan _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len); 486169691Skan return __result; 487169691Skan } 48897403Sobrien } 48997403Sobrien#endif 49097403Sobrien 491169691Skan // Assumes left and right are not 0. 492169691Skan // Does not increment (nor decrement on exception) child reference counts. 493169691Skan // Result has ref count 1. 494169691Skan template <class _CharT, class _Alloc> 495169691Skan typename rope<_CharT, _Alloc>::_RopeRep* 496169691Skan rope<_CharT, _Alloc>:: 497169691Skan _S_tree_concat(_RopeRep* __left, _RopeRep* __right) 498169691Skan { 499169691Skan _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right, 500169691Skan __left-> 501169691Skan get_allocator()); 502169691Skan size_t __depth = __result->_M_depth; 503169691Skan 504169691Skan if (__depth > 20 505169691Skan && (__result->_M_size < 1000 506169691Skan || __depth > size_t(__detail::_S_max_rope_depth))) 507169691Skan { 508169691Skan _RopeRep* __balanced; 509132720Skan 510169691Skan try 511169691Skan { 512169691Skan __balanced = _S_balance(__result); 513169691Skan __result->_M_unref_nonnil(); 514169691Skan } 515169691Skan catch(...) 516169691Skan { 517169691Skan _C_deallocate(__result,1); 518169691Skan __throw_exception_again; 519169691Skan } 520169691Skan // In case of exception, we need to deallocate 521169691Skan // otherwise dangling result node. But caller 522169691Skan // still owns its children. Thus unref is 523169691Skan // inappropriate. 524169691Skan return __balanced; 525169691Skan } 526169691Skan else 527169691Skan return __result; 528169691Skan } 529169691Skan 530169691Skan template <class _CharT, class _Alloc> 531169691Skan typename rope<_CharT, _Alloc>::_RopeRep* 532169691Skan rope<_CharT, _Alloc>:: 533169691Skan _S_concat_char_iter(_RopeRep* __r, const _CharT*__s, size_t __slen) 53497403Sobrien { 535169691Skan _RopeRep* __result; 536169691Skan if (0 == __slen) 537169691Skan { 538169691Skan _S_ref(__r); 539169691Skan return __r; 540169691Skan } 541169691Skan if (0 == __r) 542169691Skan return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, 543169691Skan __r->get_allocator()); 544169691Skan if (__r->_M_tag == __detail::_S_leaf 545169691Skan && __r->_M_size + __slen <= size_t(_S_copy_max)) 546169691Skan { 547169691Skan __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); 548169691Skan return __result; 549169691Skan } 550169691Skan if (__detail::_S_concat == __r->_M_tag 551169691Skan && __detail::_S_leaf == ((_RopeConcatenation*) __r)->_M_right->_M_tag) 552169691Skan { 553169691Skan _RopeLeaf* __right = 554169691Skan (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right); 555169691Skan if (__right->_M_size + __slen <= size_t(_S_copy_max)) 556169691Skan { 557169691Skan _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left; 558169691Skan _RopeRep* __nright = 559169691Skan _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen); 560169691Skan __left->_M_ref_nonnil(); 561169691Skan try 562169691Skan { __result = _S_tree_concat(__left, __nright); } 563169691Skan catch(...) 564169691Skan { 565169691Skan _S_unref(__left); 566169691Skan _S_unref(__nright); 567169691Skan __throw_exception_again; 568169691Skan } 569169691Skan return __result; 570169691Skan } 571169691Skan } 572169691Skan _RopeRep* __nright = 573169691Skan __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); 574132720Skan try 57597403Sobrien { 576169691Skan __r->_M_ref_nonnil(); 577169691Skan __result = _S_tree_concat(__r, __nright); 578169691Skan } 57997403Sobrien catch(...) 580132720Skan { 581169691Skan _S_unref(__r); 582169691Skan _S_unref(__nright); 58397403Sobrien __throw_exception_again; 58497403Sobrien } 585169691Skan return __result; 586132720Skan } 58797403Sobrien 588169691Skan#ifndef __GC 589169691Skan template <class _CharT, class _Alloc> 590169691Skan typename rope<_CharT,_Alloc>::_RopeRep* 591169691Skan rope<_CharT,_Alloc>:: 592169691Skan _S_destr_concat_char_iter(_RopeRep* __r, const _CharT* __s, size_t __slen) 593169691Skan { 594169691Skan _RopeRep* __result; 595169691Skan if (0 == __r) 596169691Skan return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, 597169691Skan __r->get_allocator()); 598169691Skan size_t __count = __r->_M_ref_count; 599169691Skan size_t __orig_size = __r->_M_size; 600169691Skan if (__count > 1) 601169691Skan return _S_concat_char_iter(__r, __s, __slen); 602169691Skan if (0 == __slen) 603169691Skan { 604169691Skan __r->_M_ref_count = 2; // One more than before 605169691Skan return __r; 606169691Skan } 607169691Skan if (__orig_size + __slen <= size_t(_S_copy_max) 608169691Skan && __detail::_S_leaf == __r->_M_tag) 609169691Skan { 610169691Skan __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, 611169691Skan __slen); 612169691Skan return __result; 613169691Skan } 614169691Skan if (__detail::_S_concat == __r->_M_tag) 615169691Skan { 616169691Skan _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*) 617169691Skan __r)->_M_right); 618169691Skan if (__detail::_S_leaf == __right->_M_tag 619169691Skan && __right->_M_size + __slen <= size_t(_S_copy_max)) 620169691Skan { 621169691Skan _RopeRep* __new_right = 622169691Skan _S_destr_leaf_concat_char_iter(__right, __s, __slen); 623169691Skan if (__right == __new_right) 624169691Skan __new_right->_M_ref_count = 1; 625169691Skan else 626169691Skan __right->_M_unref_nonnil(); 627169691Skan __r->_M_ref_count = 2; // One more than before. 628169691Skan ((_RopeConcatenation*)__r)->_M_right = __new_right; 629169691Skan __r->_M_size = __orig_size + __slen; 630169691Skan if (0 != __r->_M_c_string) 631169691Skan { 632169691Skan __r->_M_free_c_string(); 633169691Skan __r->_M_c_string = 0; 634169691Skan } 635169691Skan return __r; 636169691Skan } 637169691Skan } 638169691Skan _RopeRep* __right = 639169691Skan __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); 640169691Skan __r->_M_ref_nonnil(); 641169691Skan try 642169691Skan { __result = _S_tree_concat(__r, __right); } 643169691Skan catch(...) 644169691Skan { 645169691Skan _S_unref(__r); 646169691Skan _S_unref(__right); 647169691Skan __throw_exception_again; 648169691Skan } 649169691Skan return __result; 65097403Sobrien } 651169691Skan#endif /* !__GC */ 652169691Skan 653169691Skan template <class _CharT, class _Alloc> 654169691Skan typename rope<_CharT, _Alloc>::_RopeRep* 655169691Skan rope<_CharT, _Alloc>:: 656169691Skan _S_concat(_RopeRep* __left, _RopeRep* __right) 657169691Skan { 658169691Skan if (0 == __left) 659169691Skan { 660169691Skan _S_ref(__right); 661169691Skan return __right; 662169691Skan } 663169691Skan if (0 == __right) 664169691Skan { 66597403Sobrien __left->_M_ref_nonnil(); 666169691Skan return __left; 667169691Skan } 668169691Skan if (__detail::_S_leaf == __right->_M_tag) 669169691Skan { 670169691Skan if (__detail::_S_leaf == __left->_M_tag) 67197403Sobrien { 672169691Skan if (__right->_M_size + __left->_M_size <= size_t(_S_copy_max)) 673169691Skan return _S_leaf_concat_char_iter((_RopeLeaf*)__left, 674169691Skan ((_RopeLeaf*)__right)->_M_data, 675169691Skan __right->_M_size); 67697403Sobrien } 677169691Skan else if (__detail::_S_concat == __left->_M_tag 678169691Skan && __detail::_S_leaf == ((_RopeConcatenation*) 679169691Skan __left)->_M_right->_M_tag) 680169691Skan { 681169691Skan _RopeLeaf* __leftright = 682169691Skan (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); 683169691Skan if (__leftright->_M_size 684169691Skan + __right->_M_size <= size_t(_S_copy_max)) 685169691Skan { 686169691Skan _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left; 687169691Skan _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright, 688169691Skan ((_RopeLeaf*) 689169691Skan __right)-> 690169691Skan _M_data, 691169691Skan __right->_M_size); 692169691Skan __leftleft->_M_ref_nonnil(); 693169691Skan try 694169691Skan { return(_S_tree_concat(__leftleft, __rest)); } 695169691Skan catch(...) 696169691Skan { 697169691Skan _S_unref(__leftleft); 698169691Skan _S_unref(__rest); 699169691Skan __throw_exception_again; 700169691Skan } 701169691Skan } 702169691Skan } 70397403Sobrien } 704169691Skan __left->_M_ref_nonnil(); 705169691Skan __right->_M_ref_nonnil(); 706169691Skan try 707169691Skan { return(_S_tree_concat(__left, __right)); } 708169691Skan catch(...) 709169691Skan { 710169691Skan _S_unref(__left); 711169691Skan _S_unref(__right); 712169691Skan __throw_exception_again; 713169691Skan } 71497403Sobrien } 71597403Sobrien 716169691Skan template <class _CharT, class _Alloc> 717169691Skan typename rope<_CharT, _Alloc>::_RopeRep* 718169691Skan rope<_CharT, _Alloc>:: 719169691Skan _S_substring(_RopeRep* __base, size_t __start, size_t __endp1) 720169691Skan { 721169691Skan if (0 == __base) 722169691Skan return 0; 723169691Skan size_t __len = __base->_M_size; 724169691Skan size_t __adj_endp1; 725169691Skan const size_t __lazy_threshold = 128; 726169691Skan 727169691Skan if (__endp1 >= __len) 728169691Skan { 729169691Skan if (0 == __start) 730169691Skan { 731169691Skan __base->_M_ref_nonnil(); 732169691Skan return __base; 733169691Skan } 734132720Skan else 735169691Skan __adj_endp1 = __len; 736169691Skan 73797403Sobrien } 738169691Skan else 739169691Skan __adj_endp1 = __endp1; 74097403Sobrien 741169691Skan switch(__base->_M_tag) 742169691Skan { 743169691Skan case __detail::_S_concat: 744169691Skan { 745169691Skan _RopeConcatenation* __c = (_RopeConcatenation*)__base; 746169691Skan _RopeRep* __left = __c->_M_left; 747169691Skan _RopeRep* __right = __c->_M_right; 748169691Skan size_t __left_len = __left->_M_size; 749169691Skan _RopeRep* __result; 750169691Skan 751169691Skan if (__adj_endp1 <= __left_len) 752169691Skan return _S_substring(__left, __start, __endp1); 753169691Skan else if (__start >= __left_len) 754169691Skan return _S_substring(__right, __start - __left_len, 755169691Skan __adj_endp1 - __left_len); 756169691Skan _Self_destruct_ptr __left_result(_S_substring(__left, 757169691Skan __start, 758169691Skan __left_len)); 759169691Skan _Self_destruct_ptr __right_result(_S_substring(__right, 0, 760169691Skan __endp1 761169691Skan - __left_len)); 762169691Skan __result = _S_concat(__left_result, __right_result); 763169691Skan return __result; 764169691Skan } 765169691Skan case __detail::_S_leaf: 766169691Skan { 767169691Skan _RopeLeaf* __l = (_RopeLeaf*)__base; 768169691Skan _RopeLeaf* __result; 769169691Skan size_t __result_len; 770169691Skan if (__start >= __adj_endp1) 771169691Skan return 0; 772169691Skan __result_len = __adj_endp1 - __start; 773169691Skan if (__result_len > __lazy_threshold) 774169691Skan goto lazy; 775169691Skan#ifdef __GC 776169691Skan const _CharT* __section = __l->_M_data + __start; 777169691Skan __result = _S_new_RopeLeaf(__section, __result_len, 778169691Skan __base->get_allocator()); 779169691Skan __result->_M_c_string = 0; // Not eos terminated. 780169691Skan#else 781169691Skan // We should sometimes create substring node instead. 782169691Skan __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start, 783169691Skan __result_len, 784169691Skan __base-> 785169691Skan get_allocator()); 786169691Skan#endif 787169691Skan return __result; 78897403Sobrien } 789169691Skan case __detail::_S_substringfn: 790169691Skan // Avoid introducing multiple layers of substring nodes. 791169691Skan { 792169691Skan _RopeSubstring* __old = (_RopeSubstring*)__base; 793169691Skan size_t __result_len; 794169691Skan if (__start >= __adj_endp1) 795169691Skan return 0; 796169691Skan __result_len = __adj_endp1 - __start; 797169691Skan if (__result_len > __lazy_threshold) 798169691Skan { 799169691Skan _RopeSubstring* __result = 800169691Skan _S_new_RopeSubstring(__old->_M_base, 801169691Skan __start + __old->_M_start, 802169691Skan __adj_endp1 - __start, 803169691Skan __base->get_allocator()); 804169691Skan return __result; 805169691Skan 806169691Skan } // *** else fall through: *** 807169691Skan } 808169691Skan case __detail::_S_function: 809169691Skan { 810169691Skan _RopeFunction* __f = (_RopeFunction*)__base; 811169691Skan _CharT* __section; 812169691Skan size_t __result_len; 813169691Skan if (__start >= __adj_endp1) 814169691Skan return 0; 815169691Skan __result_len = __adj_endp1 - __start; 816169691Skan 817169691Skan if (__result_len > __lazy_threshold) 818169691Skan goto lazy; 819169691Skan __section = (_CharT*) 820211755Srpaulo _Rope_rep_base<_CharT, _Alloc>::_Data_allocate(_S_rounded_up_size(__result_len)); 821169691Skan try 822169691Skan { (*(__f->_M_fn))(__start, __result_len, __section); } 82397403Sobrien catch(...) 82497403Sobrien { 825169691Skan _RopeRep::__STL_FREE_STRING(__section, __result_len, 826169691Skan __base->get_allocator()); 82797403Sobrien __throw_exception_again; 82897403Sobrien } 829169691Skan _S_cond_store_eos(__section[__result_len]); 830169691Skan return _S_new_RopeLeaf(__section, __result_len, 831169691Skan __base->get_allocator()); 83297403Sobrien } 83397403Sobrien } 834169691Skan lazy: 83597403Sobrien { 83697403Sobrien // Create substring node. 83797403Sobrien return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start, 838169691Skan __base->get_allocator()); 839169691Skan } 84097403Sobrien } 84197403Sobrien 842169691Skan template<class _CharT> 843169691Skan class _Rope_flatten_char_consumer 844169691Skan : public _Rope_char_consumer<_CharT> 845169691Skan { 84697403Sobrien private: 847169691Skan _CharT* _M_buf_ptr; 84897403Sobrien public: 849169691Skan 850169691Skan _Rope_flatten_char_consumer(_CharT* __buffer) 851169691Skan { _M_buf_ptr = __buffer; }; 85297403Sobrien 853169691Skan ~_Rope_flatten_char_consumer() {} 854169691Skan 855169691Skan bool 856169691Skan operator()(const _CharT* __leaf, size_t __n) 857169691Skan { 858169691Skan uninitialized_copy_n(__leaf, __n, _M_buf_ptr); 859169691Skan _M_buf_ptr += __n; 860169691Skan return true; 861169691Skan } 862169691Skan }; 863132720Skan 864169691Skan template<class _CharT> 865169691Skan class _Rope_find_char_char_consumer 866169691Skan : public _Rope_char_consumer<_CharT> 867169691Skan { 86897403Sobrien private: 869169691Skan _CharT _M_pattern; 87097403Sobrien public: 871169691Skan size_t _M_count; // Number of nonmatching characters 872169691Skan 873169691Skan _Rope_find_char_char_consumer(_CharT __p) 874169691Skan : _M_pattern(__p), _M_count(0) {} 875169691Skan 876169691Skan ~_Rope_find_char_char_consumer() {} 877169691Skan 878169691Skan bool 879169691Skan operator()(const _CharT* __leaf, size_t __n) 880169691Skan { 881169691Skan size_t __i; 882169691Skan for (__i = 0; __i < __n; __i++) 883169691Skan { 884169691Skan if (__leaf[__i] == _M_pattern) 885169691Skan { 886169691Skan _M_count += __i; 887169691Skan return false; 888169691Skan } 889169691Skan } 890169691Skan _M_count += __n; return true; 891169691Skan } 892169691Skan }; 893132720Skan 89497403Sobrien template<class _CharT, class _Traits> 89597403Sobrien // Here _CharT is both the stream and rope character type. 896169691Skan class _Rope_insert_char_consumer 897169691Skan : public _Rope_char_consumer<_CharT> 898169691Skan { 89997403Sobrien private: 900169691Skan typedef basic_ostream<_CharT,_Traits> _Insert_ostream; 901169691Skan _Insert_ostream& _M_o; 90297403Sobrien public: 903169691Skan _Rope_insert_char_consumer(_Insert_ostream& __writer) 904169691Skan : _M_o(__writer) {}; 905169691Skan ~_Rope_insert_char_consumer() { }; 906169691Skan // Caller is presumed to own the ostream 907169691Skan bool operator() (const _CharT* __leaf, size_t __n); 908169691Skan // Returns true to continue traversal. 909169691Skan }; 910132720Skan 911169691Skan template<class _CharT, class _Traits> 912169691Skan bool 913169691Skan _Rope_insert_char_consumer<_CharT, _Traits>:: 914169691Skan operator()(const _CharT* __leaf, size_t __n) 915169691Skan { 916169691Skan size_t __i; 917169691Skan // We assume that formatting is set up correctly for each element. 918169691Skan for (__i = 0; __i < __n; __i++) 919169691Skan _M_o.put(__leaf[__i]); 920169691Skan return true; 921169691Skan } 92297403Sobrien 923169691Skan template <class _CharT, class _Alloc> 924169691Skan bool 925169691Skan rope<_CharT, _Alloc>:: 926169691Skan _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c, 927169691Skan const _RopeRep* __r, size_t __begin, size_t __end) 928169691Skan { 929169691Skan if (0 == __r) 930169691Skan return true; 931169691Skan switch(__r->_M_tag) 932169691Skan { 933169691Skan case __detail::_S_concat: 934169691Skan { 935169691Skan _RopeConcatenation* __conc = (_RopeConcatenation*)__r; 936169691Skan _RopeRep* __left = __conc->_M_left; 937169691Skan size_t __left_len = __left->_M_size; 938169691Skan if (__begin < __left_len) 939169691Skan { 940169691Skan size_t __left_end = std::min(__left_len, __end); 941169691Skan if (!_S_apply_to_pieces(__c, __left, __begin, __left_end)) 942169691Skan return false; 943169691Skan } 944169691Skan if (__end > __left_len) 945169691Skan { 946169691Skan _RopeRep* __right = __conc->_M_right; 947169691Skan size_t __right_start = std::max(__left_len, __begin); 948169691Skan if (!_S_apply_to_pieces(__c, __right, 949169691Skan __right_start - __left_len, 950169691Skan __end - __left_len)) 951169691Skan return false; 952169691Skan } 953169691Skan } 954169691Skan return true; 955169691Skan case __detail::_S_leaf: 956169691Skan { 957169691Skan _RopeLeaf* __l = (_RopeLeaf*)__r; 958169691Skan return __c(__l->_M_data + __begin, __end - __begin); 959169691Skan } 960169691Skan case __detail::_S_function: 961169691Skan case __detail::_S_substringfn: 96297403Sobrien { 963169691Skan _RopeFunction* __f = (_RopeFunction*)__r; 964169691Skan size_t __len = __end - __begin; 965169691Skan bool __result; 966169691Skan _CharT* __buffer = 967169691Skan (_CharT*)_Alloc().allocate(__len * sizeof(_CharT)); 968169691Skan try 969169691Skan { 97097403Sobrien (*(__f->_M_fn))(__begin, __len, __buffer); 97197403Sobrien __result = __c(__buffer, __len); 972132720Skan _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); 97397403Sobrien } 974169691Skan catch(...) 975169691Skan { 976169691Skan _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); 977169691Skan __throw_exception_again; 978169691Skan } 979169691Skan return __result; 98097403Sobrien } 98197403Sobrien default: 98297403Sobrien return false; 983169691Skan } 98497403Sobrien } 98597403Sobrien 98697403Sobrien template<class _CharT, class _Traits> 987169691Skan inline void 988169691Skan _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n) 989169691Skan { 990169691Skan char __f = __o.fill(); 991169691Skan size_t __i; 992169691Skan 993169691Skan for (__i = 0; __i < __n; __i++) 994169691Skan __o.put(__f); 995169691Skan } 99697403Sobrien 99797403Sobrien 998169691Skan template <class _CharT> 999169691Skan inline bool 1000169691Skan _Rope_is_simple(_CharT*) 1001169691Skan { return false; } 1002132720Skan 1003169691Skan inline bool 1004169691Skan _Rope_is_simple(char*) 1005169691Skan { return true; } 100697403Sobrien 1007169691Skan inline bool 1008169691Skan _Rope_is_simple(wchar_t*) 1009169691Skan { return true; } 1010169691Skan 1011169691Skan template<class _CharT, class _Traits, class _Alloc> 1012169691Skan basic_ostream<_CharT, _Traits>& 1013169691Skan operator<<(basic_ostream<_CharT, _Traits>& __o, 1014169691Skan const rope<_CharT, _Alloc>& __r) 1015169691Skan { 1016169691Skan size_t __w = __o.width(); 1017169691Skan bool __left = bool(__o.flags() & std::ios::left); 1018169691Skan size_t __pad_len; 1019169691Skan size_t __rope_len = __r.size(); 102097403Sobrien _Rope_insert_char_consumer<_CharT, _Traits> __c(__o); 1021169691Skan bool __is_simple = _Rope_is_simple((_CharT*)0); 1022169691Skan 1023169691Skan if (__rope_len < __w) 102497403Sobrien __pad_len = __w - __rope_len; 1025169691Skan else 102697403Sobrien __pad_len = 0; 1027169691Skan 102897403Sobrien if (!__is_simple) 1029169691Skan __o.width(__w / __rope_len); 1030169691Skan try 1031169691Skan { 1032169691Skan if (__is_simple && !__left && __pad_len > 0) 1033169691Skan _Rope_fill(__o, __pad_len); 1034169691Skan __r.apply_to_pieces(0, __r.size(), __c); 1035169691Skan if (__is_simple && __left && __pad_len > 0) 1036169691Skan _Rope_fill(__o, __pad_len); 1037169691Skan if (!__is_simple) 1038169691Skan __o.width(__w); 1039169691Skan } 1040169691Skan catch(...) 1041169691Skan { 1042169691Skan if (!__is_simple) 1043169691Skan __o.width(__w); 1044169691Skan __throw_exception_again; 1045169691Skan } 1046169691Skan return __o; 104797403Sobrien } 104897403Sobrien 1049169691Skan template <class _CharT, class _Alloc> 1050169691Skan _CharT* 1051169691Skan rope<_CharT, _Alloc>:: 1052169691Skan _S_flatten(_RopeRep* __r, size_t __start, size_t __len, 1053169691Skan _CharT* __buffer) 1054169691Skan { 1055169691Skan _Rope_flatten_char_consumer<_CharT> __c(__buffer); 1056169691Skan _S_apply_to_pieces(__c, __r, __start, __start + __len); 1057169691Skan return(__buffer + __len); 1058169691Skan } 105997403Sobrien 1060169691Skan template <class _CharT, class _Alloc> 1061169691Skan size_t 1062169691Skan rope<_CharT, _Alloc>:: 1063169691Skan find(_CharT __pattern, size_t __start) const 1064169691Skan { 1065169691Skan _Rope_find_char_char_consumer<_CharT> __c(__pattern); 1066169691Skan _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size()); 1067169691Skan size_type __result_pos = __start + __c._M_count; 1068169691Skan#ifndef __STL_OLD_ROPE_SEMANTICS 1069169691Skan if (__result_pos == size()) 1070169691Skan __result_pos = npos; 1071169691Skan#endif 1072169691Skan return __result_pos; 1073169691Skan } 107497403Sobrien 1075169691Skan template <class _CharT, class _Alloc> 1076169691Skan _CharT* 1077169691Skan rope<_CharT, _Alloc>:: 1078169691Skan _S_flatten(_RopeRep* __r, _CharT* __buffer) 1079169691Skan { 1080169691Skan if (0 == __r) 1081169691Skan return __buffer; 1082169691Skan switch(__r->_M_tag) 1083169691Skan { 1084169691Skan case __detail::_S_concat: 1085169691Skan { 1086169691Skan _RopeConcatenation* __c = (_RopeConcatenation*)__r; 1087169691Skan _RopeRep* __left = __c->_M_left; 1088169691Skan _RopeRep* __right = __c->_M_right; 1089169691Skan _CharT* __rest = _S_flatten(__left, __buffer); 1090169691Skan return _S_flatten(__right, __rest); 1091169691Skan } 1092169691Skan case __detail::_S_leaf: 1093169691Skan { 1094169691Skan _RopeLeaf* __l = (_RopeLeaf*)__r; 1095169691Skan return copy_n(__l->_M_data, __l->_M_size, __buffer).second; 1096169691Skan } 1097169691Skan case __detail::_S_function: 1098169691Skan case __detail::_S_substringfn: 1099169691Skan // We don't yet do anything with substring nodes. 1100169691Skan // This needs to be fixed before ropefiles will work well. 1101169691Skan { 1102169691Skan _RopeFunction* __f = (_RopeFunction*)__r; 1103169691Skan (*(__f->_M_fn))(0, __f->_M_size, __buffer); 1104169691Skan return __buffer + __f->_M_size; 1105169691Skan } 110697403Sobrien default: 1107169691Skan return 0; 1108169691Skan } 110997403Sobrien } 111097403Sobrien 1111169691Skan // This needs work for _CharT != char 1112169691Skan template <class _CharT, class _Alloc> 1113169691Skan void 1114169691Skan rope<_CharT, _Alloc>:: 1115169691Skan _S_dump(_RopeRep* __r, int __indent) 1116169691Skan { 1117169691Skan for (int __i = 0; __i < __indent; __i++) 1118169691Skan putchar(' '); 1119169691Skan if (0 == __r) 1120169691Skan { 1121169691Skan printf("NULL\n"); 1122169691Skan return; 1123169691Skan } 1124169691Skan if (_S_concat == __r->_M_tag) 1125169691Skan { 1126169691Skan _RopeConcatenation* __c = (_RopeConcatenation*)__r; 1127169691Skan _RopeRep* __left = __c->_M_left; 1128169691Skan _RopeRep* __right = __c->_M_right; 1129169691Skan 1130169691Skan#ifdef __GC 113197403Sobrien printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n", 1132169691Skan __r, __r->_M_depth, __r->_M_size, 1133169691Skan __r->_M_is_balanced? "" : "not"); 1134169691Skan#else 113597403Sobrien printf("Concatenation %p (rc = %ld, depth = %d, " 1136169691Skan "len = %ld, %s balanced)\n", 113797403Sobrien __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size, 113897403Sobrien __r->_M_is_balanced? "" : "not"); 1139169691Skan#endif 1140169691Skan _S_dump(__left, __indent + 2); 1141169691Skan _S_dump(__right, __indent + 2); 1142169691Skan return; 1143169691Skan } 1144169691Skan else 1145169691Skan { 1146242347Sdim const char* __kind; 1147169691Skan 1148169691Skan switch (__r->_M_tag) 1149169691Skan { 1150169691Skan case __detail::_S_leaf: 1151169691Skan __kind = "Leaf"; 1152169691Skan break; 1153169691Skan case __detail::_S_function: 1154169691Skan __kind = "Function"; 1155169691Skan break; 1156169691Skan case __detail::_S_substringfn: 1157169691Skan __kind = "Function representing substring"; 1158169691Skan break; 115997403Sobrien default: 1160169691Skan __kind = "(corrupted kind field!)"; 1161169691Skan } 1162169691Skan#ifdef __GC 116397403Sobrien printf("%s %p (depth = %d, len = %ld) ", 116497403Sobrien __kind, __r, __r->_M_depth, __r->_M_size); 1165169691Skan#else 116697403Sobrien printf("%s %p (rc = %ld, depth = %d, len = %ld) ", 116797403Sobrien __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size); 1168169691Skan#endif 1169169691Skan if (_S_is_one_byte_char_type((_CharT*)0)) 1170169691Skan { 1171169691Skan const int __max_len = 40; 1172169691Skan _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len)); 1173169691Skan _CharT __buffer[__max_len + 1]; 1174169691Skan bool __too_big = __r->_M_size > __prefix->_M_size; 1175169691Skan 1176169691Skan _S_flatten(__prefix, __buffer); 1177169691Skan __buffer[__prefix->_M_size] = _S_eos((_CharT*)0); 1178169691Skan printf("%s%s\n", (char*)__buffer, 1179169691Skan __too_big? "...\n" : "\n"); 1180169691Skan } 1181169691Skan else 118297403Sobrien printf("\n"); 118397403Sobrien } 118497403Sobrien } 118597403Sobrien 1186169691Skan template <class _CharT, class _Alloc> 1187169691Skan const unsigned long 1188169691Skan rope<_CharT, _Alloc>:: 1189169691Skan _S_min_len[int(__detail::_S_max_rope_depth) + 1] = { 1190169691Skan /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, 1191169691Skan /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, 1192169691Skan /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, 1193169691Skan /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368, 1194169691Skan /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811, 1195169691Skan /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309, 1196169691Skan /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352, 1197169691Skan /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155, 1198169691Skan /* 39 */165580141, /* 40 */267914296, /* 41 */433494437, 1199169691Skan /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903, 1200169691Skan /* 45 */2971215073u }; 1201169691Skan // These are Fibonacci numbers < 2**32. 120297403Sobrien 1203169691Skan template <class _CharT, class _Alloc> 1204169691Skan typename rope<_CharT, _Alloc>::_RopeRep* 1205169691Skan rope<_CharT, _Alloc>:: 1206169691Skan _S_balance(_RopeRep* __r) 1207169691Skan { 1208169691Skan _RopeRep* __forest[int(__detail::_S_max_rope_depth) + 1]; 1209169691Skan _RopeRep* __result = 0; 1210169691Skan int __i; 1211169691Skan // Invariant: 1212169691Skan // The concatenation of forest in descending order is equal to __r. 1213169691Skan // __forest[__i]._M_size >= _S_min_len[__i] 1214169691Skan // __forest[__i]._M_depth = __i 1215169691Skan // References from forest are included in refcount. 1216169691Skan 1217169691Skan for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i) 1218169691Skan __forest[__i] = 0; 1219169691Skan try 1220169691Skan { 1221169691Skan _S_add_to_forest(__r, __forest); 1222169691Skan for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i) 1223169691Skan if (0 != __forest[__i]) 1224169691Skan { 1225169691Skan#ifndef __GC 1226169691Skan _Self_destruct_ptr __old(__result); 1227169691Skan#endif 1228169691Skan __result = _S_concat(__forest[__i], __result); 1229169691Skan __forest[__i]->_M_unref_nonnil(); 1230169691Skan#if !defined(__GC) && defined(__EXCEPTIONS) 1231169691Skan __forest[__i] = 0; 1232169691Skan#endif 1233169691Skan } 1234169691Skan } 1235169691Skan catch(...) 1236169691Skan { 1237169691Skan for(__i = 0; __i <= int(__detail::_S_max_rope_depth); __i++) 1238169691Skan _S_unref(__forest[__i]); 1239169691Skan __throw_exception_again; 1240169691Skan } 1241169691Skan 1242169691Skan if (__result->_M_depth > int(__detail::_S_max_rope_depth)) 1243169691Skan __throw_length_error(__N("rope::_S_balance")); 1244169691Skan return(__result); 124597403Sobrien } 124697403Sobrien 1247169691Skan template <class _CharT, class _Alloc> 1248169691Skan void 1249169691Skan rope<_CharT, _Alloc>:: 1250169691Skan _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest) 1251169691Skan { 1252169691Skan if (__r->_M_is_balanced) 1253169691Skan { 1254169691Skan _S_add_leaf_to_forest(__r, __forest); 1255169691Skan return; 1256169691Skan } 125797403Sobrien 1258169691Skan { 125997403Sobrien _RopeConcatenation* __c = (_RopeConcatenation*)__r; 1260169691Skan 126197403Sobrien _S_add_to_forest(__c->_M_left, __forest); 126297403Sobrien _S_add_to_forest(__c->_M_right, __forest); 1263169691Skan } 126497403Sobrien } 126597403Sobrien 126697403Sobrien 1267169691Skan template <class _CharT, class _Alloc> 1268169691Skan void 1269169691Skan rope<_CharT, _Alloc>:: 1270169691Skan _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest) 1271169691Skan { 1272169691Skan _RopeRep* __insertee; // included in refcount 1273169691Skan _RopeRep* __too_tiny = 0; // included in refcount 1274169691Skan int __i; // forest[0..__i-1] is empty 1275169691Skan size_t __s = __r->_M_size; 1276169691Skan 1277169691Skan for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) 1278169691Skan { 1279169691Skan if (0 != __forest[__i]) 1280169691Skan { 1281169691Skan#ifndef __GC 128297403Sobrien _Self_destruct_ptr __old(__too_tiny); 1283169691Skan#endif 1284169691Skan __too_tiny = _S_concat_and_set_balanced(__forest[__i], 1285169691Skan __too_tiny); 1286169691Skan __forest[__i]->_M_unref_nonnil(); 1287169691Skan __forest[__i] = 0; 1288169691Skan } 128997403Sobrien } 1290169691Skan { 1291169691Skan#ifndef __GC 1292169691Skan _Self_destruct_ptr __old(__too_tiny); 1293169691Skan#endif 129497403Sobrien __insertee = _S_concat_and_set_balanced(__too_tiny, __r); 1295169691Skan } 1296169691Skan // Too_tiny dead, and no longer included in refcount. 1297169691Skan // Insertee is live and included. 1298169691Skan for (;; ++__i) 1299169691Skan { 1300169691Skan if (0 != __forest[__i]) 1301169691Skan { 1302169691Skan#ifndef __GC 130397403Sobrien _Self_destruct_ptr __old(__insertee); 1304169691Skan#endif 1305169691Skan __insertee = _S_concat_and_set_balanced(__forest[__i], 1306169691Skan __insertee); 1307169691Skan __forest[__i]->_M_unref_nonnil(); 1308169691Skan __forest[__i] = 0; 1309169691Skan } 1310169691Skan if (__i == int(__detail::_S_max_rope_depth) 1311169691Skan || __insertee->_M_size < _S_min_len[__i+1]) 1312169691Skan { 1313169691Skan __forest[__i] = __insertee; 1314169691Skan // refcount is OK since __insertee is now dead. 1315169691Skan return; 1316169691Skan } 131797403Sobrien } 131897403Sobrien } 131997403Sobrien 1320169691Skan template <class _CharT, class _Alloc> 1321169691Skan _CharT 1322169691Skan rope<_CharT, _Alloc>:: 1323169691Skan _S_fetch(_RopeRep* __r, size_type __i) 1324169691Skan { 1325169691Skan __GC_CONST _CharT* __cstr = __r->_M_c_string; 1326169691Skan 1327169691Skan if (0 != __cstr) 1328169691Skan return __cstr[__i]; 1329169691Skan for(;;) 1330169691Skan { 1331169691Skan switch(__r->_M_tag) 133297403Sobrien { 1333169691Skan case __detail::_S_concat: 1334169691Skan { 133597403Sobrien _RopeConcatenation* __c = (_RopeConcatenation*)__r; 133697403Sobrien _RopeRep* __left = __c->_M_left; 133797403Sobrien size_t __left_len = __left->_M_size; 1338169691Skan 1339169691Skan if (__i >= __left_len) 1340169691Skan { 134197403Sobrien __i -= __left_len; 134297403Sobrien __r = __c->_M_right; 1343169691Skan } 1344169691Skan else 1345169691Skan __r = __left; 1346169691Skan } 1347169691Skan break; 1348169691Skan case __detail::_S_leaf: 1349169691Skan { 135097403Sobrien _RopeLeaf* __l = (_RopeLeaf*)__r; 135197403Sobrien return __l->_M_data[__i]; 1352169691Skan } 1353169691Skan case __detail::_S_function: 1354169691Skan case __detail::_S_substringfn: 1355169691Skan { 135697403Sobrien _RopeFunction* __f = (_RopeFunction*)__r; 135797403Sobrien _CharT __result; 1358169691Skan 135997403Sobrien (*(__f->_M_fn))(__i, 1, &__result); 136097403Sobrien return __result; 1361169691Skan } 136297403Sobrien } 1363169691Skan } 136497403Sobrien } 1365169691Skan 1366169691Skan#ifndef __GC 1367169691Skan // Return a uniquely referenced character slot for the given 1368169691Skan // position, or 0 if that's not possible. 1369169691Skan template <class _CharT, class _Alloc> 1370169691Skan _CharT* 1371169691Skan rope<_CharT, _Alloc>:: 1372169691Skan _S_fetch_ptr(_RopeRep* __r, size_type __i) 1373169691Skan { 1374169691Skan _RopeRep* __clrstack[__detail::_S_max_rope_depth]; 1375169691Skan size_t __csptr = 0; 1376169691Skan 1377169691Skan for(;;) 1378169691Skan { 1379169691Skan if (__r->_M_ref_count > 1) 1380169691Skan return 0; 1381169691Skan switch(__r->_M_tag) 138297403Sobrien { 1383169691Skan case __detail::_S_concat: 1384169691Skan { 138597403Sobrien _RopeConcatenation* __c = (_RopeConcatenation*)__r; 138697403Sobrien _RopeRep* __left = __c->_M_left; 138797403Sobrien size_t __left_len = __left->_M_size; 1388169691Skan 1389169691Skan if (__c->_M_c_string != 0) 1390169691Skan __clrstack[__csptr++] = __c; 1391169691Skan if (__i >= __left_len) 1392169691Skan { 139397403Sobrien __i -= __left_len; 139497403Sobrien __r = __c->_M_right; 1395169691Skan } 1396169691Skan else 1397169691Skan __r = __left; 1398169691Skan } 1399169691Skan break; 1400169691Skan case __detail::_S_leaf: 1401169691Skan { 140297403Sobrien _RopeLeaf* __l = (_RopeLeaf*)__r; 140397403Sobrien if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0) 1404169691Skan __clrstack[__csptr++] = __l; 1405169691Skan while (__csptr > 0) 1406169691Skan { 140797403Sobrien -- __csptr; 140897403Sobrien _RopeRep* __d = __clrstack[__csptr]; 140997403Sobrien __d->_M_free_c_string(); 141097403Sobrien __d->_M_c_string = 0; 1411169691Skan } 141297403Sobrien return __l->_M_data + __i; 1413169691Skan } 1414169691Skan case __detail::_S_function: 1415169691Skan case __detail::_S_substringfn: 1416169691Skan return 0; 141797403Sobrien } 1418169691Skan } 141997403Sobrien } 1420169691Skan#endif /* __GC */ 142197403Sobrien 1422169691Skan // The following could be implemented trivially using 1423169691Skan // lexicographical_compare_3way. 1424169691Skan // We do a little more work to avoid dealing with rope iterators for 1425169691Skan // flat strings. 1426169691Skan template <class _CharT, class _Alloc> 1427169691Skan int 1428169691Skan rope<_CharT, _Alloc>:: 1429169691Skan _S_compare (const _RopeRep* __left, const _RopeRep* __right) 1430169691Skan { 1431169691Skan size_t __left_len; 1432169691Skan size_t __right_len; 1433169691Skan 1434169691Skan if (0 == __right) 1435169691Skan return 0 != __left; 1436169691Skan if (0 == __left) 1437169691Skan return -1; 1438169691Skan __left_len = __left->_M_size; 1439169691Skan __right_len = __right->_M_size; 1440169691Skan if (__detail::_S_leaf == __left->_M_tag) 1441169691Skan { 1442169691Skan _RopeLeaf* __l = (_RopeLeaf*) __left; 1443169691Skan if (__detail::_S_leaf == __right->_M_tag) 1444169691Skan { 1445169691Skan _RopeLeaf* __r = (_RopeLeaf*) __right; 1446169691Skan return lexicographical_compare_3way(__l->_M_data, 1447169691Skan __l->_M_data + __left_len, 1448169691Skan __r->_M_data, __r->_M_data 1449169691Skan + __right_len); 1450169691Skan } 1451169691Skan else 1452169691Skan { 1453169691Skan const_iterator __rstart(__right, 0); 1454169691Skan const_iterator __rend(__right, __right_len); 1455169691Skan return lexicographical_compare_3way(__l->_M_data, __l->_M_data 1456169691Skan + __left_len, 1457169691Skan __rstart, __rend); 1458169691Skan } 145997403Sobrien } 1460169691Skan else 1461169691Skan { 1462169691Skan const_iterator __lstart(__left, 0); 1463169691Skan const_iterator __lend(__left, __left_len); 1464169691Skan if (__detail::_S_leaf == __right->_M_tag) 1465169691Skan { 1466169691Skan _RopeLeaf* __r = (_RopeLeaf*) __right; 1467169691Skan return lexicographical_compare_3way(__lstart, __lend, 1468169691Skan __r->_M_data, __r->_M_data 1469169691Skan + __right_len); 1470169691Skan } 1471169691Skan else 1472169691Skan { 1473169691Skan const_iterator __rstart(__right, 0); 1474169691Skan const_iterator __rend(__right, __right_len); 1475169691Skan return lexicographical_compare_3way(__lstart, __lend, 1476169691Skan __rstart, __rend); 1477169691Skan } 147897403Sobrien } 147997403Sobrien } 148097403Sobrien 1481169691Skan // Assignment to reference proxies. 1482169691Skan template <class _CharT, class _Alloc> 1483169691Skan _Rope_char_ref_proxy<_CharT, _Alloc>& 1484169691Skan _Rope_char_ref_proxy<_CharT, _Alloc>:: 1485169691Skan operator=(_CharT __c) 1486169691Skan { 1487169691Skan _RopeRep* __old = _M_root->_M_tree_ptr; 1488169691Skan#ifndef __GC 1489169691Skan // First check for the case in which everything is uniquely 1490169691Skan // referenced. In that case we can do this destructively. 1491169691Skan _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos); 1492169691Skan if (0 != __ptr) 1493169691Skan { 1494169691Skan *__ptr = __c; 1495169691Skan return *this; 149697403Sobrien } 1497169691Skan#endif 1498169691Skan _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos)); 1499169691Skan _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1, 1500169691Skan __old->_M_size)); 1501169691Skan _Self_destruct_ptr __result_left(_My_rope:: 1502169691Skan _S_destr_concat_char_iter(__left, 1503169691Skan &__c, 1)); 150497403Sobrien 1505169691Skan _RopeRep* __result = _My_rope::_S_concat(__result_left, __right); 1506169691Skan#ifndef __GC 150797403Sobrien _RopeRep::_S_unref(__old); 1508169691Skan#endif 1509169691Skan _M_root->_M_tree_ptr = __result; 1510169691Skan return *this; 1511169691Skan } 151297403Sobrien 1513169691Skan template <class _CharT, class _Alloc> 1514169691Skan inline _Rope_char_ref_proxy<_CharT, _Alloc>:: 1515169691Skan operator _CharT() const 1516169691Skan { 1517169691Skan if (_M_current_valid) 151897403Sobrien return _M_current; 1519169691Skan else 1520169691Skan return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos); 152197403Sobrien } 152297403Sobrien 1523169691Skan template <class _CharT, class _Alloc> 1524169691Skan _Rope_char_ptr_proxy<_CharT, _Alloc> 1525169691Skan _Rope_char_ref_proxy<_CharT, _Alloc>:: 1526169691Skan operator&() const 1527169691Skan { return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); } 152897403Sobrien 1529169691Skan template <class _CharT, class _Alloc> 1530169691Skan rope<_CharT, _Alloc>:: 1531169691Skan rope(size_t __n, _CharT __c, const allocator_type& __a) 1532169691Skan : _Base(__a) 1533169691Skan { 1534169691Skan rope<_CharT,_Alloc> __result; 1535169691Skan const size_t __exponentiate_threshold = 32; 1536169691Skan size_t __exponent; 1537169691Skan size_t __rest; 1538169691Skan _CharT* __rest_buffer; 1539169691Skan _RopeRep* __remainder; 1540169691Skan rope<_CharT, _Alloc> __remainder_rope; 1541132720Skan 1542169691Skan if (0 == __n) 1543169691Skan return; 1544169691Skan 1545169691Skan __exponent = __n / __exponentiate_threshold; 1546169691Skan __rest = __n % __exponentiate_threshold; 1547169691Skan if (0 == __rest) 154897403Sobrien __remainder = 0; 1549169691Skan else 1550169691Skan { 1551169691Skan __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest)); 1552169691Skan __uninitialized_fill_n_a(__rest_buffer, __rest, __c, 1553169691Skan get_allocator()); 1554169691Skan _S_cond_store_eos(__rest_buffer[__rest]); 1555169691Skan try 1556169691Skan { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a); } 1557169691Skan catch(...) 1558169691Skan { 1559169691Skan _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a); 1560169691Skan __throw_exception_again; 1561169691Skan } 156297403Sobrien } 1563169691Skan __remainder_rope._M_tree_ptr = __remainder; 1564169691Skan if (__exponent != 0) 1565169691Skan { 1566169691Skan _CharT* __base_buffer = 1567169691Skan this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold)); 1568169691Skan _RopeLeaf* __base_leaf; 1569169691Skan rope __base_rope; 1570169691Skan __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c, 1571169691Skan get_allocator()); 1572169691Skan _S_cond_store_eos(__base_buffer[__exponentiate_threshold]); 1573169691Skan try 1574169691Skan { 1575169691Skan __base_leaf = _S_new_RopeLeaf(__base_buffer, 1576169691Skan __exponentiate_threshold, __a); 1577169691Skan } 1578169691Skan catch(...) 1579169691Skan { 1580169691Skan _RopeRep::__STL_FREE_STRING(__base_buffer, 1581169691Skan __exponentiate_threshold, __a); 1582169691Skan __throw_exception_again; 1583169691Skan } 1584169691Skan __base_rope._M_tree_ptr = __base_leaf; 1585169691Skan if (1 == __exponent) 1586169691Skan __result = __base_rope; 1587169691Skan else 1588169691Skan __result = power(__base_rope, __exponent, 1589169691Skan _Rope_Concat_fn<_CharT, _Alloc>()); 1590169691Skan 1591169691Skan if (0 != __remainder) 1592169691Skan __result += __remainder_rope; 159397403Sobrien } 1594169691Skan else 159597403Sobrien __result = __remainder_rope; 1596169691Skan 1597169691Skan this->_M_tree_ptr = __result._M_tree_ptr; 1598169691Skan this->_M_tree_ptr->_M_ref_nonnil(); 159997403Sobrien } 1600169691Skan 1601169691Skan template<class _CharT, class _Alloc> 1602169691Skan _CharT 1603169691Skan rope<_CharT, _Alloc>::_S_empty_c_str[1]; 1604169691Skan 1605169691Skan template<class _CharT, class _Alloc> 1606169691Skan const _CharT* 1607169691Skan rope<_CharT, _Alloc>:: 1608169691Skan c_str() const 1609169691Skan { 1610169691Skan if (0 == this->_M_tree_ptr) 1611169691Skan { 1612169691Skan _S_empty_c_str[0] = _S_eos((_CharT*)0); // Possibly redundant, 1613169691Skan // but probably fast. 1614169691Skan return _S_empty_c_str; 1615169691Skan } 1616169691Skan __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock); 1617169691Skan __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string; 1618169691Skan if (0 == __result) 1619169691Skan { 1620169691Skan size_t __s = size(); 1621169691Skan __result = this->_Data_allocate(__s + 1); 1622169691Skan _S_flatten(this->_M_tree_ptr, __result); 1623169691Skan __result[__s] = _S_eos((_CharT*)0); 1624169691Skan this->_M_tree_ptr->_M_c_string = __result; 1625169691Skan } 1626169691Skan __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock); 1627169691Skan return(__result); 162897403Sobrien } 1629169691Skan 1630169691Skan template<class _CharT, class _Alloc> 1631169691Skan const _CharT* rope<_CharT, _Alloc>:: 1632169691Skan replace_with_c_str() 1633169691Skan { 1634169691Skan if (0 == this->_M_tree_ptr) 1635169691Skan { 1636169691Skan _S_empty_c_str[0] = _S_eos((_CharT*)0); 1637169691Skan return _S_empty_c_str; 1638169691Skan } 1639169691Skan __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string; 1640169691Skan if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag 1641169691Skan && 0 != __old_c_string) 164297403Sobrien return(__old_c_string); 1643169691Skan size_t __s = size(); 1644169691Skan _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s)); 1645169691Skan _S_flatten(this->_M_tree_ptr, __result); 1646169691Skan __result[__s] = _S_eos((_CharT*)0); 1647169691Skan this->_M_tree_ptr->_M_unref_nonnil(); 1648169691Skan this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s, 1649169691Skan this->get_allocator()); 1650169691Skan return(__result); 165197403Sobrien } 165297403Sobrien 1653169691Skan // Algorithm specializations. More should be added. 1654169691Skan 1655169691Skan template<class _Rope_iterator> // was templated on CharT and Alloc 1656169691Skan void // VC++ workaround 1657169691Skan _Rope_rotate(_Rope_iterator __first, 1658169691Skan _Rope_iterator __middle, 1659169691Skan _Rope_iterator __last) 1660169691Skan { 1661169691Skan typedef typename _Rope_iterator::value_type _CharT; 1662169691Skan typedef typename _Rope_iterator::_allocator_type _Alloc; 1663169691Skan 1664169691Skan rope<_CharT, _Alloc>& __r(__first.container()); 1665169691Skan rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index()); 1666169691Skan rope<_CharT, _Alloc> __suffix = 1667169691Skan __r.substr(__last.index(), __r.size() - __last.index()); 1668169691Skan rope<_CharT, _Alloc> __part1 = 1669169691Skan __r.substr(__middle.index(), __last.index() - __middle.index()); 1670169691Skan rope<_CharT, _Alloc> __part2 = 1671169691Skan __r.substr(__first.index(), __middle.index() - __first.index()); 1672169691Skan __r = __prefix; 1673169691Skan __r += __part1; 1674169691Skan __r += __part2; 1675169691Skan __r += __suffix; 1676169691Skan } 167797403Sobrien 167897403Sobrien#if !defined(__GNUC__) 1679169691Skan // Appears to confuse g++ 1680169691Skan inline void 1681169691Skan rotate(_Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __first, 1682169691Skan _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __middle, 1683169691Skan _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __last) 1684169691Skan { _Rope_rotate(__first, __middle, __last); } 168597403Sobrien#endif 168697403Sobrien 168797403Sobrien# if 0 1688169691Skan // Probably not useful for several reasons: 1689169691Skan // - for SGIs 7.1 compiler and probably some others, 1690169691Skan // this forces lots of rope<wchar_t, ...> instantiations, creating a 1691169691Skan // code bloat and compile time problem. (Fixed in 7.2.) 1692169691Skan // - wchar_t is 4 bytes wide on most UNIX platforms, making it 1693169691Skan // unattractive for unicode strings. Unsigned short may be a better 1694169691Skan // character type. 1695169691Skan inline void 1696169691Skan rotate(_Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first, 1697169691Skan _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle, 1698169691Skan _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last) 1699169691Skan { _Rope_rotate(__first, __middle, __last); } 170097403Sobrien# endif 170197403Sobrien 1702169691Skan_GLIBCXX_END_NAMESPACE 1703