libstdc++
|
00001 // SGI's rope class -*- C++ -*- 00002 00003 // Copyright (C) 2001-2013 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 #ifdef __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 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a); 01881 } 01882 01883 rope(const rope& __x, const allocator_type& __a = allocator_type()) 01884 : _Base(__x._M_tree_ptr, __a) 01885 { _S_ref(this->_M_tree_ptr); } 01886 01887 ~rope() throw() 01888 { _S_unref(this->_M_tree_ptr); } 01889 01890 rope& 01891 operator=(const rope& __x) 01892 { 01893 _RopeRep* __old = this->_M_tree_ptr; 01894 this->_M_tree_ptr = __x._M_tree_ptr; 01895 _S_ref(this->_M_tree_ptr); 01896 _S_unref(__old); 01897 return *this; 01898 } 01899 01900 void 01901 clear() 01902 { 01903 _S_unref(this->_M_tree_ptr); 01904 this->_M_tree_ptr = 0; 01905 } 01906 01907 void 01908 push_back(_CharT __x) 01909 { 01910 _RopeRep* __old = this->_M_tree_ptr; 01911 this->_M_tree_ptr 01912 = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1); 01913 _S_unref(__old); 01914 } 01915 01916 void 01917 pop_back() 01918 { 01919 _RopeRep* __old = this->_M_tree_ptr; 01920 this->_M_tree_ptr = _S_substring(this->_M_tree_ptr, 01921 0, this->_M_tree_ptr->_M_size - 1); 01922 _S_unref(__old); 01923 } 01924 01925 _CharT 01926 back() const 01927 { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); } 01928 01929 void 01930 push_front(_CharT __x) 01931 { 01932 _RopeRep* __old = this->_M_tree_ptr; 01933 _RopeRep* __left = 01934 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator()); 01935 __try 01936 { 01937 this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr); 01938 _S_unref(__old); 01939 _S_unref(__left); 01940 } 01941 __catch(...) 01942 { 01943 _S_unref(__left); 01944 __throw_exception_again; 01945 } 01946 } 01947 01948 void 01949 pop_front() 01950 { 01951 _RopeRep* __old = this->_M_tree_ptr; 01952 this->_M_tree_ptr 01953 = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size); 01954 _S_unref(__old); 01955 } 01956 01957 _CharT 01958 front() const 01959 { return _S_fetch(this->_M_tree_ptr, 0); } 01960 01961 void 01962 balance() 01963 { 01964 _RopeRep* __old = this->_M_tree_ptr; 01965 this->_M_tree_ptr = _S_balance(this->_M_tree_ptr); 01966 _S_unref(__old); 01967 } 01968 01969 void 01970 copy(_CharT* __buffer) const 01971 { 01972 _Destroy_const(__buffer, __buffer + size(), _M_get_allocator()); 01973 _S_flatten(this->_M_tree_ptr, __buffer); 01974 } 01975 01976 // This is the copy function from the standard, but 01977 // with the arguments reordered to make it consistent with the 01978 // rest of the interface. 01979 // Note that this guaranteed not to compile if the draft standard 01980 // order is assumed. 01981 size_type 01982 copy(size_type __pos, size_type __n, _CharT* __buffer) const 01983 { 01984 size_t __size = size(); 01985 size_t __len = (__pos + __n > __size? __size - __pos : __n); 01986 01987 _Destroy_const(__buffer, __buffer + __len, _M_get_allocator()); 01988 _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer); 01989 return __len; 01990 } 01991 01992 // Print to stdout, exposing structure. May be useful for 01993 // performance debugging. 01994 void 01995 dump() 01996 { _S_dump(this->_M_tree_ptr); } 01997 01998 // Convert to 0 terminated string in new allocated memory. 01999 // Embedded 0s in the input do not terminate the copy. 02000 const _CharT* c_str() const; 02001 02002 // As above, but also use the flattened representation as 02003 // the new rope representation. 02004 const _CharT* replace_with_c_str(); 02005 02006 // Reclaim memory for the c_str generated flattened string. 02007 // Intentionally undocumented, since it's hard to say when this 02008 // is safe for multiple threads. 02009 void 02010 delete_c_str () 02011 { 02012 if (0 == this->_M_tree_ptr) 02013 return; 02014 if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag && 02015 ((_RopeLeaf*)this->_M_tree_ptr)->_M_data == 02016 this->_M_tree_ptr->_M_c_string) 02017 { 02018 // Representation shared 02019 return; 02020 } 02021 #ifndef __GC 02022 this->_M_tree_ptr->_M_free_c_string(); 02023 #endif 02024 this->_M_tree_ptr->_M_c_string = 0; 02025 } 02026 02027 _CharT 02028 operator[] (size_type __pos) const 02029 { return _S_fetch(this->_M_tree_ptr, __pos); } 02030 02031 _CharT 02032 at(size_type __pos) const 02033 { 02034 // if (__pos >= size()) throw out_of_range; // XXX 02035 return (*this)[__pos]; 02036 } 02037 02038 const_iterator 02039 begin() const 02040 { return(const_iterator(this->_M_tree_ptr, 0)); } 02041 02042 // An easy way to get a const iterator from a non-const container. 02043 const_iterator 02044 const_begin() const 02045 { return(const_iterator(this->_M_tree_ptr, 0)); } 02046 02047 const_iterator 02048 end() const 02049 { return(const_iterator(this->_M_tree_ptr, size())); } 02050 02051 const_iterator 02052 const_end() const 02053 { return(const_iterator(this->_M_tree_ptr, size())); } 02054 02055 size_type 02056 size() const 02057 { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); } 02058 02059 size_type 02060 length() const 02061 { return size(); } 02062 02063 size_type 02064 max_size() const 02065 { 02066 return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1; 02067 // Guarantees that the result can be sufficiently 02068 // balanced. Longer ropes will probably still work, 02069 // but it's harder to make guarantees. 02070 } 02071 02072 typedef std::reverse_iterator<const_iterator> const_reverse_iterator; 02073 02074 const_reverse_iterator 02075 rbegin() const 02076 { return const_reverse_iterator(end()); } 02077 02078 const_reverse_iterator 02079 const_rbegin() const 02080 { return const_reverse_iterator(end()); } 02081 02082 const_reverse_iterator 02083 rend() const 02084 { return const_reverse_iterator(begin()); } 02085 02086 const_reverse_iterator 02087 const_rend() const 02088 { return const_reverse_iterator(begin()); } 02089 02090 template<class _CharT2, class _Alloc2> 02091 friend rope<_CharT2, _Alloc2> 02092 operator+(const rope<_CharT2, _Alloc2>& __left, 02093 const rope<_CharT2, _Alloc2>& __right); 02094 02095 template<class _CharT2, class _Alloc2> 02096 friend rope<_CharT2, _Alloc2> 02097 operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right); 02098 02099 template<class _CharT2, class _Alloc2> 02100 friend rope<_CharT2, _Alloc2> 02101 operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right); 02102 02103 // The symmetric cases are intentionally omitted, since they're 02104 // presumed to be less common, and we don't handle them as well. 02105 02106 // The following should really be templatized. The first 02107 // argument should be an input iterator or forward iterator with 02108 // value_type _CharT. 02109 rope& 02110 append(const _CharT* __iter, size_t __n) 02111 { 02112 _RopeRep* __result = 02113 _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n); 02114 _S_unref(this->_M_tree_ptr); 02115 this->_M_tree_ptr = __result; 02116 return *this; 02117 } 02118 02119 rope& 02120 append(const _CharT* __c_string) 02121 { 02122 size_t __len = _S_char_ptr_len(__c_string); 02123 append(__c_string, __len); 02124 return(*this); 02125 } 02126 02127 rope& 02128 append(const _CharT* __s, const _CharT* __e) 02129 { 02130 _RopeRep* __result = 02131 _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s); 02132 _S_unref(this->_M_tree_ptr); 02133 this->_M_tree_ptr = __result; 02134 return *this; 02135 } 02136 02137 rope& 02138 append(const_iterator __s, const_iterator __e) 02139 { 02140 _Self_destruct_ptr __appendee(_S_substring(__s._M_root, 02141 __s._M_current_pos, 02142 __e._M_current_pos)); 02143 _RopeRep* __result = _S_concat(this->_M_tree_ptr, 02144 (_RopeRep*)__appendee); 02145 _S_unref(this->_M_tree_ptr); 02146 this->_M_tree_ptr = __result; 02147 return *this; 02148 } 02149 02150 rope& 02151 append(_CharT __c) 02152 { 02153 _RopeRep* __result = 02154 _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1); 02155 _S_unref(this->_M_tree_ptr); 02156 this->_M_tree_ptr = __result; 02157 return *this; 02158 } 02159 02160 rope& 02161 append() 02162 { return append(_CharT()); } // XXX why? 02163 02164 rope& 02165 append(const rope& __y) 02166 { 02167 _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr); 02168 _S_unref(this->_M_tree_ptr); 02169 this->_M_tree_ptr = __result; 02170 return *this; 02171 } 02172 02173 rope& 02174 append(size_t __n, _CharT __c) 02175 { 02176 rope<_CharT,_Alloc> __last(__n, __c); 02177 return append(__last); 02178 } 02179 02180 void 02181 swap(rope& __b) 02182 { 02183 _RopeRep* __tmp = this->_M_tree_ptr; 02184 this->_M_tree_ptr = __b._M_tree_ptr; 02185 __b._M_tree_ptr = __tmp; 02186 } 02187 02188 protected: 02189 // Result is included in refcount. 02190 static _RopeRep* 02191 replace(_RopeRep* __old, size_t __pos1, 02192 size_t __pos2, _RopeRep* __r) 02193 { 02194 if (0 == __old) 02195 { 02196 _S_ref(__r); 02197 return __r; 02198 } 02199 _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1)); 02200 _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size)); 02201 _RopeRep* __result; 02202 02203 if (0 == __r) 02204 __result = _S_concat(__left, __right); 02205 else 02206 { 02207 _Self_destruct_ptr __left_result(_S_concat(__left, __r)); 02208 __result = _S_concat(__left_result, __right); 02209 } 02210 return __result; 02211 } 02212 02213 public: 02214 void 02215 insert(size_t __p, const rope& __r) 02216 { 02217 _RopeRep* __result = 02218 replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr); 02219 _S_unref(this->_M_tree_ptr); 02220 this->_M_tree_ptr = __result; 02221 } 02222 02223 void 02224 insert(size_t __p, size_t __n, _CharT __c) 02225 { 02226 rope<_CharT,_Alloc> __r(__n,__c); 02227 insert(__p, __r); 02228 } 02229 02230 void 02231 insert(size_t __p, const _CharT* __i, size_t __n) 02232 { 02233 _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p)); 02234 _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr, 02235 __p, size())); 02236 _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n)); 02237 // _S_ destr_concat_char_iter should be safe here. 02238 // But as it stands it's probably not a win, since __left 02239 // is likely to have additional references. 02240 _RopeRep* __result = _S_concat(__left_result, __right); 02241 _S_unref(this->_M_tree_ptr); 02242 this->_M_tree_ptr = __result; 02243 } 02244 02245 void 02246 insert(size_t __p, const _CharT* __c_string) 02247 { insert(__p, __c_string, _S_char_ptr_len(__c_string)); } 02248 02249 void 02250 insert(size_t __p, _CharT __c) 02251 { insert(__p, &__c, 1); } 02252 02253 void 02254 insert(size_t __p) 02255 { 02256 _CharT __c = _CharT(); 02257 insert(__p, &__c, 1); 02258 } 02259 02260 void 02261 insert(size_t __p, const _CharT* __i, const _CharT* __j) 02262 { 02263 rope __r(__i, __j); 02264 insert(__p, __r); 02265 } 02266 02267 void 02268 insert(size_t __p, const const_iterator& __i, 02269 const const_iterator& __j) 02270 { 02271 rope __r(__i, __j); 02272 insert(__p, __r); 02273 } 02274 02275 void 02276 insert(size_t __p, const iterator& __i, 02277 const iterator& __j) 02278 { 02279 rope __r(__i, __j); 02280 insert(__p, __r); 02281 } 02282 02283 // (position, length) versions of replace operations: 02284 02285 void 02286 replace(size_t __p, size_t __n, const rope& __r) 02287 { 02288 _RopeRep* __result = 02289 replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr); 02290 _S_unref(this->_M_tree_ptr); 02291 this->_M_tree_ptr = __result; 02292 } 02293 02294 void 02295 replace(size_t __p, size_t __n, 02296 const _CharT* __i, size_t __i_len) 02297 { 02298 rope __r(__i, __i_len); 02299 replace(__p, __n, __r); 02300 } 02301 02302 void 02303 replace(size_t __p, size_t __n, _CharT __c) 02304 { 02305 rope __r(__c); 02306 replace(__p, __n, __r); 02307 } 02308 02309 void 02310 replace(size_t __p, size_t __n, const _CharT* __c_string) 02311 { 02312 rope __r(__c_string); 02313 replace(__p, __n, __r); 02314 } 02315 02316 void 02317 replace(size_t __p, size_t __n, 02318 const _CharT* __i, const _CharT* __j) 02319 { 02320 rope __r(__i, __j); 02321 replace(__p, __n, __r); 02322 } 02323 02324 void 02325 replace(size_t __p, size_t __n, 02326 const const_iterator& __i, const const_iterator& __j) 02327 { 02328 rope __r(__i, __j); 02329 replace(__p, __n, __r); 02330 } 02331 02332 void 02333 replace(size_t __p, size_t __n, 02334 const iterator& __i, const iterator& __j) 02335 { 02336 rope __r(__i, __j); 02337 replace(__p, __n, __r); 02338 } 02339 02340 // Single character variants: 02341 void 02342 replace(size_t __p, _CharT __c) 02343 { 02344 iterator __i(this, __p); 02345 *__i = __c; 02346 } 02347 02348 void 02349 replace(size_t __p, const rope& __r) 02350 { replace(__p, 1, __r); } 02351 02352 void 02353 replace(size_t __p, const _CharT* __i, size_t __i_len) 02354 { replace(__p, 1, __i, __i_len); } 02355 02356 void 02357 replace(size_t __p, const _CharT* __c_string) 02358 { replace(__p, 1, __c_string); } 02359 02360 void 02361 replace(size_t __p, const _CharT* __i, const _CharT* __j) 02362 { replace(__p, 1, __i, __j); } 02363 02364 void 02365 replace(size_t __p, const const_iterator& __i, 02366 const const_iterator& __j) 02367 { replace(__p, 1, __i, __j); } 02368 02369 void 02370 replace(size_t __p, const iterator& __i, 02371 const iterator& __j) 02372 { replace(__p, 1, __i, __j); } 02373 02374 // Erase, (position, size) variant. 02375 void 02376 erase(size_t __p, size_t __n) 02377 { 02378 _RopeRep* __result = replace(this->_M_tree_ptr, __p, 02379 __p + __n, 0); 02380 _S_unref(this->_M_tree_ptr); 02381 this->_M_tree_ptr = __result; 02382 } 02383 02384 // Erase, single character 02385 void 02386 erase(size_t __p) 02387 { erase(__p, __p + 1); } 02388 02389 // Insert, iterator variants. 02390 iterator 02391 insert(const iterator& __p, const rope& __r) 02392 { 02393 insert(__p.index(), __r); 02394 return __p; 02395 } 02396 02397 iterator 02398 insert(const iterator& __p, size_t __n, _CharT __c) 02399 { 02400 insert(__p.index(), __n, __c); 02401 return __p; 02402 } 02403 02404 iterator insert(const iterator& __p, _CharT __c) 02405 { 02406 insert(__p.index(), __c); 02407 return __p; 02408 } 02409 02410 iterator 02411 insert(const iterator& __p ) 02412 { 02413 insert(__p.index()); 02414 return __p; 02415 } 02416 02417 iterator 02418 insert(const iterator& __p, const _CharT* c_string) 02419 { 02420 insert(__p.index(), c_string); 02421 return __p; 02422 } 02423 02424 iterator 02425 insert(const iterator& __p, const _CharT* __i, size_t __n) 02426 { 02427 insert(__p.index(), __i, __n); 02428 return __p; 02429 } 02430 02431 iterator 02432 insert(const iterator& __p, const _CharT* __i, 02433 const _CharT* __j) 02434 { 02435 insert(__p.index(), __i, __j); 02436 return __p; 02437 } 02438 02439 iterator 02440 insert(const iterator& __p, 02441 const const_iterator& __i, const const_iterator& __j) 02442 { 02443 insert(__p.index(), __i, __j); 02444 return __p; 02445 } 02446 02447 iterator 02448 insert(const iterator& __p, 02449 const iterator& __i, const iterator& __j) 02450 { 02451 insert(__p.index(), __i, __j); 02452 return __p; 02453 } 02454 02455 // Replace, range variants. 02456 void 02457 replace(const iterator& __p, const iterator& __q, const rope& __r) 02458 { replace(__p.index(), __q.index() - __p.index(), __r); } 02459 02460 void 02461 replace(const iterator& __p, const iterator& __q, _CharT __c) 02462 { replace(__p.index(), __q.index() - __p.index(), __c); } 02463 02464 void 02465 replace(const iterator& __p, const iterator& __q, 02466 const _CharT* __c_string) 02467 { replace(__p.index(), __q.index() - __p.index(), __c_string); } 02468 02469 void 02470 replace(const iterator& __p, const iterator& __q, 02471 const _CharT* __i, size_t __n) 02472 { replace(__p.index(), __q.index() - __p.index(), __i, __n); } 02473 02474 void 02475 replace(const iterator& __p, const iterator& __q, 02476 const _CharT* __i, const _CharT* __j) 02477 { replace(__p.index(), __q.index() - __p.index(), __i, __j); } 02478 02479 void 02480 replace(const iterator& __p, const iterator& __q, 02481 const const_iterator& __i, const const_iterator& __j) 02482 { replace(__p.index(), __q.index() - __p.index(), __i, __j); } 02483 02484 void 02485 replace(const iterator& __p, const iterator& __q, 02486 const iterator& __i, const iterator& __j) 02487 { replace(__p.index(), __q.index() - __p.index(), __i, __j); } 02488 02489 // Replace, iterator variants. 02490 void 02491 replace(const iterator& __p, const rope& __r) 02492 { replace(__p.index(), __r); } 02493 02494 void 02495 replace(const iterator& __p, _CharT __c) 02496 { replace(__p.index(), __c); } 02497 02498 void 02499 replace(const iterator& __p, const _CharT* __c_string) 02500 { replace(__p.index(), __c_string); } 02501 02502 void 02503 replace(const iterator& __p, const _CharT* __i, size_t __n) 02504 { replace(__p.index(), __i, __n); } 02505 02506 void 02507 replace(const iterator& __p, const _CharT* __i, const _CharT* __j) 02508 { replace(__p.index(), __i, __j); } 02509 02510 void 02511 replace(const iterator& __p, const_iterator __i, const_iterator __j) 02512 { replace(__p.index(), __i, __j); } 02513 02514 void 02515 replace(const iterator& __p, iterator __i, iterator __j) 02516 { replace(__p.index(), __i, __j); } 02517 02518 // Iterator and range variants of erase 02519 iterator 02520 erase(const iterator& __p, const iterator& __q) 02521 { 02522 size_t __p_index = __p.index(); 02523 erase(__p_index, __q.index() - __p_index); 02524 return iterator(this, __p_index); 02525 } 02526 02527 iterator 02528 erase(const iterator& __p) 02529 { 02530 size_t __p_index = __p.index(); 02531 erase(__p_index, 1); 02532 return iterator(this, __p_index); 02533 } 02534 02535 rope 02536 substr(size_t __start, size_t __len = 1) const 02537 { 02538 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 02539 __start, 02540 __start + __len)); 02541 } 02542 02543 rope 02544 substr(iterator __start, iterator __end) const 02545 { 02546 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 02547 __start.index(), 02548 __end.index())); 02549 } 02550 02551 rope 02552 substr(iterator __start) const 02553 { 02554 size_t __pos = __start.index(); 02555 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 02556 __pos, __pos + 1)); 02557 } 02558 02559 rope 02560 substr(const_iterator __start, const_iterator __end) const 02561 { 02562 // This might eventually take advantage of the cache in the 02563 // iterator. 02564 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 02565 __start.index(), 02566 __end.index())); 02567 } 02568 02569 rope<_CharT, _Alloc> 02570 substr(const_iterator __start) 02571 { 02572 size_t __pos = __start.index(); 02573 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr, 02574 __pos, __pos + 1)); 02575 } 02576 02577 static const size_type npos; 02578 02579 size_type find(_CharT __c, size_type __pos = 0) const; 02580 02581 size_type 02582 find(const _CharT* __s, size_type __pos = 0) const 02583 { 02584 size_type __result_pos; 02585 const_iterator __result = 02586 std::search(const_begin() + __pos, const_end(), 02587 __s, __s + _S_char_ptr_len(__s)); 02588 __result_pos = __result.index(); 02589 #ifndef __STL_OLD_ROPE_SEMANTICS 02590 if (__result_pos == size()) 02591 __result_pos = npos; 02592 #endif 02593 return __result_pos; 02594 } 02595 02596 iterator 02597 mutable_begin() 02598 { return(iterator(this, 0)); } 02599 02600 iterator 02601 mutable_end() 02602 { return(iterator(this, size())); } 02603 02604 typedef std::reverse_iterator<iterator> reverse_iterator; 02605 02606 reverse_iterator 02607 mutable_rbegin() 02608 { return reverse_iterator(mutable_end()); } 02609 02610 reverse_iterator 02611 mutable_rend() 02612 { return reverse_iterator(mutable_begin()); } 02613 02614 reference 02615 mutable_reference_at(size_type __pos) 02616 { return reference(this, __pos); } 02617 02618 #ifdef __STD_STUFF 02619 reference 02620 operator[] (size_type __pos) 02621 { return _char_ref_proxy(this, __pos); } 02622 02623 reference 02624 at(size_type __pos) 02625 { 02626 // if (__pos >= size()) throw out_of_range; // XXX 02627 return (*this)[__pos]; 02628 } 02629 02630 void resize(size_type __n, _CharT __c) { } 02631 void resize(size_type __n) { } 02632 void reserve(size_type __res_arg = 0) { } 02633 02634 size_type 02635 capacity() const 02636 { return max_size(); } 02637 02638 // Stuff below this line is dangerous because it's error prone. 02639 // I would really like to get rid of it. 02640 // copy function with funny arg ordering. 02641 size_type 02642 copy(_CharT* __buffer, size_type __n, 02643 size_type __pos = 0) const 02644 { return copy(__pos, __n, __buffer); } 02645 02646 iterator 02647 end() 02648 { return mutable_end(); } 02649 02650 iterator 02651 begin() 02652 { return mutable_begin(); } 02653 02654 reverse_iterator 02655 rend() 02656 { return mutable_rend(); } 02657 02658 reverse_iterator 02659 rbegin() 02660 { return mutable_rbegin(); } 02661 02662 #else 02663 const_iterator 02664 end() 02665 { return const_end(); } 02666 02667 const_iterator 02668 begin() 02669 { return const_begin(); } 02670 02671 const_reverse_iterator 02672 rend() 02673 { return const_rend(); } 02674 02675 const_reverse_iterator 02676 rbegin() 02677 { return const_rbegin(); } 02678 02679 #endif 02680 }; 02681 02682 template <class _CharT, class _Alloc> 02683 const typename rope<_CharT, _Alloc>::size_type 02684 rope<_CharT, _Alloc>::npos = (size_type)(-1); 02685 02686 template <class _CharT, class _Alloc> 02687 inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02688 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02689 { return (__x._M_current_pos == __y._M_current_pos 02690 && __x._M_root == __y._M_root); } 02691 02692 template <class _CharT, class _Alloc> 02693 inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02694 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02695 { return (__x._M_current_pos < __y._M_current_pos); } 02696 02697 template <class _CharT, class _Alloc> 02698 inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02699 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02700 { return !(__x == __y); } 02701 02702 template <class _CharT, class _Alloc> 02703 inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02704 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02705 { return __y < __x; } 02706 02707 template <class _CharT, class _Alloc> 02708 inline bool 02709 operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02710 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02711 { return !(__y < __x); } 02712 02713 template <class _CharT, class _Alloc> 02714 inline bool 02715 operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02716 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02717 { return !(__x < __y); } 02718 02719 template <class _CharT, class _Alloc> 02720 inline ptrdiff_t 02721 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, 02722 const _Rope_const_iterator<_CharT, _Alloc>& __y) 02723 { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; } 02724 02725 template <class _CharT, class _Alloc> 02726 inline _Rope_const_iterator<_CharT, _Alloc> 02727 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) 02728 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, 02729 __x._M_current_pos - __n); } 02730 02731 template <class _CharT, class _Alloc> 02732 inline _Rope_const_iterator<_CharT, _Alloc> 02733 operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) 02734 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, 02735 __x._M_current_pos + __n); } 02736 02737 template <class _CharT, class _Alloc> 02738 inline _Rope_const_iterator<_CharT, _Alloc> 02739 operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x) 02740 { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root, 02741 __x._M_current_pos + __n); } 02742 02743 template <class _CharT, class _Alloc> 02744 inline bool 02745 operator==(const _Rope_iterator<_CharT, _Alloc>& __x, 02746 const _Rope_iterator<_CharT, _Alloc>& __y) 02747 {return (__x._M_current_pos == __y._M_current_pos 02748 && __x._M_root_rope == __y._M_root_rope); } 02749 02750 template <class _CharT, class _Alloc> 02751 inline bool 02752 operator<(const _Rope_iterator<_CharT, _Alloc>& __x, 02753 const _Rope_iterator<_CharT, _Alloc>& __y) 02754 { return (__x._M_current_pos < __y._M_current_pos); } 02755 02756 template <class _CharT, class _Alloc> 02757 inline bool 02758 operator!=(const _Rope_iterator<_CharT, _Alloc>& __x, 02759 const _Rope_iterator<_CharT, _Alloc>& __y) 02760 { return !(__x == __y); } 02761 02762 template <class _CharT, class _Alloc> 02763 inline bool 02764 operator>(const _Rope_iterator<_CharT, _Alloc>& __x, 02765 const _Rope_iterator<_CharT, _Alloc>& __y) 02766 { return __y < __x; } 02767 02768 template <class _CharT, class _Alloc> 02769 inline bool 02770 operator<=(const _Rope_iterator<_CharT, _Alloc>& __x, 02771 const _Rope_iterator<_CharT, _Alloc>& __y) 02772 { return !(__y < __x); } 02773 02774 template <class _CharT, class _Alloc> 02775 inline bool 02776 operator>=(const _Rope_iterator<_CharT, _Alloc>& __x, 02777 const _Rope_iterator<_CharT, _Alloc>& __y) 02778 { return !(__x < __y); } 02779 02780 template <class _CharT, class _Alloc> 02781 inline ptrdiff_t 02782 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, 02783 const _Rope_iterator<_CharT, _Alloc>& __y) 02784 { return ((ptrdiff_t)__x._M_current_pos 02785 - (ptrdiff_t)__y._M_current_pos); } 02786 02787 template <class _CharT, class _Alloc> 02788 inline _Rope_iterator<_CharT, _Alloc> 02789 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, 02790 ptrdiff_t __n) 02791 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, 02792 __x._M_current_pos - __n); } 02793 02794 template <class _CharT, class _Alloc> 02795 inline _Rope_iterator<_CharT, _Alloc> 02796 operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n) 02797 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, 02798 __x._M_current_pos + __n); } 02799 02800 template <class _CharT, class _Alloc> 02801 inline _Rope_iterator<_CharT, _Alloc> 02802 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x) 02803 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope, 02804 __x._M_current_pos + __n); } 02805 02806 template <class _CharT, class _Alloc> 02807 inline rope<_CharT, _Alloc> 02808 operator+(const rope<_CharT, _Alloc>& __left, 02809 const rope<_CharT, _Alloc>& __right) 02810 { 02811 // Inlining this should make it possible to keep __left and 02812 // __right in registers. 02813 typedef rope<_CharT, _Alloc> rope_type; 02814 return rope_type(rope_type::_S_concat(__left._M_tree_ptr, 02815 __right._M_tree_ptr)); 02816 } 02817 02818 template <class _CharT, class _Alloc> 02819 inline rope<_CharT, _Alloc>& 02820 operator+=(rope<_CharT, _Alloc>& __left, 02821 const rope<_CharT, _Alloc>& __right) 02822 { 02823 __left.append(__right); 02824 return __left; 02825 } 02826 02827 template <class _CharT, class _Alloc> 02828 inline rope<_CharT, _Alloc> 02829 operator+(const rope<_CharT, _Alloc>& __left, 02830 const _CharT* __right) 02831 { 02832 typedef rope<_CharT, _Alloc> rope_type; 02833 size_t __rlen = rope_type::_S_char_ptr_len(__right); 02834 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr, 02835 __right, __rlen)); 02836 } 02837 02838 template <class _CharT, class _Alloc> 02839 inline rope<_CharT, _Alloc>& 02840 operator+=(rope<_CharT, _Alloc>& __left, 02841 const _CharT* __right) 02842 { 02843 __left.append(__right); 02844 return __left; 02845 } 02846 02847 template <class _CharT, class _Alloc> 02848 inline rope<_CharT, _Alloc> 02849 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right) 02850 { 02851 typedef rope<_CharT, _Alloc> rope_type; 02852 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr, 02853 &__right, 1)); 02854 } 02855 02856 template <class _CharT, class _Alloc> 02857 inline rope<_CharT, _Alloc>& 02858 operator+=(rope<_CharT, _Alloc>& __left, _CharT __right) 02859 { 02860 __left.append(__right); 02861 return __left; 02862 } 02863 02864 template <class _CharT, class _Alloc> 02865 bool 02866 operator<(const rope<_CharT, _Alloc>& __left, 02867 const rope<_CharT, _Alloc>& __right) 02868 { return __left.compare(__right) < 0; } 02869 02870 template <class _CharT, class _Alloc> 02871 bool 02872 operator==(const rope<_CharT, _Alloc>& __left, 02873 const rope<_CharT, _Alloc>& __right) 02874 { return __left.compare(__right) == 0; } 02875 02876 template <class _CharT, class _Alloc> 02877 inline bool 02878 operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, 02879 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y) 02880 { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); } 02881 02882 template <class _CharT, class _Alloc> 02883 inline bool 02884 operator!=(const rope<_CharT, _Alloc>& __x, 02885 const rope<_CharT, _Alloc>& __y) 02886 { return !(__x == __y); } 02887 02888 template <class _CharT, class _Alloc> 02889 inline bool 02890 operator>(const rope<_CharT, _Alloc>& __x, 02891 const rope<_CharT, _Alloc>& __y) 02892 { return __y < __x; } 02893 02894 template <class _CharT, class _Alloc> 02895 inline bool 02896 operator<=(const rope<_CharT, _Alloc>& __x, 02897 const rope<_CharT, _Alloc>& __y) 02898 { return !(__y < __x); } 02899 02900 template <class _CharT, class _Alloc> 02901 inline bool 02902 operator>=(const rope<_CharT, _Alloc>& __x, 02903 const rope<_CharT, _Alloc>& __y) 02904 { return !(__x < __y); } 02905 02906 template <class _CharT, class _Alloc> 02907 inline bool 02908 operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x, 02909 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y) 02910 { return !(__x == __y); } 02911 02912 template<class _CharT, class _Traits, class _Alloc> 02913 std::basic_ostream<_CharT, _Traits>& 02914 operator<<(std::basic_ostream<_CharT, _Traits>& __o, 02915 const rope<_CharT, _Alloc>& __r); 02916 02917 typedef rope<char> crope; 02918 typedef rope<wchar_t> wrope; 02919 02920 inline crope::reference 02921 __mutable_reference_at(crope& __c, size_t __i) 02922 { return __c.mutable_reference_at(__i); } 02923 02924 inline wrope::reference 02925 __mutable_reference_at(wrope& __c, size_t __i) 02926 { return __c.mutable_reference_at(__i); } 02927 02928 template <class _CharT, class _Alloc> 02929 inline void 02930 swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y) 02931 { __x.swap(__y); } 02932 02933 _GLIBCXX_END_NAMESPACE_VERSION 02934 } // namespace 02935 02936 02937 namespace std _GLIBCXX_VISIBILITY(default) 02938 { 02939 namespace tr1 02940 { 02941 _GLIBCXX_BEGIN_NAMESPACE_VERSION 02942 02943 template<> 02944 struct hash<__gnu_cxx::crope> 02945 { 02946 size_t 02947 operator()(const __gnu_cxx::crope& __str) const 02948 { 02949 size_t __size = __str.size(); 02950 if (0 == __size) 02951 return 0; 02952 return 13 * __str[0] + 5 * __str[__size - 1] + __size; 02953 } 02954 }; 02955 02956 02957 template<> 02958 struct hash<__gnu_cxx::wrope> 02959 { 02960 size_t 02961 operator()(const __gnu_cxx::wrope& __str) const 02962 { 02963 size_t __size = __str.size(); 02964 if (0 == __size) 02965 return 0; 02966 return 13 * __str[0] + 5 * __str[__size - 1] + __size; 02967 } 02968 }; 02969 02970 _GLIBCXX_END_NAMESPACE_VERSION 02971 } // namespace tr1 02972 } // namespace std 02973 02974 # include <ext/ropeimpl.h> 02975 02976 #endif