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