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