rope

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

Generated on Tue Sep 7 10:05:10 2004 for libstdc++-v3 Source by doxygen 1.3.8