stl_rope.h

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

Generated on Wed Aug 4 21:43:20 2004 for libstdc++-v3 Source by doxygen 1.3.8