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