- Main Page
- Namespaces
- Classes
- Files
- Related Pages

# /Users/fpy/titan-1-5-MBARI/Mers/Executives/DeductiveController/Configs/TI_DSP_BIOS/stl/stl_rope.h

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