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