]> rtime.felk.cvut.cz Git - l4.git/blob - l4/pkg/l4re-core/libstdc++-v3/contrib/libstdc++-v3-4.8/include/ext/rope
Update
[l4.git] / l4 / pkg / l4re-core / libstdc++-v3 / contrib / libstdc++-v3-4.8 / include / ext / rope
1 // SGI's rope class -*- C++ -*-
2
3 // Copyright (C) 2001-2013 Free Software Foundation, Inc.
4 //
5 // This file is part of the GNU ISO C++ Library.  This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 3, or (at your option)
9 // any later version.
10
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
14 // GNU General Public License for more details.
15
16 // Under Section 7 of GPL version 3, you are granted additional
17 // permissions described in the GCC Runtime Library Exception, version
18 // 3.1, as published by the Free Software Foundation.
19
20 // You should have received a copy of the GNU General Public License and
21 // a copy of the GCC Runtime Library Exception along with this program;
22 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
23 // <http://www.gnu.org/licenses/>.
24
25 /*
26  * Copyright (c) 1997
27  * Silicon Graphics Computer Systems, Inc.
28  *
29  * Permission to use, copy, modify, distribute and sell this software
30  * and its documentation for any purpose is hereby granted without fee,
31  * provided that the above copyright notice appear in all copies and
32  * that both that copyright notice and this permission notice appear
33  * in supporting documentation.  Silicon Graphics makes no
34  * representations about the suitability of this software for any
35  * purpose.  It is provided "as is" without express or implied warranty.
36  */
37
38 /** @file ext/rope
39  *  This file is a GNU extension to the Standard C++ Library (possibly
40  *  containing extensions from the HP/SGI STL subset). 
41  */
42
43 #ifndef _ROPE
44 #define _ROPE 1
45
46 #pragma GCC system_header
47
48 #include <algorithm>
49 #include <iosfwd>
50 #include <bits/stl_construct.h>
51 #include <bits/stl_uninitialized.h>
52 #include <bits/stl_function.h>
53 #include <bits/stl_numeric.h>
54 #include <bits/allocator.h>
55 #include <bits/gthr.h>
56 #include <tr1/functional>
57
58 # ifdef __GC
59 #   define __GC_CONST const
60 # else
61 #   define __GC_CONST   // constant except for deallocation
62 # endif
63
64 #include <ext/memory> // For uninitialized_copy_n
65
66 namespace __gnu_cxx _GLIBCXX_VISIBILITY(default)
67 {
68   namespace __detail
69   {
70     enum { _S_max_rope_depth = 45 };
71     enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
72   } // namespace __detail
73
74   using std::size_t;
75   using std::ptrdiff_t;
76   using std::allocator;
77   using std::_Destroy;
78
79 _GLIBCXX_BEGIN_NAMESPACE_VERSION
80
81   // See libstdc++/36832.
82   template<typename _ForwardIterator, typename _Allocator>
83     void
84     _Destroy_const(_ForwardIterator __first,
85                    _ForwardIterator __last, _Allocator __alloc)
86     {
87       for (; __first != __last; ++__first)
88         __alloc.destroy(&*__first);
89     }
90
91   template<typename _ForwardIterator, typename _Tp>
92     inline void
93     _Destroy_const(_ForwardIterator __first,
94                    _ForwardIterator __last, allocator<_Tp>)
95     { _Destroy(__first, __last); }
96
97   // The _S_eos function is used for those functions that
98   // convert to/from C-like strings to detect the end of the string.
99   
100   // The end-of-C-string character.
101   // This is what the draft standard says it should be.
102   template <class _CharT>
103     inline _CharT
104     _S_eos(_CharT*)
105     { return _CharT(); }
106
107   // Test for basic character types.
108   // For basic character types leaves having a trailing eos.
109   template <class _CharT>
110     inline bool
111     _S_is_basic_char_type(_CharT*)
112     { return false; }
113   
114   template <class _CharT>
115     inline bool
116     _S_is_one_byte_char_type(_CharT*)
117     { return false; }
118
119   inline bool
120   _S_is_basic_char_type(char*)
121   { return true; }
122   
123   inline bool
124   _S_is_one_byte_char_type(char*)
125   { return true; }
126   
127   inline bool
128   _S_is_basic_char_type(wchar_t*)
129   { return true; }
130
131   // Store an eos iff _CharT is a basic character type.
132   // Do not reference _S_eos if it isn't.
133   template <class _CharT>
134     inline void
135     _S_cond_store_eos(_CharT&) { }
136
137   inline void
138   _S_cond_store_eos(char& __c)
139   { __c = 0; }
140
141   inline void
142   _S_cond_store_eos(wchar_t& __c)
143   { __c = 0; }
144
145   // char_producers are logically functions that generate a section of
146   // a string.  These can be converted to ropes.  The resulting rope
147   // invokes the char_producer on demand.  This allows, for example,
148   // files to be viewed as ropes without reading the entire file.
149   template <class _CharT>
150     class char_producer
151     {
152     public:
153       virtual ~char_producer() { };
154
155       virtual void
156       operator()(size_t __start_pos, size_t __len,
157                  _CharT* __buffer) = 0;
158       // Buffer should really be an arbitrary output iterator.
159       // That way we could flatten directly into an ostream, etc.
160       // This is thoroughly impossible, since iterator types don't
161       // have runtime descriptions.
162     };
163
164   // Sequence buffers:
165   //
166   // Sequence must provide an append operation that appends an
167   // array to the sequence.  Sequence buffers are useful only if
168   // appending an entire array is cheaper than appending element by element.
169   // This is true for many string representations.
170   // This should  perhaps inherit from ostream<sequence::value_type>
171   // and be implemented correspondingly, so that they can be used
172   // for formatted.  For the sake of portability, we don't do this yet.
173   //
174   // For now, sequence buffers behave as output iterators.  But they also
175   // behave a little like basic_ostringstream<sequence::value_type> and a
176   // little like containers.
177
178   template<class _Sequence, size_t _Buf_sz = 100>
179     class sequence_buffer
180     : public std::iterator<std::output_iterator_tag, void, void, void, void>
181     {
182     public:
183       typedef typename _Sequence::value_type value_type;
184     protected:
185       _Sequence* _M_prefix;
186       value_type _M_buffer[_Buf_sz];
187       size_t     _M_buf_count;
188     public:
189
190       void
191       flush()
192       {
193         _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
194         _M_buf_count = 0;
195       }
196       
197       ~sequence_buffer()
198       { flush(); }
199       
200       sequence_buffer()
201       : _M_prefix(0), _M_buf_count(0) { }
202
203       sequence_buffer(const sequence_buffer& __x)
204       {
205         _M_prefix = __x._M_prefix;
206         _M_buf_count = __x._M_buf_count;
207         std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
208       }
209       
210       sequence_buffer(sequence_buffer& __x)
211       {
212         __x.flush();
213         _M_prefix = __x._M_prefix;
214         _M_buf_count = 0;
215       }
216       
217       sequence_buffer(_Sequence& __s)
218       : _M_prefix(&__s), _M_buf_count(0) { }
219       
220       sequence_buffer&
221       operator=(sequence_buffer& __x)
222       {
223         __x.flush();
224         _M_prefix = __x._M_prefix;
225         _M_buf_count = 0;
226         return *this;
227       }
228
229       sequence_buffer&
230       operator=(const sequence_buffer& __x)
231       {
232         _M_prefix = __x._M_prefix;
233         _M_buf_count = __x._M_buf_count;
234         std::copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
235         return *this;
236       }
237       
238       void
239       push_back(value_type __x)
240       {
241         if (_M_buf_count < _Buf_sz)
242           {
243             _M_buffer[_M_buf_count] = __x;
244             ++_M_buf_count;
245           }
246         else
247           {
248             flush();
249             _M_buffer[0] = __x;
250             _M_buf_count = 1;
251           }
252       }
253       
254       void
255       append(value_type* __s, size_t __len)
256       {
257         if (__len + _M_buf_count <= _Buf_sz)
258           {
259             size_t __i = _M_buf_count;
260             for (size_t __j = 0; __j < __len; __i++, __j++)
261               _M_buffer[__i] = __s[__j];
262             _M_buf_count += __len;
263           }
264         else if (0 == _M_buf_count)
265           _M_prefix->append(__s, __s + __len);
266         else
267           {
268             flush();
269             append(__s, __len);
270           }
271       }
272
273       sequence_buffer&
274       write(value_type* __s, size_t __len)
275       {
276         append(__s, __len);
277         return *this;
278       }
279       
280       sequence_buffer&
281       put(value_type __x)
282       {
283         push_back(__x);
284         return *this;
285       }
286       
287       sequence_buffer&
288       operator=(const value_type& __rhs)
289       {
290         push_back(__rhs);
291         return *this;
292       }
293       
294       sequence_buffer&
295       operator*()
296       { return *this; }
297       
298       sequence_buffer&
299       operator++()
300       { return *this; }
301       
302       sequence_buffer
303       operator++(int)
304       { return *this; }
305     };
306   
307   // The following should be treated as private, at least for now.
308   template<class _CharT>
309     class _Rope_char_consumer
310     {
311     public:
312       // If we had member templates, these should not be virtual.
313       // For now we need to use run-time parametrization where
314       // compile-time would do.  Hence this should all be private
315       // for now.
316       // The symmetry with char_producer is accidental and temporary.
317       virtual ~_Rope_char_consumer() { };
318   
319       virtual bool
320       operator()(const _CharT* __buffer, size_t __len) = 0;
321     };
322   
323   // First a lot of forward declarations.  The standard seems to require
324   // much stricter "declaration before use" than many of the implementations
325   // that preceded it.
326   template<class _CharT, class _Alloc = allocator<_CharT> >
327     class rope;
328   
329   template<class _CharT, class _Alloc>
330     struct _Rope_RopeConcatenation;
331
332   template<class _CharT, class _Alloc>
333     struct _Rope_RopeLeaf;
334   
335   template<class _CharT, class _Alloc>
336     struct _Rope_RopeFunction;
337   
338   template<class _CharT, class _Alloc>
339     struct _Rope_RopeSubstring;
340   
341   template<class _CharT, class _Alloc>
342     class _Rope_iterator;
343   
344   template<class _CharT, class _Alloc>
345     class _Rope_const_iterator;
346   
347   template<class _CharT, class _Alloc>
348     class _Rope_char_ref_proxy;
349   
350   template<class _CharT, class _Alloc>
351     class _Rope_char_ptr_proxy;
352
353   template<class _CharT, class _Alloc>
354     bool
355     operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
356                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y);
357
358   template<class _CharT, class _Alloc>
359     _Rope_const_iterator<_CharT, _Alloc>
360     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
361               ptrdiff_t __n);
362
363   template<class _CharT, class _Alloc>
364     _Rope_const_iterator<_CharT, _Alloc>
365     operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x,
366               ptrdiff_t __n);
367
368   template<class _CharT, class _Alloc>
369     _Rope_const_iterator<_CharT, _Alloc>
370     operator+(ptrdiff_t __n,
371               const _Rope_const_iterator<_CharT, _Alloc>& __x);
372
373   template<class _CharT, class _Alloc>
374     bool
375     operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
376                const _Rope_const_iterator<_CharT, _Alloc>& __y);
377
378   template<class _CharT, class _Alloc>
379     bool
380     operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
381               const _Rope_const_iterator<_CharT, _Alloc>& __y);
382   
383   template<class _CharT, class _Alloc>
384     ptrdiff_t
385     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
386               const _Rope_const_iterator<_CharT, _Alloc>& __y);
387
388   template<class _CharT, class _Alloc>
389     _Rope_iterator<_CharT, _Alloc>
390     operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
391
392   template<class _CharT, class _Alloc>
393     _Rope_iterator<_CharT, _Alloc>
394     operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
395
396   template<class _CharT, class _Alloc>
397     _Rope_iterator<_CharT, _Alloc>
398     operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x);
399
400   template<class _CharT, class _Alloc>
401     bool
402     operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
403                const _Rope_iterator<_CharT, _Alloc>& __y);
404
405   template<class _CharT, class _Alloc>
406     bool
407     operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
408               const _Rope_iterator<_CharT, _Alloc>& __y);
409
410   template<class _CharT, class _Alloc>
411     ptrdiff_t
412     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
413               const _Rope_iterator<_CharT, _Alloc>& __y);
414
415   template<class _CharT, class _Alloc>
416     rope<_CharT, _Alloc>
417     operator+(const rope<_CharT, _Alloc>& __left,
418               const rope<_CharT, _Alloc>& __right);
419
420   template<class _CharT, class _Alloc>
421     rope<_CharT, _Alloc>
422     operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right);
423
424   template<class _CharT, class _Alloc>
425     rope<_CharT, _Alloc>
426     operator+(const rope<_CharT, _Alloc>& __left, _CharT __right);
427
428   // Some helpers, so we can use power on ropes.
429   // See below for why this isn't local to the implementation.
430   
431   // This uses a nonstandard refcount convention.
432   // The result has refcount 0.
433   template<class _CharT, class _Alloc>
434     struct _Rope_Concat_fn
435     : public std::binary_function<rope<_CharT, _Alloc>, rope<_CharT, _Alloc>,
436                                   rope<_CharT, _Alloc> >
437     {
438       rope<_CharT, _Alloc>
439       operator()(const rope<_CharT, _Alloc>& __x,
440                  const rope<_CharT, _Alloc>& __y)
441       { return __x + __y; }
442     };
443
444   template <class _CharT, class _Alloc>
445     inline rope<_CharT, _Alloc>
446     identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
447     { return rope<_CharT, _Alloc>(); }
448
449   // Class _Refcount_Base provides a type, _RC_t, a data member,
450   // _M_ref_count, and member functions _M_incr and _M_decr, which perform
451   // atomic preincrement/predecrement.  The constructor initializes
452   // _M_ref_count.
453   struct _Refcount_Base
454   {
455     // The type _RC_t
456     typedef size_t _RC_t;
457     
458     // The data member _M_ref_count
459     volatile _RC_t _M_ref_count;
460
461     // Constructor
462 #ifdef __GTHREAD_MUTEX_INIT
463     __gthread_mutex_t _M_ref_count_lock = __GTHREAD_MUTEX_INIT;
464 #else
465     __gthread_mutex_t _M_ref_count_lock;
466 #endif
467
468     _Refcount_Base(_RC_t __n) : _M_ref_count(__n)
469     {
470 #ifndef __GTHREAD_MUTEX_INIT
471 #ifdef __GTHREAD_MUTEX_INIT_FUNCTION
472       __GTHREAD_MUTEX_INIT_FUNCTION (&_M_ref_count_lock);
473 #else
474 #error __GTHREAD_MUTEX_INIT or __GTHREAD_MUTEX_INIT_FUNCTION should be defined by gthr.h abstraction layer, report problem to libstdc++@gcc.gnu.org.
475 #endif
476 #endif
477     }
478
479 #ifndef __GTHREAD_MUTEX_INIT
480     ~_Refcount_Base()
481     { __gthread_mutex_destroy(&_M_ref_count_lock); }
482 #endif
483
484     void
485     _M_incr()
486     {
487       __gthread_mutex_lock(&_M_ref_count_lock);
488       ++_M_ref_count;
489       __gthread_mutex_unlock(&_M_ref_count_lock);
490     }
491
492     _RC_t
493     _M_decr()
494     {
495       __gthread_mutex_lock(&_M_ref_count_lock);
496       volatile _RC_t __tmp = --_M_ref_count;
497       __gthread_mutex_unlock(&_M_ref_count_lock);
498       return __tmp;
499     }
500   };
501
502   //
503   // What follows should really be local to rope.  Unfortunately,
504   // that doesn't work, since it makes it impossible to define generic
505   // equality on rope iterators.  According to the draft standard, the
506   // template parameters for such an equality operator cannot be inferred
507   // from the occurrence of a member class as a parameter.
508   // (SGI compilers in fact allow this, but the __result wouldn't be
509   // portable.)
510   // Similarly, some of the static member functions are member functions
511   // only to avoid polluting the global namespace, and to circumvent
512   // restrictions on type inference for template functions.
513   //
514
515   //
516   // The internal data structure for representing a rope.  This is
517   // private to the implementation.  A rope is really just a pointer
518   // to one of these.
519   //
520   // A few basic functions for manipulating this data structure
521   // are members of _RopeRep.  Most of the more complex algorithms
522   // are implemented as rope members.
523   //
524   // Some of the static member functions of _RopeRep have identically
525   // named functions in rope that simply invoke the _RopeRep versions.
526
527 #define __ROPE_DEFINE_ALLOCS(__a) \
528         __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \
529         typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
530         __ROPE_DEFINE_ALLOC(__C,_C) \
531         typedef _Rope_RopeLeaf<_CharT,__a> __L; \
532         __ROPE_DEFINE_ALLOC(__L,_L) \
533         typedef _Rope_RopeFunction<_CharT,__a> __F; \
534         __ROPE_DEFINE_ALLOC(__F,_F) \
535         typedef _Rope_RopeSubstring<_CharT,__a> __S; \
536         __ROPE_DEFINE_ALLOC(__S,_S)
537
538   //  Internal rope nodes potentially store a copy of the allocator
539   //  instance used to allocate them.  This is mostly redundant.
540   //  But the alternative would be to pass allocator instances around
541   //  in some form to nearly all internal functions, since any pointer
542   //  assignment may result in a zero reference count and thus require
543   //  deallocation.
544
545 #define __STATIC_IF_SGI_ALLOC  /* not static */
546
547   template <class _CharT, class _Alloc>
548     struct _Rope_rep_base
549     : public _Alloc
550     {
551       typedef _Alloc allocator_type;
552
553       allocator_type
554       get_allocator() const
555       { return *static_cast<const _Alloc*>(this); }
556
557       allocator_type&
558       _M_get_allocator()
559       { return *static_cast<_Alloc*>(this); }
560
561       const allocator_type&
562       _M_get_allocator() const
563       { return *static_cast<const _Alloc*>(this); }
564
565       _Rope_rep_base(size_t __size, const allocator_type&)
566       : _M_size(__size) { }
567
568       size_t _M_size;
569
570 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
571         typedef typename \
572           _Alloc::template rebind<_Tp>::other __name##Alloc; \
573         static _Tp* __name##_allocate(size_t __n) \
574           { return __name##Alloc().allocate(__n); } \
575         static void __name##_deallocate(_Tp *__p, size_t __n) \
576           { __name##Alloc().deallocate(__p, __n); }
577       __ROPE_DEFINE_ALLOCS(_Alloc)
578 # undef __ROPE_DEFINE_ALLOC
579     };
580
581   template<class _CharT, class _Alloc>
582     struct _Rope_RopeRep
583     : public _Rope_rep_base<_CharT, _Alloc>
584 # ifndef __GC
585              , _Refcount_Base
586 # endif
587     {
588     public:
589       __detail::_Tag _M_tag:8;
590       bool _M_is_balanced:8;
591       unsigned char _M_depth;
592       __GC_CONST _CharT* _M_c_string;
593 #ifdef __GTHREAD_MUTEX_INIT
594       __gthread_mutex_t _M_c_string_lock = __GTHREAD_MUTEX_INIT;
595 #else
596       __gthread_mutex_t _M_c_string_lock;
597 #endif
598                         /* Flattened version of string, if needed.  */
599                         /* typically 0.                             */
600                         /* If it's not 0, then the memory is owned  */
601                         /* by this node.                            */
602                         /* In the case of a leaf, this may point to */
603                         /* the same memory as the data field.       */
604       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
605         allocator_type;
606
607       using _Rope_rep_base<_CharT, _Alloc>::get_allocator;
608       using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator;
609
610       _Rope_RopeRep(__detail::_Tag __t, int __d, bool __b, size_t __size,
611                     const allocator_type& __a)
612       : _Rope_rep_base<_CharT, _Alloc>(__size, __a),
613 #ifndef __GC
614         _Refcount_Base(1),
615 #endif
616         _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
617 #ifdef __GTHREAD_MUTEX_INIT
618       { }
619 #else
620       { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }
621       ~_Rope_RopeRep()
622       { __gthread_mutex_destroy (&_M_c_string_lock); }
623 #endif
624 #ifdef __GC
625       void
626       _M_incr () { }
627 #endif
628       static void
629       _S_free_string(__GC_CONST _CharT*, size_t __len,
630                      allocator_type& __a);
631 #define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
632                         // Deallocate data section of a leaf.
633                         // This shouldn't be a member function.
634                         // But its hard to do anything else at the
635                         // moment, because it's templatized w.r.t.
636                         // an allocator.
637                         // Does nothing if __GC is defined.
638 #ifndef __GC
639       void _M_free_c_string();
640       void _M_free_tree();
641       // Deallocate t. Assumes t is not 0.
642       void
643       _M_unref_nonnil()
644       {
645         if (0 == _M_decr())
646           _M_free_tree();
647       }
648
649       void
650       _M_ref_nonnil()
651       { _M_incr(); }
652
653       static void
654       _S_unref(_Rope_RopeRep* __t)
655       {
656         if (0 != __t)
657           __t->_M_unref_nonnil();
658       }
659
660       static void
661       _S_ref(_Rope_RopeRep* __t)
662       {
663         if (0 != __t)
664           __t->_M_incr();
665       }
666       
667       static void
668       _S_free_if_unref(_Rope_RopeRep* __t)
669       {
670         if (0 != __t && 0 == __t->_M_ref_count)
671           __t->_M_free_tree();
672       }
673 #   else /* __GC */
674       void _M_unref_nonnil() { }
675       void _M_ref_nonnil() { }
676       static void _S_unref(_Rope_RopeRep*) { }
677       static void _S_ref(_Rope_RopeRep*) { }
678       static void _S_free_if_unref(_Rope_RopeRep*) { }
679 #   endif
680 protected:
681       _Rope_RopeRep&
682       operator=(const _Rope_RopeRep&);
683
684       _Rope_RopeRep(const _Rope_RopeRep&);
685     };
686
687   template<class _CharT, class _Alloc>
688     struct _Rope_RopeLeaf
689     : public _Rope_RopeRep<_CharT, _Alloc>
690     {
691     public:
692       // Apparently needed by VC++
693       // The data fields of leaves are allocated with some
694       // extra space, to accommodate future growth and for basic
695       // character types, to hold a trailing eos character.
696       enum { _S_alloc_granularity = 8 };
697       
698       static size_t
699       _S_rounded_up_size(size_t __n)
700       {
701         size_t __size_with_eos;
702         
703         if (_S_is_basic_char_type((_CharT*)0))
704           __size_with_eos = __n + 1;
705         else
706           __size_with_eos = __n;
707 #ifdef __GC
708         return __size_with_eos;
709 #else
710         // Allow slop for in-place expansion.
711         return ((__size_with_eos + size_t(_S_alloc_granularity) - 1)
712                 &~ (size_t(_S_alloc_granularity) - 1));
713 #endif
714       }
715       __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */
716                                   /* The allocated size is         */
717                                   /* _S_rounded_up_size(size), except */
718                                   /* in the GC case, in which it   */
719                                   /* doesn't matter.               */
720       typedef typename _Rope_rep_base<_CharT,_Alloc>::allocator_type
721         allocator_type;
722
723       _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size,
724                      const allocator_type& __a)
725       : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_leaf, 0, true,
726                                       __size, __a), _M_data(__d)
727       {
728         if (_S_is_basic_char_type((_CharT *)0))
729           {
730             // already eos terminated.
731             this->_M_c_string = __d;
732           }
733       }
734       // The constructor assumes that d has been allocated with
735       // the proper allocator and the properly padded size.
736       // In contrast, the destructor deallocates the data:
737 #ifndef __GC
738       ~_Rope_RopeLeaf() throw()
739       {
740         if (_M_data != this->_M_c_string)
741           this->_M_free_c_string();
742         
743         this->__STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator());
744       }
745 #endif
746 protected:
747       _Rope_RopeLeaf&
748       operator=(const _Rope_RopeLeaf&);
749
750       _Rope_RopeLeaf(const _Rope_RopeLeaf&);
751     };
752
753   template<class _CharT, class _Alloc>
754     struct _Rope_RopeConcatenation
755     : public _Rope_RopeRep<_CharT, _Alloc>
756     {
757     public:
758       _Rope_RopeRep<_CharT, _Alloc>* _M_left;
759       _Rope_RopeRep<_CharT, _Alloc>* _M_right;
760
761       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
762         allocator_type;
763
764       _Rope_RopeConcatenation(_Rope_RopeRep<_CharT, _Alloc>* __l,
765                               _Rope_RopeRep<_CharT, _Alloc>* __r,
766                               const allocator_type& __a)
767         : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_concat,
768                                       std::max(__l->_M_depth,
769                                                __r->_M_depth) + 1,
770                                       false,
771                                       __l->_M_size + __r->_M_size, __a),
772         _M_left(__l), _M_right(__r)
773       { }
774 #ifndef __GC
775       ~_Rope_RopeConcatenation() throw()
776       {
777         this->_M_free_c_string();
778         _M_left->_M_unref_nonnil();
779         _M_right->_M_unref_nonnil();
780       }
781 #endif
782 protected:
783       _Rope_RopeConcatenation&
784       operator=(const _Rope_RopeConcatenation&);
785       
786       _Rope_RopeConcatenation(const _Rope_RopeConcatenation&);
787     };
788
789   template<class _CharT, class _Alloc>
790     struct _Rope_RopeFunction
791     : public _Rope_RopeRep<_CharT, _Alloc>
792     {
793     public:
794       char_producer<_CharT>* _M_fn;
795 #ifndef __GC
796       bool _M_delete_when_done; // Char_producer is owned by the
797                                 // rope and should be explicitly
798                                 // deleted when the rope becomes
799                                 // inaccessible.
800 #else
801       // In the GC case, we either register the rope for
802       // finalization, or not.  Thus the field is unnecessary;
803       // the information is stored in the collector data structures.
804       // We do need a finalization procedure to be invoked by the
805       // collector.
806       static void
807       _S_fn_finalization_proc(void * __tree, void *)
808       { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; }
809 #endif
810     typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
811       allocator_type;
812
813       _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size,
814                         bool __d, const allocator_type& __a)
815       : _Rope_RopeRep<_CharT, _Alloc>(__detail::_S_function, 0, true, __size, __a)
816         , _M_fn(__f)
817 #ifndef __GC
818         , _M_delete_when_done(__d)
819 #endif
820       {
821 #ifdef __GC
822         if (__d)
823           {
824             GC_REGISTER_FINALIZER(this, _Rope_RopeFunction::
825                                   _S_fn_finalization_proc, 0, 0, 0);
826           }
827 #endif
828       }
829 #ifndef __GC
830       ~_Rope_RopeFunction() throw()
831       {
832         this->_M_free_c_string();
833         if (_M_delete_when_done)
834           delete _M_fn;
835       }
836 # endif
837     protected:
838       _Rope_RopeFunction&
839       operator=(const _Rope_RopeFunction&);
840
841       _Rope_RopeFunction(const _Rope_RopeFunction&);
842     };
843   // Substring results are usually represented using just
844   // concatenation nodes.  But in the case of very long flat ropes
845   // or ropes with a functional representation that isn't practical.
846   // In that case, we represent the __result as a special case of
847   // RopeFunction, whose char_producer points back to the rope itself.
848   // In all cases except repeated substring operations and
849   // deallocation, we treat the __result as a RopeFunction.
850   template<class _CharT, class _Alloc>
851     struct _Rope_RopeSubstring
852     : public _Rope_RopeFunction<_CharT, _Alloc>,
853       public char_producer<_CharT>
854     {
855     public:
856       // XXX this whole class should be rewritten.
857       _Rope_RopeRep<_CharT,_Alloc>* _M_base;      // not 0
858       size_t _M_start;
859
860       virtual void
861       operator()(size_t __start_pos, size_t __req_len,
862                  _CharT* __buffer)
863       {
864         switch(_M_base->_M_tag)
865           {
866           case __detail::_S_function:
867           case __detail::_S_substringfn:
868             {
869               char_producer<_CharT>* __fn =
870                 ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
871               (*__fn)(__start_pos + _M_start, __req_len, __buffer);
872             }
873             break;
874           case __detail::_S_leaf:
875             {
876               __GC_CONST _CharT* __s =
877                 ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;
878               uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,
879                                    __buffer);
880             }
881             break;
882           default:
883             break;
884           }
885       }
886       
887       typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
888         allocator_type;
889
890       _Rope_RopeSubstring(_Rope_RopeRep<_CharT, _Alloc>* __b, size_t __s,
891                           size_t __l, const allocator_type& __a)
892       : _Rope_RopeFunction<_CharT, _Alloc>(this, __l, false, __a),
893         char_producer<_CharT>(), _M_base(__b), _M_start(__s)
894       {
895 #ifndef __GC
896         _M_base->_M_ref_nonnil();
897 #endif
898         this->_M_tag = __detail::_S_substringfn;
899       }
900     virtual ~_Rope_RopeSubstring() throw()
901       {
902 #ifndef __GC
903         _M_base->_M_unref_nonnil();
904         // _M_free_c_string();  -- done by parent class
905 #endif
906       }
907     };
908
909   // Self-destructing pointers to Rope_rep.
910   // These are not conventional smart pointers.  Their
911   // only purpose in life is to ensure that unref is called
912   // on the pointer either at normal exit or if an exception
913   // is raised.  It is the caller's responsibility to
914   // adjust reference counts when these pointers are initialized
915   // or assigned to.  (This convention significantly reduces
916   // the number of potentially expensive reference count
917   // updates.)
918 #ifndef __GC
919   template<class _CharT, class _Alloc>
920     struct _Rope_self_destruct_ptr
921     {
922       _Rope_RopeRep<_CharT, _Alloc>* _M_ptr;
923
924       ~_Rope_self_destruct_ptr()
925       { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); }
926 #ifdef __EXCEPTIONS
927       _Rope_self_destruct_ptr() : _M_ptr(0) { };
928 #else
929       _Rope_self_destruct_ptr() { };
930 #endif
931       _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p)
932       : _M_ptr(__p) { }
933     
934       _Rope_RopeRep<_CharT, _Alloc>&
935       operator*()
936       { return *_M_ptr; }
937     
938       _Rope_RopeRep<_CharT, _Alloc>*
939       operator->()
940       { return _M_ptr; }
941     
942       operator _Rope_RopeRep<_CharT, _Alloc>*()
943       { return _M_ptr; }
944     
945       _Rope_self_destruct_ptr&
946       operator=(_Rope_RopeRep<_CharT, _Alloc>* __x)
947       { _M_ptr = __x; return *this; }
948     };
949 #endif
950
951   // Dereferencing a nonconst iterator has to return something
952   // that behaves almost like a reference.  It's not possible to
953   // return an actual reference since assignment requires extra
954   // work.  And we would get into the same problems as with the
955   // CD2 version of basic_string.
956   template<class _CharT, class _Alloc>
957     class _Rope_char_ref_proxy
958     {
959       friend class rope<_CharT, _Alloc>;
960       friend class _Rope_iterator<_CharT, _Alloc>;
961       friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
962 #ifdef __GC
963       typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
964 #else
965       typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
966 #endif
967       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
968       typedef rope<_CharT, _Alloc> _My_rope;
969       size_t _M_pos;
970       _CharT _M_current;
971       bool _M_current_valid;
972       _My_rope* _M_root;     // The whole rope.
973     public:
974       _Rope_char_ref_proxy(_My_rope* __r, size_t __p)
975       :  _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { }
976
977       _Rope_char_ref_proxy(const _Rope_char_ref_proxy& __x)
978       : _M_pos(__x._M_pos), _M_current(__x._M_current), 
979         _M_current_valid(false), _M_root(__x._M_root) { }
980
981       // Don't preserve cache if the reference can outlive the
982       // expression.  We claim that's not possible without calling
983       // a copy constructor or generating reference to a proxy
984       // reference.  We declare the latter to have undefined semantics.
985       _Rope_char_ref_proxy(_My_rope* __r, size_t __p, _CharT __c)
986       : _M_pos(__p), _M_current(__c), _M_current_valid(true), _M_root(__r) { }
987
988       inline operator _CharT () const;
989
990       _Rope_char_ref_proxy&
991       operator=(_CharT __c);
992     
993       _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const;
994       
995       _Rope_char_ref_proxy&
996       operator=(const _Rope_char_ref_proxy& __c)
997       { return operator=((_CharT)__c); }
998     };
999
1000   template<class _CharT, class __Alloc>
1001     inline void
1002     swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
1003          _Rope_char_ref_proxy <_CharT, __Alloc > __b)
1004     {
1005       _CharT __tmp = __a;
1006       __a = __b;
1007       __b = __tmp;
1008     }
1009
1010   template<class _CharT, class _Alloc>
1011     class _Rope_char_ptr_proxy
1012     {
1013       // XXX this class should be rewritten.
1014       friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
1015       size_t _M_pos;
1016       rope<_CharT,_Alloc>* _M_root;     // The whole rope.
1017     public:
1018       _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)
1019       : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
1020
1021       _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x)
1022       : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
1023
1024       _Rope_char_ptr_proxy() { }
1025       
1026       _Rope_char_ptr_proxy(_CharT* __x)
1027       : _M_root(0), _M_pos(0) { }
1028
1029       _Rope_char_ptr_proxy&
1030       operator=(const _Rope_char_ptr_proxy& __x)
1031       {
1032         _M_pos = __x._M_pos;
1033         _M_root = __x._M_root;
1034         return *this;
1035       }
1036
1037       template<class _CharT2, class _Alloc2>
1038         friend bool
1039         operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x,
1040                    const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y);
1041
1042       _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const
1043       { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); }
1044     };
1045
1046   // Rope iterators:
1047   // Unlike in the C version, we cache only part of the stack
1048   // for rope iterators, since they must be efficiently copyable.
1049   // When we run out of cache, we have to reconstruct the iterator
1050   // value.
1051   // Pointers from iterators are not included in reference counts.
1052   // Iterators are assumed to be thread private.  Ropes can
1053   // be shared.
1054   
1055   template<class _CharT, class _Alloc>
1056     class _Rope_iterator_base
1057     : public std::iterator<std::random_access_iterator_tag, _CharT>
1058     {
1059       friend class rope<_CharT, _Alloc>;
1060     public:
1061       typedef _Alloc _allocator_type; // used in _Rope_rotate, VC++ workaround
1062       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1063       // Borland doesn't want this to be protected.
1064     protected:
1065       enum { _S_path_cache_len = 4 }; // Must be <= 9.
1066       enum { _S_iterator_buf_len = 15 };
1067       size_t _M_current_pos;
1068       _RopeRep* _M_root;     // The whole rope.
1069       size_t _M_leaf_pos;    // Starting position for current leaf
1070       __GC_CONST _CharT* _M_buf_start;
1071                              // Buffer possibly
1072                              // containing current char.
1073       __GC_CONST _CharT* _M_buf_ptr;
1074                              // Pointer to current char in buffer.
1075                              // != 0 ==> buffer valid.
1076       __GC_CONST _CharT* _M_buf_end;
1077                              // One past __last valid char in buffer.
1078       // What follows is the path cache.  We go out of our
1079       // way to make this compact.
1080       // Path_end contains the bottom section of the path from
1081       // the root to the current leaf.
1082       const _RopeRep* _M_path_end[_S_path_cache_len];
1083       int _M_leaf_index;     // Last valid __pos in path_end;
1084                              // _M_path_end[0] ... _M_path_end[leaf_index-1]
1085                              // point to concatenation nodes.
1086       unsigned char _M_path_directions;
1087                           // (path_directions >> __i) & 1 is 1
1088                           // iff we got from _M_path_end[leaf_index - __i - 1]
1089                           // to _M_path_end[leaf_index - __i] by going to the
1090                           // __right. Assumes path_cache_len <= 9.
1091       _CharT _M_tmp_buf[_S_iterator_buf_len];
1092                         // Short buffer for surrounding chars.
1093                         // This is useful primarily for
1094                         // RopeFunctions.  We put the buffer
1095                         // here to avoid locking in the
1096                         // multithreaded case.
1097       // The cached path is generally assumed to be valid
1098       // only if the buffer is valid.
1099       static void _S_setbuf(_Rope_iterator_base& __x);
1100                                         // Set buffer contents given
1101                                         // path cache.
1102       static void _S_setcache(_Rope_iterator_base& __x);
1103                                         // Set buffer contents and
1104                                         // path cache.
1105       static void _S_setcache_for_incr(_Rope_iterator_base& __x);
1106                                         // As above, but assumes path
1107                                         // cache is valid for previous posn.
1108       _Rope_iterator_base() { }
1109
1110       _Rope_iterator_base(_RopeRep* __root, size_t __pos)
1111       : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { }
1112
1113       void _M_incr(size_t __n);
1114       void _M_decr(size_t __n);
1115     public:
1116       size_t
1117       index() const
1118       { return _M_current_pos; }
1119     
1120       _Rope_iterator_base(const _Rope_iterator_base& __x)
1121       {
1122         if (0 != __x._M_buf_ptr)
1123           *this = __x;
1124         else
1125           {
1126             _M_current_pos = __x._M_current_pos;
1127             _M_root = __x._M_root;
1128             _M_buf_ptr = 0;
1129           }
1130       }
1131     };
1132
1133   template<class _CharT, class _Alloc>
1134     class _Rope_iterator;
1135
1136   template<class _CharT, class _Alloc>
1137     class _Rope_const_iterator
1138     : public _Rope_iterator_base<_CharT, _Alloc>
1139     {
1140       friend class rope<_CharT, _Alloc>;
1141     protected:
1142       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1143       // The one from the base class may not be directly visible.
1144       _Rope_const_iterator(const _RopeRep* __root, size_t __pos)
1145       : _Rope_iterator_base<_CharT, _Alloc>(const_cast<_RopeRep*>(__root),
1146                                             __pos)
1147                    // Only nonconst iterators modify root ref count
1148       { }
1149   public:
1150       typedef _CharT reference;   // Really a value.  Returning a reference
1151                                   // Would be a mess, since it would have
1152                                   // to be included in refcount.
1153       typedef const _CharT* pointer;
1154
1155     public:
1156       _Rope_const_iterator() { };
1157
1158       _Rope_const_iterator(const _Rope_const_iterator& __x)
1159       : _Rope_iterator_base<_CharT,_Alloc>(__x) { }
1160
1161       _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x);
1162     
1163       _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos)
1164       : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { }
1165
1166       _Rope_const_iterator&
1167       operator=(const _Rope_const_iterator& __x)
1168       {
1169         if (0 != __x._M_buf_ptr)
1170           *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
1171         else
1172           {
1173             this->_M_current_pos = __x._M_current_pos;
1174             this->_M_root = __x._M_root;
1175             this->_M_buf_ptr = 0;
1176           }
1177         return(*this);
1178       }
1179
1180       reference
1181       operator*()
1182       {
1183         if (0 == this->_M_buf_ptr)
1184           this->_S_setcache(*this);
1185         return *this->_M_buf_ptr;
1186       }
1187
1188       // Without this const version, Rope iterators do not meet the
1189       // requirements of an Input Iterator.
1190       reference
1191       operator*() const
1192       {
1193         return *const_cast<_Rope_const_iterator&>(*this);
1194       }
1195
1196       _Rope_const_iterator&
1197       operator++()
1198       {
1199         __GC_CONST _CharT* __next;
1200         if (0 != this->_M_buf_ptr
1201             && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end)
1202           {
1203             this->_M_buf_ptr = __next;
1204             ++this->_M_current_pos;
1205           }
1206         else
1207           this->_M_incr(1);
1208         return *this;
1209       }
1210
1211       _Rope_const_iterator&
1212       operator+=(ptrdiff_t __n)
1213       {
1214         if (__n >= 0)
1215           this->_M_incr(__n);
1216         else
1217           this->_M_decr(-__n);
1218         return *this;
1219       }
1220
1221       _Rope_const_iterator&
1222       operator--()
1223       {
1224         this->_M_decr(1);
1225         return *this;
1226       }
1227
1228       _Rope_const_iterator&
1229       operator-=(ptrdiff_t __n)
1230       {
1231         if (__n >= 0)
1232           this->_M_decr(__n);
1233         else
1234           this->_M_incr(-__n);
1235         return *this;
1236       }
1237
1238       _Rope_const_iterator
1239       operator++(int)
1240       {
1241         size_t __old_pos = this->_M_current_pos;
1242         this->_M_incr(1);
1243         return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
1244         // This makes a subsequent dereference expensive.
1245         // Perhaps we should instead copy the iterator
1246         // if it has a valid cache?
1247       }
1248
1249       _Rope_const_iterator
1250       operator--(int)
1251       {
1252         size_t __old_pos = this->_M_current_pos;
1253         this->_M_decr(1);
1254         return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
1255       }
1256
1257       template<class _CharT2, class _Alloc2>
1258         friend _Rope_const_iterator<_CharT2, _Alloc2>
1259         operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1260                   ptrdiff_t __n);
1261
1262       template<class _CharT2, class _Alloc2>
1263         friend _Rope_const_iterator<_CharT2, _Alloc2>
1264         operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1265                   ptrdiff_t __n);
1266
1267       template<class _CharT2, class _Alloc2>
1268         friend _Rope_const_iterator<_CharT2, _Alloc2>
1269         operator+(ptrdiff_t __n,
1270                   const _Rope_const_iterator<_CharT2, _Alloc2>& __x);
1271
1272       reference
1273       operator[](size_t __n)
1274       { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root,
1275                                               this->_M_current_pos + __n); }
1276
1277       template<class _CharT2, class _Alloc2>
1278         friend bool
1279         operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1280                    const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1281
1282       template<class _CharT2, class _Alloc2>
1283         friend bool
1284         operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1285                   const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1286
1287       template<class _CharT2, class _Alloc2>
1288         friend ptrdiff_t
1289         operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1290                   const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1291     };
1292
1293   template<class _CharT, class _Alloc>
1294     class _Rope_iterator
1295     : public _Rope_iterator_base<_CharT, _Alloc>
1296     {
1297       friend class rope<_CharT, _Alloc>;
1298     protected:
1299       typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep;
1300       rope<_CharT, _Alloc>* _M_root_rope;
1301
1302       // root is treated as a cached version of this, and is used to
1303       // detect changes to the underlying rope.
1304
1305       // Root is included in the reference count.  This is necessary
1306       // so that we can detect changes reliably.  Unfortunately, it
1307       // requires careful bookkeeping for the nonGC case.
1308       _Rope_iterator(rope<_CharT, _Alloc>* __r, size_t __pos)
1309       : _Rope_iterator_base<_CharT, _Alloc>(__r->_M_tree_ptr, __pos),
1310         _M_root_rope(__r)
1311       { _RopeRep::_S_ref(this->_M_root);
1312         if (!(__r -> empty()))
1313           this->_S_setcache(*this);
1314       }
1315
1316       void _M_check();
1317     public:
1318       typedef _Rope_char_ref_proxy<_CharT, _Alloc>  reference;
1319       typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer;
1320
1321       rope<_CharT, _Alloc>&
1322       container()
1323       { return *_M_root_rope; }
1324
1325       _Rope_iterator()
1326       {
1327         this->_M_root = 0;  // Needed for reference counting.
1328       };
1329
1330       _Rope_iterator(const _Rope_iterator& __x)
1331       : _Rope_iterator_base<_CharT, _Alloc>(__x)
1332       {
1333         _M_root_rope = __x._M_root_rope;
1334         _RopeRep::_S_ref(this->_M_root);
1335       }
1336
1337       _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos);
1338
1339       ~_Rope_iterator()
1340       { _RopeRep::_S_unref(this->_M_root); }
1341
1342       _Rope_iterator&
1343       operator=(const _Rope_iterator& __x)
1344       {
1345         _RopeRep* __old = this->_M_root;
1346         
1347         _RopeRep::_S_ref(__x._M_root);
1348         if (0 != __x._M_buf_ptr)
1349           {
1350             _M_root_rope = __x._M_root_rope;
1351             *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
1352           }
1353         else
1354           {
1355             this->_M_current_pos = __x._M_current_pos;
1356             this->_M_root = __x._M_root;
1357             _M_root_rope = __x._M_root_rope;
1358             this->_M_buf_ptr = 0;
1359           }
1360         _RopeRep::_S_unref(__old);
1361         return(*this);
1362       }
1363
1364       reference
1365       operator*()
1366       {
1367         _M_check();
1368         if (0 == this->_M_buf_ptr)
1369           return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1370                                                       this->_M_current_pos);
1371         else
1372           return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1373                                                       this->_M_current_pos,
1374                                                       *this->_M_buf_ptr);
1375       }
1376
1377       // See above comment.
1378       reference
1379       operator*() const
1380       {
1381         return *const_cast<_Rope_iterator&>(*this);
1382       }
1383
1384       _Rope_iterator&
1385       operator++()
1386       {
1387         this->_M_incr(1);
1388         return *this;
1389       }
1390
1391       _Rope_iterator&
1392       operator+=(ptrdiff_t __n)
1393       {
1394         if (__n >= 0)
1395           this->_M_incr(__n);
1396         else
1397           this->_M_decr(-__n);
1398         return *this;
1399       }
1400
1401       _Rope_iterator&
1402       operator--()
1403       {
1404         this->_M_decr(1);
1405         return *this;
1406       }
1407
1408       _Rope_iterator&
1409       operator-=(ptrdiff_t __n)
1410       {
1411         if (__n >= 0)
1412           this->_M_decr(__n);
1413         else
1414           this->_M_incr(-__n);
1415         return *this;
1416       }
1417
1418       _Rope_iterator
1419       operator++(int)
1420       {
1421         size_t __old_pos = this->_M_current_pos;
1422         this->_M_incr(1);
1423         return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
1424       }
1425
1426       _Rope_iterator
1427       operator--(int)
1428       {
1429         size_t __old_pos = this->_M_current_pos;
1430         this->_M_decr(1);
1431         return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
1432       }
1433
1434       reference
1435       operator[](ptrdiff_t __n)
1436       { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1437                                                     this->_M_current_pos
1438                                                     + __n); }
1439
1440       template<class _CharT2, class _Alloc2>
1441         friend bool
1442         operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1443                    const _Rope_iterator<_CharT2, _Alloc2>& __y);
1444
1445       template<class _CharT2, class _Alloc2>
1446         friend bool
1447         operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1448                   const _Rope_iterator<_CharT2, _Alloc2>& __y);
1449
1450       template<class _CharT2, class _Alloc2>
1451         friend ptrdiff_t
1452         operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1453                   const _Rope_iterator<_CharT2, _Alloc2>& __y);
1454
1455       template<class _CharT2, class _Alloc2>
1456         friend _Rope_iterator<_CharT2, _Alloc2>
1457         operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
1458
1459       template<class _CharT2, class _Alloc2>
1460         friend _Rope_iterator<_CharT2, _Alloc2>
1461         operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
1462
1463       template<class _CharT2, class _Alloc2>
1464         friend _Rope_iterator<_CharT2, _Alloc2>
1465         operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x);
1466     };
1467
1468
1469   template <class _CharT, class _Alloc>
1470     struct _Rope_base
1471     : public _Alloc
1472     {
1473       typedef _Alloc allocator_type;
1474
1475       allocator_type
1476       get_allocator() const
1477       { return *static_cast<const _Alloc*>(this); }
1478
1479       allocator_type&
1480       _M_get_allocator()
1481       { return *static_cast<_Alloc*>(this); }
1482
1483       const allocator_type&
1484       _M_get_allocator() const
1485       { return *static_cast<const _Alloc*>(this); }
1486
1487       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1488       // The one in _Base may not be visible due to template rules.
1489
1490       _Rope_base(_RopeRep* __t, const allocator_type&)
1491       : _M_tree_ptr(__t) { }
1492
1493       _Rope_base(const allocator_type&) { }
1494
1495       // The only data member of a rope:
1496       _RopeRep *_M_tree_ptr;
1497
1498 #define __ROPE_DEFINE_ALLOC(_Tp, __name) \
1499         typedef typename \
1500           _Alloc::template rebind<_Tp>::other __name##Alloc; \
1501         static _Tp* __name##_allocate(size_t __n) \
1502           { return __name##Alloc().allocate(__n); } \
1503         static void __name##_deallocate(_Tp *__p, size_t __n) \
1504           { __name##Alloc().deallocate(__p, __n); }
1505       __ROPE_DEFINE_ALLOCS(_Alloc)
1506 #undef __ROPE_DEFINE_ALLOC
1507
1508         protected:
1509       _Rope_base&
1510       operator=(const _Rope_base&);
1511       
1512       _Rope_base(const _Rope_base&);
1513     };
1514
1515   /**
1516    *  This is an SGI extension.
1517    *  @ingroup SGIextensions
1518    *  @doctodo
1519    */
1520   template <class _CharT, class _Alloc>
1521     class rope : public _Rope_base<_CharT, _Alloc>
1522     {
1523     public:
1524       typedef _CharT value_type;
1525       typedef ptrdiff_t difference_type;
1526       typedef size_t size_type;
1527       typedef _CharT const_reference;
1528       typedef const _CharT* const_pointer;
1529       typedef _Rope_iterator<_CharT, _Alloc> iterator;
1530       typedef _Rope_const_iterator<_CharT, _Alloc> const_iterator;
1531       typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
1532       typedef _Rope_char_ptr_proxy<_CharT, _Alloc> pointer;
1533
1534       friend class _Rope_iterator<_CharT, _Alloc>;
1535       friend class _Rope_const_iterator<_CharT, _Alloc>;
1536       friend struct _Rope_RopeRep<_CharT, _Alloc>;
1537       friend class _Rope_iterator_base<_CharT, _Alloc>;
1538       friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
1539       friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
1540       friend struct _Rope_RopeSubstring<_CharT, _Alloc>;
1541
1542     protected:
1543       typedef _Rope_base<_CharT, _Alloc> _Base;
1544       typedef typename _Base::allocator_type allocator_type;
1545       using _Base::_M_tree_ptr;
1546       using _Base::get_allocator;
1547       using _Base::_M_get_allocator;      
1548       typedef __GC_CONST _CharT* _Cstrptr;
1549       
1550       static _CharT _S_empty_c_str[1];
1551       
1552       static bool
1553       _S_is0(_CharT __c)
1554       { return __c == _S_eos((_CharT*)0); }
1555       
1556       enum { _S_copy_max = 23 };
1557                 // For strings shorter than _S_copy_max, we copy to
1558                 // concatenate.
1559
1560       typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1561       typedef _Rope_RopeConcatenation<_CharT, _Alloc> _RopeConcatenation;
1562       typedef _Rope_RopeLeaf<_CharT, _Alloc> _RopeLeaf;
1563       typedef _Rope_RopeFunction<_CharT, _Alloc> _RopeFunction;
1564       typedef _Rope_RopeSubstring<_CharT, _Alloc> _RopeSubstring;
1565
1566       // Retrieve a character at the indicated position.
1567       static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
1568
1569 #ifndef __GC
1570       // Obtain a pointer to the character at the indicated position.
1571       // The pointer can be used to change the character.
1572       // If such a pointer cannot be produced, as is frequently the
1573       // case, 0 is returned instead.
1574       // (Returns nonzero only if all nodes in the path have a refcount
1575       // of 1.)
1576       static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
1577 #endif
1578
1579       static bool
1580       _S_apply_to_pieces(// should be template parameter
1581                          _Rope_char_consumer<_CharT>& __c,
1582                          const _RopeRep* __r,
1583                          size_t __begin, size_t __end);
1584                          // begin and end are assumed to be in range.
1585
1586 #ifndef __GC
1587       static void
1588       _S_unref(_RopeRep* __t)
1589       { _RopeRep::_S_unref(__t); }
1590
1591       static void
1592       _S_ref(_RopeRep* __t)
1593       { _RopeRep::_S_ref(__t); }
1594
1595 #else /* __GC */
1596       static void _S_unref(_RopeRep*) { }
1597       static void _S_ref(_RopeRep*) { }
1598 #endif
1599
1600 #ifdef __GC
1601       typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
1602 #else
1603       typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
1604 #endif
1605
1606       // _Result is counted in refcount.
1607       static _RopeRep* _S_substring(_RopeRep* __base,
1608                                     size_t __start, size_t __endp1);
1609
1610       static _RopeRep* _S_concat_char_iter(_RopeRep* __r,
1611                                            const _CharT* __iter, size_t __slen);
1612       // Concatenate rope and char ptr, copying __s.
1613       // Should really take an arbitrary iterator.
1614       // Result is counted in refcount.
1615       static _RopeRep* _S_destr_concat_char_iter(_RopeRep* __r,
1616                                                  const _CharT* __iter,
1617                                                  size_t __slen)
1618         // As above, but one reference to __r is about to be
1619         // destroyed.  Thus the pieces may be recycled if all
1620         // relevant reference counts are 1.
1621 #ifdef __GC
1622         // We can't really do anything since refcounts are unavailable.
1623       { return _S_concat_char_iter(__r, __iter, __slen); }
1624 #else
1625       ;
1626 #endif
1627
1628       static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
1629       // General concatenation on _RopeRep.  _Result
1630       // has refcount of 1.  Adjusts argument refcounts.
1631
1632    public:
1633       void
1634       apply_to_pieces(size_t __begin, size_t __end,
1635                       _Rope_char_consumer<_CharT>& __c) const
1636       { _S_apply_to_pieces(__c, this->_M_tree_ptr, __begin, __end); }
1637
1638    protected:
1639
1640       static size_t
1641       _S_rounded_up_size(size_t __n)
1642       { return _RopeLeaf::_S_rounded_up_size(__n); }
1643
1644       static size_t
1645       _S_allocated_capacity(size_t __n)
1646       {
1647         if (_S_is_basic_char_type((_CharT*)0))
1648           return _S_rounded_up_size(__n) - 1;
1649         else
1650           return _S_rounded_up_size(__n);
1651         
1652       }
1653
1654       // Allocate and construct a RopeLeaf using the supplied allocator
1655       // Takes ownership of s instead of copying.
1656       static _RopeLeaf*
1657       _S_new_RopeLeaf(__GC_CONST _CharT *__s,
1658                       size_t __size, allocator_type& __a)
1659       {
1660         _RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1);
1661         return new(__space) _RopeLeaf(__s, __size, __a);
1662       }
1663
1664       static _RopeConcatenation*
1665       _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
1666                                allocator_type& __a)
1667       {
1668         _RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1);
1669         return new(__space) _RopeConcatenation(__left, __right, __a);
1670       }
1671
1672       static _RopeFunction*
1673       _S_new_RopeFunction(char_producer<_CharT>* __f,
1674                           size_t __size, bool __d, allocator_type& __a)
1675       {
1676         _RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1);
1677         return new(__space) _RopeFunction(__f, __size, __d, __a);
1678       }
1679
1680       static _RopeSubstring*
1681       _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
1682                            size_t __l, allocator_type& __a)
1683       {
1684         _RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1);
1685         return new(__space) _RopeSubstring(__b, __s, __l, __a);
1686       }
1687       
1688       static _RopeLeaf*
1689       _S_RopeLeaf_from_unowned_char_ptr(const _CharT *__s,
1690                                         size_t __size, allocator_type& __a)
1691 #define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
1692                 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
1693       {
1694         if (0 == __size)
1695           return 0;
1696         _CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
1697         
1698         __uninitialized_copy_n_a(__s, __size, __buf, __a);
1699         _S_cond_store_eos(__buf[__size]);
1700         __try
1701           { return _S_new_RopeLeaf(__buf, __size, __a); }
1702         __catch(...)
1703           {
1704             _RopeRep::__STL_FREE_STRING(__buf, __size, __a);
1705             __throw_exception_again;
1706           }
1707       }
1708
1709       // Concatenation of nonempty strings.
1710       // Always builds a concatenation node.
1711       // Rebalances if the result is too deep.
1712       // Result has refcount 1.
1713       // Does not increment left and right ref counts even though
1714       // they are referenced.
1715       static _RopeRep*
1716       _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
1717
1718       // Concatenation helper functions
1719       static _RopeLeaf*
1720       _S_leaf_concat_char_iter(_RopeLeaf* __r,
1721                                const _CharT* __iter, size_t __slen);
1722       // Concatenate by copying leaf.
1723       // should take an arbitrary iterator
1724       // result has refcount 1.
1725 #ifndef __GC
1726       static _RopeLeaf*
1727       _S_destr_leaf_concat_char_iter(_RopeLeaf* __r,
1728                                      const _CharT* __iter, size_t __slen);
1729       // A version that potentially clobbers __r if __r->_M_ref_count == 1.
1730 #endif
1731
1732     private:
1733       
1734       static size_t _S_char_ptr_len(const _CharT* __s);
1735       // slightly generalized strlen
1736
1737       rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
1738       : _Base(__t, __a) { }
1739
1740
1741       // Copy __r to the _CharT buffer.
1742       // Returns __buffer + __r->_M_size.
1743       // Assumes that buffer is uninitialized.
1744       static _CharT* _S_flatten(_RopeRep* __r, _CharT* __buffer);
1745
1746       // Again, with explicit starting position and length.
1747       // Assumes that buffer is uninitialized.
1748       static _CharT* _S_flatten(_RopeRep* __r,
1749                                 size_t __start, size_t __len,
1750                                 _CharT* __buffer);
1751
1752       static const unsigned long
1753       _S_min_len[__detail::_S_max_rope_depth + 1];
1754       
1755       static bool
1756       _S_is_balanced(_RopeRep* __r)
1757       { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
1758
1759       static bool
1760       _S_is_almost_balanced(_RopeRep* __r)
1761       { return (__r->_M_depth == 0
1762                 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
1763
1764       static bool
1765       _S_is_roughly_balanced(_RopeRep* __r)
1766       { return (__r->_M_depth <= 1
1767                 || __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }
1768
1769       // Assumes the result is not empty.
1770       static _RopeRep*
1771       _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right)
1772       {
1773         _RopeRep* __result = _S_concat(__left, __right);
1774         if (_S_is_balanced(__result))
1775           __result->_M_is_balanced = true;
1776         return __result;
1777       }
1778
1779       // The basic rebalancing operation.  Logically copies the
1780       // rope.  The result has refcount of 1.  The client will
1781       // usually decrement the reference count of __r.
1782       // The result is within height 2 of balanced by the above
1783       // definition.
1784       static _RopeRep* _S_balance(_RopeRep* __r);
1785
1786       // Add all unbalanced subtrees to the forest of balanced trees.
1787       // Used only by balance.
1788       static void _S_add_to_forest(_RopeRep*__r, _RopeRep** __forest);
1789
1790       // Add __r to forest, assuming __r is already balanced.
1791       static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
1792       
1793       // Print to stdout, exposing structure
1794       static void _S_dump(_RopeRep* __r, int __indent = 0);
1795       
1796       // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
1797       static int _S_compare(const _RopeRep* __x, const _RopeRep* __y);
1798       
1799     public:
1800       bool
1801       empty() const
1802       { return 0 == this->_M_tree_ptr; }
1803       
1804       // Comparison member function.  This is public only for those
1805       // clients that need a ternary comparison.  Others
1806       // should use the comparison operators below.
1807       int
1808       compare(const rope& __y) const
1809       { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); }
1810
1811       rope(const _CharT* __s, const allocator_type& __a = allocator_type())
1812       : _Base(__a)
1813       {
1814         this->_M_tree_ptr =
1815           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
1816                                            _M_get_allocator());
1817       }
1818
1819       rope(const _CharT* __s, size_t __len,
1820            const allocator_type& __a = allocator_type())
1821       : _Base(__a)
1822       {
1823         this->_M_tree_ptr =
1824           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, _M_get_allocator());
1825       }
1826
1827       // Should perhaps be templatized with respect to the iterator type
1828       // and use Sequence_buffer.  (It should perhaps use sequence_buffer
1829       // even now.)
1830       rope(const _CharT* __s, const _CharT* __e,
1831            const allocator_type& __a = allocator_type())
1832       : _Base(__a)
1833       {
1834         this->_M_tree_ptr =
1835           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, _M_get_allocator());
1836       }
1837
1838       rope(const const_iterator& __s, const const_iterator& __e,
1839            const allocator_type& __a = allocator_type())
1840       : _Base(_S_substring(__s._M_root, __s._M_current_pos,
1841                            __e._M_current_pos), __a)
1842       { }
1843
1844       rope(const iterator& __s, const iterator& __e,
1845            const allocator_type& __a = allocator_type())
1846       : _Base(_S_substring(__s._M_root, __s._M_current_pos,
1847                            __e._M_current_pos), __a)
1848       { }
1849
1850       rope(_CharT __c, const allocator_type& __a = allocator_type())
1851       : _Base(__a)
1852       {
1853         _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));
1854         
1855         _M_get_allocator().construct(__buf, __c);
1856         __try
1857           {
1858             this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1,
1859                                                 _M_get_allocator());
1860           }
1861         __catch(...)
1862           {
1863             _RopeRep::__STL_FREE_STRING(__buf, 1, _M_get_allocator());
1864             __throw_exception_again;
1865           }
1866       }
1867
1868       rope(size_t __n, _CharT __c,
1869            const allocator_type& __a = allocator_type());
1870
1871       rope(const allocator_type& __a = allocator_type())
1872       : _Base(0, __a) { }
1873
1874       // Construct a rope from a function that can compute its members
1875       rope(char_producer<_CharT> *__fn, size_t __len, bool __delete_fn,
1876            const allocator_type& __a = allocator_type())
1877       : _Base(__a)
1878       {
1879         this->_M_tree_ptr = (0 == __len) ?
1880           0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
1881       }
1882
1883       rope(const rope& __x, const allocator_type& __a = allocator_type())
1884       : _Base(__x._M_tree_ptr, __a)
1885       { _S_ref(this->_M_tree_ptr); }
1886
1887       ~rope() throw()
1888       { _S_unref(this->_M_tree_ptr); }
1889
1890       rope&
1891       operator=(const rope& __x)
1892       {
1893         _RopeRep* __old = this->_M_tree_ptr;
1894         this->_M_tree_ptr = __x._M_tree_ptr;
1895         _S_ref(this->_M_tree_ptr);
1896         _S_unref(__old);
1897         return *this;
1898       }
1899
1900       void
1901       clear()
1902       {
1903         _S_unref(this->_M_tree_ptr);
1904         this->_M_tree_ptr = 0;
1905       }
1906       
1907       void
1908       push_back(_CharT __x)
1909       {
1910         _RopeRep* __old = this->_M_tree_ptr;
1911         this->_M_tree_ptr
1912           = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
1913         _S_unref(__old);
1914       }
1915
1916       void
1917       pop_back()
1918       {
1919         _RopeRep* __old = this->_M_tree_ptr;
1920         this->_M_tree_ptr = _S_substring(this->_M_tree_ptr,
1921                                          0, this->_M_tree_ptr->_M_size - 1);
1922         _S_unref(__old);
1923       }
1924
1925       _CharT
1926       back() const
1927       { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); }
1928
1929       void
1930       push_front(_CharT __x)
1931       {
1932         _RopeRep* __old = this->_M_tree_ptr;
1933         _RopeRep* __left =
1934           __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator());
1935         __try
1936           {
1937             this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
1938             _S_unref(__old);
1939             _S_unref(__left);
1940           }
1941         __catch(...)
1942           {
1943             _S_unref(__left);
1944             __throw_exception_again;
1945           }
1946       }
1947
1948       void
1949       pop_front()
1950       {
1951         _RopeRep* __old = this->_M_tree_ptr;
1952         this->_M_tree_ptr
1953           = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
1954         _S_unref(__old);
1955       }
1956
1957       _CharT
1958       front() const
1959       { return _S_fetch(this->_M_tree_ptr, 0); }
1960
1961       void
1962       balance()
1963       {
1964         _RopeRep* __old = this->_M_tree_ptr;
1965         this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
1966         _S_unref(__old);
1967       }
1968
1969       void
1970       copy(_CharT* __buffer) const
1971       {
1972         _Destroy_const(__buffer, __buffer + size(), _M_get_allocator());
1973         _S_flatten(this->_M_tree_ptr, __buffer);
1974       }
1975
1976       // This is the copy function from the standard, but
1977       // with the arguments reordered to make it consistent with the
1978       // rest of the interface.
1979       // Note that this guaranteed not to compile if the draft standard
1980       // order is assumed.
1981       size_type
1982       copy(size_type __pos, size_type __n, _CharT* __buffer) const
1983       {
1984         size_t __size = size();
1985         size_t __len = (__pos + __n > __size? __size - __pos : __n);
1986
1987         _Destroy_const(__buffer, __buffer + __len, _M_get_allocator());
1988         _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
1989         return __len;
1990       }
1991
1992       // Print to stdout, exposing structure.  May be useful for
1993       // performance debugging.
1994       void
1995       dump()
1996       { _S_dump(this->_M_tree_ptr); }
1997       
1998       // Convert to 0 terminated string in new allocated memory.
1999       // Embedded 0s in the input do not terminate the copy.
2000       const _CharT* c_str() const;
2001
2002       // As above, but also use the flattened representation as
2003       // the new rope representation.
2004       const _CharT* replace_with_c_str();
2005       
2006       // Reclaim memory for the c_str generated flattened string.
2007       // Intentionally undocumented, since it's hard to say when this
2008       // is safe for multiple threads.
2009       void
2010       delete_c_str ()
2011       {
2012         if (0 == this->_M_tree_ptr)
2013           return;
2014         if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag &&
2015             ((_RopeLeaf*)this->_M_tree_ptr)->_M_data ==
2016             this->_M_tree_ptr->_M_c_string)
2017           {
2018             // Representation shared
2019             return;
2020           }
2021 #ifndef __GC
2022         this->_M_tree_ptr->_M_free_c_string();
2023 #endif
2024         this->_M_tree_ptr->_M_c_string = 0;
2025       }
2026
2027       _CharT
2028       operator[] (size_type __pos) const
2029       { return _S_fetch(this->_M_tree_ptr, __pos); }
2030
2031       _CharT
2032       at(size_type __pos) const
2033       {
2034         // if (__pos >= size()) throw out_of_range;  // XXX
2035         return (*this)[__pos];
2036       }
2037
2038       const_iterator
2039       begin() const
2040       { return(const_iterator(this->_M_tree_ptr, 0)); }
2041
2042       // An easy way to get a const iterator from a non-const container.
2043       const_iterator
2044       const_begin() const
2045       { return(const_iterator(this->_M_tree_ptr, 0)); }
2046
2047       const_iterator
2048       end() const
2049       { return(const_iterator(this->_M_tree_ptr, size())); }
2050
2051       const_iterator
2052       const_end() const
2053       { return(const_iterator(this->_M_tree_ptr, size())); }
2054
2055       size_type
2056       size() const
2057       { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); }
2058       
2059       size_type
2060       length() const
2061       { return size(); }
2062
2063       size_type
2064       max_size() const
2065       {
2066         return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1;
2067         //  Guarantees that the result can be sufficiently
2068         //  balanced.  Longer ropes will probably still work,
2069         //  but it's harder to make guarantees.
2070       }
2071
2072       typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
2073
2074       const_reverse_iterator
2075       rbegin() const
2076       { return const_reverse_iterator(end()); }
2077
2078       const_reverse_iterator
2079       const_rbegin() const
2080       { return const_reverse_iterator(end()); }
2081
2082       const_reverse_iterator
2083       rend() const
2084       { return const_reverse_iterator(begin()); }
2085       
2086       const_reverse_iterator
2087       const_rend() const
2088       { return const_reverse_iterator(begin()); }
2089
2090       template<class _CharT2, class _Alloc2>
2091         friend rope<_CharT2, _Alloc2>
2092         operator+(const rope<_CharT2, _Alloc2>& __left,
2093                   const rope<_CharT2, _Alloc2>& __right);
2094
2095       template<class _CharT2, class _Alloc2>
2096         friend rope<_CharT2, _Alloc2>
2097         operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right);
2098
2099       template<class _CharT2, class _Alloc2>
2100         friend rope<_CharT2, _Alloc2>
2101         operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right);
2102
2103       // The symmetric cases are intentionally omitted, since they're
2104       // presumed to be less common, and we don't handle them as well.
2105
2106       // The following should really be templatized.  The first
2107       // argument should be an input iterator or forward iterator with
2108       // value_type _CharT.
2109       rope&
2110       append(const _CharT* __iter, size_t __n)
2111       {
2112         _RopeRep* __result =
2113           _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n);
2114         _S_unref(this->_M_tree_ptr);
2115         this->_M_tree_ptr = __result;
2116         return *this;
2117       }
2118
2119       rope&
2120       append(const _CharT* __c_string)
2121       {
2122         size_t __len = _S_char_ptr_len(__c_string);
2123         append(__c_string, __len);
2124         return(*this);
2125       }
2126
2127       rope&
2128       append(const _CharT* __s, const _CharT* __e)
2129       {
2130         _RopeRep* __result =
2131           _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s);
2132         _S_unref(this->_M_tree_ptr);
2133         this->_M_tree_ptr = __result;
2134         return *this;
2135       }
2136
2137       rope&
2138       append(const_iterator __s, const_iterator __e)
2139       {
2140         _Self_destruct_ptr __appendee(_S_substring(__s._M_root,
2141                                                    __s._M_current_pos,
2142                                                    __e._M_current_pos));
2143         _RopeRep* __result = _S_concat(this->_M_tree_ptr, 
2144                                        (_RopeRep*)__appendee);
2145         _S_unref(this->_M_tree_ptr);
2146         this->_M_tree_ptr = __result;
2147         return *this;
2148       }
2149
2150       rope&
2151       append(_CharT __c)
2152       {
2153         _RopeRep* __result =
2154           _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1);
2155         _S_unref(this->_M_tree_ptr);
2156         this->_M_tree_ptr = __result;
2157         return *this;
2158       }
2159
2160       rope&
2161       append()
2162       { return append(_CharT()); }  // XXX why?
2163
2164       rope&
2165       append(const rope& __y)
2166       {
2167         _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr);
2168         _S_unref(this->_M_tree_ptr);
2169         this->_M_tree_ptr = __result;
2170         return *this;
2171       }
2172
2173       rope&
2174       append(size_t __n, _CharT __c)
2175       {
2176         rope<_CharT,_Alloc> __last(__n, __c);
2177         return append(__last);
2178       }
2179
2180       void
2181       swap(rope& __b)
2182       {
2183         _RopeRep* __tmp = this->_M_tree_ptr;
2184         this->_M_tree_ptr = __b._M_tree_ptr;
2185         __b._M_tree_ptr = __tmp;
2186       }
2187
2188     protected:
2189       // Result is included in refcount.
2190       static _RopeRep*
2191       replace(_RopeRep* __old, size_t __pos1,
2192               size_t __pos2, _RopeRep* __r)
2193       {
2194         if (0 == __old)
2195           {
2196             _S_ref(__r);
2197             return __r;
2198           }
2199         _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
2200         _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size));
2201         _RopeRep* __result;
2202
2203         if (0 == __r)
2204           __result = _S_concat(__left, __right);
2205         else
2206           {
2207             _Self_destruct_ptr __left_result(_S_concat(__left, __r));
2208             __result = _S_concat(__left_result, __right);
2209           }
2210         return __result;
2211       }
2212
2213     public:
2214       void
2215       insert(size_t __p, const rope& __r)
2216       {
2217         _RopeRep* __result =
2218           replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr);
2219         _S_unref(this->_M_tree_ptr);
2220         this->_M_tree_ptr = __result;
2221       }
2222
2223       void
2224       insert(size_t __p, size_t __n, _CharT __c)
2225       {
2226         rope<_CharT,_Alloc> __r(__n,__c);
2227         insert(__p, __r);
2228       }
2229       
2230       void
2231       insert(size_t __p, const _CharT* __i, size_t __n)
2232       {
2233         _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p));
2234         _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr,
2235                                                 __p, size()));
2236         _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n));
2237         // _S_ destr_concat_char_iter should be safe here.
2238         // But as it stands it's probably not a win, since __left
2239         // is likely to have additional references.
2240         _RopeRep* __result = _S_concat(__left_result, __right);
2241         _S_unref(this->_M_tree_ptr);
2242         this->_M_tree_ptr = __result;
2243       }
2244
2245       void
2246       insert(size_t __p, const _CharT* __c_string)
2247       { insert(__p, __c_string, _S_char_ptr_len(__c_string)); }
2248
2249       void
2250       insert(size_t __p, _CharT __c)
2251       { insert(__p, &__c, 1); }
2252
2253       void
2254       insert(size_t __p)
2255       {
2256         _CharT __c = _CharT();
2257         insert(__p, &__c, 1);
2258       }
2259
2260       void
2261       insert(size_t __p, const _CharT* __i, const _CharT* __j)
2262       {
2263         rope __r(__i, __j);
2264         insert(__p, __r);
2265       }
2266
2267       void
2268       insert(size_t __p, const const_iterator& __i,
2269              const const_iterator& __j)
2270       {
2271         rope __r(__i, __j);
2272         insert(__p, __r);
2273       }
2274
2275       void
2276       insert(size_t __p, const iterator& __i,
2277              const iterator& __j)
2278       {
2279         rope __r(__i, __j);
2280         insert(__p, __r);
2281       }
2282
2283       // (position, length) versions of replace operations:
2284       
2285       void
2286       replace(size_t __p, size_t __n, const rope& __r)
2287       {
2288         _RopeRep* __result =
2289           replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
2290         _S_unref(this->_M_tree_ptr);
2291         this->_M_tree_ptr = __result;
2292       }
2293
2294       void
2295       replace(size_t __p, size_t __n,
2296               const _CharT* __i, size_t __i_len)
2297       {
2298         rope __r(__i, __i_len);
2299         replace(__p, __n, __r);
2300       }
2301
2302       void
2303       replace(size_t __p, size_t __n, _CharT __c)
2304       {
2305         rope __r(__c);
2306         replace(__p, __n, __r);
2307       }
2308
2309       void
2310       replace(size_t __p, size_t __n, const _CharT* __c_string)
2311       {
2312         rope __r(__c_string);
2313         replace(__p, __n, __r);
2314       }
2315       
2316       void
2317       replace(size_t __p, size_t __n,
2318               const _CharT* __i, const _CharT* __j)
2319       {
2320         rope __r(__i, __j);
2321         replace(__p, __n, __r);
2322       }
2323       
2324       void
2325       replace(size_t __p, size_t __n,
2326               const const_iterator& __i, const const_iterator& __j)
2327       {
2328         rope __r(__i, __j);
2329         replace(__p, __n, __r);
2330       }
2331
2332       void
2333       replace(size_t __p, size_t __n,
2334               const iterator& __i, const iterator& __j)
2335       {
2336         rope __r(__i, __j);
2337         replace(__p, __n, __r);
2338       }
2339
2340       // Single character variants:
2341       void
2342       replace(size_t __p, _CharT __c)
2343       {
2344         iterator __i(this, __p);
2345         *__i = __c;
2346       }
2347
2348       void
2349       replace(size_t __p, const rope& __r)
2350       { replace(__p, 1, __r); }
2351
2352       void
2353       replace(size_t __p, const _CharT* __i, size_t __i_len)
2354       { replace(__p, 1, __i, __i_len); }
2355
2356       void
2357       replace(size_t __p, const _CharT* __c_string)
2358       { replace(__p, 1, __c_string); }
2359
2360       void
2361       replace(size_t __p, const _CharT* __i, const _CharT* __j)
2362       { replace(__p, 1, __i, __j); }
2363
2364       void
2365       replace(size_t __p, const const_iterator& __i,
2366               const const_iterator& __j)
2367       { replace(__p, 1, __i, __j); }
2368
2369       void
2370       replace(size_t __p, const iterator& __i,
2371               const iterator& __j)
2372       { replace(__p, 1, __i, __j); }
2373
2374       // Erase, (position, size) variant.
2375       void
2376       erase(size_t __p, size_t __n)
2377       {
2378         _RopeRep* __result = replace(this->_M_tree_ptr, __p,
2379                                      __p + __n, 0);
2380         _S_unref(this->_M_tree_ptr);
2381         this->_M_tree_ptr = __result;
2382       }
2383
2384       // Erase, single character
2385       void
2386       erase(size_t __p)
2387       { erase(__p, __p + 1); }
2388
2389       // Insert, iterator variants.
2390       iterator
2391       insert(const iterator& __p, const rope& __r)
2392       {
2393         insert(__p.index(), __r);
2394         return __p;
2395       }
2396
2397       iterator
2398       insert(const iterator& __p, size_t __n, _CharT __c)
2399       {
2400         insert(__p.index(), __n, __c);
2401         return __p;
2402       }
2403
2404       iterator insert(const iterator& __p, _CharT __c)
2405       {
2406         insert(__p.index(), __c);
2407         return __p;
2408       }
2409       
2410       iterator
2411       insert(const iterator& __p )
2412       {
2413         insert(__p.index());
2414         return __p;
2415       }
2416       
2417       iterator
2418       insert(const iterator& __p, const _CharT* c_string)
2419       {
2420         insert(__p.index(), c_string);
2421         return __p;
2422       }
2423       
2424       iterator
2425       insert(const iterator& __p, const _CharT* __i, size_t __n)
2426       {
2427         insert(__p.index(), __i, __n);
2428         return __p;
2429       }
2430       
2431       iterator
2432       insert(const iterator& __p, const _CharT* __i,
2433              const _CharT* __j)
2434       {
2435         insert(__p.index(), __i, __j); 
2436         return __p;
2437       }
2438       
2439       iterator
2440       insert(const iterator& __p,
2441              const const_iterator& __i, const const_iterator& __j)
2442       {
2443         insert(__p.index(), __i, __j);
2444         return __p;
2445       }
2446       
2447       iterator
2448       insert(const iterator& __p,
2449              const iterator& __i, const iterator& __j)
2450       {
2451         insert(__p.index(), __i, __j);
2452         return __p;
2453       }
2454
2455       // Replace, range variants.
2456       void
2457       replace(const iterator& __p, const iterator& __q, const rope& __r)
2458       { replace(__p.index(), __q.index() - __p.index(), __r); }
2459
2460       void
2461       replace(const iterator& __p, const iterator& __q, _CharT __c)
2462       { replace(__p.index(), __q.index() - __p.index(), __c); }
2463       
2464       void
2465       replace(const iterator& __p, const iterator& __q,
2466               const _CharT* __c_string)
2467       { replace(__p.index(), __q.index() - __p.index(), __c_string); }
2468       
2469       void
2470       replace(const iterator& __p, const iterator& __q,
2471               const _CharT* __i, size_t __n)
2472       { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
2473       
2474       void
2475       replace(const iterator& __p, const iterator& __q,
2476               const _CharT* __i, const _CharT* __j)
2477       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2478       
2479       void
2480       replace(const iterator& __p, const iterator& __q,
2481               const const_iterator& __i, const const_iterator& __j)
2482       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2483       
2484       void
2485       replace(const iterator& __p, const iterator& __q,
2486               const iterator& __i, const iterator& __j)
2487       { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2488
2489       // Replace, iterator variants.
2490       void
2491       replace(const iterator& __p, const rope& __r)
2492       { replace(__p.index(), __r); }
2493       
2494       void
2495       replace(const iterator& __p, _CharT __c)
2496       { replace(__p.index(), __c); }
2497       
2498       void
2499       replace(const iterator& __p, const _CharT* __c_string)
2500       { replace(__p.index(), __c_string); }
2501       
2502       void
2503       replace(const iterator& __p, const _CharT* __i, size_t __n)
2504       { replace(__p.index(), __i, __n); }
2505       
2506       void
2507       replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
2508       { replace(__p.index(), __i, __j); }
2509       
2510       void
2511       replace(const iterator& __p, const_iterator __i, const_iterator __j)
2512       { replace(__p.index(), __i, __j); }
2513       
2514       void
2515       replace(const iterator& __p, iterator __i, iterator __j)
2516       { replace(__p.index(), __i, __j); }
2517
2518       // Iterator and range variants of erase
2519       iterator
2520       erase(const iterator& __p, const iterator& __q)
2521       {
2522         size_t __p_index = __p.index();
2523         erase(__p_index, __q.index() - __p_index);
2524         return iterator(this, __p_index);
2525       }
2526
2527       iterator
2528       erase(const iterator& __p)
2529       {
2530         size_t __p_index = __p.index();
2531         erase(__p_index, 1);
2532         return iterator(this, __p_index);
2533       }
2534
2535       rope
2536       substr(size_t __start, size_t __len = 1) const
2537       {
2538         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2539                                                  __start,
2540                                                  __start + __len));
2541       }
2542
2543       rope
2544       substr(iterator __start, iterator __end) const
2545       {
2546         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2547                                                  __start.index(),
2548                                                  __end.index()));
2549       }
2550
2551       rope
2552       substr(iterator __start) const
2553       {
2554         size_t __pos = __start.index();
2555         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2556                                                  __pos, __pos + 1));
2557       }
2558
2559       rope
2560       substr(const_iterator __start, const_iterator __end) const
2561       {
2562         // This might eventually take advantage of the cache in the
2563         // iterator.
2564         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2565                                                  __start.index(),
2566                                                  __end.index()));
2567       }
2568
2569       rope<_CharT, _Alloc>
2570       substr(const_iterator __start)
2571       {
2572         size_t __pos = __start.index();
2573         return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2574                                                  __pos, __pos + 1));
2575       }
2576
2577       static const size_type npos;
2578
2579       size_type find(_CharT __c, size_type __pos = 0) const;
2580
2581       size_type
2582       find(const _CharT* __s, size_type __pos = 0) const
2583       {
2584         size_type __result_pos;
2585         const_iterator __result =
2586           std::search(const_begin() + __pos, const_end(),
2587                       __s, __s + _S_char_ptr_len(__s));
2588         __result_pos = __result.index();
2589 #ifndef __STL_OLD_ROPE_SEMANTICS
2590         if (__result_pos == size())
2591           __result_pos = npos;
2592 #endif
2593         return __result_pos;
2594       }
2595
2596       iterator
2597       mutable_begin()
2598       { return(iterator(this, 0)); }
2599       
2600       iterator
2601       mutable_end()
2602       { return(iterator(this, size())); }
2603
2604       typedef std::reverse_iterator<iterator> reverse_iterator;
2605       
2606       reverse_iterator
2607       mutable_rbegin()
2608       { return reverse_iterator(mutable_end()); }
2609
2610       reverse_iterator
2611       mutable_rend()
2612       { return reverse_iterator(mutable_begin()); }
2613
2614       reference
2615       mutable_reference_at(size_type __pos)
2616       { return reference(this, __pos); }
2617
2618 #ifdef __STD_STUFF
2619       reference
2620       operator[] (size_type __pos)
2621       { return _char_ref_proxy(this, __pos); }
2622
2623       reference
2624       at(size_type __pos)
2625       {
2626         // if (__pos >= size()) throw out_of_range;  // XXX
2627         return (*this)[__pos];
2628       }
2629       
2630       void resize(size_type __n, _CharT __c) { }
2631       void resize(size_type __n) { }
2632       void reserve(size_type __res_arg = 0) { }
2633       
2634       size_type
2635       capacity() const
2636       { return max_size(); }
2637
2638       // Stuff below this line is dangerous because it's error prone.
2639       // I would really like to get rid of it.
2640       // copy function with funny arg ordering.
2641       size_type
2642       copy(_CharT* __buffer, size_type __n,
2643            size_type __pos = 0) const
2644       { return copy(__pos, __n, __buffer); }
2645
2646       iterator
2647       end()
2648       { return mutable_end(); }
2649
2650       iterator
2651       begin()
2652       { return mutable_begin(); }
2653
2654       reverse_iterator
2655       rend()
2656       { return mutable_rend(); }
2657       
2658       reverse_iterator
2659       rbegin()
2660       { return mutable_rbegin(); }
2661
2662 #else
2663       const_iterator
2664       end()
2665       { return const_end(); }
2666
2667       const_iterator
2668       begin()
2669       { return const_begin(); }
2670
2671       const_reverse_iterator
2672       rend()
2673       { return const_rend(); }
2674
2675       const_reverse_iterator
2676       rbegin()
2677       { return const_rbegin(); }
2678
2679 #endif
2680     };
2681
2682   template <class _CharT, class _Alloc>
2683     const typename rope<_CharT, _Alloc>::size_type
2684     rope<_CharT, _Alloc>::npos = (size_type)(-1);
2685   
2686   template <class _CharT, class _Alloc>
2687     inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2688                            const _Rope_const_iterator<_CharT, _Alloc>& __y)
2689     { return (__x._M_current_pos == __y._M_current_pos
2690               && __x._M_root == __y._M_root); }
2691
2692   template <class _CharT, class _Alloc>
2693     inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2694                           const _Rope_const_iterator<_CharT, _Alloc>& __y)
2695     { return (__x._M_current_pos < __y._M_current_pos); }
2696
2697   template <class _CharT, class _Alloc>
2698     inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2699                            const _Rope_const_iterator<_CharT, _Alloc>& __y)
2700     { return !(__x == __y); }
2701
2702   template <class _CharT, class _Alloc>
2703     inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2704                           const _Rope_const_iterator<_CharT, _Alloc>& __y)
2705     { return __y < __x; }
2706
2707   template <class _CharT, class _Alloc>
2708     inline bool
2709     operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2710                const _Rope_const_iterator<_CharT, _Alloc>& __y)
2711     { return !(__y < __x); }
2712
2713   template <class _CharT, class _Alloc>
2714     inline bool
2715     operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2716                const _Rope_const_iterator<_CharT, _Alloc>& __y)
2717     { return !(__x < __y); }
2718
2719   template <class _CharT, class _Alloc>
2720     inline ptrdiff_t
2721     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2722               const _Rope_const_iterator<_CharT, _Alloc>& __y)
2723     { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }
2724
2725   template <class _CharT, class _Alloc>
2726     inline _Rope_const_iterator<_CharT, _Alloc>
2727     operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2728     { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2729                                                   __x._M_current_pos - __n); }
2730
2731   template <class _CharT, class _Alloc>
2732     inline _Rope_const_iterator<_CharT, _Alloc>
2733     operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2734     { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2735                                                   __x._M_current_pos + __n); }
2736
2737   template <class _CharT, class _Alloc>
2738     inline _Rope_const_iterator<_CharT, _Alloc>
2739     operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x)
2740   { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2741                                                 __x._M_current_pos + __n); }
2742
2743   template <class _CharT, class _Alloc>
2744     inline bool
2745     operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
2746                const _Rope_iterator<_CharT, _Alloc>& __y)
2747     {return (__x._M_current_pos == __y._M_current_pos
2748              && __x._M_root_rope == __y._M_root_rope); }
2749   
2750   template <class _CharT, class _Alloc>
2751     inline bool
2752     operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
2753               const _Rope_iterator<_CharT, _Alloc>& __y)
2754     { return (__x._M_current_pos < __y._M_current_pos); }
2755
2756   template <class _CharT, class _Alloc>
2757     inline bool
2758     operator!=(const _Rope_iterator<_CharT, _Alloc>& __x,
2759                const _Rope_iterator<_CharT, _Alloc>& __y)
2760     { return !(__x == __y); }
2761
2762   template <class _CharT, class _Alloc>
2763     inline bool
2764     operator>(const _Rope_iterator<_CharT, _Alloc>& __x,
2765               const _Rope_iterator<_CharT, _Alloc>& __y)
2766     { return __y < __x; }
2767
2768   template <class _CharT, class _Alloc>
2769     inline bool
2770     operator<=(const _Rope_iterator<_CharT, _Alloc>& __x,
2771                const _Rope_iterator<_CharT, _Alloc>& __y)
2772     { return !(__y < __x); }
2773
2774   template <class _CharT, class _Alloc>
2775     inline bool
2776     operator>=(const _Rope_iterator<_CharT, _Alloc>& __x,
2777                const _Rope_iterator<_CharT, _Alloc>& __y)
2778     { return !(__x < __y); }
2779
2780   template <class _CharT, class _Alloc>
2781     inline ptrdiff_t
2782     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
2783               const _Rope_iterator<_CharT, _Alloc>& __y)
2784     { return ((ptrdiff_t)__x._M_current_pos
2785               - (ptrdiff_t)__y._M_current_pos); }
2786
2787   template <class _CharT, class _Alloc>
2788     inline _Rope_iterator<_CharT, _Alloc>
2789     operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
2790               ptrdiff_t __n)
2791     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2792                                             __x._M_current_pos - __n); }
2793
2794   template <class _CharT, class _Alloc>
2795     inline _Rope_iterator<_CharT, _Alloc>
2796     operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2797     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2798                                             __x._M_current_pos + __n); }
2799
2800   template <class _CharT, class _Alloc>
2801     inline _Rope_iterator<_CharT, _Alloc>
2802     operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x)
2803     { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2804                                             __x._M_current_pos + __n); }
2805
2806   template <class _CharT, class _Alloc>
2807     inline rope<_CharT, _Alloc>
2808     operator+(const rope<_CharT, _Alloc>& __left,
2809               const rope<_CharT, _Alloc>& __right)
2810     {
2811       // Inlining this should make it possible to keep __left and
2812       // __right in registers.
2813       typedef rope<_CharT, _Alloc> rope_type;
2814       return rope_type(rope_type::_S_concat(__left._M_tree_ptr, 
2815                                             __right._M_tree_ptr));
2816     }
2817
2818   template <class _CharT, class _Alloc>
2819     inline rope<_CharT, _Alloc>&
2820     operator+=(rope<_CharT, _Alloc>& __left,
2821                const rope<_CharT, _Alloc>& __right)
2822     {
2823       __left.append(__right);
2824       return __left;
2825     }
2826
2827   template <class _CharT, class _Alloc>
2828     inline rope<_CharT, _Alloc>
2829     operator+(const rope<_CharT, _Alloc>& __left,
2830               const _CharT* __right)
2831     {
2832       typedef rope<_CharT, _Alloc> rope_type;
2833       size_t __rlen = rope_type::_S_char_ptr_len(__right);
2834       return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2835                                                       __right, __rlen));
2836     }
2837
2838   template <class _CharT, class _Alloc>
2839     inline rope<_CharT, _Alloc>&
2840     operator+=(rope<_CharT, _Alloc>& __left,
2841                const _CharT* __right)
2842     {
2843       __left.append(__right);
2844       return __left;
2845     }
2846
2847   template <class _CharT, class _Alloc>
2848     inline rope<_CharT, _Alloc>
2849     operator+(const rope<_CharT, _Alloc>& __left, _CharT __right)
2850     {
2851       typedef rope<_CharT, _Alloc> rope_type;
2852       return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2853                                                       &__right, 1));
2854     }
2855
2856   template <class _CharT, class _Alloc>
2857     inline rope<_CharT, _Alloc>&
2858     operator+=(rope<_CharT, _Alloc>& __left, _CharT __right)
2859     {
2860       __left.append(__right);
2861       return __left;
2862     }
2863   
2864   template <class _CharT, class _Alloc>
2865     bool
2866     operator<(const rope<_CharT, _Alloc>& __left,
2867               const rope<_CharT, _Alloc>& __right)
2868     { return __left.compare(__right) < 0; }
2869
2870   template <class _CharT, class _Alloc>
2871     bool
2872     operator==(const rope<_CharT, _Alloc>& __left,
2873                const rope<_CharT, _Alloc>& __right)
2874     { return __left.compare(__right) == 0; }
2875
2876   template <class _CharT, class _Alloc>
2877     inline bool
2878     operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2879                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2880     { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); }
2881
2882   template <class _CharT, class _Alloc>
2883     inline bool
2884     operator!=(const rope<_CharT, _Alloc>& __x,
2885                const rope<_CharT, _Alloc>& __y)
2886     { return !(__x == __y); }
2887
2888   template <class _CharT, class _Alloc>
2889     inline bool
2890     operator>(const rope<_CharT, _Alloc>& __x,
2891               const rope<_CharT, _Alloc>& __y)
2892     { return __y < __x; }
2893
2894   template <class _CharT, class _Alloc>
2895     inline bool
2896     operator<=(const rope<_CharT, _Alloc>& __x,
2897                const rope<_CharT, _Alloc>& __y)
2898     { return !(__y < __x); }
2899
2900   template <class _CharT, class _Alloc>
2901     inline bool
2902     operator>=(const rope<_CharT, _Alloc>& __x,
2903                const rope<_CharT, _Alloc>& __y)
2904     { return !(__x < __y); }
2905
2906   template <class _CharT, class _Alloc>
2907     inline bool
2908     operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2909                const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2910     { return !(__x == __y); }
2911
2912   template<class _CharT, class _Traits, class _Alloc>
2913     std::basic_ostream<_CharT, _Traits>&
2914     operator<<(std::basic_ostream<_CharT, _Traits>& __o,
2915                const rope<_CharT, _Alloc>& __r);
2916
2917   typedef rope<char> crope;
2918   typedef rope<wchar_t> wrope;
2919
2920   inline crope::reference
2921   __mutable_reference_at(crope& __c, size_t __i)
2922   { return __c.mutable_reference_at(__i); }
2923
2924   inline wrope::reference
2925   __mutable_reference_at(wrope& __c, size_t __i)
2926   { return __c.mutable_reference_at(__i); }
2927
2928   template <class _CharT, class _Alloc>
2929     inline void
2930     swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
2931     { __x.swap(__y); }
2932
2933 _GLIBCXX_END_NAMESPACE_VERSION
2934 } // namespace
2935
2936
2937 namespace std _GLIBCXX_VISIBILITY(default)
2938
2939 namespace tr1
2940 {
2941 _GLIBCXX_BEGIN_NAMESPACE_VERSION
2942
2943   template<>
2944     struct hash<__gnu_cxx::crope>
2945     {
2946       size_t
2947       operator()(const __gnu_cxx::crope& __str) const
2948       {
2949         size_t __size = __str.size();
2950         if (0 == __size)
2951           return 0;
2952         return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2953       }
2954     };
2955
2956
2957   template<>
2958     struct hash<__gnu_cxx::wrope>
2959     {
2960       size_t
2961       operator()(const __gnu_cxx::wrope& __str) const
2962       {
2963         size_t __size = __str.size();
2964         if (0 == __size)
2965           return 0;
2966         return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2967       }
2968     };
2969
2970 _GLIBCXX_END_NAMESPACE_VERSION
2971 } // namespace tr1
2972 } // namespace std
2973
2974 # include <ext/ropeimpl.h>
2975
2976 #endif