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