libstdc++
|
00001 // SGI's rope class -*- C++ -*- 00002 00003 // Copyright (C) 2001-2015 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 3, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // Under Section 7 of GPL version 3, you are granted additional 00017 // permissions described in the GCC Runtime Library Exception, version 00018 // 3.1, as published by the Free Software Foundation. 00019 00020 // You should have received a copy of the GNU General Public License and 00021 // a copy of the GCC Runtime Library Exception along with this program; 00022 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 00023 // <http://www.gnu.org/licenses/>. 00024 00025 /* 00026 * Copyright (c) 1997 00027 * Silicon Graphics Computer Systems, Inc. 00028 * 00029 * Permission to use, copy, modify, distribute and sell this software 00030 * and its documentation for any purpose is hereby granted without fee, 00031 * provided that the above copyright notice appear in all copies and 00032 * that both that copyright notice and this permission notice appear 00033 * in supporting documentation. Silicon Graphics makes no 00034 * representations about the suitability of this software for any 00035 * purpose. It is provided "as is" without express or implied warranty. 00036 */ 00037 00038 /** @file ext/rope 00039 * This file is a GNU extension to the Standard C++ Library (possibly 00040 * containing extensions from the HP/SGI STL subset). 00041 */ 00042 00043 #ifndef _ROPE 00044 #define _ROPE 1 00045 00046 #pragma GCC system_header 00047 00048 #include <algorithm> 00049 #include <iosfwd> 00050 #include <bits/stl_construct.h> 00051 #include <bits/stl_uninitialized.h> 00052 #include <bits/stl_function.h> 00053 #include <bits/stl_numeric.h> 00054 #include <bits/allocator.h> 00055 #include <bits/gthr.h> 00056 #include <tr1/functional> 00057 00058 # ifdef __GC 00059 # define __GC_CONST const 00060 # else 00061 # define __GC_CONST // constant except for deallocation 00062 # endif 00063 00064 #include <ext/memory> // For uninitialized_copy_n 00065 00066 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) 00067 { 00068 namespace __detail 00069 { 00070 enum { _S_max_rope_depth = 45 }; 00071 enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function}; 00072 } // namespace __detail 00073 00074 using std::size_t; 00075 using std::ptrdiff_t; 00076 using std::allocator; 00077 using std::_Destroy; 00078 00079 _GLIBCXX_BEGIN_NAMESPACE_VERSION 00080 00081 // See libstdc++/36832. 00082 template<typename _ForwardIterator, typename _Allocator> 00083 void 00084 _Destroy_const(_ForwardIterator __first, 00085 _ForwardIterator __last, _Allocator __alloc) 00086 { 00087 for (; __first != __last; ++__first) 00088 __alloc.destroy(&*__first); 00089 } 00090 00091 template<typename _ForwardIterator, typename _Tp> 00092 inline void 00093 _Destroy_const(_ForwardIterator __first, 00094 _ForwardIterator __last, allocator<_Tp>) 00095 { _Destroy(__first, __last); } 00096 00097 // The _S_eos function is used for those functions that 00098 // convert to/from C-like strings to detect the end of the string. 00099 00100 // The end-of-C-string character. 00101 // This is what the draft standard says it should be. 00102 template <class _CharT> 00103 inline _CharT 00104 _S_eos(_CharT*) 00105 { return _CharT(); } 00106 00107 // Test for basic character types. 00108 // For basic character types leaves having a trailing eos. 00109 template <class _CharT> 00110 inline bool 00111 _S_is_basic_char_type(_CharT*) 00112 { return false; } 00113 00114 template <class _CharT> 00115 inline bool 00116 _S_is_one_byte_char_type(_CharT*) 00117 { return false; } 00118 00119 inline bool 00120 _S_is_basic_char_type(char*) 00121 { return true; } 00122 00123 inline bool 00124 _S_is_one_byte_char_type(char*) 00125 { return true; } 00126 00127 inline bool 00128 _S_is_basic_char_type(wchar_t*) 00129 { return true; } 00130 00131 // Store an eos iff _CharT is a basic character type. 00132 // Do not reference _S_eos if it isn't. 00133 template <class _CharT> 00134 inline void 00135 _S_cond_store_eos(_CharT&) { } 00136 00137 inline void 00138 _S_cond_store_eos(char& __c) 00139 { __c = 0; } 00140 00141 inline void 00142 _S_cond_store_eos(wchar_t& __c) 00143 { __c = 0; } 00144 00145 // char_producers are logically functions that generate a section of 00146 // a string. These can be converted to ropes. The resulting rope 00147 // invokes the char_producer on demand. This allows, for example, 00148 // files to be viewed as ropes without reading the entire file. 00149 template <class _CharT> 00150 class char_producer 00151 { 00152 public: 00153 virtual ~char_producer() { }; 00154 00155 virtual void 00156 operator()(size_t __start_pos, size_t __len, 00157 _CharT* __buffer) = 0; 00158 // Buffer should really be an arbitrary output iterator. 00159 // That way we could flatten directly into an ostream, etc. 00160 // This is thoroughly impossible, since iterator types don't 00161 // have runtime descriptions. 00162 }; 00163 00164 // Sequence buffers: 00165 // 00166 // Sequence must provide an append operation that appends an 00167 // array to the sequence. Sequence buffers are useful only if 00168 // appending an entire array is cheaper than appending element by element. 00169 // This is true for many string representations. 00170 // This should perhaps inherit from ostream<sequence::value_type> 00171 // and be implemented correspondingly, so that they can be used 00172 // for formatted. For the sake of portability, we don't do this yet. 00173 // 00174 // For now, sequence buffers behave as output iterators. But they also 00175 // behave a little like basic_ostringstream<sequence::value_type> and a 00176 // little like containers. 00177 00178 template<class _Sequence, size_t _Buf_sz = 100> 00179 class sequence_buffer 00180 : public std::iterator<std::output_iterator_tag, void, void, void, void> 00181 { 00182 public: 00183 typedef typename _Sequence::value_type value_type; 00184 protected: 00185 _Sequence* _M_prefix; 00186 value_type _M_buffer[_Buf_sz]; 00187 size_t _M_buf_count; 00188 public: 00189 00190 void 00191 flush() 00192 { 00193 _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count); 00194 _M_buf_count = 0; 00195 } 00196 00197 ~sequence_buffer() 00198 { flush(); } 00199 00200 sequence_buffer() 00201 : _M_prefix(0), _M_buf_count(0) { } 00202 00203 sequence_buffer(const sequence_buffer& __x) 00204 { 00205 _M_prefix = __x._M_prefix; 00206 _M_buf_count = __x._M_buf_count; 00207 std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer); 00208 } 00209 00210 sequence_buffer(sequence_buffer& __x) 00211 { 00212 __x.flush(); 00213 _M_prefix = __x._M_prefix; 00214 _M_buf_count = 0; 00215 } 00216 00217 sequence_buffer(_Sequence& __s) 00218 : _M_prefix(&__s), _M_buf_count(0) { } 00219 00220 sequence_buffer& 00221 operator=(sequence_buffer& __x) 00222 { 00223 __x.flush(); 00224 _M_prefix = __x._M_prefix; 00225 _M_buf_count = 0; 00226 return *this; 00227 } 00228 00229 sequence_buffer& 00230 operator=(const sequence_buffer& __x) 00231 { 00232 _M_prefix = __x._M_prefix; 00233 _M_buf_count = __x._M_buf_count; 00234 std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer); 00235 return *this; 00236 } 00237 00238 void 00239 push_back(value_type __x) 00240 { 00241 if (_M_buf_count < _Buf_sz) 00242 { 00243 _M_buffer[_M_buf_count] = __x; 00244 ++_M_buf_count; 00245 } 00246 else 00247 { 00248 flush(); 00249 _M_buffer[0] = __x; 00250 _M_buf_count = 1; 00251 } 00252 } 00253 00254 void 00255 append(value_type* __s, size_t __len) 00256 { 00257 if (__len + _M_buf_count <= _Buf_sz) 00258 { 00259 size_t __i = _M_buf_count; 00260 for (size_t __j = 0; __j < __len; __i++, __j++) 00261 _M_buffer[__i] = __s[__j]; 00262 _M_buf_count += __len; 00263 } 00264 else if (0 == _M_buf_count) 00265 _M_prefix->append(__s, __s + __len); 00266 else 00267 { 00268 flush(); 00269 append(__s, __len); 00270 } 00271 } 00272 00273 sequence_buffer& 00274 write(value_type* __s, size_t __len) 00275 { 00276 append(__s, __len); 00277 return *this; 00278 } 00279 00280 sequence_buffer& 00281 put(value_type __x) 00282 { 00283 push_back(__x); 00284 return *this; 00285 } 00286 00287 sequence_buffer& 00288 operator=(const value_type& __rhs) 00289 { 00290 push_back(__rhs); 00291 return *this; 00292 } 00293 00294 sequence_buffer& 00295 operator*() 00296 { return *this; } 00297 00298 sequence_buffer& 00299 operator++() 00300 { return *this; } 00301 00302 sequence_buffer 00303 operator++(int) 00304 { return *this; } 00305 }; 00306 00307 // The following should be treated as private, at least for now. 00308 template<class _CharT> 00309 class _Rope_char_consumer 00310 { 00311 public: 00312 // If we had member templates, these should not be virtual. 00313 // For now we need to use run-time parametrization where 00314 // compile-time would do. Hence this should all be private 00315 // for now. 00316 // The symmetry with char_producer is accidental and temporary. 00317 virtual ~_Rope_char_consumer() { }; 00318 00319 virtual bool 00320 operator()(const _CharT* __buffer, size_t __len) = 0; 00321 }; 00322 00323 // First a lot of forward declarations. The standard seems to require 00324 // much stricter "declaration before use" than many of the implementations 00325 // that preceded it. 00326 template<class _CharT, class _Alloc = allocator<_CharT> > 00327 class rope; 00328 00329 template<class _CharT, class _Alloc> 00330 struct _Rope_RopeConcatenation; 00331 00332 template<class _CharT, class _Alloc> 00333 struct _Rope_RopeLeaf; 00334 00335 template<class _CharT, class _Alloc> 00336 struct _Rope_RopeFunction; 00337 00338 template<class _CharT, class _Alloc> 00339 struct _Rope_RopeSubstring; 00340 00341 template<class _CharT, class _Alloc> 00342 class _Rope_iterator; 00343 00344 template<class _CharT, class _Alloc> 00345 class _Rope_const_iterator; 00346 00347 template<class _CharT, class _Alloc> 00348 class _Rope_char_ref_proxy; 00349 00350 template<class _CharT, class _Alloc> 00351 class _Rope_char_ptr_proxy; 00352 00353 template<class _CharT, class _Alloc> 00354 bool 00355 operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, 00356 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y); 00357 00358 template<class _CharT, class _Alloc> 00359 _Rope_const_iterator<_CharT, _Alloc> 00360 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, 00361 ptrdiff_t __n); 00362 00363 template<class _CharT, class _Alloc> 00364 _Rope_const_iterator<_CharT, _Alloc> 00365 operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, 00366 ptrdiff_t __n); 00367 00368 template<class _CharT, class _Alloc> 00369 _Rope_const_iterator<_CharT, _Alloc> 00370 operator+(ptrdiff_t __n, 00371 const _Rope_const_iterator<_CharT, _Alloc>& __x); 00372 00373 template<class _CharT, class _Alloc> 00374 bool 00375 operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x, 00376 const _Rope_const_iterator<_CharT, _Alloc>& __y); 00377 00378 template<class _CharT, class _Alloc> 00379 bool 00380 operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x, 00381 const _Rope_const_iterator<_CharT, _Alloc>& __y); 00382 00383 template<class _CharT, class _Alloc> 00384 ptrdiff_t 00385 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, 00386 const _Rope_const_iterator<_CharT, _Alloc>& __y); 00387 00388 template<class _CharT, class _Alloc> 00389 _Rope_iterator<_CharT, _Alloc> 00390 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n); 00391 00392 template<class _CharT, class _Alloc> 00393 _Rope_iterator<_CharT, _Alloc> 00394 operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n); 00395 00396 template<class _CharT, class _Alloc> 00397 _Rope_iterator<_CharT, _Alloc> 00398 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x); 00399 00400 template<class _CharT, class _Alloc> 00401 bool 00402 operator==(const _Rope_iterator<_CharT, _Alloc>& __x, 00403 const _Rope_iterator<_CharT, _Alloc>& __y); 00404 00405 template<class _CharT, class _Alloc> 00406 bool 00407 operator<(const _Rope_iterator<_CharT, _Alloc>& __x, 00408 const _Rope_iterator<_CharT, _Alloc>& __y); 00409 00410 template<class _CharT, class _Alloc> 00411 ptrdiff_t 00412 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, 00413 const _Rope_iterator<_CharT, _Alloc>& __y); 00414 00415 template<class _CharT, class _Alloc> 00416 rope<_CharT, _Alloc> 00417 operator+(const rope<_CharT, _Alloc>& __left, 00418 const rope<_CharT, _Alloc>& __right); 00419 00420 template<class _CharT, class _Alloc> 00421 rope<_CharT, _Alloc> 00422 operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right); 00423 00424 template<class _CharT, class _Alloc> 00425 rope<_CharT, _Alloc> 00426 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right); 00427 00428 // Some helpers, so we can use power on ropes. 00429 // See below for why this isn't local to the implementation. 00430 00431 // This uses a nonstandard refcount convention. 00432 // The result has refcount 0. 00433 template<class _CharT, class _Alloc> 00434 struct _Rope_Concat_fn 00435 : public std::binary_function<rope<_CharT, _Alloc>, rope<_CharT, _Alloc>, 00436 rope<_CharT, _Alloc> > 00437 { 00438 rope<_CharT, _Alloc> 00439 operator()(const rope<_CharT, _Alloc>& __x, 00440 const rope<_CharT, _Alloc>& __y) 00441 { return __x + __y; } 00442 }; 00443 00444 template <class _CharT, class _Alloc> 00445 inline rope<_CharT, _Alloc> 00446 identity_element(_Rope_Concat_fn<_CharT, _Alloc>) 00447 { return rope<_CharT, _Alloc>(); } 00448 00449 // Class _Refcount_Base provides a type, _RC_t, a data member, 00450 // _M_ref_count, and member functions _M_incr and _M_decr, which perform 00451 // atomic preincrement/predecrement. The constructor initializes 00452 // _M_ref_count. 00453 struct _Refcount_Base 00454 { 00455 // The type _RC_t 00456 typedef size_t _RC_t; 00457 00458 // The data member _M_ref_count 00459 volatile _RC_t _M_ref_count; 00460 00461 // Constructor 00462 #ifdef __GTHREAD_MUTEX_INIT 00463 __gthread_mutex_t _M_ref_count_lock = __GTHREAD_MUTEX_INIT; 00464 #else 00465 __gthread_mutex_t _M_ref_count_lock; 00466 #endif 00467 00468 _Refcount_Base(_RC_t __n) : _M_ref_count(__n) 00469 { 00470 #ifndef __GTHREAD_MUTEX_INIT 00471 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION 00472 __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock); 00473 #else 00474 #error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org. 00475 #endif 00476 #endif 00477 } 00478 00479 #ifndef __GTHREAD_MUTEX_INIT 00480 ~_Refcount_Base() 00481 { __gthread_mutex_destroy(&_M_ref_count_lock); } 00482 #endif 00483 00484 void 00485 _M_incr() 00486 { 00487 __gthread_mutex_lock(&_M_ref_count_lock); 00488 ++_M_ref_count; 00489 __gthread_mutex_unlock(&_M_ref_count_lock); 00490 } 00491 00492 _RC_t 00493 _M_decr() 00494 { 00495 __gthread_mutex_lock(&_M_ref_count_lock); 00496 volatile _RC_t __tmp = --_M_ref_count; 00497 __gthread_mutex_unlock(&_M_ref_count_lock); 00498 return __tmp; 00499 } 00500 }; 00501 00502 // 00503 // What follows should really be local to rope. Unfortunately, 00504 // that doesn't work, since it makes it impossible to define generic 00505 // equality on rope iterators. According to the draft standard, the 00506 // template parameters for such an equality operator cannot be inferred 00507 // from the occurrence of a member class as a parameter. 00508 // (SGI compilers in fact allow this, but the __result wouldn't be 00509 // portable.) 00510 // Similarly, some of the static member functions are member functions 00511 // only to avoid polluting the global namespace, and to circumvent 00512 // restrictions on type inference for template functions. 00513 // 00514 00515 // 00516 // The internal data structure for representing a rope. This is 00517 // private to the implementation. A rope is really just a pointer 00518 // to one of these. 00519 // 00520 // A few basic functions for manipulating this data structure 00521 // are members of _RopeRep. Most of the more complex algorithms 00522 // are implemented as rope members. 00523 // 00524 // Some of the static member functions of _RopeRep have identically 00525 // named functions in rope that simply invoke the _RopeRep versions. 00526 00527 #define __ROPE_DEFINE_ALLOCS(__a) \ 00528 __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \ 00529 typedef _Rope_RopeConcatenation<_CharT,__a> __C; \ 00530 __ROPE_DEFINE_ALLOC(__C,_C) \ 00531 typedef _Rope_RopeLeaf<_CharT,__a> __L; \ 00532 __ROPE_DEFINE_ALLOC(__L,_L) \ 00533 typedef _Rope_RopeFunction<_CharT,__a> __F; \ 00534 __ROPE_DEFINE_ALLOC(__F,_F) \ 00535 typedef _Rope_RopeSubstring<_CharT,__a> __S; \ 00536 __ROPE_DEFINE_ALLOC(__S,_S) 00537 00538 // Internal rope nodes potentially store a copy of the allocator 00539 // instance used to allocate them. This is mostly redundant. 00540 // But the alternative would be to pass allocator instances around 00541 // in some form to nearly all internal functions, since any pointer 00542 // assignment may result in a zero reference count and thus require 00543 // deallocation. 00544 00545 #define __STATIC_IF_SGI_ALLOC /* not static */ 00546 00547 template <class _CharT, class _Alloc> 00548 struct _Rope_rep_base 00549 : public _Alloc 00550 { 00551 typedef _Alloc allocator_type; 00552 00553 allocator_type 00554 get_allocator() const 00555 { return *static_cast<const _Alloc*>(this); } 00556 00557 allocator_type& 00558 _M_get_allocator() 00559 { return *static_cast<_Alloc*>(this); } 00560 00561 const allocator_type& 00562 _M_get_allocator() const 00563 { return *static_cast<const _Alloc*>(this); } 00564 00565 _Rope_rep_base(size_t __size, const allocator_type&) 00566 : _M_size(__size) { } 00567 00568 size_t _M_size; 00569 00570 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \ 00571 typedef typename \ 00572 _Alloc::template rebind<_Tp>::other __name##Alloc; \ 00573 static _Tp* __name##_allocate(size_t __n) \ 00574 { return __name##Alloc().allocate(__n); } \ 00575 static void __name##_deallocate(_Tp *__p, size_t __n) \ 00576 { __name##Alloc().deallocate(__p, __n); } 00577 __ROPE_DEFINE_ALLOCS(_Alloc) 00578 # undef __ROPE_DEFINE_ALLOC 00579 }; 00580 00581 template<class _CharT, class _Alloc> 00582 struct _Rope_RopeRep 00583 : public _Rope_rep_base<_CharT, _Alloc> 00584 # ifndef __GC 00585 , _Refcount_Base 00586 # endif 00587 { 00588 public: 00589 __detail::_Tag _M_tag:8; 00590 bool _M_is_balanced:8; 00591 unsigned char _M_depth; 00592 __GC_CONST _CharT* _M_c_string; 00593 #ifdef __GTHREAD_MUTEX_INIT 00594 __gthread_mutex_t _M_c_string_lock = __GTHREAD_MUTEX_INIT; 00595 #else 00596 __gthread_mutex_t _M_c_string_lock; 00597 #endif 00598 /* Flattened version of string, if needed. */ 00599 /* typically 0. */ 00600 /* If it's not 0, then the memory is owned */ 00601 /* by this node. */ 00602 /* In the case of a leaf, this may point to */ 00603 /* the same memory as the data field. */ 00604 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type 00605 allocator_type; 00606 00607 using _Rope_rep_base<_CharT, _Alloc>::get_allocator; 00608 using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator; 00609 00610 _Rope_RopeRep(__detail::_Tag __t, int __d, bool __b, size_t __size, 00611 const allocator_type& __a) 00612 : _Rope_rep_base<_CharT, _Alloc>(__size, __a), 00613 #ifndef __GC 00614 _Refcount_Base(1), 00615 #endif 00616 _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0) 00617 #ifdef __GTHREAD_MUTEX_INIT 00618 { } 00619 #else 00620 { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); } 00621 ~_Rope_RopeRep() 00622 { __gthread_mutex_destroy (&_M_c_string_lock); } 00623 #endif 00624 #ifdef __GC 00625 void 00626 _M_incr () { } 00627 #endif 00628 static void 00629 _S_free_string(__GC_CONST _CharT*, size_t __len, 00630 allocator_type& __a); 00631 #define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a); 00632 // Deallocate data section of a leaf. 00633 // This shouldn't be a member function. 00634 // But its hard to do anything else at the 00635 // moment, because it's templatized w.r.t. 00636 // an allocator. 00637 // Does nothing if __GC is defined. 00638 #ifndef __GC 00639 void _M_free_c_string(); 00640 void _M_free_tree(); 00641 // Deallocate t. Assumes t is not 0. 00642 void 00643 _M_unref_nonnil() 00644 { 00645 if (0 == _M_decr()) 00646 _M_free_tree(); 00647 } 00648 00649 void 00650 _M_ref_nonnil() 00651 { _M_incr(); } 00652 00653 static void 00654 _S_unref(_Rope_RopeRep* __t) 00655 { 00656 if (0 != __t) 00657 __t->_M_unref_nonnil(); 00658 } 00659 00660 static void 00661 _S_ref(_Rope_RopeRep* __t) 00662 { 00663 if (0 != __t) 00664 __t->_M_incr(); 00665 } 00666 00667 static void 00668 _S_free_if_unref(_Rope_RopeRep* __t) 00669 { 00670 if (0 != __t && 0 == __t->_M_ref_count) 00671 __t->_M_free_tree(); 00672 } 00673 # else /* __GC */ 00674 void _M_unref_nonnil() { } 00675 void _M_ref_nonnil() { } 00676 static void _S_unref(_Rope_RopeRep*) { } 00677 static void _S_ref(_Rope_RopeRep*) { } 00678 static void _S_free_if_unref(_Rope_RopeRep*) { } 00679 # endif 00680 protected: 00681 _Rope_RopeRep& 00682 operator=(const _Rope_RopeRep&); 00683 00684 _Rope_RopeRep(const _Rope_RopeRep&); 00685 }; 00686 00687 template<class _CharT, class _Alloc> 00688 struct _Rope_RopeLeaf 00689 : public _Rope_RopeRep<_CharT, _Alloc> 00690 { 00691 public: 00692 // Apparently needed by VC++ 00693 // The data fields of leaves are allocated with some 00694 // extra space, to accommodate future growth and for basic 00695 // character types, to hold a trailing eos character. 00696 enum { _S_alloc_granularity = 8 }; 00697 00698 static size_t 00699 _S_rounded_up_size(size_t __n) 00700 { 00701 size_t __size_with_eos; 00702 00703 if (_S_is_basic_char_type((_CharT*)0)) 00704 __size_with_eos = __n + 1; 00705 else 00706 __size_with_eos = __n; 00707 #ifdef __GC 00708 return __size_with_eos; 00709 #else 00710 // Allow slop for in-place expansion. 00711 return ((__size_with_eos + size_t(_S_alloc_granularity) - 1) 00712 &~ (size_t(_S_alloc_granularity) - 1)); 00713 #endif 00714 } 00715 __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */ 00716 /* The allocated size is */ 00717 /* _S_rounded_up_size(size), except */ 00718 /* in the GC case, in which it */ 00719 /* doesn't matter. */ 00720 typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type 00721 allocator_type; 00722 00723 _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size, 00724 const allocator_type& __a) 00725 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true, 00726 __size, __a), _M_data(__d) 00727 { 00728 if (_S_is_basic_char_type((_CharT *)0)) 00729 { 00730 // already eos terminated. 00731 this->_M_c_string = __d; 00732 } 00733 } 00734 // The constructor assumes that d has been allocated with 00735 // the proper allocator and the properly padded size. 00736 // In contrast, the destructor deallocates the data: 00737 #ifndef __GC 00738 ~_Rope_RopeLeaf() throw() 00739 { 00740 if (_M_data != this->_M_c_string) 00741 this->_M_free_c_string(); 00742 00743 this->__STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator()); 00744 } 00745 #endif 00746 protected: 00747 _Rope_RopeLeaf& 00748 operator=(const _Rope_RopeLeaf&); 00749 00750 _Rope_RopeLeaf(const _Rope_RopeLeaf&); 00751 }; 00752 00753 template<class _CharT, class _Alloc> 00754 struct _Rope_RopeConcatenation 00755 : public _Rope_RopeRep<_CharT, _Alloc> 00756 { 00757 public: 00758 _Rope_RopeRep<_CharT, _Alloc>* _M_left; 00759 _Rope_RopeRep<_CharT, _Alloc>* _M_right; 00760 00761 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type 00762 allocator_type; 00763 00764 _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l, 00765 _Rope_RopeRep<_CharT, _Alloc>* __r, 00766 const allocator_type& __a) 00767 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat, 00768 std::max(__l->_M_depth, 00769 __r->_M_depth) + 1, 00770 false, 00771 __l->_M_size + __r->_M_size, __a), 00772 _M_left(__l), _M_right(__r) 00773 { } 00774 #ifndef __GC 00775 ~_Rope_RopeConcatenation() throw() 00776 { 00777 this->_M_free_c_string(); 00778 _M_left->_M_unref_nonnil(); 00779 _M_right->_M_unref_nonnil(); 00780 } 00781 #endif 00782 protected: 00783 _Rope_RopeConcatenation& 00784 operator=(const _Rope_RopeConcatenation&); 00785 00786 _Rope_RopeConcatenation(const _Rope_RopeConcatenation&); 00787 }; 00788 00789 template<class _CharT, class _Alloc> 00790 struct _Rope_RopeFunction 00791 : public _Rope_RopeRep<_CharT, _Alloc> 00792 { 00793 public: 00794 char_producer<_CharT>* _M_fn; 00795 #ifndef __GC 00796 bool _M_delete_when_done; // Char_producer is owned by the 00797 // rope and should be explicitly 00798 // deleted when the rope becomes 00799 // inaccessible. 00800 #else 00801 // In the GC case, we either register the rope for 00802 // finalization, or not. Thus the field is unnecessary; 00803 // the information is stored in the collector data structures. 00804 // We do need a finalization procedure to be invoked by the 00805 // collector. 00806 static void 00807 _S_fn_finalization_proc(void * __tree, void *) 00808 { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; } 00809 #endif 00810 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type 00811 allocator_type; 00812 00813 _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size, 00814 bool __d, const allocator_type& __a) 00815 : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a) 00816 , _M_fn(__f) 00817 #ifndef __GC 00818 , _M_delete_when_done(__d) 00819 #endif 00820 { 00821 #ifdef __GC 00822 if (__d) 00823 { 00824 GC_REGISTER_FINALIZER(this, _Rope_RopeFunction:: 00825 _S_fn_finalization_proc, 0, 0, 0); 00826 } 00827 #endif 00828 } 00829 #ifndef __GC 00830 ~_Rope_RopeFunction() throw() 00831 { 00832 this->_M_free_c_string(); 00833 if (_M_delete_when_done) 00834 delete _M_fn; 00835 } 00836 # endif 00837 protected: 00838 _Rope_RopeFunction& 00839 operator=(const _Rope_RopeFunction&); 00840 00841 _Rope_RopeFunction(const _Rope_RopeFunction&); 00842 }; 00843 // Substring results are usually represented using just 00844 // concatenation nodes. But in the case of very long flat ropes 00845 // or ropes with a functional representation that isn't practical. 00846 // In that case, we represent the __result as a special case of 00847 // RopeFunction, whose char_producer points back to the rope itself. 00848 // In all cases except repeated substring operations and 00849 // deallocation, we treat the __result as a RopeFunction. 00850 template<class _CharT, class _Alloc> 00851 struct _Rope_RopeSubstring 00852 : public _Rope_RopeFunction<_CharT, _Alloc>, 00853 public char_producer<_CharT> 00854 { 00855 public: 00856 // XXX this whole class should be rewritten. 00857 _Rope_RopeRep<_CharT,_Alloc>* _M_base; // not 0 00858 size_t _M_start; 00859 00860 virtual void 00861 operator()(size_t __start_pos, size_t __req_len, 00862 _CharT* __buffer) 00863 { 00864 switch(_M_base->_M_tag) 00865 { 00866 case __detail::_S_function: 00867 case __detail::_S_substringfn: 00868 { 00869 char_producer<_CharT>* __fn = 00870 ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn; 00871 (*__fn)(__start_pos + _M_start, __req_len, __buffer); 00872 } 00873 break; 00874 case __detail::_S_leaf: 00875 { 00876 __GC_CONST _CharT* __s = 00877 ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data; 00878 uninitialized_copy_n(__s + __start_pos + _M_start, __req_len, 00879 __buffer); 00880 } 00881 break; 00882 default: 00883 break; 00884 } 00885 } 00886 00887 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type 00888 allocator_type; 00889 00890 _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s, 00891 size_t __l, const allocator_type& __a) 00892 : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a), 00893 char_producer<_CharT>(), _M_base(__b), _M_start(__s) 00894 { 00895 #ifndef __GC 00896 _M_base->_M_ref_nonnil(); 00897 #endif 00898 this->_M_tag = __detail::_S_substringfn; 00899 } 00900 virtual ~_Rope_RopeSubstring() throw() 00901 { 00902 #ifndef __GC 00903 _M_base->_M_unref_nonnil(); 00904 // _M_free_c_string(); -- done by parent class 00905 #endif 00906 } 00907 }; 00908 00909 // Self-destructing pointers to Rope_rep. 00910 // These are not conventional smart pointers. Their 00911 // only purpose in life is to ensure that unref is called 00912 // on the pointer either at normal exit or if an exception 00913 // is raised. It is the caller's responsibility to 00914 // adjust reference counts when these pointers are initialized 00915 // or assigned to. (This convention significantly reduces 00916 // the number of potentially expensive reference count 00917 // updates.) 00918 #ifndef __GC 00919 template<class _CharT, class _Alloc> 00920 struct _Rope_self_destruct_ptr 00921 { 00922 _Rope_RopeRep<_CharT, _Alloc>* _M_ptr; 00923 00924 ~_Rope_self_destruct_ptr() 00925 { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); } 00926 #if __cpp_exceptions 00927 _Rope_self_destruct_ptr() : _M_ptr(0) { }; 00928 #else 00929 _Rope_self_destruct_ptr() { }; 00930 #endif 00931 _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p) 00932 : _M_ptr(__p) { } 00933 00934 _Rope_RopeRep<_CharT, _Alloc>& 00935 operator*() 00936 { return *_M_ptr; } 00937 00938 _Rope_RopeRep<_CharT, _Alloc>* 00939 operator->() 00940 { return _M_ptr; } 00941 00942 operator _Rope_RopeRep<_CharT, _Alloc>*() 00943 { return _M_ptr; } 00944 00945 _Rope_self_destruct_ptr& 00946 operator=(_Rope_RopeRep<_CharT, _Alloc>* __x) 00947 { _M_ptr = __x; return *this; } 00948 }; 00949 #endif 00950 00951 // Dereferencing a nonconst iterator has to return something 00952 // that behaves almost like a reference. It's not possible to 00953 // return an actual reference since assignment requires extra 00954 // work. And we would get into the same problems as with the 00955 // CD2 version of basic_string. 00956 template<class _CharT, class _Alloc> 00957 class _Rope_char_ref_proxy 00958 { 00959 friend class rope<_CharT, _Alloc>; 00960 friend class _Rope_iterator<_CharT, _Alloc>; 00961 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>; 00962 #ifdef __GC 00963 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr; 00964 #else 00965 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr; 00966 #endif 00967 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 00968 typedef rope<_CharT, _Alloc> _My_rope; 00969 size_t _M_pos; 00970 _CharT _M_current; 00971 bool _M_current_valid; 00972 _My_rope* _M_root; // The whole rope. 00973 public: 00974 _Rope_char_ref_proxy(_My_rope* __r, size_t __p) 00975 : _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { } 00976 00977 _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x) 00978 : _M_pos(__x._M_pos), _M_current(__x._M_current), 00979 _M_current_valid(false), _M_root(__x._M_root) { } 00980 00981 // Don't preserve cache if the reference can outlive the 00982 // expression. We claim that's not possible without calling 00983 // a copy constructor or generating reference to a proxy 00984 // reference. We declare the latter to have undefined semantics. 00985 _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c) 00986 : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { } 00987 00988 inline operator _CharT () const; 00989 00990 _Rope_char_ref_proxy& 00991 operator=(_CharT __c); 00992 00993 _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const; 00994 00995 _Rope_char_ref_proxy& 00996 operator=(const _Rope_char_ref_proxy& __c) 00997 { return operator=((_CharT)__c); } 00998 }; 00999 01000 template<class _CharT, class __Alloc> 01001 inline void 01002 swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a, 01003 _Rope_char_ref_proxy <_CharT, __Alloc > __b) 01004 { 01005 _CharT __tmp = __a; 01006 __a = __b; 01007 __b = __tmp; 01008 } 01009 01010 template<class _CharT, class _Alloc> 01011 class _Rope_char_ptr_proxy 01012 { 01013 // XXX this class should be rewritten. 01014 friend class _Rope_char_ref_proxy<_CharT, _Alloc>; 01015 size_t _M_pos; 01016 rope<_CharT,_Alloc>* _M_root; // The whole rope. 01017 public: 01018 _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x) 01019 : _M_pos(__x._M_pos), _M_root(__x._M_root) { } 01020 01021 _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x) 01022 : _M_pos(__x._M_pos), _M_root(__x._M_root) { } 01023 01024 _Rope_char_ptr_proxy() { } 01025 01026 _Rope_char_ptr_proxy(_CharT* __x) 01027 : _M_root(0), _M_pos(0) { } 01028 01029 _Rope_char_ptr_proxy& 01030 operator=(const _Rope_char_ptr_proxy& __x) 01031 { 01032 _M_pos = __x._M_pos; 01033 _M_root = __x._M_root; 01034 return *this; 01035 } 01036 01037 template<class _CharT2, class _Alloc2> 01038 friend bool 01039 operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x, 01040 const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y); 01041 01042 _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const 01043 { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); } 01044 }; 01045 01046 // Rope iterators: 01047 // Unlike in the C version, we cache only part of the stack 01048 // for rope iterators, since they must be efficiently copyable. 01049 // When we run out of cache, we have to reconstruct the iterator 01050 // value. 01051 // Pointers from iterators are not included in reference counts. 01052 // Iterators are assumed to be thread private. Ropes can 01053 // be shared. 01054 01055 template<class _CharT, class _Alloc> 01056 class _Rope_iterator_base 01057 : public std::iterator<std::random_access_iterator_tag, _CharT> 01058 { 01059 friend class rope<_CharT, _Alloc>; 01060 public: 01061 typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround 01062 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 01063 // Borland doesn't want this to be protected. 01064 protected: 01065 enum { _S_path_cache_len = 4 }; // Must be <= 9. 01066 enum { _S_iterator_buf_len = 15 }; 01067 size_t _M_current_pos; 01068 _RopeRep* _M_root; // The whole rope. 01069 size_t _M_leaf_pos; // Starting position for current leaf 01070 __GC_CONST _CharT* _M_buf_start; 01071 // Buffer possibly 01072 // containing current char. 01073 __GC_CONST _CharT* _M_buf_ptr; 01074 // Pointer to current char in buffer. 01075 // != 0 ==> buffer valid. 01076 __GC_CONST _CharT* _M_buf_end; 01077 // One past __last valid char in buffer. 01078 // What follows is the path cache. We go out of our 01079 // way to make this compact. 01080 // Path_end contains the bottom section of the path from 01081 // the root to the current leaf. 01082 const _RopeRep* _M_path_end[_S_path_cache_len]; 01083 int _M_leaf_index; // Last valid __pos in path_end; 01084 // _M_path_end[0] ... _M_path_end[leaf_index-1] 01085 // point to concatenation nodes. 01086 unsigned char _M_path_directions; 01087 // (path_directions >> __i) & 1 is 1 01088 // iff we got from _M_path_end[leaf_index - __i - 1] 01089 // to _M_path_end[leaf_index - __i] by going to the 01090 // __right. Assumes path_cache_len <= 9. 01091 _CharT _M_tmp_buf[_S_iterator_buf_len]; 01092 // Short buffer for surrounding chars. 01093 // This is useful primarily for 01094 // RopeFunctions. We put the buffer 01095 // here to avoid locking in the 01096 // multithreaded case. 01097 // The cached path is generally assumed to be valid 01098 // only if the buffer is valid. 01099 static void _S_setbuf(_Rope_iterator_base& __x); 01100 // Set buffer contents given 01101 // path cache. 01102 static void _S_setcache(_Rope_iterator_base& __x); 01103 // Set buffer contents and 01104 // path cache. 01105 static void _S_setcache_for_incr(_Rope_iterator_base& __x); 01106 // As above, but assumes path 01107 // cache is valid for previous posn. 01108 _Rope_iterator_base() { } 01109 01110 _Rope_iterator_base(_RopeRep* __root, size_t __pos) 01111 : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { } 01112 01113 void _M_incr(size_t __n); 01114 void _M_decr(size_t __n); 01115 public: 01116 size_t 01117 index() const 01118 { return _M_current_pos; } 01119 01120 _Rope_iterator_base(const _Rope_iterator_base& __x) 01121 { 01122 if (0 != __x._M_buf_ptr) 01123 *this = __x; 01124 else 01125 { 01126 _M_current_pos = __x._M_current_pos; 01127 _M_root = __x._M_root; 01128 _M_buf_ptr = 0; 01129 } 01130 } 01131 }; 01132 01133 template<class _CharT, class _Alloc> 01134 class _Rope_iterator; 01135 01136 template<class _CharT, class _Alloc> 01137 class _Rope_const_iterator 01138 : public _Rope_iterator_base<_CharT, _Alloc> 01139 { 01140 friend class rope<_CharT, _Alloc>; 01141 protected: 01142 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 01143 // The one from the base class may not be directly visible. 01144 _Rope_const_iterator(const _RopeRep* __root, size_t __pos) 01145 : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root), 01146 __pos) 01147 // Only nonconst iterators modify root ref count 01148 { } 01149 public: 01150 typedef _CharT reference; // Really a value. Returning a reference 01151 // Would be a mess, since it would have 01152 // to be included in refcount. 01153 typedef const _CharT* pointer; 01154 01155 public: 01156 _Rope_const_iterator() { }; 01157 01158 _Rope_const_iterator(const _Rope_const_iterator& __x) 01159 : _Rope_iterator_base<_CharT,_Alloc>(__x) { } 01160 01161 _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x); 01162 01163 _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos) 01164 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { } 01165 01166 _Rope_const_iterator& 01167 operator=(const _Rope_const_iterator& __x) 01168 { 01169 if (0 != __x._M_buf_ptr) 01170 *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x; 01171 else 01172 { 01173 this->_M_current_pos = __x._M_current_pos; 01174 this->_M_root = __x._M_root; 01175 this->_M_buf_ptr = 0; 01176 } 01177 return(*this); 01178 } 01179 01180 reference 01181 operator*() 01182 { 01183 if (0 == this->_M_buf_ptr) 01184 this->_S_setcache(*this); 01185 return *this->_M_buf_ptr; 01186 } 01187 01188 // Without this const version, Rope iterators do not meet the 01189 // requirements of an Input Iterator. 01190 reference 01191 operator*() const 01192 { 01193 return *const_cast<_Rope_const_iterator&>(*this); 01194 } 01195 01196 _Rope_const_iterator& 01197 operator++() 01198 { 01199 __GC_CONST _CharT* __next; 01200 if (0 != this->_M_buf_ptr 01201 && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end) 01202 { 01203 this->_M_buf_ptr = __next; 01204 ++this->_M_current_pos; 01205 } 01206 else 01207 this->_M_incr(1); 01208 return *this; 01209 } 01210 01211 _Rope_const_iterator& 01212 operator+=(ptrdiff_t __n) 01213 { 01214 if (__n >= 0) 01215 this->_M_incr(__n); 01216 else 01217 this->_M_decr(-__n); 01218 return *this; 01219 } 01220 01221 _Rope_const_iterator& 01222 operator--() 01223 { 01224 this->_M_decr(1); 01225 return *this; 01226 } 01227 01228 _Rope_const_iterator& 01229 operator-=(ptrdiff_t __n) 01230 { 01231 if (__n >= 0) 01232 this->_M_decr(__n); 01233 else 01234 this->_M_incr(-__n); 01235 return *this; 01236 } 01237 01238 _Rope_const_iterator 01239 operator++(int) 01240 { 01241 size_t __old_pos = this->_M_current_pos; 01242 this->_M_incr(1); 01243 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos); 01244 // This makes a subsequent dereference expensive. 01245 // Perhaps we should instead copy the iterator 01246 // if it has a valid cache? 01247 } 01248 01249 _Rope_const_iterator 01250 operator--(int) 01251 { 01252 size_t __old_pos = this->_M_current_pos; 01253 this->_M_decr(1); 01254 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos); 01255 } 01256 01257 template<class _CharT2, class _Alloc2> 01258 friend _Rope_const_iterator<_CharT2, _Alloc2> 01259 operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, 01260 ptrdiff_t __n); 01261 01262 template<class _CharT2, class _Alloc2> 01263 friend _Rope_const_iterator<_CharT2, _Alloc2> 01264 operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, 01265 ptrdiff_t __n); 01266 01267 template<class _CharT2, class _Alloc2> 01268 friend _Rope_const_iterator<_CharT2, _Alloc2> 01269 operator+(ptrdiff_t __n, 01270 const _Rope_const_iterator<_CharT2, _Alloc2>& __x); 01271 01272 reference 01273 operator[](size_t __n) 01274 { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root, 01275 this->_M_current_pos + __n); } 01276 01277 template<class _CharT2, class _Alloc2> 01278 friend bool 01279 operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, 01280 const _Rope_const_iterator<_CharT2, _Alloc2>& __y); 01281 01282 template<class _CharT2, class _Alloc2> 01283 friend bool 01284 operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, 01285 const _Rope_const_iterator<_CharT2, _Alloc2>& __y); 01286 01287 template<class _CharT2, class _Alloc2> 01288 friend ptrdiff_t 01289 operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x, 01290 const _Rope_const_iterator<_CharT2, _Alloc2>& __y); 01291 }; 01292 01293 template<class _CharT, class _Alloc> 01294 class _Rope_iterator 01295 : public _Rope_iterator_base<_CharT, _Alloc> 01296 { 01297 friend class rope<_CharT, _Alloc>; 01298 protected: 01299 typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep; 01300 rope<_CharT, _Alloc>* _M_root_rope; 01301 01302 // root is treated as a cached version of this, and is used to 01303 // detect changes to the underlying rope. 01304 01305 // Root is included in the reference count. This is necessary 01306 // so that we can detect changes reliably. Unfortunately, it 01307 // requires careful bookkeeping for the nonGC case. 01308 _Rope_iterator(rope<_CharT, _Alloc>* __r, size_t __pos) 01309 : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos), 01310 _M_root_rope(__r) 01311 { _RopeRep::_S_ref(this->_M_root); 01312 if (!(__r -> empty())) 01313 this->_S_setcache(*this); 01314 } 01315 01316 void _M_check(); 01317 public: 01318 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference; 01319 typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer; 01320 01321 rope<_CharT, _Alloc>& 01322 container() 01323 { return *_M_root_rope; } 01324 01325 _Rope_iterator() 01326 { 01327 this->_M_root = 0; // Needed for reference counting. 01328 }; 01329 01330 _Rope_iterator(const _Rope_iterator& __x) 01331 : _Rope_iterator_base<_CharT, _Alloc>(__x) 01332 { 01333 _M_root_rope = __x._M_root_rope; 01334 _RopeRep::_S_ref(this->_M_root); 01335 } 01336 01337 _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos); 01338 01339 ~_Rope_iterator() 01340 { _RopeRep::_S_unref(this->_M_root); } 01341 01342 _Rope_iterator& 01343 operator=(const _Rope_iterator& __x) 01344 { 01345 _RopeRep* __old = this->_M_root; 01346 01347 _RopeRep::_S_ref(__x._M_root); 01348 if (0 != __x._M_buf_ptr) 01349 { 01350 _M_root_rope = __x._M_root_rope; 01351 *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x; 01352 } 01353 else 01354 { 01355 this->_M_current_pos = __x._M_current_pos; 01356 this->_M_root = __x._M_root; 01357 _M_root_rope = __x._M_root_rope; 01358 this->_M_buf_ptr = 0; 01359 } 01360 _RopeRep::_S_unref(__old); 01361 return(*this); 01362 } 01363 01364 reference 01365 operator*() 01366 { 01367 _M_check(); 01368 if (0 == this->_M_buf_ptr) 01369 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope, 01370 this->_M_current_pos); 01371 else 01372 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope, 01373 this->_M_current_pos, 01374 *this->_M_buf_ptr); 01375 } 01376 01377 // See above comment. 01378 reference 01379 operator*() const 01380 { 01381 return *const_cast<_Rope_iterator&>(*this); 01382 } 01383 01384 _Rope_iterator& 01385 operator++() 01386 { 01387 this->_M_incr(1); 01388 return *this; 01389 } 01390 01391 _Rope_iterator& 01392 operator+=(ptrdiff_t __n) 01393 { 01394 if (__n >= 0) 01395 this->_M_incr(__n); 01396 else 01397 this->_M_decr(-__n); 01398 return *this; 01399 } 01400 01401 _Rope_iterator& 01402 operator--() 01403 { 01404 this->_M_decr(1); 01405 return *this; 01406 } 01407 01408 _Rope_iterator& 01409 operator-=(ptrdiff_t __n) 01410 { 01411 if (__n >= 0) 01412 this->_M_decr(__n); 01413 else 01414 this->_M_incr(-__n); 01415 return *this; 01416 } 01417 01418 _Rope_iterator 01419 operator++(int) 01420 { 01421 size_t __old_pos = this->_M_current_pos; 01422 this->_M_incr(1); 01423 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos); 01424 } 01425 01426 _Rope_iterator 01427 operator--(int) 01428 { 01429 size_t __old_pos = this->_M_current_pos; 01430 this->_M_decr(1); 01431 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos); 01432 } 01433 01434 reference 01435 operator[](ptrdiff_t __n) 01436 { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope, 01437 this->_M_current_pos 01438 + __n); } 01439 01440 template<class _CharT2, class _Alloc2> 01441 friend bool 01442 operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x, 01443 const _Rope_iterator<_CharT2, _Alloc2>& __y); 01444 01445 template<class _CharT2, class _Alloc2> 01446 friend bool 01447 operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x, 01448 const _Rope_iterator<_CharT2, _Alloc2>& __y); 01449 01450 template<class _CharT2, class _Alloc2> 01451 friend ptrdiff_t 01452 operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, 01453 const _Rope_iterator<_CharT2, _Alloc2>& __y); 01454 01455 template<class _CharT2, class _Alloc2> 01456 friend _Rope_iterator<_CharT2, _Alloc2> 01457 operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n); 01458 01459 template<class _CharT2, class _Alloc2> 01460 friend _Rope_iterator<_CharT2, _Alloc2> 01461 operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n); 01462 01463 template<class _CharT2, class _Alloc2> 01464 friend _Rope_iterator<_CharT2, _Alloc2> 01465 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x); 01466 }; 01467 01468 01469 template <class _CharT, class _Alloc> 01470 struct _Rope_base 01471 : public _Alloc 01472 { 01473 typedef _Alloc allocator_type; 01474 01475 allocator_type 01476 get_allocator() const 01477 { return *static_cast<const _Alloc*>(this); } 01478 01479 allocator_type& 01480 _M_get_allocator() 01481 { return *static_cast<_Alloc*>(this); } 01482 01483 const allocator_type& 01484 _M_get_allocator() const 01485 { return *static_cast<const _Alloc*>(this); } 01486 01487 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 01488 // The one in _Base may not be visible due to template rules. 01489 01490 _Rope_base(_RopeRep* __t, const allocator_type&) 01491 : _M_tree_ptr(__t) { } 01492 01493 _Rope_base(const allocator_type&) { } 01494 01495 // The only data member of a rope: 01496 _RopeRep *_M_tree_ptr; 01497 01498 #define __ROPE_DEFINE_ALLOC(_Tp, __name) \ 01499 typedef typename \ 01500 _Alloc::template rebind<_Tp>::other __name##Alloc; \ 01501 static _Tp* __name##_allocate(size_t __n) \ 01502 { return __name##Alloc().allocate(__n); } \ 01503 static void __name##_deallocate(_Tp *__p, size_t __n) \ 01504 { __name##Alloc().deallocate(__p, __n); } 01505 __ROPE_DEFINE_ALLOCS(_Alloc) 01506 #undef __ROPE_DEFINE_ALLOC 01507 01508 protected: 01509 _Rope_base& 01510 operator=(const _Rope_base&); 01511 01512 _Rope_base(const _Rope_base&); 01513 }; 01514 01515 /** 01516 * This is an SGI extension. 01517 * @ingroup SGIextensions 01518 * @doctodo 01519 */ 01520 template <class _CharT, class _Alloc> 01521 class rope : public _Rope_base<_CharT, _Alloc> 01522 { 01523 public: 01524 typedef _CharT value_type; 01525 typedef ptrdiff_t difference_type; 01526 typedef size_t size_type; 01527 typedef _CharT const_reference; 01528 typedef const _CharT* const_pointer; 01529 typedef _Rope_iterator<_CharT, _Alloc> iterator; 01530 typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator; 01531 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference; 01532 typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer; 01533 01534 friend class _Rope_iterator<_CharT, _Alloc>; 01535 friend class _Rope_const_iterator<_CharT, _Alloc>; 01536 friend struct _Rope_RopeRep<_CharT, _Alloc>; 01537 friend class _Rope_iterator_base<_CharT, _Alloc>; 01538 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>; 01539 friend class _Rope_char_ref_proxy<_CharT, _Alloc>; 01540 friend struct _Rope_RopeSubstring<_CharT, _Alloc>; 01541 01542 protected: 01543 typedef _Rope_base<_CharT, _Alloc> _Base; 01544 typedef typename _Base::allocator_type allocator_type; 01545 using _Base::_M_tree_ptr; 01546 using _Base::get_allocator; 01547 using _Base::_M_get_allocator; 01548 typedef __GC_CONST _CharT* _Cstrptr; 01549 01550 static _CharT _S_empty_c_str[1]; 01551 01552 static bool 01553 _S_is0(_CharT __c) 01554 { return __c == _S_eos((_CharT*)0); } 01555 01556 enum { _S_copy_max = 23 }; 01557 // For strings shorter than _S_copy_max, we copy to 01558 // concatenate. 01559 01560 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep; 01561 typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation; 01562 typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf; 01563 typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction; 01564 typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring; 01565 01566 // Retrieve a character at the indicated position. 01567 static _CharT _S_fetch(_RopeRep* __r, size_type __pos); 01568 01569 #ifndef __GC 01570 // Obtain a pointer to the character at the indicated position. 01571 // The pointer can be used to change the character. 01572 // If such a pointer cannot be produced, as is frequently the 01573 // case, 0 is returned instead. 01574 // (Returns nonzero only if all nodes in the path have a refcount 01575 // of 1.) 01576 static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos); 01577 #endif 01578 01579 static bool 01580 _S_apply_to_pieces(// should be template parameter 01581 _Rope_char_consumer<_CharT>& __c, 01582 const _RopeRep* __r, 01583 size_t __begin, size_t __end); 01584 // begin and end are assumed to be in range. 01585 01586 #ifndef __GC 01587 static void 01588 _S_unref(_RopeRep* __t) 01589 { _RopeRep::_S_unref(__t); } 01590 01591 static void 01592 _S_ref(_RopeRep* __t) 01593 { _RopeRep::_S_ref(__t); } 01594 01595 #else /* __GC */ 01596 static void _S_unref(_RopeRep*) { } 01597 static void _S_ref(_RopeRep*) { } 01598 #endif 01599 01600 #ifdef __GC 01601 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr; 01602 #else 01603 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr; 01604 #endif 01605 01606 // _Result is counted in refcount. 01607 static _RopeRep* _S_substring(_RopeRep* __base, 01608 size_t __start, size_t __endp1); 01609 01610 static _RopeRep* _S_concat_char_iter(_RopeRep* __r, 01611 const _CharT* __iter, size_t __slen); 01612 // Concatenate rope and char ptr, copying __s. 01613 // Should really take an arbitrary iterator. 01614 // Result is counted in refcount. 01615 static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r, 01616 const _CharT* __iter, 01617 size_t __slen) 01618 // As above, but one reference to __r is about to be 01619 // destroyed. Thus the pieces may be recycled if all 01620 // relevant reference counts are 1. 01621 #ifdef __GC 01622 // We can't really do anything since refcounts are unavailable. 01623 { return _S_concat_char_iter(__r, __iter, __slen); } 01624 #else 01625 ; 01626 #endif 01627 01628 static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right); 01629 // General concatenation on _RopeRep. _Result 01630 // has refcount of 1. Adjusts argument refcounts. 01631 01632 public: 01633 void 01634 apply_to_pieces(size_t __begin, size_t __end, 01635 _Rope_char_consumer<_CharT>& __c) const 01636 { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); } 01637 01638 protected: 01639 01640 static size_t 01641 _S_rounded_up_size(size_t __n) 01642 { return _RopeLeaf::_S_rounded_up_size(__n); } 01643 01644 static size_t 01645 _S_allocated_capacity(size_t __n) 01646 { 01647 if (_S_is_basic_char_type((_CharT*)0)) 01648 return _S_rounded_up_size(__n) - 1; 01649 else 01650 return _S_rounded_up_size(__n); 01651 01652 } 01653 01654 // Allocate and construct a RopeLeaf using the supplied allocator 01655 // Takes ownership of s instead of copying. 01656 static _RopeLeaf* 01657 _S_new_RopeLeaf(__GC_CONST _CharT *__s, 01658 size_t __size, allocator_type& __a) 01659 { 01660 _RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1); 01661 return new(__space) _RopeLeaf(__s, __size, __a); 01662 } 01663 01664 static _RopeConcatenation* 01665 _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right, 01666 allocator_type& __a) 01667 { 01668 _RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1); 01669 return new(__space) _RopeConcatenation(__left, __right, __a); 01670 } 01671 01672 static _RopeFunction* 01673 _S_new_RopeFunction(char_producer<_CharT>* __f, 01674 size_t __size, bool __d, allocator_type& __a) 01675 { 01676 _RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1); 01677 return new(__space) _RopeFunction(__f, __size, __d, __a); 01678 } 01679 01680 static _RopeSubstring* 01681 _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s, 01682 size_t __l, allocator_type& __a) 01683 { 01684 _RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1); 01685 return new(__space) _RopeSubstring(__b, __s, __l, __a); 01686 } 01687 01688 static _RopeLeaf* 01689 _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s, 01690 size_t __size, allocator_type& __a) 01691 #define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \ 01692 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a) 01693 { 01694 if (0 == __size) 01695 return 0; 01696 _CharT* __buf = __a.allocate(_S_rounded_up_size(__size)); 01697 01698 __uninitialized_copy_n_a(__s, __size, __buf, __a); 01699 _S_cond_store_eos(__buf[__size]); 01700 __try 01701 { return _S_new_RopeLeaf(__buf, __size, __a); } 01702 __catch(...) 01703 { 01704 _RopeRep::__STL_FREE_STRING(__buf, __size, __a); 01705 __throw_exception_again; 01706 } 01707 } 01708 01709 // Concatenation of nonempty strings. 01710 // Always builds a concatenation node. 01711 // Rebalances if the result is too deep. 01712 // Result has refcount 1. 01713 // Does not increment left and right ref counts even though 01714 // they are referenced. 01715 static _RopeRep* 01716 _S_tree_concat(_RopeRep* __left, _RopeRep* __right); 01717 01718 // Concatenation helper functions 01719 static _RopeLeaf* 01720 _S_leaf_concat_char_iter(_RopeLeaf* __r, 01721 const _CharT* __iter, size_t __slen); 01722 // Concatenate by copying leaf. 01723 // should take an arbitrary iterator 01724 // result has refcount 1. 01725 #ifndef __GC 01726 static _RopeLeaf* 01727 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r, 01728 const _CharT* __iter, size_t __slen); 01729 // A version that potentially clobbers __r if __r->_M_ref_count == 1. 01730 #endif 01731 01732 private: 01733 01734 static size_t _S_char_ptr_len(const _CharT* __s); 01735 // slightly generalized strlen 01736 01737 rope(_RopeRep* __t, const allocator_type& __a = allocator_type()) 01738 : _Base(__t, __a) { } 01739 01740 01741 // Copy __r to the _CharT buffer. 01742 // Returns __buffer + __r->_M_size. 01743 // Assumes that buffer is uninitialized. 01744 static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer); 01745 01746 // Again, with explicit starting position and length. 01747 // Assumes that buffer is uninitialized. 01748 static _CharT* _S_flatten(_RopeRep* __r, 01749 size_t __start, size_t __len, 01750 _CharT* __buffer); 01751 01752 static const unsigned long 01753 _S_min_len[__detail::_S_max_rope_depth + 1]; 01754 01755 static bool 01756 _S_is_balanced(_RopeRep* __r) 01757 { return (__r->_M_size >= _S_min_len[__r->_M_depth]); } 01758 01759 static bool 01760 _S_is_almost_balanced(_RopeRep* __r) 01761 { return (__r->_M_depth == 0 01762 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); } 01763 01764 static bool 01765 _S_is_roughly_balanced(_RopeRep* __r) 01766 { return (__r->_M_depth <= 1 01767 || __r->_M_size >= _S_min_len[__r->_M_depth - 2]); } 01768 01769 // Assumes the result is not empty. 01770 static _RopeRep* 01771 _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right) 01772 { 01773 _RopeRep* __result = _S_concat(__left, __right); 01774 if (_S_is_balanced(__result)) 01775 __result->_M_is_balanced = true; 01776 return __result; 01777 } 01778 01779 // The basic rebalancing operation. Logically copies the 01780 // rope. The result has refcount of 1. The client will 01781 // usually decrement the reference count of __r. 01782 // The result is within height 2 of balanced by the above 01783 // definition. 01784 static _RopeRep* _S_balance(_RopeRep* __r); 01785 01786 // Add all unbalanced subtrees to the forest of balanced trees. 01787 // Used only by balance. 01788 static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest); 01789 01790 // Add __r to forest, assuming __r is already balanced. 01791 static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest); 01792 01793 // Print to stdout, exposing structure 01794 static void _S_dump(_RopeRep* __r, int __indent = 0); 01795 01796 // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp. 01797 static int _S_compare(const _RopeRep* __x, const _RopeRep* __y); 01798 01799 public: 01800 bool 01801 empty() const 01802 { return 0 == this->_M_tree_ptr; } 01803 01804 // Comparison member function. This is public only for those 01805 // clients that need a ternary comparison. Others 01806 // should use the comparison operators below. 01807 int 01808 compare(const rope& __y) const 01809 { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); } 01810 01811 rope(const _CharT* __s, const allocator_type& __a = allocator_type()) 01812 : _Base(__a) 01813 { 01814 this->_M_tree_ptr = 01815 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s), 01816 _M_get_allocator()); 01817 } 01818 01819 rope(const _CharT* __s, size_t __len, 01820 const allocator_type& __a = allocator_type()) 01821 : _Base(__a) 01822 { 01823 this->_M_tree_ptr = 01824 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, _M_get_allocator()); 01825 } 01826 01827 // Should perhaps be templatized with respect to the iterator type 01828 // and use Sequence_buffer. (It should perhaps use sequence_buffer 01829 // even now.) 01830 rope(const _CharT* __s, const _CharT* __e, 01831 const allocator_type& __a = allocator_type()) 01832 : _Base(__a) 01833 { 01834 this->_M_tree_ptr = 01835 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, _M_get_allocator()); 01836 } 01837 01838 rope(const const_iterator& __s, const const_iterator& __e, 01839 const allocator_type& __a = allocator_type()) 01840 : _Base(_S_substring(__s._M_root, __s._M_current_pos, 01841 __e._M_current_pos), __a) 01842 { } 01843 01844 rope(const iterator& __s, const iterator& __e, 01845 const allocator_type& __a = allocator_type()) 01846 : _Base(_S_substring(__s._M_root, __s._M_current_pos, 01847 __e._M_current_pos), __a) 01848 { } 01849 01850 rope(_CharT __c, const allocator_type& __a = allocator_type()) 01851 : _Base(__a) 01852 { 01853 _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1)); 01854 01855 _M_get_allocator().construct(__buf, __c); 01856 __try 01857 { 01858 this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1, 01859 _M_get_allocator()); 01860 } 01861 __catch(...) 01862 { 01863 _RopeRep::__STL_FREE_STRING(__buf, 1, _M_get_allocator()); 01864 __throw_exception_again; 01865 } 01866 } 01867 01868 rope(size_t __n, _CharT __c, 01869 const allocator_type& __a = allocator_type()); 01870 01871 rope(const allocator_type& __a = allocator_type()) 01872 : _Base(0, __a) { } 01873 01874 // Construct a rope from a function that can compute its members 01875 rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn, 01876 const allocator_type& __a = allocator_type()) 01877 : _Base(__a) 01878 { 01879 this->_M_tree_ptr = (0 == __len) 01880 ? 0 01881 : _S_new_RopeFunction(__fn, __len, __delete_fn, _M_get_allocator()); 01882 } 01883 01884 rope(const rope& __x, const allocator_type& __a = allocator_type()) 01885 : _Base(__x._M_tree_ptr, __a) 01886 { _S_ref(this->_M_tree_ptr); } 01887 01888 ~rope() throw() 01889 { _S_unref(this->_M_tree_ptr); } 01890 01891 rope& 01892 operator=(const rope& __x) 01893 { 01894 _RopeRep* __old = this->_M_tree_ptr; 01895 this->_M_tree_ptr = __x._M_tree_ptr; 01896 _S_ref(this->_M_tree_ptr); 01897 _S_unref(__old); 01898 return *this; 01899 } 01900 01901 void 01902 clear() 01903 { 01904 _S_unref(this->_M_tree_ptr); 01905 this->_M_tree_ptr = 0; 01906 } 01907 01908 void 01909 push_back(_CharT __x) 01910 { 01911 _RopeRep* __old = this->_M_tree_ptr; 01912 this->_M_tree_ptr 01913 = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1); 01914 _S_unref(__old); 01915 } 01916 01917 void 01918 pop_back() 01919 { 01920 _RopeRep* __old = this->_M_tree_ptr; 01921 this->_M_tree_ptr = _S_substring(this->_M_tree_ptr, 01922 0, this->_M_tree_ptr->_M_size - 1); 01923 _S_unref(__old); 01924 } 01925 01926 _CharT 01927 back() const 01928 { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); } 01929 01930 void 01931 push_front(_CharT __x) 01932 { 01933 _RopeRep* __old = this->_M_tree_ptr; 01934 _RopeRep* __left = 01935 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator()); 01936 __try 01937 { 01938 this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr); 01939 _S_unref(__old); 01940 _S_unref(__left); 01941 } 01942 __catch(...) 01943 { 01944 _S_unref(__left); 01945 __throw_exception_again; 01946 } 01947 } 01948 01949 void 01950 pop_front() 01951 { 01952 _RopeRep* __old = this->_M_tree_ptr; 01953 this->_M_tree_ptr 01954 = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size); 01955 _S_unref(__old); 01956 } 01957 01958 _CharT 01959 front() const 01960 { return _S_fetch(this->_M_tree_ptr, 0); } 01961 01962 void 01963 balance() 01964 { 01965 _RopeRep* __old = this->_M_tree_ptr; 01966 this->_M_tree_ptr = _S_balance(this->_M_tree_ptr); 01967 _S_unref(__old); 01968 } 01969 01970 void 01971 copy(_CharT* __buffer) const 01972 { 01973 _Destroy_const(__buffer, __buffer + size(), _M_get_allocator()); 01974 _S_flatten(this->_M_tree_ptr, __buffer); 01975 } 01976 01977 // This is the copy function from the standard, but 01978 // with the arguments reordered to make it consistent with the 01979 // rest of the interface. 01980 // Note that this guaranteed not to compile if the draft standard 01981 // order is assumed. 01982 size_type 01983 copy(size_type __pos, size_type __n, _CharT* __buffer) const 01984 { 01985 size_t __size = size(); 01986 size_t __len = (__pos + __n > __size? __size - __pos : __n); 01987 01988 _Destroy_const(__buffer, __buffer + __len, _M_get_allocator()); 01989 _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer); 01990 return __len; 01991 } 01992 01993 // Print to stdout, exposing structure. May be useful for 01994 // performance debugging. 01995 void 01996 dump() 01997 { _S_dump(this->_M_tree_ptr); } 01998 01999 // Convert to 0 terminated string in new allocated memory. 02000 // Embedded 0s in the input do not terminate the copy. 02001 const _CharT* c_str() const; 02002 02003 // As above, but also use the flattened representation as 02004 // the new rope representation. 02005 const _CharT* replace_with_c_str(); 02006 02007 // Reclaim memory for the c_str generated flattened string. 02008 // Intentionally undocumented, since it's hard to say when this 02009 // is safe for multiple threads. 02010 void 02011 delete_c_str () 02012 { 02013 if (0 == this->_M_tree_ptr) 02014 return; 02015 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag && 02016 ((_RopeLeaf*)this->_M_tree_ptr)->_M_data == 02017 this->_M_tree_ptr->_M_c_string) 02018 { 02019 // Representation shared 02020 return; 02021 } 02022 #ifndef __GC 02023 this->_M_tree_ptr->_M_free_c_string(); 02024 #endif 02025 this->_M_tree_ptr->_M_c_string = 0; 02026 } 02027 02028 _CharT 02029 operator[] (size_type __pos) const 02030 { return _S_fetch(this->_M_tree_ptr, __pos); } 02031 02032 _CharT 02033 at(size_type __pos) const 02034 { 02035 // if (__pos >= size()) throw out_of_range; // XXX 02036 return (*this)[__pos]; 02037 } 02038 02039 const_iterator 02040 begin() const 02041 { return(const_iterator(this->_M_tree_ptr, 0)); } 02042 02043 // An easy way to get a const iterator from a non-const container. 02044 const_iterator 02045 const_begin() const 02046 { return(const_iterator(this->_M_tree_ptr, 0)); } 02047 02048 const_iterator 02049 end() const 02050 { return(const_iterator(this->_M_tree_ptr, size())); } 02051 02052 const_iterator 02053 const_end() const 02054 { return(const_iterator(this->_M_tree_ptr, size())); } 02055 02056 size_type 02057 size() const 02058 { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); } 02059 02060 size_type 02061 length() const 02062 { return size(); } 02063 02064 size_type 02065 max_size() const 02066 { 02067 return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1; 02068 // Guarantees that the result can be sufficiently 02069 // balanced. Longer ropes will probably still work, 02070 // but it's harder to make guarantees. 02071 } 02072 02073 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 02074 02075 const_reverse_iterator 02076 rbegin() const 02077 { return const_reverse_iterator(end()); } 02078 02079 const_reverse_iterator 02080 const_rbegin() const 02081 { return const_reverse_iterator(end()); } 02082 02083 const_reverse_iterator 02084 rend() const 02085 { return const_reverse_iterator(begin()); } 02086 02087 const_reverse_iterator 02088 const_rend() const 02089 { return const_reverse_iterator(begin()); } 02090 02091 template<class _CharT2, class _Alloc2> 02092 friend rope<_CharT2, _Alloc2> 02093 operator+(const rope<_CharT2, _Alloc2>& __left, 02094 const rope<_CharT2, _Alloc2>& __right); 02095 02096 template<class _CharT2, class _Alloc2> 02097 friend rope<_CharT2, _Alloc2> 02098 operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right); 02099 02100 template<class _CharT2, class _Alloc2> 02101 friend rope<_CharT2, _Alloc2> 02102 operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right); 02103 02104 // The symmetric cases are intentionally omitted, since they're 02105 // presumed to be less common, and we don't handle them as well. 02106 02107 // The following should really be templatized. The first 02108 // argument should be an input iterator or forward iterator with 02109 // value_type _CharT. 02110 rope& 02111 append(const _CharT* __iter, size_t __n) 02112 { 02113 _RopeRep* __result = 02114 _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n); 02115 _S_unref(this->_M_tree_ptr); 02116 this->_M_tree_ptr = __result; 02117 return *this; 02118 } 02119 02120 rope& 02121 append(const _CharT* __c_string) 02122 { 02123 size_t __len = _S_char_ptr_len(__c_string); 02124 append(__c_string, __len); 02125 return(*this); 02126 } 02127 02128 rope& 02129 append(const _CharT* __s, const _CharT* __e) 02130 { 02131 _RopeRep* __result = 02132 _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s); 02133 _S_unref(this->_M_tree_ptr); 02134 this->_M_tree_ptr = __result; 02135 return *this; 02136 } 02137 02138 rope& 02139 append(const_iterator __s, const_iterator __e) 02140 { 02141 _Self_destruct_ptr __appendee(_S_substring(__s._M_root, 02142 __s._M_current_pos, 02143 __e._M_current_pos)); 02144 _RopeRep* __result = _S_concat(this->_M_tree_ptr, 02145 (_RopeRep*)__appendee); 02146 _S_unref(this->_M_tree_ptr); 02147 this->_M_tree_ptr = __result; 02148 return *this; 02149 } 02150 02151 rope& 02152 append(_CharT __c) 02153 { 02154 _RopeRep* __result = 02155 _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1); 02156 _S_unref(this->_M_tree_ptr); 02157 this->_M_tree_ptr = __result; 02158 return *this; 02159 } 02160 02161 rope& 02162 append() 02163 { return append(_CharT()); } // XXX why? 02164 02165 rope& 02166 append(const rope& __y) 02167 { 02168 _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr); 02169 _S_unref(this->_M_tree_ptr); 02170 this->_M_tree_ptr = __result; 02171 return *this; 02172 } 02173 02174 rope& 02175 append(size_t __n, _CharT __c) 02176 { 02177 rope<_CharT,_Alloc> __last(__n, __c); 02178 return append(__last); 02179 } 02180 02181 void 02182 swap(rope& __b) 02183 { 02184 _RopeRep* __tmp = this->_M_tree_ptr; 02185 this->_M_tree_ptr = __b._M_tree_ptr; 02186 __b._M_tree_ptr = __tmp; 02187 } 02188 02189 protected: 02190 // Result is included in refcount. 02191 static _RopeRep* 02192 replace(_RopeRep* __old, size_t __pos1, 02193 size_t __pos2, _RopeRep* __r) 02194 { 02195 if (0 == __old) 02196 { 02197 _S_ref(__r); 02198 return __r; 02199 } 02200 _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1)); 02201 _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size)); 02202 _RopeRep* __result; 02203 02204 if (0 == __r) 02205 __result = _S_concat(__left, __right); 02206 else 02207 { 02208 _Self_destruct_ptr __left_result(_S_concat(__left, __r)); 02209 __result = _S_concat(__left_result, __right); 02210 } 02211 return __result; 02212 } 02213 02214 public: 02215 void 02216 insert(size_t __p, const rope& __r) 02217 { 02218 _RopeRep* __result = 02219 replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr); 02220 _S_unref(this->_M_tree_ptr); 02221 this->_M_tree_ptr = __result; 02222 } 02223 02224 void 02225 insert(size_t __p, size_t __n, _CharT __c) 02226 { 02227 rope<_CharT,_Alloc> __r(__n,__c); 02228 insert(__p, __r); 02229 } 02230 02231 void 02232 insert(size_t __p, const _CharT* __i, size_t __n) 02233 { 02234 _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p)); 02235 _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr, 02236 __p, size())); 02237 _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n)); 02238 // _S_ destr_concat_char_iter should be safe here. 02239 // But as it stands it's probably not a win, since __left 02240 // is likely to have additional references. 02241 _RopeRep* __result = _S_concat(__left_result, __right); 02242 _S_unref(this->_M_tree_ptr); 02243 this->_M_tree_ptr = __result; 02244 } 02245 02246 void 02247 insert(size_t __p, const _CharT* __c_string) 02248 { insert(__p, __c_string, _S_char_ptr_len(__c_string)); } 02249 02250 void 02251 insert(size_t __p, _CharT __c) 02252 { insert(__p, &__c, 1); } 02253 02254 void 02255 insert(size_t __p) 02256 { 02257 _CharT __c = _CharT(); 02258 insert(__p, &__c, 1); 02259 } 02260 02261 void 02262 insert(size_t __p, const _CharT* __i, const _CharT* __j) 02263 { 02264 rope __r(__i, __j); 02265 insert(__p, __r); 02266 } 02267 02268 void 02269 insert(size_t __p, const const_iterator& __i, 02270 const const_iterator& __j) 02271 { 02272 rope __r(__i, __j); 02273 insert(__p, __r); 02274 } 02275 02276 void 02277 insert(size_t __p, const iterator& __i, 02278 const iterator& __j) 02279 { 02280 rope __r(__i, __j); 02281 insert(__p, __r); 02282 } 02283 02284 // (position, length) versions of replace operations: 02285 02286 void 02287 replace(size_t __p, size_t __n, const rope& __r) 02288 { 02289 _RopeRep* __result = 02290 replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr); 02291 _S_unref(this->_M_tree_ptr); 02292 this->_M_tree_ptr = __result; 02293 } 02294 02295 void 02296 replace(size_t __p, size_t __n, 02297 const _CharT* __i, size_t __i_len) 02298 { 02299 rope __r(__i, __i_len); 02300 replace(__p, __n, __r); 02301 } 02302 02303 void 02304 replace(size_t __p, size_t __n, _CharT __c) 02305 { 02306 rope __r(__c); 02307 replace(__p, __n, __r); 02308 } 02309 02310 void 02311 replace(size_t __p, size_t __n, const _CharT* __c_string) 02312 { 02313 rope __r(__c_string); 02314 replace(__p, __n, __r); 02315 } 02316 02317 void 02318 replace(size_t __p, size_t __n, 02319 const _CharT* __i, const _CharT* __j) 02320 { 02321 rope __r(__i, __j); 02322 replace(__p, __n, __r); 02323 } 02324 02325 void 02326 replace(size_t __p, size_t __n, 02327 const const_iterator& __i, const const_iterator& __j) 02328 { 02329 rope __r(__i, __j); 02330 replace(__p, __n, __r); 02331 } 02332 02333 void 02334 replace(size_t __p, size_t __n, 02335 const iterator& __i, const iterator& __j) 02336 { 02337 rope __r(__i, __j); 02338 replace(__p, __n, __r); 02339 } 02340 02341 // Single character variants: 02342 void 02343 replace(size_t __p, _CharT __c) 02344 { 02345 iterator __i(this, __p); 02346 *__i = __c; 02347 } 02348 02349 void 02350 replace(size_t __p, const rope& __r) 02351 { replace(__p, 1, __r); } 02352 02353 void 02354 replace(size_t __p, const _CharT* __i, size_t __i_len) 02355 { replace(__p, 1, __i, __i_len); } 02356 02357 void 02358 replace(size_t __p, const _CharT* __c_string) 02359 { replace(__p, 1, __c_string); } 02360 02361 void 02362 replace(size_t __p, const _CharT* __i, const _CharT* __j) 02363 { replace(__p, 1, __i, __j); } 02364 02365 void 02366 replace(size_t __p, const const_iterator& __i, 02367 const const_iterator& __j) 02368 { replace(__p, 1, __i, __j); } 02369 02370 void 02371 replace(size_t __p, const iterator& __i, 02372 const iterator& __j) 02373 { replace(__p, 1, __i, __j); } 02374 02375 // Erase, (position, size) variant. 02376 void 02377 erase(size_t __p, size_t __n) 02378 { 02379 _RopeRep* __result = replace(this->_M_tree_ptr, __p, 02380 __p + __n, 0); 02381 _S_unref(this->_M_tree_ptr); 02382 this->_M_tree_ptr = __result; 02383 } 02384 02385 // Erase, single character 02386 void 02387 erase(size_t __p) 02388 { erase(__p, __p + 1); } 02389 02390 // Insert, iterator variants. 02391 iterator 02392 insert(const iterator& __p, const rope& __r) 02393 { 02394 insert(__p.index(), __r); 02395 return __p; 02396 } 02397 02398 iterator 02399 insert(const iterator& __p, size_t __n, _CharT __c) 02400 { 02401 insert(__p.index(), __n, __c); 02402 return __p; 02403 } 02404 02405 iterator insert(const iterator& __p, _CharT __c) 02406 { 02407 insert(__p.index(), __c); 02408 return __p; 02409 } 02410 02411 iterator 02412 insert(const iterator& __p ) 02413 { 02414 insert(__p.index()); 02415 return __p; 02416 } 02417 02418 iterator 02419 insert(const iterator& __p, const _CharT* c_string) 02420 { 02421 insert(__p.index(), c_string); 02422 return __p; 02423 } 02424 02425 iterator 02426 insert(const iterator& __p, const _CharT* __i, size_t __n) 02427 { 02428 insert(__p.index(), __i, __n); 02429 return __p; 02430 } 02431 02432 iterator 02433 insert(const iterator& __p, const _CharT* __i, 02434 const _CharT* __j) 02435 { 02436 insert(__p.index(), __i, __j); 02437 return __p; 02438 } 02439 02440 iterator 02441 insert(const iterator& __p, 02442 const const_iterator& __i, const const_iterator& __j) 02443 { 02444 insert(__p.index(), __i, __j); 02445 return __p; 02446 } 02447 02448 iterator 02449 insert(const iterator& __p, 02450 const iterator& __i, const iterator& __j) 02451 { 02452 insert(__p.index(), __i, __j); 02453 return __p; 02454 } 02455 02456 // Replace, range variants. 02457 void 02458 replace(const iterator& __p, const iterator& __q, const rope& __r) 02459 { replace(__p.index(), __q.index() - __p.index(), __r); } 02460 02461 void 02462 replace(const iterator& __p, const iterator& __q, _CharT __c) 02463 { replace(__p.index(), __q.index() - __p.index(), __c); } 02464 02465 void 02466 replace(const iterator& __p, const iterator& __q, 02467 const _CharT* __c_string) 02468 { replace(__p.index(), __q.index() - __p.index(), __c_string); } 02469 02470 void 02471 replace(const iterator& __p, const iterator& __q, 02472 const _CharT* __i, size_t __n) 02473 { replace(__p.index(), __q.index() - __p.index(), __i, __n); } 02474 02475 void 02476 replace(const iterator& __p, const iterator& __q, 02477 const _CharT* __i, const _CharT* __j) 02478 { replace(__p.index(), __q.index() - __p.index(), __i, __j); } 02479 02480 void 02481 replace(const iterator& __p, const iterator& __q, 02482 const const_iterator& __i, const const_iterator& __j) 02483 { replace(__p.index(), __q.index() - __p.index(), __i, __j); } 02484 02485 void 02486 replace(const iterator& __p, const iterator& __q, 02487 const iterator& __i, const iterator& __j) 02488 { replace(__p.index(), __q.index() - __p.index(), __i, __j); } 02489 02490 // Replace, iterator variants. 02491 void 02492 replace(const iterator& __p, const rope& __r) 02493 { replace(__p.index(), __r); } 02494 02495 void 02496 replace(const iterator& __p, _CharT __c) 02497 { replace(__p.index(), __c); } 02498 02499 void 02500 replace(const iterator& __p, const _CharT* __c_string) 02501 { replace(__p.index(), __c_string); } 02502 02503 void 02504 replace(const iterator& __p, const _CharT* __i, size_t __n) 02505 { replace(__p.index(), __i, __n); } 02506 02507 void 02508 replace(const iterator& __p, const _CharT* __i, const _CharT* __j) 02509 { replace(__p.index(), __i, __j); } 02510 02511 void 02512 replace(const iterator& __p, const_iterator __i, const_iterator __j) 02513 { replace(__p.index(), __i, __j); } 02514 02515 void 02516 replace(const iterator& __p, iterator __i, iterator __j) 02517 { replace(__p.index(), __i, __j); } 02518 02519 // Iterator and range variants of erase 02520 iterator 02521 erase(const iterator& __p, const iterator& __q) 02522 { 02523 size_t __p_index = __p.index(); 02524 erase(__p_index, __q.index() - __p_index); 02525 return iterator(this, __p_index); 02526 } 02527 02528 iterator 02529 erase(const iterator& __p) 02530 { 02531 size_t __p_index = __p.index(); 02532 erase(__p_index, 1); 02533 return iterator(this, __p_index); 02534 } 02535 02536 rope 02537 substr(size_t __start, size_t __len = 1) const 02538 { 02539 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 02540 __start, 02541 __start + __len)); 02542 } 02543 02544 rope 02545 substr(iterator __start, iterator __end) const 02546 { 02547 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 02548 __start.index(), 02549 __end.index())); 02550 } 02551 02552 rope 02553 substr(iterator __start) const 02554 { 02555 size_t __pos = __start.index(); 02556 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 02557 __pos, __pos + 1)); 02558 } 02559 02560 rope 02561 substr(const_iterator __start, const_iterator __end) const 02562 { 02563 // This might eventually take advantage of the cache in the 02564 // iterator. 02565 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 02566 __start.index(), 02567 __end.index())); 02568 } 02569 02570 rope<_CharT, _Alloc> 02571 substr(const_iterator __start) 02572 { 02573 size_t __pos = __start.index(); 02574 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 02575 __pos, __pos + 1)); 02576 } 02577 02578 static const size_type npos; 02579 02580 size_type find(_CharT __c, size_type __pos = 0) const; 02581 02582 size_type 02583 find(const _CharT* __s, size_type __pos = 0) const 02584 { 02585 size_type __result_pos; 02586 const_iterator __result = 02587 std::search(const_begin() + __pos, const_end(), 02588 __s, __s + _S_char_ptr_len(__s)); 02589 __result_pos = __result.index(); 02590 #ifndef __STL_OLD_ROPE_SEMANTICS 02591 if (__result_pos == size()) 02592 __result_pos = npos; 02593 #endif 02594 return __result_pos; 02595 } 02596 02597 iterator 02598 mutable_begin() 02599 { return(iterator(this, 0)); } 02600 02601 iterator 02602 mutable_end() 02603 { return(iterator(this, size())); } 02604 02605 typedef std::reverse_iterator<iterator> reverse_iterator; 02606 02607 reverse_iterator 02608 mutable_rbegin() 02609 { return reverse_iterator(mutable_end()); } 02610 02611 reverse_iterator 02612 mutable_rend() 02613 { return reverse_iterator(mutable_begin()); } 02614 02615 reference 02616 mutable_reference_at(size_type __pos) 02617 { return reference(this, __pos); } 02618 02619 #ifdef __STD_STUFF 02620 reference 02621 operator[] (size_type __pos) 02622 { return _char_ref_proxy(this, __pos); } 02623 02624 reference 02625 at(size_type __pos) 02626 { 02627 // if (__pos >= size()) throw out_of_range; // XXX 02628 return (*this)[__pos]; 02629 } 02630 02631 void resize(size_type __n, _CharT __c) { } 02632 void resize(size_type __n) { } 02633 void reserve(size_type __res_arg = 0) { } 02634 02635 size_type 02636 capacity() const 02637 { return max_size(); } 02638 02639 // Stuff below this line is dangerous because it's error prone. 02640 // I would really like to get rid of it. 02641 // copy function with funny arg ordering. 02642 size_type 02643 copy(_CharT* __buffer, size_type __n, 02644 size_type __pos = 0) const 02645 { return copy(__pos, __n, __buffer); } 02646 02647 iterator 02648 end() 02649 { return mutable_end(); } 02650 02651 iterator 02652 begin() 02653 { return mutable_begin(); } 02654 02655 reverse_iterator 02656 rend() 02657 { return mutable_rend(); } 02658 02659 reverse_iterator 02660 rbegin() 02661 { return mutable_rbegin(); } 02662 02663 #else 02664 const_iterator 02665 end() 02666 { return const_end(); } 02667 02668 const_iterator 02669 begin() 02670 { return const_begin(); } 02671 02672 const_reverse_iterator 02673 rend() 02674 { return const_rend(); } 02675 02676 const_reverse_iterator 02677 rbegin() 02678 { return const_rbegin(); } 02679 02680 #endif 02681 }; 02682 02683 template <class _CharT, class _Alloc> 02684 const typename rope<_CharT, _Alloc>::size_type 02685 rope<_CharT, _Alloc>::npos = (size_type)(-1); 02686 02687 template <class _CharT, class _Alloc> 02688 inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02689 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02690 { return (__x._M_current_pos == __y._M_current_pos 02691 && __x._M_root == __y._M_root); } 02692 02693 template <class _CharT, class _Alloc> 02694 inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02695 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02696 { return (__x._M_current_pos < __y._M_current_pos); } 02697 02698 template <class _CharT, class _Alloc> 02699 inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02700 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02701 { return !(__x == __y); } 02702 02703 template <class _CharT, class _Alloc> 02704 inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02705 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02706 { return __y < __x; } 02707 02708 template <class _CharT, class _Alloc> 02709 inline bool 02710 operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02711 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02712 { return !(__y < __x); } 02713 02714 template <class _CharT, class _Alloc> 02715 inline bool 02716 operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02717 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02718 { return !(__x < __y); } 02719 02720 template <class _CharT, class _Alloc> 02721 inline ptrdiff_t 02722 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02723 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02724 { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; } 02725 02726 template <class _CharT, class _Alloc> 02727 inline _Rope_const_iterator<_CharT, _Alloc> 02728 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) 02729 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, 02730 __x._M_current_pos - __n); } 02731 02732 template <class _CharT, class _Alloc> 02733 inline _Rope_const_iterator<_CharT, _Alloc> 02734 operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) 02735 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, 02736 __x._M_current_pos + __n); } 02737 02738 template <class _CharT, class _Alloc> 02739 inline _Rope_const_iterator<_CharT, _Alloc> 02740 operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x) 02741 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, 02742 __x._M_current_pos + __n); } 02743 02744 template <class _CharT, class _Alloc> 02745 inline bool 02746 operator==(const _Rope_iterator<_CharT, _Alloc>& __x, 02747 const _Rope_iterator<_CharT, _Alloc>& __y) 02748 {return (__x._M_current_pos == __y._M_current_pos 02749 && __x._M_root_rope == __y._M_root_rope); } 02750 02751 template <class _CharT, class _Alloc> 02752 inline bool 02753 operator<(const _Rope_iterator<_CharT, _Alloc>& __x, 02754 const _Rope_iterator<_CharT, _Alloc>& __y) 02755 { return (__x._M_current_pos < __y._M_current_pos); } 02756 02757 template <class _CharT, class _Alloc> 02758 inline bool 02759 operator!=(const _Rope_iterator<_CharT, _Alloc>& __x, 02760 const _Rope_iterator<_CharT, _Alloc>& __y) 02761 { return !(__x == __y); } 02762 02763 template <class _CharT, class _Alloc> 02764 inline bool 02765 operator>(const _Rope_iterator<_CharT, _Alloc>& __x, 02766 const _Rope_iterator<_CharT, _Alloc>& __y) 02767 { return __y < __x; } 02768 02769 template <class _CharT, class _Alloc> 02770 inline bool 02771 operator<=(const _Rope_iterator<_CharT, _Alloc>& __x, 02772 const _Rope_iterator<_CharT, _Alloc>& __y) 02773 { return !(__y < __x); } 02774 02775 template <class _CharT, class _Alloc> 02776 inline bool 02777 operator>=(const _Rope_iterator<_CharT, _Alloc>& __x, 02778 const _Rope_iterator<_CharT, _Alloc>& __y) 02779 { return !(__x < __y); } 02780 02781 template <class _CharT, class _Alloc> 02782 inline ptrdiff_t 02783 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, 02784 const _Rope_iterator<_CharT, _Alloc>& __y) 02785 { return ((ptrdiff_t)__x._M_current_pos 02786 - (ptrdiff_t)__y._M_current_pos); } 02787 02788 template <class _CharT, class _Alloc> 02789 inline _Rope_iterator<_CharT, _Alloc> 02790 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, 02791 ptrdiff_t __n) 02792 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, 02793 __x._M_current_pos - __n); } 02794 02795 template <class _CharT, class _Alloc> 02796 inline _Rope_iterator<_CharT, _Alloc> 02797 operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) 02798 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, 02799 __x._M_current_pos + __n); } 02800 02801 template <class _CharT, class _Alloc> 02802 inline _Rope_iterator<_CharT, _Alloc> 02803 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x) 02804 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, 02805 __x._M_current_pos + __n); } 02806 02807 template <class _CharT, class _Alloc> 02808 inline rope<_CharT, _Alloc> 02809 operator+(const rope<_CharT, _Alloc>& __left, 02810 const rope<_CharT, _Alloc>& __right) 02811 { 02812 // Inlining this should make it possible to keep __left and 02813 // __right in registers. 02814 typedef rope<_CharT, _Alloc> rope_type; 02815 return rope_type(rope_type::_S_concat(__left._M_tree_ptr, 02816 __right._M_tree_ptr)); 02817 } 02818 02819 template <class _CharT, class _Alloc> 02820 inline rope<_CharT, _Alloc>& 02821 operator+=(rope<_CharT, _Alloc>& __left, 02822 const rope<_CharT, _Alloc>& __right) 02823 { 02824 __left.append(__right); 02825 return __left; 02826 } 02827 02828 template <class _CharT, class _Alloc> 02829 inline rope<_CharT, _Alloc> 02830 operator+(const rope<_CharT, _Alloc>& __left, 02831 const _CharT* __right) 02832 { 02833 typedef rope<_CharT, _Alloc> rope_type; 02834 size_t __rlen = rope_type::_S_char_ptr_len(__right); 02835 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr, 02836 __right, __rlen)); 02837 } 02838 02839 template <class _CharT, class _Alloc> 02840 inline rope<_CharT, _Alloc>& 02841 operator+=(rope<_CharT, _Alloc>& __left, 02842 const _CharT* __right) 02843 { 02844 __left.append(__right); 02845 return __left; 02846 } 02847 02848 template <class _CharT, class _Alloc> 02849 inline rope<_CharT, _Alloc> 02850 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right) 02851 { 02852 typedef rope<_CharT, _Alloc> rope_type; 02853 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr, 02854 &__right, 1)); 02855 } 02856 02857 template <class _CharT, class _Alloc> 02858 inline rope<_CharT, _Alloc>& 02859 operator+=(rope<_CharT, _Alloc>& __left, _CharT __right) 02860 { 02861 __left.append(__right); 02862 return __left; 02863 } 02864 02865 template <class _CharT, class _Alloc> 02866 bool 02867 operator<(const rope<_CharT, _Alloc>& __left, 02868 const rope<_CharT, _Alloc>& __right) 02869 { return __left.compare(__right) < 0; } 02870 02871 template <class _CharT, class _Alloc> 02872 bool 02873 operator==(const rope<_CharT, _Alloc>& __left, 02874 const rope<_CharT, _Alloc>& __right) 02875 { return __left.compare(__right) == 0; } 02876 02877 template <class _CharT, class _Alloc> 02878 inline bool 02879 operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, 02880 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y) 02881 { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); } 02882 02883 template <class _CharT, class _Alloc> 02884 inline bool 02885 operator!=(const rope<_CharT, _Alloc>& __x, 02886 const rope<_CharT, _Alloc>& __y) 02887 { return !(__x == __y); } 02888 02889 template <class _CharT, class _Alloc> 02890 inline bool 02891 operator>(const rope<_CharT, _Alloc>& __x, 02892 const rope<_CharT, _Alloc>& __y) 02893 { return __y < __x; } 02894 02895 template <class _CharT, class _Alloc> 02896 inline bool 02897 operator<=(const rope<_CharT, _Alloc>& __x, 02898 const rope<_CharT, _Alloc>& __y) 02899 { return !(__y < __x); } 02900 02901 template <class _CharT, class _Alloc> 02902 inline bool 02903 operator>=(const rope<_CharT, _Alloc>& __x, 02904 const rope<_CharT, _Alloc>& __y) 02905 { return !(__x < __y); } 02906 02907 template <class _CharT, class _Alloc> 02908 inline bool 02909 operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, 02910 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y) 02911 { return !(__x == __y); } 02912 02913 template<class _CharT, class _Traits, class _Alloc> 02914 std::basic_ostream<_CharT, _Traits>& 02915 operator<<(std::basic_ostream<_CharT, _Traits>& __o, 02916 const rope<_CharT, _Alloc>& __r); 02917 02918 typedef rope<char> crope; 02919 typedef rope<wchar_t> wrope; 02920 02921 inline crope::reference 02922 __mutable_reference_at(crope& __c, size_t __i) 02923 { return __c.mutable_reference_at(__i); } 02924 02925 inline wrope::reference 02926 __mutable_reference_at(wrope& __c, size_t __i) 02927 { return __c.mutable_reference_at(__i); } 02928 02929 template <class _CharT, class _Alloc> 02930 inline void 02931 swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y) 02932 { __x.swap(__y); } 02933 02934 _GLIBCXX_END_NAMESPACE_VERSION 02935 } // namespace 02936 02937 02938 namespace std _GLIBCXX_VISIBILITY(default) 02939 { 02940 namespace tr1 02941 { 02942 _GLIBCXX_BEGIN_NAMESPACE_VERSION 02943 02944 template<> 02945 struct hash<__gnu_cxx::crope> 02946 { 02947 size_t 02948 operator()(const __gnu_cxx::crope& __str) const 02949 { 02950 size_t __size = __str.size(); 02951 if (0 == __size) 02952 return 0; 02953 return 13 * __str[0] + 5 * __str[__size - 1] + __size; 02954 } 02955 }; 02956 02957 02958 template<> 02959 struct hash<__gnu_cxx::wrope> 02960 { 02961 size_t 02962 operator()(const __gnu_cxx::wrope& __str) const 02963 { 02964 size_t __size = __str.size(); 02965 if (0 == __size) 02966 return 0; 02967 return 13 * __str[0] + 5 * __str[__size - 1] + __size; 02968 } 02969 }; 02970 02971 _GLIBCXX_END_NAMESPACE_VERSION 02972 } // namespace tr1 02973 } // namespace std 02974 02975 # include <ext/ropeimpl.h> 02976 02977 #endif