1 // SGI's rope class -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 4 // 2012 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 ext/rope 40 * This file is a GNU extension to the Standard C++ Library (possibly 41 * containing extensions from the HP/SGI STL subset). 42 */ 43 44 #ifndef _ROPE 45 #define _ROPE 1 46 47 #pragma GCC system_header 48 49 #include <algorithm> 50 #include <iosfwd> 51 #include <bits/stl_construct.h> 52 #include <bits/stl_uninitialized.h> 53 #include <bits/stl_function.h> 54 #include <bits/stl_numeric.h> 55 #include <bits/allocator.h> 56 #include <bits/gthr.h> 57 #include <tr1/functional> 58 59 # ifdef __GC 60 # define __GC_CONST const 61 # else 62 # define __GC_CONST // constant except for deallocation 63 # endif 64 65 #include <ext/memory> // For uninitialized_copy_n 66 67 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 68 { 69 namespace __detail 70 { 71 enum { _S_max_rope_depth = 45 }; 72 enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function}; 73 } // namespace __detail 74 75 using std::size_t; 76 using std::ptrdiff_t; 77 using std::allocator; 78 using std::_Destroy; 79 80 _GLIBCXX_BEGIN_NAMESPACE_VERSION 81 82 // See libstdc++/36832. 83 template<typename _ForwardIterator, typename _Allocator> 84 void 85 _Destroy_const(_ForwardIterator __first, 86 _ForwardIterator __last, _Allocator __alloc) 87 { 88 for (; __first != __last; ++__first) 89 __alloc.destroy(&*__first); 90 } 91 92 template<typename _ForwardIterator, typename _Tp> 93 inline void 94 _Destroy_const(_ForwardIterator __first, 95 _ForwardIterator __last, allocator<_Tp>) 96 { _Destroy(__first, __last); } 97 98 // The _S_eos function is used for those functions that 99 // convert to/from C-like strings to detect the end of the string. 100 101 // The end-of-C-string character. 102 // This is what the draft standard says it should be. 103 template <class _CharT> 104 inline _CharT 105 _S_eos(_CharT*) 106 { return _CharT(); } 107 108 // Test for basic character types. 109 // For basic character types leaves having a trailing eos. 110 template <class _CharT> 111 inline bool 112 _S_is_basic_char_type(_CharT*) 113 { return false; } 114 115 template <class _CharT> 116 inline bool 117 _S_is_one_byte_char_type(_CharT*) 118 { return false; } 119 120 inline bool 121 _S_is_basic_char_type(char*) 122 { return true; } 123 124 inline bool 125 _S_is_one_byte_char_type(char*) 126 { return true; } 127 128 inline bool 129 _S_is_basic_char_type(wchar_t*) 130 { return true; } 131 132 // Store an eos iff _CharT is a basic character type. 133 // Do not reference _S_eos if it isn't. 134 template <class _CharT> 135 inline void 136 _S_cond_store_eos(_CharT&) { } 137 138 inline void 139 _S_cond_store_eos(char& __c) 140 { __c = 0; } 141 142 inline void 143 _S_cond_store_eos(wchar_t& __c) 144 { __c = 0; } 145 146 // char_producers are logically functions that generate a section of 147 // a string. These can be converted to ropes. The resulting rope 148 // invokes the char_producer on demand. This allows, for example, 149 // files to be viewed as ropes without reading the entire file. 150 template <class _CharT> 151 class char_producer 152 { 153 public: 154 virtual ~char_producer() { }; 155 156 virtual void 157 operator()(size_t __start_pos, size_t __len, 158 _CharT* __buffer) = 0; 159 // Buffer should really be an arbitrary output iterator. 160 // That way we could flatten directly into an ostream, etc. 161 // This is thoroughly impossible, since iterator types don't 162 // have runtime descriptions. 163 }; 164 165 // Sequence buffers: 166 // 167 // Sequence must provide an append operation that appends an 168 // array to the sequence. Sequence buffers are useful only if 169 // appending an entire array is cheaper than appending element by element. 170 // This is true for many string representations. 171 // This should perhaps inherit from ostream<sequence::value_type> 172 // and be implemented correspondingly, so that they can be used 173 // for formatted. For the sake of portability, we don't do this yet. 174 // 175 // For now, sequence buffers behave as output iterators. But they also 176 // behave a little like basic_ostringstream<sequence::value_type> and a 177 // little like containers. 178 179 template<class _Sequence, size_t _Buf_sz = 100> 180 class sequence_buffer 181 : public std::iterator<std::output_iterator_tag, void, void, void, void> 182 { 183 public: 184 typedef typename _Sequence::value_type value_type; 185 protected: 186 _Sequence* _M_prefix; 187 value_type _M_buffer[_Buf_sz]; 188 size_t _M_buf_count; 189 public: 190 191 void 192 flush() 193 { 194 _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count); 195 _M_buf_count = 0; 196 } 197 198 ~sequence_buffer() 199 { flush(); } 200 201 sequence_buffer() 202 : _M_prefix(0), _M_buf_count(0) { } 203 204 sequence_buffer(const sequence_buffer& __x) 205 { 206 _M_prefix = __x._M_prefix; 207 _M_buf_count = __x._M_buf_count; 208 std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer); 209 } 210 211 sequence_buffer(sequence_buffer& __x) 212 { 213 __x.flush(); 214 _M_prefix = __x._M_prefix; 215 _M_buf_count = 0; 216 } 217 218 sequence_buffer(_Sequence& __s) 219 : _M_prefix(&__s), _M_buf_count(0) { } 220 221 sequence_buffer& 222 operator=(sequence_buffer& __x) 223 { 224 __x.flush(); 225 _M_prefix = __x._M_prefix; 226 _M_buf_count = 0; 227 return *this; 228 } 229 230 sequence_buffer& 231 operator=(const sequence_buffer& __x) 232 { 233 _M_prefix = __x._M_prefix; 234 _M_buf_count = __x._M_buf_count; 235 std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer); 236 return *this; 237 } 238 239 void 240 push_back(value_type __x) 241 { 242 if (_M_buf_count < _Buf_sz) 243 { 244 _M_buffer[_M_buf_count] = __x; 245 ++_M_buf_count; 246 } 247 else 248 { 249 flush(); 250 _M_buffer[0] = __x; 251 _M_buf_count = 1; 252 } 253 } 254 255 void 256 append(value_type* __s, size_t __len) 257 { 258 if (__len + _M_buf_count <= _Buf_sz) 259 { 260 size_t __i = _M_buf_count; 261 for (size_t __j = 0; __j < __len; __i++, __j++) 262 _M_buffer[__i] = __s[__j]; 263 _M_buf_count += __len; 264 } 265 else if (0 == _M_buf_count) 266 _M_prefix->append(__s, __s + __len); 267 else 268 { 269 flush(); 270 append(__s, __len); 271 } 272 } 273 274 sequence_buffer& 275 write(value_type* __s, size_t __len) 276 { 277 append(__s, __len); 278 return *this; 279 } 280 281 sequence_buffer& 282 put(value_type __x) 283 { 284 push_back(__x); 285 return *this; 286 } 287 288 sequence_buffer& 289 operator=(const value_type& __rhs) 290 { 291 push_back(__rhs); 292 return *this; 293 } 294 295 sequence_buffer& 296 operator*() 297 { return *this; } 298 299 sequence_buffer& 300 operator++() 301 { return *this; } 302 303 sequence_buffer 304 operator++(int) 305 { return *this; } 306 }; 307 308 // The following should be treated as private, at least for now. 309 template<class _CharT> 310 class _Rope_char_consumer 311 { 312 public: 313 // If we had member templates, these should not be virtual. 314 // For now we need to use run-time parametrization where 315 // compile-time would do. Hence this should all be private 316 // for now. 317 // The symmetry with char_producer is accidental and temporary. 318 virtual ~_Rope_char_consumer() { }; 319 320 virtual bool 321 operator()(const _CharT* __buffer, size_t __len) = 0; 322 }; 323 324 // First a lot of forward declarations. The standard seems to require 325 // much stricter "declaration before use" than many of the implementations 326 // that preceded it. 327 template<class _CharT, class _Alloc = allocator<_CharT> > 328 class rope; 329 330 template<class _CharT, class _Alloc> 331 struct _Rope_RopeConcatenation; 332 333 template<class _CharT, class _Alloc> 334 struct _Rope_RopeLeaf; 335 336 template<class _CharT, class _Alloc> 337 struct _Rope_RopeFunction; 338 339 template<class _CharT, class _Alloc> 340 struct _Rope_RopeSubstring; 341 342 template<class _CharT, class _Alloc> 343 class _Rope_iterator; 344 345 template<class _CharT, class _Alloc> 346 class _Rope_const_iterator; 347 348 template<class _CharT, class _Alloc> 349 class _Rope_char_ref_proxy; 350 351 template<class _CharT, class _Alloc> 352 class _Rope_char_ptr_proxy; 353 354 template<class _CharT, class _Alloc> 355 bool 356 operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, 357 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y); 358 359 template<class _CharT, class _Alloc> 360 _Rope_const_iterator<_CharT, _Alloc> 361 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, 362 ptrdiff_t __n); 363 364 template<class _CharT, class _Alloc> 365 _Rope_const_iterator<_CharT, _Alloc> 366 operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, 367 ptrdiff_t __n); 368 369 template<class _CharT, class _Alloc> 370 _Rope_const_iterator<_CharT, _Alloc> 371 operator+(ptrdiff_t __n, 372 const _Rope_const_iterator<_CharT, _Alloc>& __x); 373 374 template<class _CharT, class _Alloc> 375 bool 376 operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x, 377 const _Rope_const_iterator<_CharT, _Alloc>& __y); 378 379 template<class _CharT, class _Alloc> 380 bool 381 operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x, 382 const _Rope_const_iterator<_CharT, _Alloc>& __y); 383 384 template<class _CharT, class _Alloc> 385 ptrdiff_t 386 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, 387 const _Rope_const_iterator<_CharT, _Alloc>& __y); 388 389 template<class _CharT, class _Alloc> 390 _Rope_iterator<_CharT, _Alloc> 391 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n); 392 393 template<class _CharT, class _Alloc> 394 _Rope_iterator<_CharT, _Alloc> 395 operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n); 396 397 template<class _CharT, class _Alloc> 398 _Rope_iterator<_CharT, _Alloc> 399 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x); 400 401 template<class _CharT, class _Alloc> 402 bool 403 operator==(const _Rope_iterator<_CharT, _Alloc>& __x, 404 const _Rope_iterator<_CharT, _Alloc>& __y); 405 406 template<class _CharT, class _Alloc> 407 bool 408 operator<(const _Rope_iterator<_CharT, _Alloc>& __x, 409 const _Rope_iterator<_CharT, _Alloc>& __y); 410 411 template<class _CharT, class _Alloc> 412 ptrdiff_t 413 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, 414 const _Rope_iterator<_CharT, _Alloc>& __y); 415 416 template<class _CharT, class _Alloc> 417 rope<_CharT, _Alloc> 418 operator+(const rope<_CharT, _Alloc>& __left, 419 const rope<_CharT, _Alloc>& __right); 420 421 template<class _CharT, class _Alloc> 422 rope<_CharT, _Alloc> 423 operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right); 424 425 template<class _CharT, class _Alloc> 426 rope<_CharT, _Alloc> 427 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right); 428 429 // Some helpers, so we can use power on ropes. 430 // See below for why this isn't local to the implementation. 431 432 // This uses a nonstandard refcount convention. 433 // The result has refcount 0. 434 template<class _CharT, class _Alloc> 435 struct _Rope_Concat_fn 436 : public std::binary_function<rope<_CharT, _Alloc>, rope<_CharT, _Alloc>, 437 rope<_CharT, _Alloc> > 438 { 439 rope<_CharT, _Alloc> 440 operator()(const rope<_CharT, _Alloc>& __x, 441 const rope<_CharT, _Alloc>& __y) 442 { return __x + __y; } 443 }; 444 445 template <class _CharT, class _Alloc> 446 inline rope<_CharT, _Alloc> 447 identity_element(_Rope_Concat_fn<_CharT, _Alloc>) 448 { return rope<_CharT, _Alloc>(); } 449 450 // Class _Refcount_Base provides a type, _RC_t, a data member, 451 // _M_ref_count, and member functions _M_incr and _M_decr, which perform 452 // atomic preincrement/predecrement. The constructor initializes 453 // _M_ref_count. 454 struct _Refcount_Base 455 { 456 // The type _RC_t 457 typedef size_t _RC_t; 458 459 // The data member _M_ref_count 460 volatile _RC_t _M_ref_count; 461 462 // Constructor 463 #ifdef __GTHREAD_MUTEX_INIT 464 __gthread_mutex_t _M_ref_count_lock = __GTHREAD_MUTEX_INIT; 465 #else 466 __gthread_mutex_t _M_ref_count_lock; 467 #endif 468 469 _Refcount_Base(_RC_t __n) : _M_ref_count(__n) 470 { 471 #ifndef __GTHREAD_MUTEX_INIT 472 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION 473 __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock); 474 #else 475 #error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org. 476 #endif 477 #endif 478 } 479 480 #ifndef __GTHREAD_MUTEX_INIT 481 ~_Refcount_Base() 482 { __gthread_mutex_destroy(&_M_ref_count_lock); } 483 #endif 484 485 void 486 _M_incr() 487 { 488 __gthread_mutex_lock(&_M_ref_count_lock); 489 ++_M_ref_count; 490 __gthread_mutex_unlock(&_M_ref_count_lock); 491 } 492 493 _RC_t 494 _M_decr() 495 { 496 __gthread_mutex_lock(&_M_ref_count_lock); 497 volatile _RC_t __tmp = --_M_ref_count; 498 __gthread_mutex_unlock(&_M_ref_count_lock); 499 return __tmp; 500 } 501 }; 502 503 // 504 // What follows should really be local to rope. Unfortunately, 505 // that doesn't work, since it makes it impossible to define generic 506 // equality on rope iterators. According to the draft standard, the 507 // template parameters for such an equality operator cannot be inferred 508 // from the occurrence of a member class as a parameter. 509 // (SGI compilers in fact allow this, but the __result wouldn't be 510 // portable.) 511 // Similarly, some of the static member functions are member functions 512 // only to avoid polluting the global namespace, and to circumvent 513 // restrictions on type inference for template functions. 514 // 515 516 // 517 // The internal data structure for representing a rope. This is 518 // private to the implementation. A rope is really just a pointer 519 // to one of these. 520 // 521 // A few basic functions for manipulating this data structure 522 // are members of _RopeRep. Most of the more complex algorithms 523 // are implemented as rope members. 524 // 525 // Some of the static member functions of _RopeRep have identically 526 // named functions in rope that simply invoke the _RopeRep versions. 527 528 #define __ROPE_DEFINE_ALLOCS(__a) \ 529 __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \ 530 typedef _Rope_RopeConcatenation<_CharT,__a> __C; \ 531 __ROPE_DEFINE_ALLOC(__C,_C) \ 532 typedef _Rope_RopeLeaf<_CharT,__a> __L; \ 533 __ROPE_DEFINE_ALLOC(__L,_L) \ 534 typedef _Rope_RopeFunction<_CharT,__a> __F; \ 535 __ROPE_DEFINE_ALLOC(__F,_F) \ 536 typedef _Rope_RopeSubstring<_CharT,__a> __S; \ 537 __ROPE_DEFINE_ALLOC(__S,_S) 538 539 // Internal rope nodes potentially store a copy of the allocator 540 // instance used to allocate them. This is mostly redundant. 541 // But the alternative would be to pass allocator instances around 542 // in some form to nearly all internal functions, since any pointer 543 // assignment may result in a zero reference count and thus require 544 // deallocation. 545 546 #define __STATIC_IF_SGI_ALLOC /* not static */ 547 548 template <class _CharT, class _Alloc> 549 struct _Rope_rep_base 550 : public _Alloc 551 { 552 typedef _Alloc allocator_type; 553 554 allocator_type 555 get_allocator() const 556 { return *static_cast<const _Alloc*>(this); } 557 558 allocator_type& 559 _M_get_allocator() 560 { return *static_cast<_Alloc*>(this); } 561 562 const allocator_type& 563 _M_get_allocator() const 564 { return *static_cast<const _Alloc*>(this); } 565 566 _Rope_rep_base(size_t __size, const allocator_type&) 567 : _M_size(__size) { } 568 569 size_t _M_size; 570 571 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \ 572 typedef typename \ 573 _Alloc::template rebind<_Tp>::other __name##Alloc; \ 574 static _Tp* __name##_allocate(size_t __n) \ 575 { return __name##Alloc().allocate(__n); } \ 576 static void __name##_deallocate(_Tp *__p, size_t __n) \ 577 { __name##Alloc().deallocate(__p, __n); } 578 __ROPE_DEFINE_ALLOCS(_Alloc) 579 # undef __ROPE_DEFINE_ALLOC 580 }; 581 582 template<class _CharT, class _Alloc> 583 struct _Rope_RopeRep 584 : public _Rope_rep_base<_CharT, _Alloc> 585 # ifndef __GC 586 , _Refcount_Base 587 # endif 588 { 589 public: 590 __detail::_Tag _M_tag:8; 591 bool _M_is_balanced:8; 592 unsigned char _M_depth; 593 __GC_CONST _CharT* _M_c_string; 594 #ifdef __GTHREAD_MUTEX_INIT 595 __gthread_mutex_t _M_c_string_lock = __GTHREAD_MUTEX_INIT; 596 #else 597 __gthread_mutex_t _M_c_string_lock; 598 #endif 599 /* Flattened version of string, if needed. */ 600 /* typically 0. */ 601 /* If it's not 0, then the memory is owned */ 602 /* by this node. */ 603 /* In the case of a leaf, this may point to */ 604 /* the same memory as the data field. */ 605 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type 606 allocator_type; 607 608 using _Rope_rep_base<_CharT, _Alloc>::get_allocator; 609 using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator; 610 611 _Rope_RopeRep(__detail::_Tag __t, int __d, bool __b, size_t __size, 612 const allocator_type& __a) 613 : _Rope_rep_base<_CharT, _Alloc>(__size, __a), 614 #ifndef __GC 615 _Refcount_Base(1), 616 #endif 617 _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0) 618 #ifdef __GTHREAD_MUTEX_INIT 619 { } 620 #else 621 { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); } 622 ~_Rope_RopeRep() 623 { __gthread_mutex_destroy (&_M_c_string_lock); } 624 #endif 625 #ifdef __GC 626 void 627 _M_incr () { } 628 #endif 629 static void 630 _S_free_string(__GC_CONST _CharT*, size_t __len, 631 allocator_type& __a); 632 #define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a); 633 // Deallocate data section of a leaf. 634 // This shouldn't be a member function. 635 // But its hard to do anything else at the 636 // moment, because it's templatized w.r.t. 637 // an allocator. 638 // Does nothing if __GC is defined. 639 #ifndef __GC 640 void _M_free_c_string(); 641 void _M_free_tree(); 642 // Deallocate t. Assumes t is not 0. 643 void 644 _M_unref_nonnil() 645 { 646 if (0 == _M_decr()) 647 _M_free_tree(); 648 } 649 650 void 651 _M_ref_nonnil() 652 { _M_incr(); } 653 654 static void 655 _S_unref(_Rope_RopeRep* __t) 656 { 657 if (0 != __t) 658 __t->_M_unref_nonnil(); 659 } 660 661 static void 662 _S_ref(_Rope_RopeRep* __t) 663 { 664 if (0 != __t) 665 __t->_M_incr(); 666 } 667 668 static void 669 _S_free_if_unref(_Rope_RopeRep* __t) 670 { 671 if (0 != __t && 0 == __t->_M_ref_count) 672 __t->_M_free_tree(); 673 } 674 # else /* __GC */ 675 void _M_unref_nonnil() { } 676 void _M_ref_nonnil() { } 677 static void _S_unref(_Rope_RopeRep*) { } 678 static void _S_ref(_Rope_RopeRep*) { } 679 static void _S_free_if_unref(_Rope_RopeRep*) { } 680 # endif 681 protected: 682 _Rope_RopeRep& 683 operator=(const _Rope_RopeRep&); 684 685 _Rope_RopeRep(const _Rope_RopeRep&); 686 }; 687 688 template<class _CharT, class _Alloc> 689 struct _Rope_RopeLeaf 690 : public _Rope_RopeRep<_CharT, _Alloc> 691 { 692 public: 693 // Apparently needed by VC++ 694 // The data fields of leaves are allocated with some 695 // extra space, to accommodate future growth and for basic 696 // character types, to hold a trailing eos character. 697 enum { _S_alloc_granularity = 8 }; 698 699 static size_t 700 _S_rounded_up_size(size_t __n) 701 { 702 size_t __size_with_eos; 703 704 if (_S_is_basic_char_type((_CharT*)0)) 705 __size_with_eos = __n + 1; 706 else 707 __size_with_eos = __n; 708 #ifdef __GC 709 return __size_with_eos; 710 #else 711 // Allow slop for in-place expansion. 712 return ((__size_with_eos + size_t(_S_alloc_granularity) - 1) 713 &~ (size_t(_S_alloc_granularity) - 1)); 714 #endif 715 } 716 __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */ 717 /* The allocated size is */ 718 /* _S_rounded_up_size(size), except */ 719 /* in the GC case, in which it */ 720 /* doesn't matter. */ 721 typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type 722 allocator_type; 723 724 _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size, 725 const allocator_type& __a) 726 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true, 727 __size, __a), _M_data(__d) 728 { 729 if (_S_is_basic_char_type((_CharT *)0)) 730 { 731 // already eos terminated. 732 this->_M_c_string = __d; 733 } 734 } 735 // The constructor assumes that d has been allocated with 736 // the proper allocator and the properly padded size. 737 // In contrast, the destructor deallocates the data: 738 #ifndef __GC 739 ~_Rope_RopeLeaf() throw() 740 { 741 if (_M_data != this->_M_c_string) 742 this->_M_free_c_string(); 743 744 this->__STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator()); 745 } 746 #endif 747 protected: 748 _Rope_RopeLeaf& 749 operator=(const _Rope_RopeLeaf&); 750 751 _Rope_RopeLeaf(const _Rope_RopeLeaf&); 752 }; 753 754 template<class _CharT, class _Alloc> 755 struct _Rope_RopeConcatenation 756 : public _Rope_RopeRep<_CharT, _Alloc> 757 { 758 public: 759 _Rope_RopeRep<_CharT, _Alloc>* _M_left; 760 _Rope_RopeRep<_CharT, _Alloc>* _M_right; 761 762 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type 763 allocator_type; 764 765 _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l, 766 _Rope_RopeRep<_CharT, _Alloc>* __r, 767 const allocator_type& __a) 768 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat, 769 std::max(__l->_M_depth, 770 __r->_M_depth) + 1, 771 false, 772 __l->_M_size + __r->_M_size, __a), 773 _M_left(__l), _M_right(__r) 774 { } 775 #ifndef __GC 776 ~_Rope_RopeConcatenation() throw() 777 { 778 this->_M_free_c_string(); 779 _M_left->_M_unref_nonnil(); 780 _M_right->_M_unref_nonnil(); 781 } 782 #endif 783 protected: 784 _Rope_RopeConcatenation& 785 operator=(const _Rope_RopeConcatenation&); 786 787 _Rope_RopeConcatenation(const _Rope_RopeConcatenation&); 788 }; 789 790 template<class _CharT, class _Alloc> 791 struct _Rope_RopeFunction 792 : public _Rope_RopeRep<_CharT, _Alloc> 793 { 794 public: 795 char_producer<_CharT>* _M_fn; 796 #ifndef __GC 797 bool _M_delete_when_done; // Char_producer is owned by the 798 // rope and should be explicitly 799 // deleted when the rope becomes 800 // inaccessible. 801 #else 802 // In the GC case, we either register the rope for 803 // finalization, or not. Thus the field is unnecessary; 804 // the information is stored in the collector data structures. 805 // We do need a finalization procedure to be invoked by the 806 // collector. 807 static void 808 _S_fn_finalization_proc(void * __tree, void *) 809 { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; } 810 #endif 811 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type 812 allocator_type; 813 814 _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size, 815 bool __d, const allocator_type& __a) 816 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a) 817 , _M_fn(__f) 818 #ifndef __GC 819 , _M_delete_when_done(__d) 820 #endif 821 { 822 #ifdef __GC 823 if (__d) 824 { 825 GC_REGISTER_FINALIZER(this, _Rope_RopeFunction:: 826 _S_fn_finalization_proc, 0, 0, 0); 827 } 828 #endif 829 } 830 #ifndef __GC 831 ~_Rope_RopeFunction() throw() 832 { 833 this->_M_free_c_string(); 834 if (_M_delete_when_done) 835 delete _M_fn; 836 } 837 # endif 838 protected: 839 _Rope_RopeFunction& 840 operator=(const _Rope_RopeFunction&); 841 842 _Rope_RopeFunction(const _Rope_RopeFunction&); 843 }; 844 // Substring results are usually represented using just 845 // concatenation nodes. But in the case of very long flat ropes 846 // or ropes with a functional representation that isn't practical. 847 // In that case, we represent the __result as a special case of 848 // RopeFunction, whose char_producer points back to the rope itself. 849 // In all cases except repeated substring operations and 850 // deallocation, we treat the __result as a RopeFunction. 851 template<class _CharT, class _Alloc> 852 struct _Rope_RopeSubstring 853 : public _Rope_RopeFunction<_CharT, _Alloc>, 854 public char_producer<_CharT> 855 { 856 public: 857 // XXX this whole class should be rewritten. 858 _Rope_RopeRep<_CharT,_Alloc>* _M_base; // not 0 859 size_t _M_start; 860 861 virtual void 862 operator()(size_t __start_pos, size_t __req_len, 863 _CharT* __buffer) 864 { 865 switch(_M_base->_M_tag) 866 { 867 case __detail::_S_function: 868 case __detail::_S_substringfn: 869 { 870 char_producer<_CharT>* __fn = 871 ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn; 872 (*__fn)(__start_pos + _M_start, __req_len, __buffer); 873 } 874 break; 875 case __detail::_S_leaf: 876 { 877 __GC_CONST _CharT* __s = 878 ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data; 879 uninitialized_copy_n(__s + __start_pos + _M_start, __req_len, 880 __buffer); 881 } 882 break; 883 default: 884 break; 885 } 886 } 887 888 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type 889 allocator_type; 890 891 _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s, 892 size_t __l, const allocator_type& __a) 893 : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a), 894 char_producer<_CharT>(), _M_base(__b), _M_start(__s) 895 { 896 #ifndef __GC 897 _M_base->_M_ref_nonnil(); 898 #endif 899 this->_M_tag = __detail::_S_substringfn; 900 } 901 virtual ~_Rope_RopeSubstring() throw() 902 { 903 #ifndef __GC 904 _M_base->_M_unref_nonnil(); 905 // _M_free_c_string(); -- done by parent class 906 #endif 907 } 908 }; 909 910 // Self-destructing pointers to Rope_rep. 911 // These are not conventional smart pointers. Their 912 // only purpose in life is to ensure that unref is called 913 // on the pointer either at normal exit or if an exception 914 // is raised. It is the caller's responsibility to 915 // adjust reference counts when these pointers are initialized 916 // or assigned to. (This convention significantly reduces 917 // the number of potentially expensive reference count 918 // updates.) 919 #ifndef __GC 920 template<class _CharT, class _Alloc> 921 struct _Rope_self_destruct_ptr 922 { 923 _Rope_RopeRep<_CharT, _Alloc>* _M_ptr; 924 925 ~_Rope_self_destruct_ptr() 926 { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); } 927 #ifdef __EXCEPTIONS 928 _Rope_self_destruct_ptr() : _M_ptr(0) { }; 929 #else 930 _Rope_self_destruct_ptr() { }; 931 #endif 932 _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p) 933 : _M_ptr(__p) { } 934 935 _Rope_RopeRep<_CharT, _Alloc>& 936 operator*() 937 { return *_M_ptr; } 938 939 _Rope_RopeRep<_CharT, _Alloc>* 940 operator->() 941 { return _M_ptr; } 942 943 operator _Rope_RopeRep<_CharT, _Alloc>*() 944 { return _M_ptr; } 945 946 _Rope_self_destruct_ptr& 947 operator=(_Rope_RopeRep<_CharT, _Alloc>* __x) 948 { _M_ptr = __x; return *this; } 949 }; 950 #endif 951 952 // Dereferencing a nonconst iterator has to return something 953 // that behaves almost like a reference. It's not possible to 954 // return an actual reference since assignment requires extra 955 // work. And we would get into the same problems as with the 956 // CD2 version of basic_string. 957 template<class _CharT, class _Alloc> 958 class _Rope_char_ref_proxy 959 { 960 friend class rope<_CharT, _Alloc>; 961 friend class _Rope_iterator<_CharT, _Alloc>; 962 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>; 963 #ifdef __GC 964 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr; 965 #else 966 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr; 967 #endif 968 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 969 typedef rope<_CharT, _Alloc> _My_rope; 970 size_t _M_pos; 971 _CharT _M_current; 972 bool _M_current_valid; 973 _My_rope* _M_root; // The whole rope. 974 public: 975 _Rope_char_ref_proxy(_My_rope* __r, size_t __p) 976 : _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { } 977 978 _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x) 979 : _M_pos(__x._M_pos), _M_current(__x._M_current), 980 _M_current_valid(false), _M_root(__x._M_root) { } 981 982 // Don't preserve cache if the reference can outlive the 983 // expression. We claim that's not possible without calling 984 // a copy constructor or generating reference to a proxy 985 // reference. We declare the latter to have undefined semantics. 986 _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c) 987 : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { } 988 989 inline operator _CharT () const; 990 991 _Rope_char_ref_proxy& 992 operator=(_CharT __c); 993 994 _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const; 995 996 _Rope_char_ref_proxy& 997 operator=(const _Rope_char_ref_proxy& __c) 998 { return operator=((_CharT)__c); } 999 }; 1000 1001 template<class _CharT, class __Alloc> 1002 inline void 1003 swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a, 1004 _Rope_char_ref_proxy <_CharT, __Alloc > __b) 1005 { 1006 _CharT __tmp = __a; 1007 __a = __b; 1008 __b = __tmp; 1009 } 1010 1011 template<class _CharT, class _Alloc> 1012 class _Rope_char_ptr_proxy 1013 { 1014 // XXX this class should be rewritten. 1015 friend class _Rope_char_ref_proxy<_CharT, _Alloc>; 1016 size_t _M_pos; 1017 rope<_CharT,_Alloc>* _M_root; // The whole rope. 1018 public: 1019 _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x) 1020 : _M_pos(__x._M_pos), _M_root(__x._M_root) { } 1021 1022 _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x) 1023 : _M_pos(__x._M_pos), _M_root(__x._M_root) { } 1024 1025 _Rope_char_ptr_proxy() { } 1026 1027 _Rope_char_ptr_proxy(_CharT* __x) 1028 : _M_root(0), _M_pos(0) { } 1029 1030 _Rope_char_ptr_proxy& 1031 operator=(const _Rope_char_ptr_proxy& __x) 1032 { 1033 _M_pos = __x._M_pos; 1034 _M_root = __x._M_root; 1035 return *this; 1036 } 1037 1038 template<class _CharT2, class _Alloc2> 1039 friend bool 1040 operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x, 1041 const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y); 1042 1043 _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const 1044 { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); } 1045 }; 1046 1047 // Rope iterators: 1048 // Unlike in the C version, we cache only part of the stack 1049 // for rope iterators, since they must be efficiently copyable. 1050 // When we run out of cache, we have to reconstruct the iterator 1051 // value. 1052 // Pointers from iterators are not included in reference counts. 1053 // Iterators are assumed to be thread private. Ropes can 1054 // be shared. 1055 1056 template<class _CharT, class _Alloc> 1057 class _Rope_iterator_base 1058 : public std::iterator<std::random_access_iterator_tag, _CharT> 1059 { 1060 friend class rope<_CharT, _Alloc>; 1061 public: 1062 typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround 1063 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 1064 // Borland doesn't want this to be protected. 1065 protected: 1066 enum { _S_path_cache_len = 4 }; // Must be <= 9. 1067 enum { _S_iterator_buf_len = 15 }; 1068 size_t _M_current_pos; 1069 _RopeRep* _M_root; // The whole rope. 1070 size_t _M_leaf_pos; // Starting position for current leaf 1071 __GC_CONST _CharT* _M_buf_start; 1072 // Buffer possibly 1073 // containing current char. 1074 __GC_CONST _CharT* _M_buf_ptr; 1075 // Pointer to current char in buffer. 1076 // != 0 ==> buffer valid. 1077 __GC_CONST _CharT* _M_buf_end; 1078 // One past __last valid char in buffer. 1079 // What follows is the path cache. We go out of our 1080 // way to make this compact. 1081 // Path_end contains the bottom section of the path from 1082 // the root to the current leaf. 1083 const _RopeRep* _M_path_end[_S_path_cache_len]; 1084 int _M_leaf_index; // Last valid __pos in path_end; 1085 // _M_path_end[0] ... _M_path_end[leaf_index-1] 1086 // point to concatenation nodes. 1087 unsigned char _M_path_directions; 1088 // (path_directions >> __i) & 1 is 1 1089 // iff we got from _M_path_end[leaf_index - __i - 1] 1090 // to _M_path_end[leaf_index - __i] by going to the 1091 // __right. Assumes path_cache_len <= 9. 1092 _CharT _M_tmp_buf[_S_iterator_buf_len]; 1093 // Short buffer for surrounding chars. 1094 // This is useful primarily for 1095 // RopeFunctions. We put the buffer 1096 // here to avoid locking in the 1097 // multithreaded case. 1098 // The cached path is generally assumed to be valid 1099 // only if the buffer is valid. 1100 static void _S_setbuf(_Rope_iterator_base& __x); 1101 // Set buffer contents given 1102 // path cache. 1103 static void _S_setcache(_Rope_iterator_base& __x); 1104 // Set buffer contents and 1105 // path cache. 1106 static void _S_setcache_for_incr(_Rope_iterator_base& __x); 1107 // As above, but assumes path 1108 // cache is valid for previous posn. 1109 _Rope_iterator_base() { } 1110 1111 _Rope_iterator_base(_RopeRep* __root, size_t __pos) 1112 : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { } 1113 1114 void _M_incr(size_t __n); 1115 void _M_decr(size_t __n); 1116 public: 1117 size_t 1118 index() const 1119 { return _M_current_pos; } 1120 1121 _Rope_iterator_base(const _Rope_iterator_base& __x) 1122 { 1123 if (0 != __x._M_buf_ptr) 1124 *this = __x; 1125 else 1126 { 1127 _M_current_pos = __x._M_current_pos; 1128 _M_root = __x._M_root; 1129 _M_buf_ptr = 0; 1130 } 1131 } 1132 }; 1133 1134 template<class _CharT, class _Alloc> 1135 class _Rope_iterator; 1136 1137 template<class _CharT, class _Alloc> 1138 class _Rope_const_iterator 1139 : public _Rope_iterator_base<_CharT, _Alloc> 1140 { 1141 friend class rope<_CharT, _Alloc>; 1142 protected: 1143 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 1144 // The one from the base class may not be directly visible. 1145 _Rope_const_iterator(const _RopeRep* __root, size_t __pos) 1146 : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root), 1147 __pos) 1148 // Only nonconst iterators modify root ref count 1149 { } 1150 public: 1151 typedef _CharT reference; // Really a value. Returning a reference 1152 // Would be a mess, since it would have 1153 // to be included in refcount. 1154 typedef const _CharT* pointer; 1155 1156 public: 1157 _Rope_const_iterator() { }; 1158 1159 _Rope_const_iterator(const _Rope_const_iterator& __x) 1160 : _Rope_iterator_base<_CharT,_Alloc>(__x) { } 1161 1162 _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x); 1163 1164 _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos) 1165 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { } 1166 1167 _Rope_const_iterator& 1168 operator=(const _Rope_const_iterator& __x) 1169 { 1170 if (0 != __x._M_buf_ptr) 1171 *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x; 1172 else 1173 { 1174 this->_M_current_pos = __x._M_current_pos; 1175 this->_M_root = __x._M_root; 1176 this->_M_buf_ptr = 0; 1177 } 1178 return(*this); 1179 } 1180 1181 reference 1182 operator*() 1183 { 1184 if (0 == this->_M_buf_ptr) 1185 this->_S_setcache(*this); 1186 return *this->_M_buf_ptr; 1187 } 1188 1189 // Without this const version, Rope iterators do not meet the 1190 // requirements of an Input Iterator. 1191 reference 1192 operator*() const 1193 { 1194 return *const_cast<_Rope_const_iterator&>(*this); 1195 } 1196 1197 _Rope_const_iterator& 1198 operator++() 1199 { 1200 __GC_CONST _CharT* __next; 1201 if (0 != this->_M_buf_ptr 1202 && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end) 1203 { 1204 this->_M_buf_ptr = __next; 1205 ++this->_M_current_pos; 1206 } 1207 else 1208 this->_M_incr(1); 1209 return *this; 1210 } 1211 1212 _Rope_const_iterator& 1213 operator+=(ptrdiff_t __n) 1214 { 1215 if (__n >= 0) 1216 this->_M_incr(__n); 1217 else 1218 this->_M_decr(-__n); 1219 return *this; 1220 } 1221 1222 _Rope_const_iterator& 1223 operator--() 1224 { 1225 this->_M_decr(1); 1226 return *this; 1227 } 1228 1229 _Rope_const_iterator& 1230 operator-=(ptrdiff_t __n) 1231 { 1232 if (__n >= 0) 1233 this->_M_decr(__n); 1234 else 1235 this->_M_incr(-__n); 1236 return *this; 1237 } 1238 1239 _Rope_const_iterator 1240 operator++(int) 1241 { 1242 size_t __old_pos = this->_M_current_pos; 1243 this->_M_incr(1); 1244 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos); 1245 // This makes a subsequent dereference expensive. 1246 // Perhaps we should instead copy the iterator 1247 // if it has a valid cache? 1248 } 1249 1250 _Rope_const_iterator 1251 operator--(int) 1252 { 1253 size_t __old_pos = this->_M_current_pos; 1254 this->_M_decr(1); 1255 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos); 1256 } 1257 1258 template<class _CharT2, class _Alloc2> 1259 friend _Rope_const_iterator<_CharT2, _Alloc2> 1260 operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, 1261 ptrdiff_t __n); 1262 1263 template<class _CharT2, class _Alloc2> 1264 friend _Rope_const_iterator<_CharT2, _Alloc2> 1265 operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, 1266 ptrdiff_t __n); 1267 1268 template<class _CharT2, class _Alloc2> 1269 friend _Rope_const_iterator<_CharT2, _Alloc2> 1270 operator+(ptrdiff_t __n, 1271 const _Rope_const_iterator<_CharT2, _Alloc2>& __x); 1272 1273 reference 1274 operator[](size_t __n) 1275 { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root, 1276 this->_M_current_pos + __n); } 1277 1278 template<class _CharT2, class _Alloc2> 1279 friend bool 1280 operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, 1281 const _Rope_const_iterator<_CharT2, _Alloc2>& __y); 1282 1283 template<class _CharT2, class _Alloc2> 1284 friend bool 1285 operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, 1286 const _Rope_const_iterator<_CharT2, _Alloc2>& __y); 1287 1288 template<class _CharT2, class _Alloc2> 1289 friend ptrdiff_t 1290 operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, 1291 const _Rope_const_iterator<_CharT2, _Alloc2>& __y); 1292 }; 1293 1294 template<class _CharT, class _Alloc> 1295 class _Rope_iterator 1296 : public _Rope_iterator_base<_CharT, _Alloc> 1297 { 1298 friend class rope<_CharT, _Alloc>; 1299 protected: 1300 typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep; 1301 rope<_CharT, _Alloc>* _M_root_rope; 1302 1303 // root is treated as a cached version of this, and is used to 1304 // detect changes to the underlying rope. 1305 1306 // Root is included in the reference count. This is necessary 1307 // so that we can detect changes reliably. Unfortunately, it 1308 // requires careful bookkeeping for the nonGC case. 1309 _Rope_iterator(rope<_CharT, _Alloc>* __r, size_t __pos) 1310 : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos), 1311 _M_root_rope(__r) 1312 { _RopeRep::_S_ref(this->_M_root); 1313 if (!(__r -> empty())) 1314 this->_S_setcache(*this); 1315 } 1316 1317 void _M_check(); 1318 public: 1319 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference; 1320 typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer; 1321 1322 rope<_CharT, _Alloc>& 1323 container() 1324 { return *_M_root_rope; } 1325 1326 _Rope_iterator() 1327 { 1328 this->_M_root = 0; // Needed for reference counting. 1329 }; 1330 1331 _Rope_iterator(const _Rope_iterator& __x) 1332 : _Rope_iterator_base<_CharT, _Alloc>(__x) 1333 { 1334 _M_root_rope = __x._M_root_rope; 1335 _RopeRep::_S_ref(this->_M_root); 1336 } 1337 1338 _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos); 1339 1340 ~_Rope_iterator() 1341 { _RopeRep::_S_unref(this->_M_root); } 1342 1343 _Rope_iterator& 1344 operator=(const _Rope_iterator& __x) 1345 { 1346 _RopeRep* __old = this->_M_root; 1347 1348 _RopeRep::_S_ref(__x._M_root); 1349 if (0 != __x._M_buf_ptr) 1350 { 1351 _M_root_rope = __x._M_root_rope; 1352 *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x; 1353 } 1354 else 1355 { 1356 this->_M_current_pos = __x._M_current_pos; 1357 this->_M_root = __x._M_root; 1358 _M_root_rope = __x._M_root_rope; 1359 this->_M_buf_ptr = 0; 1360 } 1361 _RopeRep::_S_unref(__old); 1362 return(*this); 1363 } 1364 1365 reference 1366 operator*() 1367 { 1368 _M_check(); 1369 if (0 == this->_M_buf_ptr) 1370 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope, 1371 this->_M_current_pos); 1372 else 1373 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope, 1374 this->_M_current_pos, 1375 *this->_M_buf_ptr); 1376 } 1377 1378 // See above comment. 1379 reference 1380 operator*() const 1381 { 1382 return *const_cast<_Rope_iterator&>(*this); 1383 } 1384 1385 _Rope_iterator& 1386 operator++() 1387 { 1388 this->_M_incr(1); 1389 return *this; 1390 } 1391 1392 _Rope_iterator& 1393 operator+=(ptrdiff_t __n) 1394 { 1395 if (__n >= 0) 1396 this->_M_incr(__n); 1397 else 1398 this->_M_decr(-__n); 1399 return *this; 1400 } 1401 1402 _Rope_iterator& 1403 operator--() 1404 { 1405 this->_M_decr(1); 1406 return *this; 1407 } 1408 1409 _Rope_iterator& 1410 operator-=(ptrdiff_t __n) 1411 { 1412 if (__n >= 0) 1413 this->_M_decr(__n); 1414 else 1415 this->_M_incr(-__n); 1416 return *this; 1417 } 1418 1419 _Rope_iterator 1420 operator++(int) 1421 { 1422 size_t __old_pos = this->_M_current_pos; 1423 this->_M_incr(1); 1424 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos); 1425 } 1426 1427 _Rope_iterator 1428 operator--(int) 1429 { 1430 size_t __old_pos = this->_M_current_pos; 1431 this->_M_decr(1); 1432 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos); 1433 } 1434 1435 reference 1436 operator[](ptrdiff_t __n) 1437 { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope, 1438 this->_M_current_pos 1439 + __n); } 1440 1441 template<class _CharT2, class _Alloc2> 1442 friend bool 1443 operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x, 1444 const _Rope_iterator<_CharT2, _Alloc2>& __y); 1445 1446 template<class _CharT2, class _Alloc2> 1447 friend bool 1448 operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x, 1449 const _Rope_iterator<_CharT2, _Alloc2>& __y); 1450 1451 template<class _CharT2, class _Alloc2> 1452 friend ptrdiff_t 1453 operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, 1454 const _Rope_iterator<_CharT2, _Alloc2>& __y); 1455 1456 template<class _CharT2, class _Alloc2> 1457 friend _Rope_iterator<_CharT2, _Alloc2> 1458 operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n); 1459 1460 template<class _CharT2, class _Alloc2> 1461 friend _Rope_iterator<_CharT2, _Alloc2> 1462 operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n); 1463 1464 template<class _CharT2, class _Alloc2> 1465 friend _Rope_iterator<_CharT2, _Alloc2> 1466 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x); 1467 }; 1468 1469 1470 template <class _CharT, class _Alloc> 1471 struct _Rope_base 1472 : public _Alloc 1473 { 1474 typedef _Alloc allocator_type; 1475 1476 allocator_type 1477 get_allocator() const 1478 { return *static_cast<const _Alloc*>(this); } 1479 1480 allocator_type& 1481 _M_get_allocator() 1482 { return *static_cast<_Alloc*>(this); } 1483 1484 const allocator_type& 1485 _M_get_allocator() const 1486 { return *static_cast<const _Alloc*>(this); } 1487 1488 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 1489 // The one in _Base may not be visible due to template rules. 1490 1491 _Rope_base(_RopeRep* __t, const allocator_type&) 1492 : _M_tree_ptr(__t) { } 1493 1494 _Rope_base(const allocator_type&) { } 1495 1496 // The only data member of a rope: 1497 _RopeRep *_M_tree_ptr; 1498 1499 #define __ROPE_DEFINE_ALLOC(_Tp, __name) \ 1500 typedef typename \ 1501 _Alloc::template rebind<_Tp>::other __name##Alloc; \ 1502 static _Tp* __name##_allocate(size_t __n) \ 1503 { return __name##Alloc().allocate(__n); } \ 1504 static void __name##_deallocate(_Tp *__p, size_t __n) \ 1505 { __name##Alloc().deallocate(__p, __n); } 1506 __ROPE_DEFINE_ALLOCS(_Alloc) 1507 #undef __ROPE_DEFINE_ALLOC 1508 1509 protected: 1510 _Rope_base& 1511 operator=(const _Rope_base&); 1512 1513 _Rope_base(const _Rope_base&); 1514 }; 1515 1516 /** 1517 * This is an SGI extension. 1518 * @ingroup SGIextensions 1519 * @doctodo 1520 */ 1521 template <class _CharT, class _Alloc> 1522 class rope : public _Rope_base<_CharT, _Alloc> 1523 { 1524 public: 1525 typedef _CharT value_type; 1526 typedef ptrdiff_t difference_type; 1527 typedef size_t size_type; 1528 typedef _CharT const_reference; 1529 typedef const _CharT* const_pointer; 1530 typedef _Rope_iterator<_CharT, _Alloc> iterator; 1531 typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator; 1532 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference; 1533 typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer; 1534 1535 friend class _Rope_iterator<_CharT, _Alloc>; 1536 friend class _Rope_const_iterator<_CharT, _Alloc>; 1537 friend struct _Rope_RopeRep<_CharT, _Alloc>; 1538 friend class _Rope_iterator_base<_CharT, _Alloc>; 1539 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>; 1540 friend class _Rope_char_ref_proxy<_CharT, _Alloc>; 1541 friend struct _Rope_RopeSubstring<_CharT, _Alloc>; 1542 1543 protected: 1544 typedef _Rope_base<_CharT, _Alloc> _Base; 1545 typedef typename _Base::allocator_type allocator_type; 1546 using _Base::_M_tree_ptr; 1547 using _Base::get_allocator; 1548 using _Base::_M_get_allocator; 1549 typedef __GC_CONST _CharT* _Cstrptr; 1550 1551 static _CharT _S_empty_c_str[1]; 1552 1553 static bool 1554 _S_is0(_CharT __c) 1555 { return __c == _S_eos((_CharT*)0); } 1556 1557 enum { _S_copy_max = 23 }; 1558 // For strings shorter than _S_copy_max, we copy to 1559 // concatenate. 1560 1561 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 1562 typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation; 1563 typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf; 1564 typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction; 1565 typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring; 1566 1567 // Retrieve a character at the indicated position. 1568 static _CharT _S_fetch(_RopeRep* __r, size_type __pos); 1569 1570 #ifndef __GC 1571 // Obtain a pointer to the character at the indicated position. 1572 // The pointer can be used to change the character. 1573 // If such a pointer cannot be produced, as is frequently the 1574 // case, 0 is returned instead. 1575 // (Returns nonzero only if all nodes in the path have a refcount 1576 // of 1.) 1577 static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos); 1578 #endif 1579 1580 static bool 1581 _S_apply_to_pieces(// should be template parameter 1582 _Rope_char_consumer<_CharT>& __c, 1583 const _RopeRep* __r, 1584 size_t __begin, size_t __end); 1585 // begin and end are assumed to be in range. 1586 1587 #ifndef __GC 1588 static void 1589 _S_unref(_RopeRep* __t) 1590 { _RopeRep::_S_unref(__t); } 1591 1592 static void 1593 _S_ref(_RopeRep* __t) 1594 { _RopeRep::_S_ref(__t); } 1595 1596 #else /* __GC */ 1597 static void _S_unref(_RopeRep*) { } 1598 static void _S_ref(_RopeRep*) { } 1599 #endif 1600 1601 #ifdef __GC 1602 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr; 1603 #else 1604 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr; 1605 #endif 1606 1607 // _Result is counted in refcount. 1608 static _RopeRep* _S_substring(_RopeRep* __base, 1609 size_t __start, size_t __endp1); 1610 1611 static _RopeRep* _S_concat_char_iter(_RopeRep* __r, 1612 const _CharT* __iter, size_t __slen); 1613 // Concatenate rope and char ptr, copying __s. 1614 // Should really take an arbitrary iterator. 1615 // Result is counted in refcount. 1616 static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r, 1617 const _CharT* __iter, 1618 size_t __slen) 1619 // As above, but one reference to __r is about to be 1620 // destroyed. Thus the pieces may be recycled if all 1621 // relevant reference counts are 1. 1622 #ifdef __GC 1623 // We can't really do anything since refcounts are unavailable. 1624 { return _S_concat_char_iter(__r, __iter, __slen); } 1625 #else 1626 ; 1627 #endif 1628 1629 static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right); 1630 // General concatenation on _RopeRep. _Result 1631 // has refcount of 1. Adjusts argument refcounts. 1632 1633 public: 1634 void 1635 apply_to_pieces(size_t __begin, size_t __end, 1636 _Rope_char_consumer<_CharT>& __c) const 1637 { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); } 1638 1639 protected: 1640 1641 static size_t 1642 _S_rounded_up_size(size_t __n) 1643 { return _RopeLeaf::_S_rounded_up_size(__n); } 1644 1645 static size_t 1646 _S_allocated_capacity(size_t __n) 1647 { 1648 if (_S_is_basic_char_type((_CharT*)0)) 1649 return _S_rounded_up_size(__n) - 1; 1650 else 1651 return _S_rounded_up_size(__n); 1652 1653 } 1654 1655 // Allocate and construct a RopeLeaf using the supplied allocator 1656 // Takes ownership of s instead of copying. 1657 static _RopeLeaf* 1658 _S_new_RopeLeaf(__GC_CONST _CharT *__s, 1659 size_t __size, allocator_type& __a) 1660 { 1661 _RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1); 1662 return new(__space) _RopeLeaf(__s, __size, __a); 1663 } 1664 1665 static _RopeConcatenation* 1666 _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right, 1667 allocator_type& __a) 1668 { 1669 _RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1); 1670 return new(__space) _RopeConcatenation(__left, __right, __a); 1671 } 1672 1673 static _RopeFunction* 1674 _S_new_RopeFunction(char_producer<_CharT>* __f, 1675 size_t __size, bool __d, allocator_type& __a) 1676 { 1677 _RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1); 1678 return new(__space) _RopeFunction(__f, __size, __d, __a); 1679 } 1680 1681 static _RopeSubstring* 1682 _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s, 1683 size_t __l, allocator_type& __a) 1684 { 1685 _RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1); 1686 return new(__space) _RopeSubstring(__b, __s, __l, __a); 1687 } 1688 1689 static _RopeLeaf* 1690 _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s, 1691 size_t __size, allocator_type& __a) 1692 #define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \ 1693 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a) 1694 { 1695 if (0 == __size) 1696 return 0; 1697 _CharT* __buf = __a.allocate(_S_rounded_up_size(__size)); 1698 1699 __uninitialized_copy_n_a(__s, __size, __buf, __a); 1700 _S_cond_store_eos(__buf[__size]); 1701 __try 1702 { return _S_new_RopeLeaf(__buf, __size, __a); } 1703 __catch(...) 1704 { 1705 _RopeRep::__STL_FREE_STRING(__buf, __size, __a); 1706 __throw_exception_again; 1707 } 1708 } 1709 1710 // Concatenation of nonempty strings. 1711 // Always builds a concatenation node. 1712 // Rebalances if the result is too deep. 1713 // Result has refcount 1. 1714 // Does not increment left and right ref counts even though 1715 // they are referenced. 1716 static _RopeRep* 1717 _S_tree_concat(_RopeRep* __left, _RopeRep* __right); 1718 1719 // Concatenation helper functions 1720 static _RopeLeaf* 1721 _S_leaf_concat_char_iter(_RopeLeaf* __r, 1722 const _CharT* __iter, size_t __slen); 1723 // Concatenate by copying leaf. 1724 // should take an arbitrary iterator 1725 // result has refcount 1. 1726 #ifndef __GC 1727 static _RopeLeaf* 1728 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r, 1729 const _CharT* __iter, size_t __slen); 1730 // A version that potentially clobbers __r if __r->_M_ref_count == 1. 1731 #endif 1732 1733 private: 1734 1735 static size_t _S_char_ptr_len(const _CharT* __s); 1736 // slightly generalized strlen 1737 1738 rope(_RopeRep* __t, const allocator_type& __a = allocator_type()) 1739 : _Base(__t, __a) { } 1740 1741 1742 // Copy __r to the _CharT buffer. 1743 // Returns __buffer + __r->_M_size. 1744 // Assumes that buffer is uninitialized. 1745 static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer); 1746 1747 // Again, with explicit starting position and length. 1748 // Assumes that buffer is uninitialized. 1749 static _CharT* _S_flatten(_RopeRep* __r, 1750 size_t __start, size_t __len, 1751 _CharT* __buffer); 1752 1753 static const unsigned long 1754 _S_min_len[__detail::_S_max_rope_depth + 1]; 1755 1756 static bool 1757 _S_is_balanced(_RopeRep* __r) 1758 { return (__r->_M_size >= _S_min_len[__r->_M_depth]); } 1759 1760 static bool 1761 _S_is_almost_balanced(_RopeRep* __r) 1762 { return (__r->_M_depth == 0 1763 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); } 1764 1765 static bool 1766 _S_is_roughly_balanced(_RopeRep* __r) 1767 { return (__r->_M_depth <= 1 1768 || __r->_M_size >= _S_min_len[__r->_M_depth - 2]); } 1769 1770 // Assumes the result is not empty. 1771 static _RopeRep* 1772 _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right) 1773 { 1774 _RopeRep* __result = _S_concat(__left, __right); 1775 if (_S_is_balanced(__result)) 1776 __result->_M_is_balanced = true; 1777 return __result; 1778 } 1779 1780 // The basic rebalancing operation. Logically copies the 1781 // rope. The result has refcount of 1. The client will 1782 // usually decrement the reference count of __r. 1783 // The result is within height 2 of balanced by the above 1784 // definition. 1785 static _RopeRep* _S_balance(_RopeRep* __r); 1786 1787 // Add all unbalanced subtrees to the forest of balanced trees. 1788 // Used only by balance. 1789 static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest); 1790 1791 // Add __r to forest, assuming __r is already balanced. 1792 static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest); 1793 1794 // Print to stdout, exposing structure 1795 static void _S_dump(_RopeRep* __r, int __indent = 0); 1796 1797 // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp. 1798 static int _S_compare(const _RopeRep* __x, const _RopeRep* __y); 1799 1800 public: 1801 bool 1802 empty() const 1803 { return 0 == this->_M_tree_ptr; } 1804 1805 // Comparison member function. This is public only for those 1806 // clients that need a ternary comparison. Others 1807 // should use the comparison operators below. 1808 int 1809 compare(const rope& __y) const 1810 { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); } 1811 1812 rope(const _CharT* __s, const allocator_type& __a = allocator_type()) 1813 : _Base(__a) 1814 { 1815 this->_M_tree_ptr = 1816 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s), 1817 _M_get_allocator()); 1818 } 1819 1820 rope(const _CharT* __s, size_t __len, 1821 const allocator_type& __a = allocator_type()) 1822 : _Base(__a) 1823 { 1824 this->_M_tree_ptr = 1825 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, _M_get_allocator()); 1826 } 1827 1828 // Should perhaps be templatized with respect to the iterator type 1829 // and use Sequence_buffer. (It should perhaps use sequence_buffer 1830 // even now.) 1831 rope(const _CharT* __s, const _CharT* __e, 1832 const allocator_type& __a = allocator_type()) 1833 : _Base(__a) 1834 { 1835 this->_M_tree_ptr = 1836 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, _M_get_allocator()); 1837 } 1838 1839 rope(const const_iterator& __s, const const_iterator& __e, 1840 const allocator_type& __a = allocator_type()) 1841 : _Base(_S_substring(__s._M_root, __s._M_current_pos, 1842 __e._M_current_pos), __a) 1843 { } 1844 1845 rope(const iterator& __s, const iterator& __e, 1846 const allocator_type& __a = allocator_type()) 1847 : _Base(_S_substring(__s._M_root, __s._M_current_pos, 1848 __e._M_current_pos), __a) 1849 { } 1850 1851 rope(_CharT __c, const allocator_type& __a = allocator_type()) 1852 : _Base(__a) 1853 { 1854 _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1)); 1855 1856 _M_get_allocator().construct(__buf, __c); 1857 __try 1858 { 1859 this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1, 1860 _M_get_allocator()); 1861 } 1862 __catch(...) 1863 { 1864 _RopeRep::__STL_FREE_STRING(__buf, 1, _M_get_allocator()); 1865 __throw_exception_again; 1866 } 1867 } 1868 1869 rope(size_t __n, _CharT __c, 1870 const allocator_type& __a = allocator_type()); 1871 1872 rope(const allocator_type& __a = allocator_type()) 1873 : _Base(0, __a) { } 1874 1875 // Construct a rope from a function that can compute its members 1876 rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn, 1877 const allocator_type& __a = allocator_type()) 1878 : _Base(__a) 1879 { 1880 this->_M_tree_ptr = (0 == __len) ? 1881 0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a); 1882 } 1883 1884 rope(const rope& __x, const allocator_type& __a = allocator_type()) 1885 : _Base(__x._M_tree_ptr, __a) 1886 { _S_ref(this->_M_tree_ptr); } 1887 1888 ~rope() throw() 1889 { _S_unref(this->_M_tree_ptr); } 1890 1891 rope& 1892 operator=(const rope& __x) 1893 { 1894 _RopeRep* __old = this->_M_tree_ptr; 1895 this->_M_tree_ptr = __x._M_tree_ptr; 1896 _S_ref(this->_M_tree_ptr); 1897 _S_unref(__old); 1898 return *this; 1899 } 1900 1901 void 1902 clear() 1903 { 1904 _S_unref(this->_M_tree_ptr); 1905 this->_M_tree_ptr = 0; 1906 } 1907 1908 void 1909 push_back(_CharT __x) 1910 { 1911 _RopeRep* __old = this->_M_tree_ptr; 1912 this->_M_tree_ptr 1913 = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1); 1914 _S_unref(__old); 1915 } 1916 1917 void 1918 pop_back() 1919 { 1920 _RopeRep* __old = this->_M_tree_ptr; 1921 this->_M_tree_ptr = _S_substring(this->_M_tree_ptr, 1922 0, this->_M_tree_ptr->_M_size - 1); 1923 _S_unref(__old); 1924 } 1925 1926 _CharT 1927 back() const 1928 { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); } 1929 1930 void 1931 push_front(_CharT __x) 1932 { 1933 _RopeRep* __old = this->_M_tree_ptr; 1934 _RopeRep* __left = 1935 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator()); 1936 __try 1937 { 1938 this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr); 1939 _S_unref(__old); 1940 _S_unref(__left); 1941 } 1942 __catch(...) 1943 { 1944 _S_unref(__left); 1945 __throw_exception_again; 1946 } 1947 } 1948 1949 void 1950 pop_front() 1951 { 1952 _RopeRep* __old = this->_M_tree_ptr; 1953 this->_M_tree_ptr 1954 = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size); 1955 _S_unref(__old); 1956 } 1957 1958 _CharT 1959 front() const 1960 { return _S_fetch(this->_M_tree_ptr, 0); } 1961 1962 void 1963 balance() 1964 { 1965 _RopeRep* __old = this->_M_tree_ptr; 1966 this->_M_tree_ptr = _S_balance(this->_M_tree_ptr); 1967 _S_unref(__old); 1968 } 1969 1970 void 1971 copy(_CharT* __buffer) const 1972 { 1973 _Destroy_const(__buffer, __buffer + size(), _M_get_allocator()); 1974 _S_flatten(this->_M_tree_ptr, __buffer); 1975 } 1976 1977 // This is the copy function from the standard, but 1978 // with the arguments reordered to make it consistent with the 1979 // rest of the interface. 1980 // Note that this guaranteed not to compile if the draft standard 1981 // order is assumed. 1982 size_type 1983 copy(size_type __pos, size_type __n, _CharT* __buffer) const 1984 { 1985 size_t __size = size(); 1986 size_t __len = (__pos + __n > __size? __size - __pos : __n); 1987 1988 _Destroy_const(__buffer, __buffer + __len, _M_get_allocator()); 1989 _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer); 1990 return __len; 1991 } 1992 1993 // Print to stdout, exposing structure. May be useful for 1994 // performance debugging. 1995 void 1996 dump() 1997 { _S_dump(this->_M_tree_ptr); } 1998 1999 // Convert to 0 terminated string in new allocated memory. 2000 // Embedded 0s in the input do not terminate the copy. 2001 const _CharT* c_str() const; 2002 2003 // As above, but also use the flattened representation as 2004 // the new rope representation. 2005 const _CharT* replace_with_c_str(); 2006 2007 // Reclaim memory for the c_str generated flattened string. 2008 // Intentionally undocumented, since it's hard to say when this 2009 // is safe for multiple threads. 2010 void 2011 delete_c_str () 2012 { 2013 if (0 == this->_M_tree_ptr) 2014 return; 2015 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag && 2016 ((_RopeLeaf*)this->_M_tree_ptr)->_M_data == 2017 this->_M_tree_ptr->_M_c_string) 2018 { 2019 // Representation shared 2020 return; 2021 } 2022 #ifndef __GC 2023 this->_M_tree_ptr->_M_free_c_string(); 2024 #endif 2025 this->_M_tree_ptr->_M_c_string = 0; 2026 } 2027 2028 _CharT 2029 operator[] (size_type __pos) const 2030 { return _S_fetch(this->_M_tree_ptr, __pos); } 2031 2032 _CharT 2033 at(size_type __pos) const 2034 { 2035 // if (__pos >= size()) throw out_of_range; // XXX 2036 return (*this)[__pos]; 2037 } 2038 2039 const_iterator 2040 begin() const 2041 { return(const_iterator(this->_M_tree_ptr, 0)); } 2042 2043 // An easy way to get a const iterator from a non-const container. 2044 const_iterator 2045 const_begin() const 2046 { return(const_iterator(this->_M_tree_ptr, 0)); } 2047 2048 const_iterator 2049 end() const 2050 { return(const_iterator(this->_M_tree_ptr, size())); } 2051 2052 const_iterator 2053 const_end() const 2054 { return(const_iterator(this->_M_tree_ptr, size())); } 2055 2056 size_type 2057 size() const 2058 { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); } 2059 2060 size_type 2061 length() const 2062 { return size(); } 2063 2064 size_type 2065 max_size() const 2066 { 2067 return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1; 2068 // Guarantees that the result can be sufficiently 2069 // balanced. Longer ropes will probably still work, 2070 // but it's harder to make guarantees. 2071 } 2072 2073 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 2074 2075 const_reverse_iterator 2076 rbegin() const 2077 { return const_reverse_iterator(end()); } 2078 2079 const_reverse_iterator 2080 const_rbegin() const 2081 { return const_reverse_iterator(end()); } 2082 2083 const_reverse_iterator 2084 rend() const 2085 { return const_reverse_iterator(begin()); } 2086 2087 const_reverse_iterator 2088 const_rend() const 2089 { return const_reverse_iterator(begin()); } 2090 2091 template<class _CharT2, class _Alloc2> 2092 friend rope<_CharT2, _Alloc2> 2093 operator+(const rope<_CharT2, _Alloc2>& __left, 2094 const rope<_CharT2, _Alloc2>& __right); 2095 2096 template<class _CharT2, class _Alloc2> 2097 friend rope<_CharT2, _Alloc2> 2098 operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right); 2099 2100 template<class _CharT2, class _Alloc2> 2101 friend rope<_CharT2, _Alloc2> 2102 operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right); 2103 2104 // The symmetric cases are intentionally omitted, since they're 2105 // presumed to be less common, and we don't handle them as well. 2106 2107 // The following should really be templatized. The first 2108 // argument should be an input iterator or forward iterator with 2109 // value_type _CharT. 2110 rope& 2111 append(const _CharT* __iter, size_t __n) 2112 { 2113 _RopeRep* __result = 2114 _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n); 2115 _S_unref(this->_M_tree_ptr); 2116 this->_M_tree_ptr = __result; 2117 return *this; 2118 } 2119 2120 rope& 2121 append(const _CharT* __c_string) 2122 { 2123 size_t __len = _S_char_ptr_len(__c_string); 2124 append(__c_string, __len); 2125 return(*this); 2126 } 2127 2128 rope& 2129 append(const _CharT* __s, const _CharT* __e) 2130 { 2131 _RopeRep* __result = 2132 _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s); 2133 _S_unref(this->_M_tree_ptr); 2134 this->_M_tree_ptr = __result; 2135 return *this; 2136 } 2137 2138 rope& 2139 append(const_iterator __s, const_iterator __e) 2140 { 2141 _Self_destruct_ptr __appendee(_S_substring(__s._M_root, 2142 __s._M_current_pos, 2143 __e._M_current_pos)); 2144 _RopeRep* __result = _S_concat(this->_M_tree_ptr, 2145 (_RopeRep*)__appendee); 2146 _S_unref(this->_M_tree_ptr); 2147 this->_M_tree_ptr = __result; 2148 return *this; 2149 } 2150 2151 rope& 2152 append(_CharT __c) 2153 { 2154 _RopeRep* __result = 2155 _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1); 2156 _S_unref(this->_M_tree_ptr); 2157 this->_M_tree_ptr = __result; 2158 return *this; 2159 } 2160 2161 rope& 2162 append() 2163 { return append(_CharT()); } // XXX why? 2164 2165 rope& 2166 append(const rope& __y) 2167 { 2168 _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr); 2169 _S_unref(this->_M_tree_ptr); 2170 this->_M_tree_ptr = __result; 2171 return *this; 2172 } 2173 2174 rope& 2175 append(size_t __n, _CharT __c) 2176 { 2177 rope<_CharT,_Alloc> __last(__n, __c); 2178 return append(__last); 2179 } 2180 2181 void 2182 swap(rope& __b) 2183 { 2184 _RopeRep* __tmp = this->_M_tree_ptr; 2185 this->_M_tree_ptr = __b._M_tree_ptr; 2186 __b._M_tree_ptr = __tmp; 2187 } 2188 2189 protected: 2190 // Result is included in refcount. 2191 static _RopeRep* 2192 replace(_RopeRep* __old, size_t __pos1, 2193 size_t __pos2, _RopeRep* __r) 2194 { 2195 if (0 == __old) 2196 { 2197 _S_ref(__r); 2198 return __r; 2199 } 2200 _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1)); 2201 _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size)); 2202 _RopeRep* __result; 2203 2204 if (0 == __r) 2205 __result = _S_concat(__left, __right); 2206 else 2207 { 2208 _Self_destruct_ptr __left_result(_S_concat(__left, __r)); 2209 __result = _S_concat(__left_result, __right); 2210 } 2211 return __result; 2212 } 2213 2214 public: 2215 void 2216 insert(size_t __p, const rope& __r) 2217 { 2218 _RopeRep* __result = 2219 replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr); 2220 _S_unref(this->_M_tree_ptr); 2221 this->_M_tree_ptr = __result; 2222 } 2223 2224 void 2225 insert(size_t __p, size_t __n, _CharT __c) 2226 { 2227 rope<_CharT,_Alloc> __r(__n,__c); 2228 insert(__p, __r); 2229 } 2230 2231 void 2232 insert(size_t __p, const _CharT* __i, size_t __n) 2233 { 2234 _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p)); 2235 _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr, 2236 __p, size())); 2237 _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n)); 2238 // _S_ destr_concat_char_iter should be safe here. 2239 // But as it stands it's probably not a win, since __left 2240 // is likely to have additional references. 2241 _RopeRep* __result = _S_concat(__left_result, __right); 2242 _S_unref(this->_M_tree_ptr); 2243 this->_M_tree_ptr = __result; 2244 } 2245 2246 void 2247 insert(size_t __p, const _CharT* __c_string) 2248 { insert(__p, __c_string, _S_char_ptr_len(__c_string)); } 2249 2250 void 2251 insert(size_t __p, _CharT __c) 2252 { insert(__p, &__c, 1); } 2253 2254 void 2255 insert(size_t __p) 2256 { 2257 _CharT __c = _CharT(); 2258 insert(__p, &__c, 1); 2259 } 2260 2261 void 2262 insert(size_t __p, const _CharT* __i, const _CharT* __j) 2263 { 2264 rope __r(__i, __j); 2265 insert(__p, __r); 2266 } 2267 2268 void 2269 insert(size_t __p, const const_iterator& __i, 2270 const const_iterator& __j) 2271 { 2272 rope __r(__i, __j); 2273 insert(__p, __r); 2274 } 2275 2276 void 2277 insert(size_t __p, const iterator& __i, 2278 const iterator& __j) 2279 { 2280 rope __r(__i, __j); 2281 insert(__p, __r); 2282 } 2283 2284 // (position, length) versions of replace operations: 2285 2286 void 2287 replace(size_t __p, size_t __n, const rope& __r) 2288 { 2289 _RopeRep* __result = 2290 replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr); 2291 _S_unref(this->_M_tree_ptr); 2292 this->_M_tree_ptr = __result; 2293 } 2294 2295 void 2296 replace(size_t __p, size_t __n, 2297 const _CharT* __i, size_t __i_len) 2298 { 2299 rope __r(__i, __i_len); 2300 replace(__p, __n, __r); 2301 } 2302 2303 void 2304 replace(size_t __p, size_t __n, _CharT __c) 2305 { 2306 rope __r(__c); 2307 replace(__p, __n, __r); 2308 } 2309 2310 void 2311 replace(size_t __p, size_t __n, const _CharT* __c_string) 2312 { 2313 rope __r(__c_string); 2314 replace(__p, __n, __r); 2315 } 2316 2317 void 2318 replace(size_t __p, size_t __n, 2319 const _CharT* __i, const _CharT* __j) 2320 { 2321 rope __r(__i, __j); 2322 replace(__p, __n, __r); 2323 } 2324 2325 void 2326 replace(size_t __p, size_t __n, 2327 const const_iterator& __i, const const_iterator& __j) 2328 { 2329 rope __r(__i, __j); 2330 replace(__p, __n, __r); 2331 } 2332 2333 void 2334 replace(size_t __p, size_t __n, 2335 const iterator& __i, const iterator& __j) 2336 { 2337 rope __r(__i, __j); 2338 replace(__p, __n, __r); 2339 } 2340 2341 // Single character variants: 2342 void 2343 replace(size_t __p, _CharT __c) 2344 { 2345 iterator __i(this, __p); 2346 *__i = __c; 2347 } 2348 2349 void 2350 replace(size_t __p, const rope& __r) 2351 { replace(__p, 1, __r); } 2352 2353 void 2354 replace(size_t __p, const _CharT* __i, size_t __i_len) 2355 { replace(__p, 1, __i, __i_len); } 2356 2357 void 2358 replace(size_t __p, const _CharT* __c_string) 2359 { replace(__p, 1, __c_string); } 2360 2361 void 2362 replace(size_t __p, const _CharT* __i, const _CharT* __j) 2363 { replace(__p, 1, __i, __j); } 2364 2365 void 2366 replace(size_t __p, const const_iterator& __i, 2367 const const_iterator& __j) 2368 { replace(__p, 1, __i, __j); } 2369 2370 void 2371 replace(size_t __p, const iterator& __i, 2372 const iterator& __j) 2373 { replace(__p, 1, __i, __j); } 2374 2375 // Erase, (position, size) variant. 2376 void 2377 erase(size_t __p, size_t __n) 2378 { 2379 _RopeRep* __result = replace(this->_M_tree_ptr, __p, 2380 __p + __n, 0); 2381 _S_unref(this->_M_tree_ptr); 2382 this->_M_tree_ptr = __result; 2383 } 2384 2385 // Erase, single character 2386 void 2387 erase(size_t __p) 2388 { erase(__p, __p + 1); } 2389 2390 // Insert, iterator variants. 2391 iterator 2392 insert(const iterator& __p, const rope& __r) 2393 { 2394 insert(__p.index(), __r); 2395 return __p; 2396 } 2397 2398 iterator 2399 insert(const iterator& __p, size_t __n, _CharT __c) 2400 { 2401 insert(__p.index(), __n, __c); 2402 return __p; 2403 } 2404 2405 iterator insert(const iterator& __p, _CharT __c) 2406 { 2407 insert(__p.index(), __c); 2408 return __p; 2409 } 2410 2411 iterator 2412 insert(const iterator& __p ) 2413 { 2414 insert(__p.index()); 2415 return __p; 2416 } 2417 2418 iterator 2419 insert(const iterator& __p, const _CharT* c_string) 2420 { 2421 insert(__p.index(), c_string); 2422 return __p; 2423 } 2424 2425 iterator 2426 insert(const iterator& __p, const _CharT* __i, size_t __n) 2427 { 2428 insert(__p.index(), __i, __n); 2429 return __p; 2430 } 2431 2432 iterator 2433 insert(const iterator& __p, const _CharT* __i, 2434 const _CharT* __j) 2435 { 2436 insert(__p.index(), __i, __j); 2437 return __p; 2438 } 2439 2440 iterator 2441 insert(const iterator& __p, 2442 const const_iterator& __i, const const_iterator& __j) 2443 { 2444 insert(__p.index(), __i, __j); 2445 return __p; 2446 } 2447 2448 iterator 2449 insert(const iterator& __p, 2450 const iterator& __i, const iterator& __j) 2451 { 2452 insert(__p.index(), __i, __j); 2453 return __p; 2454 } 2455 2456 // Replace, range variants. 2457 void 2458 replace(const iterator& __p, const iterator& __q, const rope& __r) 2459 { replace(__p.index(), __q.index() - __p.index(), __r); } 2460 2461 void 2462 replace(const iterator& __p, const iterator& __q, _CharT __c) 2463 { replace(__p.index(), __q.index() - __p.index(), __c); } 2464 2465 void 2466 replace(const iterator& __p, const iterator& __q, 2467 const _CharT* __c_string) 2468 { replace(__p.index(), __q.index() - __p.index(), __c_string); } 2469 2470 void 2471 replace(const iterator& __p, const iterator& __q, 2472 const _CharT* __i, size_t __n) 2473 { replace(__p.index(), __q.index() - __p.index(), __i, __n); } 2474 2475 void 2476 replace(const iterator& __p, const iterator& __q, 2477 const _CharT* __i, const _CharT* __j) 2478 { replace(__p.index(), __q.index() - __p.index(), __i, __j); } 2479 2480 void 2481 replace(const iterator& __p, const iterator& __q, 2482 const const_iterator& __i, const const_iterator& __j) 2483 { replace(__p.index(), __q.index() - __p.index(), __i, __j); } 2484 2485 void 2486 replace(const iterator& __p, const iterator& __q, 2487 const iterator& __i, const iterator& __j) 2488 { replace(__p.index(), __q.index() - __p.index(), __i, __j); } 2489 2490 // Replace, iterator variants. 2491 void 2492 replace(const iterator& __p, const rope& __r) 2493 { replace(__p.index(), __r); } 2494 2495 void 2496 replace(const iterator& __p, _CharT __c) 2497 { replace(__p.index(), __c); } 2498 2499 void 2500 replace(const iterator& __p, const _CharT* __c_string) 2501 { replace(__p.index(), __c_string); } 2502 2503 void 2504 replace(const iterator& __p, const _CharT* __i, size_t __n) 2505 { replace(__p.index(), __i, __n); } 2506 2507 void 2508 replace(const iterator& __p, const _CharT* __i, const _CharT* __j) 2509 { replace(__p.index(), __i, __j); } 2510 2511 void 2512 replace(const iterator& __p, const_iterator __i, const_iterator __j) 2513 { replace(__p.index(), __i, __j); } 2514 2515 void 2516 replace(const iterator& __p, iterator __i, iterator __j) 2517 { replace(__p.index(), __i, __j); } 2518 2519 // Iterator and range variants of erase 2520 iterator 2521 erase(const iterator& __p, const iterator& __q) 2522 { 2523 size_t __p_index = __p.index(); 2524 erase(__p_index, __q.index() - __p_index); 2525 return iterator(this, __p_index); 2526 } 2527 2528 iterator 2529 erase(const iterator& __p) 2530 { 2531 size_t __p_index = __p.index(); 2532 erase(__p_index, 1); 2533 return iterator(this, __p_index); 2534 } 2535 2536 rope 2537 substr(size_t __start, size_t __len = 1) const 2538 { 2539 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 2540 __start, 2541 __start + __len)); 2542 } 2543 2544 rope 2545 substr(iterator __start, iterator __end) const 2546 { 2547 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 2548 __start.index(), 2549 __end.index())); 2550 } 2551 2552 rope 2553 substr(iterator __start) const 2554 { 2555 size_t __pos = __start.index(); 2556 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 2557 __pos, __pos + 1)); 2558 } 2559 2560 rope 2561 substr(const_iterator __start, const_iterator __end) const 2562 { 2563 // This might eventually take advantage of the cache in the 2564 // iterator. 2565 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 2566 __start.index(), 2567 __end.index())); 2568 } 2569 2570 rope<_CharT, _Alloc> 2571 substr(const_iterator __start) 2572 { 2573 size_t __pos = __start.index(); 2574 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 2575 __pos, __pos + 1)); 2576 } 2577 2578 static const size_type npos; 2579 2580 size_type find(_CharT __c, size_type __pos = 0) const; 2581 2582 size_type 2583 find(const _CharT* __s, size_type __pos = 0) const 2584 { 2585 size_type __result_pos; 2586 const_iterator __result = 2587 std::search(const_begin() + __pos, const_end(), 2588 __s, __s + _S_char_ptr_len(__s)); 2589 __result_pos = __result.index(); 2590 #ifndef __STL_OLD_ROPE_SEMANTICS 2591 if (__result_pos == size()) 2592 __result_pos = npos; 2593 #endif 2594 return __result_pos; 2595 } 2596 2597 iterator 2598 mutable_begin() 2599 { return(iterator(this, 0)); } 2600 2601 iterator 2602 mutable_end() 2603 { return(iterator(this, size())); } 2604 2605 typedef std::reverse_iterator<iterator> reverse_iterator; 2606 2607 reverse_iterator 2608 mutable_rbegin() 2609 { return reverse_iterator(mutable_end()); } 2610 2611 reverse_iterator 2612 mutable_rend() 2613 { return reverse_iterator(mutable_begin()); } 2614 2615 reference 2616 mutable_reference_at(size_type __pos) 2617 { return reference(this, __pos); } 2618 2619 #ifdef __STD_STUFF 2620 reference 2621 operator[] (size_type __pos) 2622 { return _char_ref_proxy(this, __pos); } 2623 2624 reference 2625 at(size_type __pos) 2626 { 2627 // if (__pos >= size()) throw out_of_range; // XXX 2628 return (*this)[__pos]; 2629 } 2630 2631 void resize(size_type __n, _CharT __c) { } 2632 void resize(size_type __n) { } 2633 void reserve(size_type __res_arg = 0) { } 2634 2635 size_type 2636 capacity() const 2637 { return max_size(); } 2638 2639 // Stuff below this line is dangerous because it's error prone. 2640 // I would really like to get rid of it. 2641 // copy function with funny arg ordering. 2642 size_type 2643 copy(_CharT* __buffer, size_type __n, 2644 size_type __pos = 0) const 2645 { return copy(__pos, __n, __buffer); } 2646 2647 iterator 2648 end() 2649 { return mutable_end(); } 2650 2651 iterator 2652 begin() 2653 { return mutable_begin(); } 2654 2655 reverse_iterator 2656 rend() 2657 { return mutable_rend(); } 2658 2659 reverse_iterator 2660 rbegin() 2661 { return mutable_rbegin(); } 2662 2663 #else 2664 const_iterator 2665 end() 2666 { return const_end(); } 2667 2668 const_iterator 2669 begin() 2670 { return const_begin(); } 2671 2672 const_reverse_iterator 2673 rend() 2674 { return const_rend(); } 2675 2676 const_reverse_iterator 2677 rbegin() 2678 { return const_rbegin(); } 2679 2680 #endif 2681 }; 2682 2683 template <class _CharT, class _Alloc> 2684 const typename rope<_CharT, _Alloc>::size_type 2685 rope<_CharT, _Alloc>::npos = (size_type)(-1); 2686 2687 template <class _CharT, class _Alloc> 2688 inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x, 2689 const _Rope_const_iterator<_CharT, _Alloc>& __y) 2690 { return (__x._M_current_pos == __y._M_current_pos 2691 && __x._M_root == __y._M_root); } 2692 2693 template <class _CharT, class _Alloc> 2694 inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x, 2695 const _Rope_const_iterator<_CharT, _Alloc>& __y) 2696 { return (__x._M_current_pos < __y._M_current_pos); } 2697 2698 template <class _CharT, class _Alloc> 2699 inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x, 2700 const _Rope_const_iterator<_CharT, _Alloc>& __y) 2701 { return !(__x == __y); } 2702 2703 template <class _CharT, class _Alloc> 2704 inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x, 2705 const _Rope_const_iterator<_CharT, _Alloc>& __y) 2706 { return __y < __x; } 2707 2708 template <class _CharT, class _Alloc> 2709 inline bool 2710 operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x, 2711 const _Rope_const_iterator<_CharT, _Alloc>& __y) 2712 { return !(__y < __x); } 2713 2714 template <class _CharT, class _Alloc> 2715 inline bool 2716 operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x, 2717 const _Rope_const_iterator<_CharT, _Alloc>& __y) 2718 { return !(__x < __y); } 2719 2720 template <class _CharT, class _Alloc> 2721 inline ptrdiff_t 2722 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, 2723 const _Rope_const_iterator<_CharT, _Alloc>& __y) 2724 { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; } 2725 2726 template <class _CharT, class _Alloc> 2727 inline _Rope_const_iterator<_CharT, _Alloc> 2728 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) 2729 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, 2730 __x._M_current_pos - __n); } 2731 2732 template <class _CharT, class _Alloc> 2733 inline _Rope_const_iterator<_CharT, _Alloc> 2734 operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) 2735 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, 2736 __x._M_current_pos + __n); } 2737 2738 template <class _CharT, class _Alloc> 2739 inline _Rope_const_iterator<_CharT, _Alloc> 2740 operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x) 2741 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, 2742 __x._M_current_pos + __n); } 2743 2744 template <class _CharT, class _Alloc> 2745 inline bool 2746 operator==(const _Rope_iterator<_CharT, _Alloc>& __x, 2747 const _Rope_iterator<_CharT, _Alloc>& __y) 2748 {return (__x._M_current_pos == __y._M_current_pos 2749 && __x._M_root_rope == __y._M_root_rope); } 2750 2751 template <class _CharT, class _Alloc> 2752 inline bool 2753 operator<(const _Rope_iterator<_CharT, _Alloc>& __x, 2754 const _Rope_iterator<_CharT, _Alloc>& __y) 2755 { return (__x._M_current_pos < __y._M_current_pos); } 2756 2757 template <class _CharT, class _Alloc> 2758 inline bool 2759 operator!=(const _Rope_iterator<_CharT, _Alloc>& __x, 2760 const _Rope_iterator<_CharT, _Alloc>& __y) 2761 { return !(__x == __y); } 2762 2763 template <class _CharT, class _Alloc> 2764 inline bool 2765 operator>(const _Rope_iterator<_CharT, _Alloc>& __x, 2766 const _Rope_iterator<_CharT, _Alloc>& __y) 2767 { return __y < __x; } 2768 2769 template <class _CharT, class _Alloc> 2770 inline bool 2771 operator<=(const _Rope_iterator<_CharT, _Alloc>& __x, 2772 const _Rope_iterator<_CharT, _Alloc>& __y) 2773 { return !(__y < __x); } 2774 2775 template <class _CharT, class _Alloc> 2776 inline bool 2777 operator>=(const _Rope_iterator<_CharT, _Alloc>& __x, 2778 const _Rope_iterator<_CharT, _Alloc>& __y) 2779 { return !(__x < __y); } 2780 2781 template <class _CharT, class _Alloc> 2782 inline ptrdiff_t 2783 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, 2784 const _Rope_iterator<_CharT, _Alloc>& __y) 2785 { return ((ptrdiff_t)__x._M_current_pos 2786 - (ptrdiff_t)__y._M_current_pos); } 2787 2788 template <class _CharT, class _Alloc> 2789 inline _Rope_iterator<_CharT, _Alloc> 2790 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, 2791 ptrdiff_t __n) 2792 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, 2793 __x._M_current_pos - __n); } 2794 2795 template <class _CharT, class _Alloc> 2796 inline _Rope_iterator<_CharT, _Alloc> 2797 operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) 2798 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, 2799 __x._M_current_pos + __n); } 2800 2801 template <class _CharT, class _Alloc> 2802 inline _Rope_iterator<_CharT, _Alloc> 2803 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x) 2804 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, 2805 __x._M_current_pos + __n); } 2806 2807 template <class _CharT, class _Alloc> 2808 inline rope<_CharT, _Alloc> 2809 operator+(const rope<_CharT, _Alloc>& __left, 2810 const rope<_CharT, _Alloc>& __right) 2811 { 2812 // Inlining this should make it possible to keep __left and 2813 // __right in registers. 2814 typedef rope<_CharT, _Alloc> rope_type; 2815 return rope_type(rope_type::_S_concat(__left._M_tree_ptr, 2816 __right._M_tree_ptr)); 2817 } 2818 2819 template <class _CharT, class _Alloc> 2820 inline rope<_CharT, _Alloc>& 2821 operator+=(rope<_CharT, _Alloc>& __left, 2822 const rope<_CharT, _Alloc>& __right) 2823 { 2824 __left.append(__right); 2825 return __left; 2826 } 2827 2828 template <class _CharT, class _Alloc> 2829 inline rope<_CharT, _Alloc> 2830 operator+(const rope<_CharT, _Alloc>& __left, 2831 const _CharT* __right) 2832 { 2833 typedef rope<_CharT, _Alloc> rope_type; 2834 size_t __rlen = rope_type::_S_char_ptr_len(__right); 2835 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr, 2836 __right, __rlen)); 2837 } 2838 2839 template <class _CharT, class _Alloc> 2840 inline rope<_CharT, _Alloc>& 2841 operator+=(rope<_CharT, _Alloc>& __left, 2842 const _CharT* __right) 2843 { 2844 __left.append(__right); 2845 return __left; 2846 } 2847 2848 template <class _CharT, class _Alloc> 2849 inline rope<_CharT, _Alloc> 2850 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right) 2851 { 2852 typedef rope<_CharT, _Alloc> rope_type; 2853 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr, 2854 &__right, 1)); 2855 } 2856 2857 template <class _CharT, class _Alloc> 2858 inline rope<_CharT, _Alloc>& 2859 operator+=(rope<_CharT, _Alloc>& __left, _CharT __right) 2860 { 2861 __left.append(__right); 2862 return __left; 2863 } 2864 2865 template <class _CharT, class _Alloc> 2866 bool 2867 operator<(const rope<_CharT, _Alloc>& __left, 2868 const rope<_CharT, _Alloc>& __right) 2869 { return __left.compare(__right) < 0; } 2870 2871 template <class _CharT, class _Alloc> 2872 bool 2873 operator==(const rope<_CharT, _Alloc>& __left, 2874 const rope<_CharT, _Alloc>& __right) 2875 { return __left.compare(__right) == 0; } 2876 2877 template <class _CharT, class _Alloc> 2878 inline bool 2879 operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, 2880 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y) 2881 { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); } 2882 2883 template <class _CharT, class _Alloc> 2884 inline bool 2885 operator!=(const rope<_CharT, _Alloc>& __x, 2886 const rope<_CharT, _Alloc>& __y) 2887 { return !(__x == __y); } 2888 2889 template <class _CharT, class _Alloc> 2890 inline bool 2891 operator>(const rope<_CharT, _Alloc>& __x, 2892 const rope<_CharT, _Alloc>& __y) 2893 { return __y < __x; } 2894 2895 template <class _CharT, class _Alloc> 2896 inline bool 2897 operator<=(const rope<_CharT, _Alloc>& __x, 2898 const rope<_CharT, _Alloc>& __y) 2899 { return !(__y < __x); } 2900 2901 template <class _CharT, class _Alloc> 2902 inline bool 2903 operator>=(const rope<_CharT, _Alloc>& __x, 2904 const rope<_CharT, _Alloc>& __y) 2905 { return !(__x < __y); } 2906 2907 template <class _CharT, class _Alloc> 2908 inline bool 2909 operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, 2910 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y) 2911 { return !(__x == __y); } 2912 2913 template<class _CharT, class _Traits, class _Alloc> 2914 std::basic_ostream<_CharT, _Traits>& 2915 operator<<(std::basic_ostream<_CharT, _Traits>& __o, 2916 const rope<_CharT, _Alloc>& __r); 2917 2918 typedef rope<char> crope; 2919 typedef rope<wchar_t> wrope; 2920 2921 inline crope::reference 2922 __mutable_reference_at(crope& __c, size_t __i) 2923 { return __c.mutable_reference_at(__i); } 2924 2925 inline wrope::reference 2926 __mutable_reference_at(wrope& __c, size_t __i) 2927 { return __c.mutable_reference_at(__i); } 2928 2929 template <class _CharT, class _Alloc> 2930 inline void 2931 swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y) 2932 { __x.swap(__y); } 2933 2934 _GLIBCXX_END_NAMESPACE_VERSION 2935 } // namespace 2936 2937 2938 namespace std _GLIBCXX_VISIBILITY(default) 2939 { 2940 namespace tr1 2941 { 2942 _GLIBCXX_BEGIN_NAMESPACE_VERSION 2943 2944 template<> 2945 struct hash<__gnu_cxx::crope> 2946 { 2947 size_t 2948 operator()(const __gnu_cxx::crope& __str) const 2949 { 2950 size_t __size = __str.size(); 2951 if (0 == __size) 2952 return 0; 2953 return 13 * __str[0] + 5 * __str[__size - 1] + __size; 2954 } 2955 }; 2956 2957 2958 template<> 2959 struct hash<__gnu_cxx::wrope> 2960 { 2961 size_t 2962 operator()(const __gnu_cxx::wrope& __str) const 2963 { 2964 size_t __size = __str.size(); 2965 if (0 == __size) 2966 return 0; 2967 return 13 * __str[0] + 5 * __str[__size - 1] + __size; 2968 } 2969 }; 2970 2971 _GLIBCXX_END_NAMESPACE_VERSION 2972 } // namespace tr1 2973 } // namespace std 2974 2975 # include <ext/ropeimpl.h> 2976 2977 #endif 2978
