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