rope

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

Generated on Sat Dec 12 09:40:13 2009 for libstdc++ by  doxygen 1.5.6