1// SGI's rope class implementation -*- C++ -*- 2 3// Copyright (C) 2001-2022 Free Software Foundation, Inc. 4// 5// This file is part of the GNU ISO C++ Library. This library is free 6// software; you can redistribute it and/or modify it under the 7// terms of the GNU General Public License as published by the 8// Free Software Foundation; either version 3, or (at your option) 9// any later version. 10 11// This library is distributed in the hope that it will be useful, 12// but WITHOUT ANY WARRANTY; without even the implied warranty of 13// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14// GNU General Public License for more details. 15 16// Under Section 7 of GPL version 3, you are granted additional 17// permissions described in the GCC Runtime Library Exception, version 18// 3.1, as published by the Free Software Foundation. 19 20// You should have received a copy of the GNU General Public License and 21// a copy of the GCC Runtime Library Exception along with this program; 22// see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23// <http://www.gnu.org/licenses/>. 24 25/* 26 * Copyright (c) 1997 27 * Silicon Graphics Computer Systems, Inc. 28 * 29 * Permission to use, copy, modify, distribute and sell this software 30 * and its documentation for any purpose is hereby granted without fee, 31 * provided that the above copyright notice appear in all copies and 32 * that both that copyright notice and this permission notice appear 33 * in supporting documentation. Silicon Graphics makes no 34 * representations about the suitability of this software for any 35 * purpose. It is provided "as is" without express or implied warranty. 36 */ 37 38/** @file ropeimpl.h 39 * This is an internal header file, included by other library headers. 40 * Do not attempt to use it directly. @headername{ext/rope} 41 */ 42 43#include <cstdio> 44#include <ostream> 45#include <bits/functexcept.h> 46 47#include <ext/algorithm> // For copy_n and lexicographical_compare_3way 48#include <ext/memory> // For uninitialized_copy_n 49#include <ext/numeric> // For power 50 51namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 52{ 53_GLIBCXX_BEGIN_NAMESPACE_VERSION 54 55 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf 56 // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct. 57 // Results in a valid buf_ptr if the iterator can be legitimately 58 // dereferenced. 59 template <class _CharT, class _Alloc> 60 void 61 _Rope_iterator_base<_CharT, _Alloc>:: 62 _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x) 63 { 64 using std::size_t; 65 const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index]; 66 size_t __leaf_pos = __x._M_leaf_pos; 67 size_t __pos = __x._M_current_pos; 68 69 switch(__leaf->_M_tag) 70 { 71 case __detail::_S_leaf: 72 __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data; 73 __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos); 74 __x._M_buf_end = __x._M_buf_start + __leaf->_M_size; 75 break; 76 case __detail::_S_function: 77 case __detail::_S_substringfn: 78 { 79 size_t __len = _S_iterator_buf_len; 80 size_t __buf_start_pos = __leaf_pos; 81 size_t __leaf_end = __leaf_pos + __leaf->_M_size; 82 char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT, 83 _Alloc>*)__leaf)->_M_fn; 84 if (__buf_start_pos + __len <= __pos) 85 { 86 __buf_start_pos = __pos - __len / 4; 87 if (__buf_start_pos + __len > __leaf_end) 88 __buf_start_pos = __leaf_end - __len; 89 } 90 if (__buf_start_pos + __len > __leaf_end) 91 __len = __leaf_end - __buf_start_pos; 92 (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf); 93 __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos); 94 __x._M_buf_start = __x._M_tmp_buf; 95 __x._M_buf_end = __x._M_tmp_buf + __len; 96 } 97 break; 98 default: 99 break; 100 } 101 } 102 103 // Set path and buffer inside a rope iterator. We assume that 104 // pos and root are already set. 105 template <class _CharT, class _Alloc> 106 void 107 _Rope_iterator_base<_CharT, _Alloc>:: 108 _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x) 109 { 110 using std::size_t; 111 const _RopeRep* __path[int(__detail::_S_max_rope_depth) + 1]; 112 const _RopeRep* __curr_rope; 113 int __curr_depth = -1; /* index into path */ 114 size_t __curr_start_pos = 0; 115 size_t __pos = __x._M_current_pos; 116 unsigned char __dirns = 0; // Bit vector marking right turns in the path 117 118 if (__pos >= __x._M_root->_M_size) 119 { 120 __x._M_buf_ptr = 0; 121 return; 122 } 123 __curr_rope = __x._M_root; 124 if (0 != __curr_rope->_M_c_string) 125 { 126 /* Treat the root as a leaf. */ 127 __x._M_buf_start = __curr_rope->_M_c_string; 128 __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size; 129 __x._M_buf_ptr = __curr_rope->_M_c_string + __pos; 130 __x._M_path_end[0] = __curr_rope; 131 __x._M_leaf_index = 0; 132 __x._M_leaf_pos = 0; 133 return; 134 } 135 for(;;) 136 { 137 ++__curr_depth; 138 __path[__curr_depth] = __curr_rope; 139 switch(__curr_rope->_M_tag) 140 { 141 case __detail::_S_leaf: 142 case __detail::_S_function: 143 case __detail::_S_substringfn: 144 __x._M_leaf_pos = __curr_start_pos; 145 goto done; 146 case __detail::_S_concat: 147 { 148 _Rope_RopeConcatenation<_CharT, _Alloc>* __c = 149 (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope; 150 _RopeRep* __left = __c->_M_left; 151 size_t __left_len = __left->_M_size; 152 153 __dirns <<= 1; 154 if (__pos >= __curr_start_pos + __left_len) 155 { 156 __dirns |= 1; 157 __curr_rope = __c->_M_right; 158 __curr_start_pos += __left_len; 159 } 160 else 161 __curr_rope = __left; 162 } 163 break; 164 } 165 } 166 done: 167 // Copy last section of path into _M_path_end. 168 { 169 int __i = -1; 170 int __j = __curr_depth + 1 - int(_S_path_cache_len); 171 172 if (__j < 0) __j = 0; 173 while (__j <= __curr_depth) 174 __x._M_path_end[++__i] = __path[__j++]; 175 __x._M_leaf_index = __i; 176 } 177 __x._M_path_directions = __dirns; 178 _S_setbuf(__x); 179 } 180 181 // Specialized version of the above. Assumes that 182 // the path cache is valid for the previous position. 183 template <class _CharT, class _Alloc> 184 void 185 _Rope_iterator_base<_CharT, _Alloc>:: 186 _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x) 187 { 188 using std::size_t; 189 int __current_index = __x._M_leaf_index; 190 const _RopeRep* __current_node = __x._M_path_end[__current_index]; 191 size_t __len = __current_node->_M_size; 192 size_t __node_start_pos = __x._M_leaf_pos; 193 unsigned char __dirns = __x._M_path_directions; 194 _Rope_RopeConcatenation<_CharT, _Alloc>* __c; 195 196 if (__x._M_current_pos - __node_start_pos < __len) 197 { 198 /* More stuff in this leaf, we just didn't cache it. */ 199 _S_setbuf(__x); 200 return; 201 } 202 // node_start_pos is starting position of last_node. 203 while (--__current_index >= 0) 204 { 205 if (!(__dirns & 1) /* Path turned left */) 206 break; 207 __current_node = __x._M_path_end[__current_index]; 208 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node; 209 // Otherwise we were in the right child. Thus we should pop 210 // the concatenation node. 211 __node_start_pos -= __c->_M_left->_M_size; 212 __dirns >>= 1; 213 } 214 if (__current_index < 0) 215 { 216 // We underflowed the cache. Punt. 217 _S_setcache(__x); 218 return; 219 } 220 __current_node = __x._M_path_end[__current_index]; 221 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node; 222 // current_node is a concatenation node. We are positioned on the first 223 // character in its right child. 224 // node_start_pos is starting position of current_node. 225 __node_start_pos += __c->_M_left->_M_size; 226 __current_node = __c->_M_right; 227 __x._M_path_end[++__current_index] = __current_node; 228 __dirns |= 1; 229 while (__detail::_S_concat == __current_node->_M_tag) 230 { 231 ++__current_index; 232 if (int(_S_path_cache_len) == __current_index) 233 { 234 int __i; 235 for (__i = 0; __i < int(_S_path_cache_len) - 1; __i++) 236 __x._M_path_end[__i] = __x._M_path_end[__i+1]; 237 --__current_index; 238 } 239 __current_node = 240 ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left; 241 __x._M_path_end[__current_index] = __current_node; 242 __dirns <<= 1; 243 // node_start_pos is unchanged. 244 } 245 __x._M_leaf_index = __current_index; 246 __x._M_leaf_pos = __node_start_pos; 247 __x._M_path_directions = __dirns; 248 _S_setbuf(__x); 249 } 250 251 template <class _CharT, class _Alloc> 252 void 253 _Rope_iterator_base<_CharT, _Alloc>:: 254 _M_incr(std::size_t __n) 255 { 256 _M_current_pos += __n; 257 if (0 != _M_buf_ptr) 258 { 259 std::size_t __chars_left = _M_buf_end - _M_buf_ptr; 260 if (__chars_left > __n) 261 _M_buf_ptr += __n; 262 else if (__chars_left == __n) 263 { 264 _M_buf_ptr += __n; 265 _S_setcache_for_incr(*this); 266 } 267 else 268 _M_buf_ptr = 0; 269 } 270 } 271 272 template <class _CharT, class _Alloc> 273 void 274 _Rope_iterator_base<_CharT, _Alloc>:: 275 _M_decr(std::size_t __n) 276 { 277 if (0 != _M_buf_ptr) 278 { 279 std::size_t __chars_left = _M_buf_ptr - _M_buf_start; 280 if (__chars_left >= __n) 281 _M_buf_ptr -= __n; 282 else 283 _M_buf_ptr = 0; 284 } 285 _M_current_pos -= __n; 286 } 287 288 template <class _CharT, class _Alloc> 289 void 290 _Rope_iterator<_CharT, _Alloc>:: 291 _M_check() 292 { 293 if (_M_root_rope->_M_tree_ptr != this->_M_root) 294 { 295 // _Rope was modified. Get things fixed up. 296 _RopeRep::_S_unref(this->_M_root); 297 this->_M_root = _M_root_rope->_M_tree_ptr; 298 _RopeRep::_S_ref(this->_M_root); 299 this->_M_buf_ptr = 0; 300 } 301 } 302 303 template <class _CharT, class _Alloc> 304 inline 305 _Rope_const_iterator<_CharT, _Alloc>:: 306 _Rope_const_iterator(const _Rope_iterator<_CharT, _Alloc>& __x) 307 : _Rope_iterator_base<_CharT, _Alloc>(__x) 308 { } 309 310 template <class _CharT, class _Alloc> 311 inline 312 _Rope_iterator<_CharT, _Alloc>:: 313 _Rope_iterator(rope<_CharT, _Alloc>& __r, std::size_t __pos) 314 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos), 315 _M_root_rope(&__r) 316 { _RopeRep::_S_ref(this->_M_root); } 317 318 template <class _CharT, class _Alloc> 319 inline std::size_t 320 rope<_CharT, _Alloc>:: 321 _S_char_ptr_len(const _CharT* __s) 322 { 323 const _CharT* __p = __s; 324 325 while (!_S_is0(*__p)) 326 ++__p; 327 return (__p - __s); 328 } 329 330 331#ifndef __GC 332 333 template <class _CharT, class _Alloc> 334 inline void 335 _Rope_RopeRep<_CharT, _Alloc>:: 336 _M_free_c_string() 337 { 338 _CharT* __cstr = _M_c_string; 339 if (0 != __cstr) 340 { 341 std::size_t __size = this->_M_size + 1; 342 std::_Destroy(__cstr, __cstr + __size, _M_get_allocator()); 343 this->_Data_deallocate(__cstr, __size); 344 } 345 } 346 347 template <class _CharT, class _Alloc> 348 inline void 349 _Rope_RopeRep<_CharT, _Alloc>:: 350 _S_free_string(_CharT* __s, std::size_t __n, allocator_type& __a) 351 { 352 if (!_S_is_basic_char_type((_CharT*)0)) 353 std::_Destroy(__s, __s + __n, __a); 354 355 // This has to be a static member, so this gets a bit messy 356 __a.deallocate(__s, 357 _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n)); 358 } 359 360 // There are several reasons for not doing this with virtual destructors 361 // and a class specific delete operator: 362 // - A class specific delete operator can't easily get access to 363 // allocator instances if we need them. 364 // - Any virtual function would need a 4 or byte vtable pointer; 365 // this only requires a one byte tag per object. 366 template <class _CharT, class _Alloc> 367 void 368 _Rope_RopeRep<_CharT, _Alloc>:: 369 _M_free_tree() 370 { 371 switch(_M_tag) 372 { 373 case __detail::_S_leaf: 374 { 375 _Rope_RopeLeaf<_CharT, _Alloc>* __l 376 = (_Rope_RopeLeaf<_CharT, _Alloc>*)this; 377 __l->_Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf(); 378 this->_L_deallocate(__l, 1); 379 break; 380 } 381 case __detail::_S_concat: 382 { 383 _Rope_RopeConcatenation<_CharT,_Alloc>* __c 384 = (_Rope_RopeConcatenation<_CharT, _Alloc>*)this; 385 __c->_Rope_RopeConcatenation<_CharT, _Alloc>:: 386 ~_Rope_RopeConcatenation(); 387 this->_C_deallocate(__c, 1); 388 break; 389 } 390 case __detail::_S_function: 391 { 392 _Rope_RopeFunction<_CharT, _Alloc>* __f 393 = (_Rope_RopeFunction<_CharT, _Alloc>*)this; 394 __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction(); 395 this->_F_deallocate(__f, 1); 396 break; 397 } 398 case __detail::_S_substringfn: 399 { 400 _Rope_RopeSubstring<_CharT, _Alloc>* __ss = 401 (_Rope_RopeSubstring<_CharT, _Alloc>*)this; 402 __ss->_Rope_RopeSubstring<_CharT, _Alloc>:: 403 ~_Rope_RopeSubstring(); 404 this->_S_deallocate(__ss, 1); 405 break; 406 } 407 } 408 } 409#else 410 411 template <class _CharT, class _Alloc> 412 inline void 413 _Rope_RopeRep<_CharT, _Alloc>:: 414 _S_free_string(const _CharT*, std::size_t, allocator_type) 415 { } 416 417#endif 418 419 // Concatenate a C string onto a leaf rope by copying the rope data. 420 // Used for short ropes. 421 template <class _CharT, class _Alloc> 422 typename rope<_CharT, _Alloc>::_RopeLeaf* 423 rope<_CharT, _Alloc>:: 424 _S_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, 425 std::size_t __len) 426 { 427 std::size_t __old_len = __r->_M_size; 428 _CharT* __new_data = (_CharT*) 429 rope::_Data_allocate(_S_rounded_up_size(__old_len + __len)); 430 _RopeLeaf* __result; 431 432 uninitialized_copy_n(__r->_M_data, __old_len, __new_data); 433 uninitialized_copy_n(__iter, __len, __new_data + __old_len); 434 _S_cond_store_eos(__new_data[__old_len + __len]); 435 __try 436 { 437 __result = _S_new_RopeLeaf(__new_data, __old_len + __len, 438 __r->_M_get_allocator()); 439 } 440 __catch(...) 441 { 442 _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len, 443 __r->_M_get_allocator()); 444 __throw_exception_again; 445 } 446 return __result; 447 } 448 449#ifndef __GC 450 // As above, but it's OK to clobber original if refcount is 1 451 template <class _CharT, class _Alloc> 452 typename rope<_CharT,_Alloc>::_RopeLeaf* 453 rope<_CharT, _Alloc>:: 454 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, 455 std::size_t __len) 456 { 457 if (__r->_M_ref_count > 1) 458 return _S_leaf_concat_char_iter(__r, __iter, __len); 459 std::size_t __old_len = __r->_M_size; 460 if (_S_allocated_capacity(__old_len) >= __old_len + __len) 461 { 462 // The space has been partially initialized for the standard 463 // character types. But that doesn't matter for those types. 464 uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len); 465 if (_S_is_basic_char_type((_CharT*)0)) 466 _S_cond_store_eos(__r->_M_data[__old_len + __len]); 467 else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) 468 { 469 __r->_M_free_c_string(); 470 __r->_M_c_string = 0; 471 } 472 __r->_M_size = __old_len + __len; 473 __r->_M_ref_count = 2; 474 return __r; 475 } 476 else 477 { 478 _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len); 479 return __result; 480 } 481 } 482#endif 483 484 // Assumes left and right are not 0. 485 // Does not increment (nor decrement on exception) child reference counts. 486 // Result has ref count 1. 487 template <class _CharT, class _Alloc> 488 typename rope<_CharT, _Alloc>::_RopeRep* 489 rope<_CharT, _Alloc>:: 490 _S_tree_concat(_RopeRep* __left, _RopeRep* __right) 491 { 492 using std::size_t; 493 _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right, 494 __left-> 495 _M_get_allocator()); 496 size_t __depth = __result->_M_depth; 497 498 if (__depth > 20 499 && (__result->_M_size < 1000 500 || __depth > size_t(__detail::_S_max_rope_depth))) 501 { 502 _RopeRep* __balanced; 503 504 __try 505 { 506 __balanced = _S_balance(__result); 507 __result->_M_unref_nonnil(); 508 } 509 __catch(...) 510 { 511 rope::_C_deallocate(__result,1); 512 __throw_exception_again; 513 } 514 // In case of exception, we need to deallocate 515 // otherwise dangling result node. But caller 516 // still owns its children. Thus unref is 517 // inappropriate. 518 return __balanced; 519 } 520 else 521 return __result; 522 } 523 524 template <class _CharT, class _Alloc> 525 typename rope<_CharT, _Alloc>::_RopeRep* 526 rope<_CharT, _Alloc>:: 527 _S_concat_char_iter(_RopeRep* __r, const _CharT*__s, std::size_t __slen, 528 allocator_type& __a) 529 { 530 using std::size_t; 531 _RopeRep* __result; 532 if (0 == __slen) 533 { 534 _S_ref(__r); 535 return __r; 536 } 537 if (0 == __r) 538 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a); 539 if (__r->_M_tag == __detail::_S_leaf 540 && __r->_M_size + __slen <= size_t(_S_copy_max)) 541 { 542 __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); 543 return __result; 544 } 545 if (__detail::_S_concat == __r->_M_tag 546 && __detail::_S_leaf == ((_RopeConcatenation*) __r)->_M_right->_M_tag) 547 { 548 _RopeLeaf* __right = 549 (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right); 550 if (__right->_M_size + __slen <= size_t(_S_copy_max)) 551 { 552 _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left; 553 _RopeRep* __nright = 554 _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen); 555 __left->_M_ref_nonnil(); 556 __try 557 { __result = _S_tree_concat(__left, __nright); } 558 __catch(...) 559 { 560 _S_unref(__left); 561 _S_unref(__nright); 562 __throw_exception_again; 563 } 564 return __result; 565 } 566 } 567 _RopeRep* __nright = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a); 568 __try 569 { 570 __r->_M_ref_nonnil(); 571 __result = _S_tree_concat(__r, __nright); 572 } 573 __catch(...) 574 { 575 _S_unref(__r); 576 _S_unref(__nright); 577 __throw_exception_again; 578 } 579 return __result; 580 } 581 582#ifndef __GC 583 template <class _CharT, class _Alloc> 584 typename rope<_CharT,_Alloc>::_RopeRep* 585 rope<_CharT,_Alloc>:: 586 _S_destr_concat_char_iter(_RopeRep* __r, const _CharT* __s, 587 std::size_t __slen, allocator_type& __a) 588 { 589 using std::size_t; 590 _RopeRep* __result; 591 if (0 == __r) 592 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a); 593 size_t __count = __r->_M_ref_count; 594 size_t __orig_size = __r->_M_size; 595 if (__count > 1) 596 return _S_concat_char_iter(__r, __s, __slen, __a); 597 if (0 == __slen) 598 { 599 __r->_M_ref_count = 2; // One more than before 600 return __r; 601 } 602 if (__orig_size + __slen <= size_t(_S_copy_max) 603 && __detail::_S_leaf == __r->_M_tag) 604 { 605 __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, 606 __slen); 607 return __result; 608 } 609 if (__detail::_S_concat == __r->_M_tag) 610 { 611 _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*) 612 __r)->_M_right); 613 if (__detail::_S_leaf == __right->_M_tag 614 && __right->_M_size + __slen <= size_t(_S_copy_max)) 615 { 616 _RopeRep* __new_right = 617 _S_destr_leaf_concat_char_iter(__right, __s, __slen); 618 if (__right == __new_right) 619 __new_right->_M_ref_count = 1; 620 else 621 __right->_M_unref_nonnil(); 622 __r->_M_ref_count = 2; // One more than before. 623 ((_RopeConcatenation*)__r)->_M_right = __new_right; 624 __r->_M_size = __orig_size + __slen; 625 if (0 != __r->_M_c_string) 626 { 627 __r->_M_free_c_string(); 628 __r->_M_c_string = 0; 629 } 630 return __r; 631 } 632 } 633 _RopeRep* __right = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __a); 634 __r->_M_ref_nonnil(); 635 __try 636 { __result = _S_tree_concat(__r, __right); } 637 __catch(...) 638 { 639 _S_unref(__r); 640 _S_unref(__right); 641 __throw_exception_again; 642 } 643 return __result; 644 } 645#endif /* !__GC */ 646 647 template <class _CharT, class _Alloc> 648 typename rope<_CharT, _Alloc>::_RopeRep* 649 rope<_CharT, _Alloc>:: 650 _S_concat(_RopeRep* __left, _RopeRep* __right) 651 { 652 using std::size_t; 653 if (0 == __left) 654 { 655 _S_ref(__right); 656 return __right; 657 } 658 if (0 == __right) 659 { 660 __left->_M_ref_nonnil(); 661 return __left; 662 } 663 if (__detail::_S_leaf == __right->_M_tag) 664 { 665 if (__detail::_S_leaf == __left->_M_tag) 666 { 667 if (__right->_M_size + __left->_M_size <= size_t(_S_copy_max)) 668 return _S_leaf_concat_char_iter((_RopeLeaf*)__left, 669 ((_RopeLeaf*)__right)->_M_data, 670 __right->_M_size); 671 } 672 else if (__detail::_S_concat == __left->_M_tag 673 && __detail::_S_leaf == ((_RopeConcatenation*) 674 __left)->_M_right->_M_tag) 675 { 676 _RopeLeaf* __leftright = 677 (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); 678 if (__leftright->_M_size 679 + __right->_M_size <= size_t(_S_copy_max)) 680 { 681 _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left; 682 _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright, 683 ((_RopeLeaf*) 684 __right)-> 685 _M_data, 686 __right->_M_size); 687 __leftleft->_M_ref_nonnil(); 688 __try 689 { return(_S_tree_concat(__leftleft, __rest)); } 690 __catch(...) 691 { 692 _S_unref(__leftleft); 693 _S_unref(__rest); 694 __throw_exception_again; 695 } 696 } 697 } 698 } 699 __left->_M_ref_nonnil(); 700 __right->_M_ref_nonnil(); 701 __try 702 { return(_S_tree_concat(__left, __right)); } 703 __catch(...) 704 { 705 _S_unref(__left); 706 _S_unref(__right); 707 __throw_exception_again; 708 } 709 } 710 711 template <class _CharT, class _Alloc> 712 typename rope<_CharT, _Alloc>::_RopeRep* 713 rope<_CharT, _Alloc>:: 714 _S_substring(_RopeRep* __base, std::size_t __start, std::size_t __endp1) 715 { 716 using std::size_t; 717 if (0 == __base) 718 return 0; 719 size_t __len = __base->_M_size; 720 size_t __adj_endp1; 721 const size_t __lazy_threshold = 128; 722 723 if (__endp1 >= __len) 724 { 725 if (0 == __start) 726 { 727 __base->_M_ref_nonnil(); 728 return __base; 729 } 730 else 731 __adj_endp1 = __len; 732 733 } 734 else 735 __adj_endp1 = __endp1; 736 737 switch(__base->_M_tag) 738 { 739 case __detail::_S_concat: 740 { 741 _RopeConcatenation* __c = (_RopeConcatenation*)__base; 742 _RopeRep* __left = __c->_M_left; 743 _RopeRep* __right = __c->_M_right; 744 size_t __left_len = __left->_M_size; 745 _RopeRep* __result; 746 747 if (__adj_endp1 <= __left_len) 748 return _S_substring(__left, __start, __endp1); 749 else if (__start >= __left_len) 750 return _S_substring(__right, __start - __left_len, 751 __adj_endp1 - __left_len); 752 _Self_destruct_ptr __left_result(_S_substring(__left, 753 __start, 754 __left_len)); 755 _Self_destruct_ptr __right_result(_S_substring(__right, 0, 756 __endp1 757 - __left_len)); 758 __result = _S_concat(__left_result, __right_result); 759 return __result; 760 } 761 case __detail::_S_leaf: 762 { 763 _RopeLeaf* __l = (_RopeLeaf*)__base; 764 _RopeLeaf* __result; 765 size_t __result_len; 766 if (__start >= __adj_endp1) 767 return 0; 768 __result_len = __adj_endp1 - __start; 769 if (__result_len > __lazy_threshold) 770 goto lazy; 771#ifdef __GC 772 const _CharT* __section = __l->_M_data + __start; 773 __result = _S_new_RopeLeaf(__section, __result_len, 774 __base->_M_get_allocator()); 775 __result->_M_c_string = 0; // Not eos terminated. 776#else 777 // We should sometimes create substring node instead. 778 __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start, 779 __result_len, 780 __base-> 781 _M_get_allocator()); 782#endif 783 return __result; 784 } 785 case __detail::_S_substringfn: 786 // Avoid introducing multiple layers of substring nodes. 787 { 788 _RopeSubstring* __old = (_RopeSubstring*)__base; 789 size_t __result_len; 790 if (__start >= __adj_endp1) 791 return 0; 792 __result_len = __adj_endp1 - __start; 793 if (__result_len > __lazy_threshold) 794 { 795 _RopeSubstring* __result = 796 _S_new_RopeSubstring(__old->_M_base, 797 __start + __old->_M_start, 798 __adj_endp1 - __start, 799 __base->_M_get_allocator()); 800 return __result; 801 802 } // *** else fall through: *** 803 } 804 case __detail::_S_function: 805 { 806 _RopeFunction* __f = (_RopeFunction*)__base; 807 _CharT* __section; 808 size_t __result_len; 809 if (__start >= __adj_endp1) 810 return 0; 811 __result_len = __adj_endp1 - __start; 812 813 if (__result_len > __lazy_threshold) 814 goto lazy; 815 __section = (_CharT*) 816 rope::_Data_allocate(_S_rounded_up_size(__result_len)); 817 __try 818 { (*(__f->_M_fn))(__start, __result_len, __section); } 819 __catch(...) 820 { 821 _RopeRep::__STL_FREE_STRING(__section, __result_len, 822 __base->_M_get_allocator()); 823 __throw_exception_again; 824 } 825 _S_cond_store_eos(__section[__result_len]); 826 return _S_new_RopeLeaf(__section, __result_len, 827 __base->_M_get_allocator()); 828 } 829 } 830 lazy: 831 { 832 // Create substring node. 833 return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start, 834 __base->_M_get_allocator()); 835 } 836 } 837 838 template<class _CharT> 839 class _Rope_flatten_char_consumer 840 : public _Rope_char_consumer<_CharT> 841 { 842 private: 843 _CharT* _M_buf_ptr; 844 public: 845 846 _Rope_flatten_char_consumer(_CharT* __buffer) 847 { _M_buf_ptr = __buffer; } 848 849 ~_Rope_flatten_char_consumer() {} 850 851 bool 852 operator()(const _CharT* __leaf, std::size_t __n) 853 { 854 uninitialized_copy_n(__leaf, __n, _M_buf_ptr); 855 _M_buf_ptr += __n; 856 return true; 857 } 858 }; 859 860 template<class _CharT> 861 class _Rope_find_char_char_consumer 862 : public _Rope_char_consumer<_CharT> 863 { 864 private: 865 _CharT _M_pattern; 866 public: 867 std::size_t _M_count; // Number of nonmatching characters 868 869 _Rope_find_char_char_consumer(_CharT __p) 870 : _M_pattern(__p), _M_count(0) {} 871 872 ~_Rope_find_char_char_consumer() {} 873 874 bool 875 operator()(const _CharT* __leaf, std::size_t __n) 876 { 877 std::size_t __i; 878 for (__i = 0; __i < __n; __i++) 879 { 880 if (__leaf[__i] == _M_pattern) 881 { 882 _M_count += __i; 883 return false; 884 } 885 } 886 _M_count += __n; return true; 887 } 888 }; 889 890 template<class _CharT, class _Traits> 891 // Here _CharT is both the stream and rope character type. 892 class _Rope_insert_char_consumer 893 : public _Rope_char_consumer<_CharT> 894 { 895 private: 896 typedef std::basic_ostream<_CharT,_Traits> _Insert_ostream; 897 _Insert_ostream& _M_o; 898 public: 899 _Rope_insert_char_consumer(_Insert_ostream& __writer) 900 : _M_o(__writer) {} 901 ~_Rope_insert_char_consumer() { } 902 // Caller is presumed to own the ostream 903 bool operator() (const _CharT* __leaf, std::size_t __n); 904 // Returns true to continue traversal. 905 }; 906 907 template<class _CharT, class _Traits> 908 bool 909 _Rope_insert_char_consumer<_CharT, _Traits>:: 910 operator()(const _CharT* __leaf, std::size_t __n) 911 { 912 std::size_t __i; 913 // We assume that formatting is set up correctly for each element. 914 for (__i = 0; __i < __n; __i++) 915 _M_o.put(__leaf[__i]); 916 return true; 917 } 918 919 template <class _CharT, class _Alloc> 920 bool 921 rope<_CharT, _Alloc>:: 922 _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c, const _RopeRep* __r, 923 std::size_t __begin, std::size_t __end) 924 { 925 using std::size_t; 926 if (0 == __r) 927 return true; 928 switch(__r->_M_tag) 929 { 930 case __detail::_S_concat: 931 { 932 _RopeConcatenation* __conc = (_RopeConcatenation*)__r; 933 _RopeRep* __left = __conc->_M_left; 934 size_t __left_len = __left->_M_size; 935 if (__begin < __left_len) 936 { 937 size_t __left_end = std::min(__left_len, __end); 938 if (!_S_apply_to_pieces(__c, __left, __begin, __left_end)) 939 return false; 940 } 941 if (__end > __left_len) 942 { 943 _RopeRep* __right = __conc->_M_right; 944 size_t __right_start = std::max(__left_len, __begin); 945 if (!_S_apply_to_pieces(__c, __right, 946 __right_start - __left_len, 947 __end - __left_len)) 948 return false; 949 } 950 } 951 return true; 952 case __detail::_S_leaf: 953 { 954 _RopeLeaf* __l = (_RopeLeaf*)__r; 955 return __c(__l->_M_data + __begin, __end - __begin); 956 } 957 case __detail::_S_function: 958 case __detail::_S_substringfn: 959 { 960 _RopeFunction* __f = (_RopeFunction*)__r; 961 size_t __len = __end - __begin; 962 bool __result; 963 _CharT* __buffer = 964 (_CharT*)_Alloc().allocate(__len * sizeof(_CharT)); 965 __try 966 { 967 (*(__f->_M_fn))(__begin, __len, __buffer); 968 __result = __c(__buffer, __len); 969 _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); 970 } 971 __catch(...) 972 { 973 _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); 974 __throw_exception_again; 975 } 976 return __result; 977 } 978 default: 979 return false; 980 } 981 } 982 983 template<class _CharT, class _Traits> 984 inline void 985 _Rope_fill(std::basic_ostream<_CharT, _Traits>& __o, std::size_t __n) 986 { 987 char __f = __o.fill(); 988 std::size_t __i; 989 990 for (__i = 0; __i < __n; __i++) 991 __o.put(__f); 992 } 993 994 995 template <class _CharT> 996 inline bool 997 _Rope_is_simple(_CharT*) 998 { return false; } 999 1000 inline bool 1001 _Rope_is_simple(char*) 1002 { return true; } 1003 1004 inline bool 1005 _Rope_is_simple(wchar_t*) 1006 { return true; } 1007 1008 template<class _CharT, class _Traits, class _Alloc> 1009 std::basic_ostream<_CharT, _Traits>& 1010 operator<<(std::basic_ostream<_CharT, _Traits>& __o, 1011 const rope<_CharT, _Alloc>& __r) 1012 { 1013 using std::size_t; 1014 size_t __w = __o.width(); 1015 bool __left = bool(__o.flags() & std::ios::left); 1016 size_t __pad_len; 1017 size_t __rope_len = __r.size(); 1018 _Rope_insert_char_consumer<_CharT, _Traits> __c(__o); 1019 bool __is_simple = _Rope_is_simple((_CharT*)0); 1020 1021 if (__rope_len < __w) 1022 __pad_len = __w - __rope_len; 1023 else 1024 __pad_len = 0; 1025 1026 if (!__is_simple) 1027 __o.width(__w / __rope_len); 1028 __try 1029 { 1030 if (__is_simple && !__left && __pad_len > 0) 1031 _Rope_fill(__o, __pad_len); 1032 __r.apply_to_pieces(0, __r.size(), __c); 1033 if (__is_simple && __left && __pad_len > 0) 1034 _Rope_fill(__o, __pad_len); 1035 if (!__is_simple) 1036 __o.width(__w); 1037 } 1038 __catch(...) 1039 { 1040 if (!__is_simple) 1041 __o.width(__w); 1042 __throw_exception_again; 1043 } 1044 return __o; 1045 } 1046 1047 template <class _CharT, class _Alloc> 1048 _CharT* 1049 rope<_CharT, _Alloc>:: 1050 _S_flatten(_RopeRep* __r, std::size_t __start, std::size_t __len, 1051 _CharT* __buffer) 1052 { 1053 _Rope_flatten_char_consumer<_CharT> __c(__buffer); 1054 _S_apply_to_pieces(__c, __r, __start, __start + __len); 1055 return(__buffer + __len); 1056 } 1057 1058 template <class _CharT, class _Alloc> 1059 std::size_t 1060 rope<_CharT, _Alloc>:: 1061 find(_CharT __pattern, std::size_t __start) const 1062 { 1063 _Rope_find_char_char_consumer<_CharT> __c(__pattern); 1064 _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size()); 1065 size_type __result_pos = __start + __c._M_count; 1066#ifndef __STL_OLD_ROPE_SEMANTICS 1067 if (__result_pos == size()) 1068 __result_pos = npos; 1069#endif 1070 return __result_pos; 1071 } 1072 1073 template <class _CharT, class _Alloc> 1074 _CharT* 1075 rope<_CharT, _Alloc>:: 1076 _S_flatten(_RopeRep* __r, _CharT* __buffer) 1077 { 1078 if (0 == __r) 1079 return __buffer; 1080 switch(__r->_M_tag) 1081 { 1082 case __detail::_S_concat: 1083 { 1084 _RopeConcatenation* __c = (_RopeConcatenation*)__r; 1085 _RopeRep* __left = __c->_M_left; 1086 _RopeRep* __right = __c->_M_right; 1087 _CharT* __rest = _S_flatten(__left, __buffer); 1088 return _S_flatten(__right, __rest); 1089 } 1090 case __detail::_S_leaf: 1091 { 1092 _RopeLeaf* __l = (_RopeLeaf*)__r; 1093 return copy_n(__l->_M_data, __l->_M_size, __buffer).second; 1094 } 1095 case __detail::_S_function: 1096 case __detail::_S_substringfn: 1097 // We don't yet do anything with substring nodes. 1098 // This needs to be fixed before ropefiles will work well. 1099 { 1100 _RopeFunction* __f = (_RopeFunction*)__r; 1101 (*(__f->_M_fn))(0, __f->_M_size, __buffer); 1102 return __buffer + __f->_M_size; 1103 } 1104 default: 1105 return 0; 1106 } 1107 } 1108 1109 // This needs work for _CharT != char 1110 template <class _CharT, class _Alloc> 1111 void 1112 rope<_CharT, _Alloc>:: 1113 _S_dump(_RopeRep* __r, int __indent) 1114 { 1115 using std::printf; 1116 for (int __i = 0; __i < __indent; __i++) 1117 putchar(' '); 1118 if (0 == __r) 1119 { 1120 printf("NULL\n"); 1121 return; 1122 } 1123 if (__detail::_S_concat == __r->_M_tag) 1124 { 1125 _RopeConcatenation* __c = (_RopeConcatenation*)__r; 1126 _RopeRep* __left = __c->_M_left; 1127 _RopeRep* __right = __c->_M_right; 1128 1129#ifdef __GC 1130 printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n", 1131 __r, __r->_M_depth, __r->_M_size, 1132 __r->_M_is_balanced? "" : "not"); 1133#else 1134 printf("Concatenation %p (rc = %ld, depth = %d, " 1135 "len = %ld, %s balanced)\n", 1136 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size, 1137 __r->_M_is_balanced? "" : "not"); 1138#endif 1139 _S_dump(__left, __indent + 2); 1140 _S_dump(__right, __indent + 2); 1141 return; 1142 } 1143 else 1144 { 1145 const char* __kind; 1146 1147 switch (__r->_M_tag) 1148 { 1149 case __detail::_S_leaf: 1150 __kind = "Leaf"; 1151 break; 1152 case __detail::_S_function: 1153 __kind = "Function"; 1154 break; 1155 case __detail::_S_substringfn: 1156 __kind = "Function representing substring"; 1157 break; 1158 default: 1159 __kind = "(corrupted kind field!)"; 1160 } 1161#ifdef __GC 1162 printf("%s %p (depth = %d, len = %ld) ", 1163 __kind, __r, __r->_M_depth, __r->_M_size); 1164#else 1165 printf("%s %p (rc = %ld, depth = %d, len = %ld) ", 1166 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size); 1167#endif 1168 if (_S_is_one_byte_char_type((_CharT*)0)) 1169 { 1170 const int __max_len = 40; 1171 _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len)); 1172 _CharT __buffer[__max_len + 1]; 1173 bool __too_big = __r->_M_size > __prefix->_M_size; 1174 1175 _S_flatten(__prefix, __buffer); 1176 __buffer[__prefix->_M_size] = _S_eos((_CharT*)0); 1177 printf("%s%s\n", (char*)__buffer, 1178 __too_big? "...\n" : "\n"); 1179 } 1180 else 1181 printf("\n"); 1182 } 1183 } 1184 1185 template <class _CharT, class _Alloc> 1186 const unsigned long 1187 rope<_CharT, _Alloc>:: 1188 _S_min_len[int(__detail::_S_max_rope_depth) + 1] = { 1189 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, 1190 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, 1191 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, 1192 /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368, 1193 /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811, 1194 /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309, 1195 /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352, 1196 /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155, 1197 /* 39 */165580141, /* 40 */267914296, /* 41 */433494437, 1198 /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903, 1199 /* 45 */2971215073u }; 1200 // These are Fibonacci numbers < 2**32. 1201 1202 template <class _CharT, class _Alloc> 1203 typename rope<_CharT, _Alloc>::_RopeRep* 1204 rope<_CharT, _Alloc>:: 1205 _S_balance(_RopeRep* __r) 1206 { 1207 _RopeRep* __forest[int(__detail::_S_max_rope_depth) + 1]; 1208 _RopeRep* __result = 0; 1209 int __i; 1210 // Invariant: 1211 // The concatenation of forest in descending order is equal to __r. 1212 // __forest[__i]._M_size >= _S_min_len[__i] 1213 // __forest[__i]._M_depth = __i 1214 // References from forest are included in refcount. 1215 1216 for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i) 1217 __forest[__i] = 0; 1218 __try 1219 { 1220 _S_add_to_forest(__r, __forest); 1221 for (__i = 0; __i <= int(__detail::_S_max_rope_depth); ++__i) 1222 if (0 != __forest[__i]) 1223 { 1224#ifndef __GC 1225 _Self_destruct_ptr __old(__result); 1226#endif 1227 __result = _S_concat(__forest[__i], __result); 1228 __forest[__i]->_M_unref_nonnil(); 1229#if !defined(__GC) && __cpp_exceptions 1230 __forest[__i] = 0; 1231#endif 1232 } 1233 } 1234 __catch(...) 1235 { 1236 for(__i = 0; __i <= int(__detail::_S_max_rope_depth); __i++) 1237 _S_unref(__forest[__i]); 1238 __throw_exception_again; 1239 } 1240 1241 if (__result->_M_depth > int(__detail::_S_max_rope_depth)) 1242 std::__throw_length_error(__N("rope::_S_balance")); 1243 return(__result); 1244 } 1245 1246 template <class _CharT, class _Alloc> 1247 void 1248 rope<_CharT, _Alloc>:: 1249 _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest) 1250 { 1251 if (__r->_M_is_balanced) 1252 { 1253 _S_add_leaf_to_forest(__r, __forest); 1254 return; 1255 } 1256 1257 { 1258 _RopeConcatenation* __c = (_RopeConcatenation*)__r; 1259 1260 _S_add_to_forest(__c->_M_left, __forest); 1261 _S_add_to_forest(__c->_M_right, __forest); 1262 } 1263 } 1264 1265 1266 template <class _CharT, class _Alloc> 1267 void 1268 rope<_CharT, _Alloc>:: 1269 _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest) 1270 { 1271 _RopeRep* __insertee; // included in refcount 1272 _RopeRep* __too_tiny = 0; // included in refcount 1273 int __i; // forest[0..__i-1] is empty 1274 std::size_t __s = __r->_M_size; 1275 1276 for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) 1277 { 1278 if (0 != __forest[__i]) 1279 { 1280#ifndef __GC 1281 _Self_destruct_ptr __old(__too_tiny); 1282#endif 1283 __too_tiny = _S_concat_and_set_balanced(__forest[__i], 1284 __too_tiny); 1285 __forest[__i]->_M_unref_nonnil(); 1286 __forest[__i] = 0; 1287 } 1288 } 1289 { 1290#ifndef __GC 1291 _Self_destruct_ptr __old(__too_tiny); 1292#endif 1293 __insertee = _S_concat_and_set_balanced(__too_tiny, __r); 1294 } 1295 // Too_tiny dead, and no longer included in refcount. 1296 // Insertee is live and included. 1297 for (;; ++__i) 1298 { 1299 if (0 != __forest[__i]) 1300 { 1301#ifndef __GC 1302 _Self_destruct_ptr __old(__insertee); 1303#endif 1304 __insertee = _S_concat_and_set_balanced(__forest[__i], 1305 __insertee); 1306 __forest[__i]->_M_unref_nonnil(); 1307 __forest[__i] = 0; 1308 } 1309 if (__i == int(__detail::_S_max_rope_depth) 1310 || __insertee->_M_size < _S_min_len[__i+1]) 1311 { 1312 __forest[__i] = __insertee; 1313 // refcount is OK since __insertee is now dead. 1314 return; 1315 } 1316 } 1317 } 1318 1319 template <class _CharT, class _Alloc> 1320 _CharT 1321 rope<_CharT, _Alloc>:: 1322 _S_fetch(_RopeRep* __r, size_type __i) 1323 { 1324 __GC_CONST _CharT* __cstr = __r->_M_c_string; 1325 1326 if (0 != __cstr) 1327 return __cstr[__i]; 1328 for(;;) 1329 { 1330 switch(__r->_M_tag) 1331 { 1332 case __detail::_S_concat: 1333 { 1334 _RopeConcatenation* __c = (_RopeConcatenation*)__r; 1335 _RopeRep* __left = __c->_M_left; 1336 std::size_t __left_len = __left->_M_size; 1337 1338 if (__i >= __left_len) 1339 { 1340 __i -= __left_len; 1341 __r = __c->_M_right; 1342 } 1343 else 1344 __r = __left; 1345 } 1346 break; 1347 case __detail::_S_leaf: 1348 { 1349 _RopeLeaf* __l = (_RopeLeaf*)__r; 1350 return __l->_M_data[__i]; 1351 } 1352 case __detail::_S_function: 1353 case __detail::_S_substringfn: 1354 { 1355 _RopeFunction* __f = (_RopeFunction*)__r; 1356 _CharT __result; 1357 1358 (*(__f->_M_fn))(__i, 1, &__result); 1359 return __result; 1360 } 1361 } 1362 } 1363 } 1364 1365#ifndef __GC 1366 // Return a uniquely referenced character slot for the given 1367 // position, or 0 if that's not possible. 1368 template <class _CharT, class _Alloc> 1369 _CharT* 1370 rope<_CharT, _Alloc>:: 1371 _S_fetch_ptr(_RopeRep* __r, size_type __i) 1372 { 1373 _RopeRep* __clrstack[__detail::_S_max_rope_depth]; 1374 std::size_t __csptr = 0; 1375 1376 for(;;) 1377 { 1378 if (__r->_M_ref_count > 1) 1379 return 0; 1380 switch(__r->_M_tag) 1381 { 1382 case __detail::_S_concat: 1383 { 1384 _RopeConcatenation* __c = (_RopeConcatenation*)__r; 1385 _RopeRep* __left = __c->_M_left; 1386 std::size_t __left_len = __left->_M_size; 1387 1388 if (__c->_M_c_string != 0) 1389 __clrstack[__csptr++] = __c; 1390 if (__i >= __left_len) 1391 { 1392 __i -= __left_len; 1393 __r = __c->_M_right; 1394 } 1395 else 1396 __r = __left; 1397 } 1398 break; 1399 case __detail::_S_leaf: 1400 { 1401 _RopeLeaf* __l = (_RopeLeaf*)__r; 1402 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0) 1403 __clrstack[__csptr++] = __l; 1404 while (__csptr > 0) 1405 { 1406 -- __csptr; 1407 _RopeRep* __d = __clrstack[__csptr]; 1408 __d->_M_free_c_string(); 1409 __d->_M_c_string = 0; 1410 } 1411 return __l->_M_data + __i; 1412 } 1413 case __detail::_S_function: 1414 case __detail::_S_substringfn: 1415 return 0; 1416 } 1417 } 1418 } 1419#endif /* __GC */ 1420 1421 // The following could be implemented trivially using 1422 // lexicographical_compare_3way. 1423 // We do a little more work to avoid dealing with rope iterators for 1424 // flat strings. 1425 template <class _CharT, class _Alloc> 1426 int 1427 rope<_CharT, _Alloc>:: 1428 _S_compare (const _RopeRep* __left, const _RopeRep* __right) 1429 { 1430 std::size_t __left_len; 1431 std::size_t __right_len; 1432 1433 if (0 == __right) 1434 return 0 != __left; 1435 if (0 == __left) 1436 return -1; 1437 __left_len = __left->_M_size; 1438 __right_len = __right->_M_size; 1439 if (__detail::_S_leaf == __left->_M_tag) 1440 { 1441 _RopeLeaf* __l = (_RopeLeaf*) __left; 1442 if (__detail::_S_leaf == __right->_M_tag) 1443 { 1444 _RopeLeaf* __r = (_RopeLeaf*) __right; 1445 return lexicographical_compare_3way(__l->_M_data, 1446 __l->_M_data + __left_len, 1447 __r->_M_data, __r->_M_data 1448 + __right_len); 1449 } 1450 else 1451 { 1452 const_iterator __rstart(__right, 0); 1453 const_iterator __rend(__right, __right_len); 1454 return lexicographical_compare_3way(__l->_M_data, __l->_M_data 1455 + __left_len, 1456 __rstart, __rend); 1457 } 1458 } 1459 else 1460 { 1461 const_iterator __lstart(__left, 0); 1462 const_iterator __lend(__left, __left_len); 1463 if (__detail::_S_leaf == __right->_M_tag) 1464 { 1465 _RopeLeaf* __r = (_RopeLeaf*) __right; 1466 return lexicographical_compare_3way(__lstart, __lend, 1467 __r->_M_data, __r->_M_data 1468 + __right_len); 1469 } 1470 else 1471 { 1472 const_iterator __rstart(__right, 0); 1473 const_iterator __rend(__right, __right_len); 1474 return lexicographical_compare_3way(__lstart, __lend, 1475 __rstart, __rend); 1476 } 1477 } 1478 } 1479 1480 // Assignment to reference proxies. 1481 template <class _CharT, class _Alloc> 1482 _Rope_char_ref_proxy<_CharT, _Alloc>& 1483 _Rope_char_ref_proxy<_CharT, _Alloc>:: 1484 operator=(_CharT __c) 1485 { 1486 _RopeRep* __old = _M_root->_M_tree_ptr; 1487#ifndef __GC 1488 // First check for the case in which everything is uniquely 1489 // referenced. In that case we can do this destructively. 1490 _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos); 1491 if (0 != __ptr) 1492 { 1493 *__ptr = __c; 1494 return *this; 1495 } 1496#endif 1497 _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos)); 1498 _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1, 1499 __old->_M_size)); 1500 typename _RopeRep::allocator_type __a = _M_root->_M_get_allocator(); 1501 _Self_destruct_ptr __result_left(_My_rope:: 1502 _S_destr_concat_char_iter(__left, 1503 &__c, 1, 1504 __a)); 1505 1506 _RopeRep* __result = _My_rope::_S_concat(__result_left, __right); 1507#ifndef __GC 1508 _RopeRep::_S_unref(__old); 1509#endif 1510 _M_root->_M_tree_ptr = __result; 1511 return *this; 1512 } 1513 1514 template <class _CharT, class _Alloc> 1515 inline _Rope_char_ref_proxy<_CharT, _Alloc>:: 1516 operator _CharT() const 1517 { 1518 if (_M_current_valid) 1519 return _M_current; 1520 else 1521 return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos); 1522 } 1523 1524 template <class _CharT, class _Alloc> 1525 _Rope_char_ptr_proxy<_CharT, _Alloc> 1526 _Rope_char_ref_proxy<_CharT, _Alloc>:: 1527 operator&() const 1528 { return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); } 1529 1530 template <class _CharT, class _Alloc> 1531 rope<_CharT, _Alloc>:: 1532 rope(std::size_t __n, _CharT __c, const allocator_type& __a) 1533 : _Base(__a) 1534 { 1535 using std::__uninitialized_fill_n_a; 1536 1537 rope<_CharT,_Alloc> __result; 1538 const std::size_t __exponentiate_threshold = 32; 1539 std::size_t __exponent; 1540 std::size_t __rest; 1541 _CharT* __rest_buffer; 1542 _RopeRep* __remainder; 1543 rope<_CharT, _Alloc> __remainder_rope; 1544 1545 if (0 == __n) 1546 return; 1547 1548 __exponent = __n / __exponentiate_threshold; 1549 __rest = __n % __exponentiate_threshold; 1550 if (0 == __rest) 1551 __remainder = 0; 1552 else 1553 { 1554 __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest)); 1555 __uninitialized_fill_n_a(__rest_buffer, __rest, __c, 1556 _M_get_allocator()); 1557 _S_cond_store_eos(__rest_buffer[__rest]); 1558 __try 1559 { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, 1560 _M_get_allocator()); } 1561 __catch(...) 1562 { 1563 _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, 1564 _M_get_allocator()); 1565 __throw_exception_again; 1566 } 1567 } 1568 __remainder_rope._M_tree_ptr = __remainder; 1569 if (__exponent != 0) 1570 { 1571 _CharT* __base_buffer = 1572 this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold)); 1573 _RopeLeaf* __base_leaf; 1574 rope __base_rope; 1575 __uninitialized_fill_n_a(__base_buffer, __exponentiate_threshold, __c, 1576 _M_get_allocator()); 1577 _S_cond_store_eos(__base_buffer[__exponentiate_threshold]); 1578 __try 1579 { 1580 __base_leaf = _S_new_RopeLeaf(__base_buffer, 1581 __exponentiate_threshold, 1582 _M_get_allocator()); 1583 } 1584 __catch(...) 1585 { 1586 _RopeRep::__STL_FREE_STRING(__base_buffer, 1587 __exponentiate_threshold, 1588 _M_get_allocator()); 1589 __throw_exception_again; 1590 } 1591 __base_rope._M_tree_ptr = __base_leaf; 1592 if (1 == __exponent) 1593 __result = __base_rope; 1594 else 1595 __result = power(__base_rope, __exponent, 1596 _Rope_Concat_fn<_CharT, _Alloc>()); 1597 1598 if (0 != __remainder) 1599 __result += __remainder_rope; 1600 } 1601 else 1602 __result = __remainder_rope; 1603 1604 this->_M_tree_ptr = __result._M_tree_ptr; 1605 this->_M_tree_ptr->_M_ref_nonnil(); 1606 } 1607 1608 template<class _CharT, class _Alloc> 1609 _CharT 1610 rope<_CharT, _Alloc>::_S_empty_c_str[1]; 1611 1612 template<class _CharT, class _Alloc> 1613 const _CharT* 1614 rope<_CharT, _Alloc>:: 1615 c_str() const 1616 { 1617 if (0 == this->_M_tree_ptr) 1618 { 1619 _S_empty_c_str[0] = _S_eos((_CharT*)0); // Possibly redundant, 1620 // but probably fast. 1621 return _S_empty_c_str; 1622 } 1623 __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock); 1624 __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string; 1625 if (0 == __result) 1626 { 1627 std::size_t __s = size(); 1628 __result = this->_Data_allocate(__s + 1); 1629 _S_flatten(this->_M_tree_ptr, __result); 1630 __result[__s] = _S_eos((_CharT*)0); 1631 this->_M_tree_ptr->_M_c_string = __result; 1632 } 1633 __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock); 1634 return(__result); 1635 } 1636 1637 template<class _CharT, class _Alloc> 1638 const _CharT* rope<_CharT, _Alloc>:: 1639 replace_with_c_str() 1640 { 1641 if (0 == this->_M_tree_ptr) 1642 { 1643 _S_empty_c_str[0] = _S_eos((_CharT*)0); 1644 return _S_empty_c_str; 1645 } 1646 __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string; 1647 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag 1648 && 0 != __old_c_string) 1649 return(__old_c_string); 1650 std::size_t __s = size(); 1651 _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s)); 1652 _S_flatten(this->_M_tree_ptr, __result); 1653 __result[__s] = _S_eos((_CharT*)0); 1654 this->_M_tree_ptr->_M_unref_nonnil(); 1655 this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s, 1656 this->_M_get_allocator()); 1657 return(__result); 1658 } 1659 1660 // Algorithm specializations. More should be added. 1661 1662 template<class _Rope_iterator> // was templated on CharT and Alloc 1663 void // VC++ workaround 1664 _Rope_rotate(_Rope_iterator __first, 1665 _Rope_iterator __middle, 1666 _Rope_iterator __last) 1667 { 1668 typedef typename _Rope_iterator::value_type _CharT; 1669 typedef typename _Rope_iterator::_allocator_type _Alloc; 1670 1671 rope<_CharT, _Alloc>& __r(__first.container()); 1672 rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index()); 1673 rope<_CharT, _Alloc> __suffix = 1674 __r.substr(__last.index(), __r.size() - __last.index()); 1675 rope<_CharT, _Alloc> __part1 = 1676 __r.substr(__middle.index(), __last.index() - __middle.index()); 1677 rope<_CharT, _Alloc> __part2 = 1678 __r.substr(__first.index(), __middle.index() - __first.index()); 1679 __r = __prefix; 1680 __r += __part1; 1681 __r += __part2; 1682 __r += __suffix; 1683 } 1684 1685#if !defined(__GNUC__) 1686 // Appears to confuse g++ 1687 inline void 1688 rotate(_Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __first, 1689 _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __middle, 1690 _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __last) 1691 { _Rope_rotate(__first, __middle, __last); } 1692#endif 1693 1694# if 0 1695 // Probably not useful for several reasons: 1696 // - for SGIs 7.1 compiler and probably some others, 1697 // this forces lots of rope<wchar_t, ...> instantiations, creating a 1698 // code bloat and compile time problem. (Fixed in 7.2.) 1699 // - wchar_t is 4 bytes wide on most UNIX platforms, making it 1700 // unattractive for unicode strings. Unsigned short may be a better 1701 // character type. 1702 inline void 1703 rotate(_Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first, 1704 _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle, 1705 _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last) 1706 { _Rope_rotate(__first, __middle, __last); } 1707# endif 1708 1709_GLIBCXX_END_NAMESPACE_VERSION 1710} // namespace 1711