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