libstdc++
rope
Go to the documentation of this file.
1 // SGI's rope class -*- C++ -*-
2 
3 // Copyright (C) 2001-2015 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 [email protected].
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 #if __cpp_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
1881  : _S_new_RopeFunction(__fn, __len, __delete_fn, _M_get_allocator());
1882  }
1883 
1884  rope(const rope& __x, const allocator_type& __a = allocator_type())
1885  : _Base(__x._M_tree_ptr, __a)
1886  { _S_ref(this->_M_tree_ptr); }
1887 
1888  ~rope() throw()
1889  { _S_unref(this->_M_tree_ptr); }
1890 
1891  rope&
1892  operator=(const rope& __x)
1893  {
1894  _RopeRep* __old = this->_M_tree_ptr;
1895  this->_M_tree_ptr = __x._M_tree_ptr;
1896  _S_ref(this->_M_tree_ptr);
1897  _S_unref(__old);
1898  return *this;
1899  }
1900 
1901  void
1902  clear()
1903  {
1904  _S_unref(this->_M_tree_ptr);
1905  this->_M_tree_ptr = 0;
1906  }
1907 
1908  void
1909  push_back(_CharT __x)
1910  {
1911  _RopeRep* __old = this->_M_tree_ptr;
1912  this->_M_tree_ptr
1913  = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
1914  _S_unref(__old);
1915  }
1916 
1917  void
1918  pop_back()
1919  {
1920  _RopeRep* __old = this->_M_tree_ptr;
1921  this->_M_tree_ptr = _S_substring(this->_M_tree_ptr,
1922  0, this->_M_tree_ptr->_M_size - 1);
1923  _S_unref(__old);
1924  }
1925 
1926  _CharT
1927  back() const
1928  { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); }
1929 
1930  void
1931  push_front(_CharT __x)
1932  {
1933  _RopeRep* __old = this->_M_tree_ptr;
1934  _RopeRep* __left =
1935  __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator());
1936  __try
1937  {
1938  this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
1939  _S_unref(__old);
1940  _S_unref(__left);
1941  }
1942  __catch(...)
1943  {
1944  _S_unref(__left);
1945  __throw_exception_again;
1946  }
1947  }
1948 
1949  void
1950  pop_front()
1951  {
1952  _RopeRep* __old = this->_M_tree_ptr;
1953  this->_M_tree_ptr
1954  = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
1955  _S_unref(__old);
1956  }
1957 
1958  _CharT
1959  front() const
1960  { return _S_fetch(this->_M_tree_ptr, 0); }
1961 
1962  void
1963  balance()
1964  {
1965  _RopeRep* __old = this->_M_tree_ptr;
1966  this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
1967  _S_unref(__old);
1968  }
1969 
1970  void
1971  copy(_CharT* __buffer) const
1972  {
1973  _Destroy_const(__buffer, __buffer + size(), _M_get_allocator());
1974  _S_flatten(this->_M_tree_ptr, __buffer);
1975  }
1976 
1977  // This is the copy function from the standard, but
1978  // with the arguments reordered to make it consistent with the
1979  // rest of the interface.
1980  // Note that this guaranteed not to compile if the draft standard
1981  // order is assumed.
1982  size_type
1983  copy(size_type __pos, size_type __n, _CharT* __buffer) const
1984  {
1985  size_t __size = size();
1986  size_t __len = (__pos + __n > __size? __size - __pos : __n);
1987 
1988  _Destroy_const(__buffer, __buffer + __len, _M_get_allocator());
1989  _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
1990  return __len;
1991  }
1992 
1993  // Print to stdout, exposing structure. May be useful for
1994  // performance debugging.
1995  void
1996  dump()
1997  { _S_dump(this->_M_tree_ptr); }
1998 
1999  // Convert to 0 terminated string in new allocated memory.
2000  // Embedded 0s in the input do not terminate the copy.
2001  const _CharT* c_str() const;
2002 
2003  // As above, but also use the flattened representation as
2004  // the new rope representation.
2005  const _CharT* replace_with_c_str();
2006 
2007  // Reclaim memory for the c_str generated flattened string.
2008  // Intentionally undocumented, since it's hard to say when this
2009  // is safe for multiple threads.
2010  void
2011  delete_c_str ()
2012  {
2013  if (0 == this->_M_tree_ptr)
2014  return;
2015  if (__detail::_S_leaf == this->_M_tree_ptr->_M_tag &&
2016  ((_RopeLeaf*)this->_M_tree_ptr)->_M_data ==
2017  this->_M_tree_ptr->_M_c_string)
2018  {
2019  // Representation shared
2020  return;
2021  }
2022 #ifndef __GC
2023  this->_M_tree_ptr->_M_free_c_string();
2024 #endif
2025  this->_M_tree_ptr->_M_c_string = 0;
2026  }
2027 
2028  _CharT
2029  operator[] (size_type __pos) const
2030  { return _S_fetch(this->_M_tree_ptr, __pos); }
2031 
2032  _CharT
2033  at(size_type __pos) const
2034  {
2035  // if (__pos >= size()) throw out_of_range; // XXX
2036  return (*this)[__pos];
2037  }
2038 
2039  const_iterator
2040  begin() const
2041  { return(const_iterator(this->_M_tree_ptr, 0)); }
2042 
2043  // An easy way to get a const iterator from a non-const container.
2044  const_iterator
2045  const_begin() const
2046  { return(const_iterator(this->_M_tree_ptr, 0)); }
2047 
2048  const_iterator
2049  end() const
2050  { return(const_iterator(this->_M_tree_ptr, size())); }
2051 
2052  const_iterator
2053  const_end() const
2054  { return(const_iterator(this->_M_tree_ptr, size())); }
2055 
2056  size_type
2057  size() const
2058  { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); }
2059 
2060  size_type
2061  length() const
2062  { return size(); }
2063 
2064  size_type
2065  max_size() const
2066  {
2067  return _S_min_len[int(__detail::_S_max_rope_depth) - 1] - 1;
2068  // Guarantees that the result can be sufficiently
2069  // balanced. Longer ropes will probably still work,
2070  // but it's harder to make guarantees.
2071  }
2072 
2073  typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
2074 
2075  const_reverse_iterator
2076  rbegin() const
2077  { return const_reverse_iterator(end()); }
2078 
2079  const_reverse_iterator
2080  const_rbegin() const
2081  { return const_reverse_iterator(end()); }
2082 
2083  const_reverse_iterator
2084  rend() const
2085  { return const_reverse_iterator(begin()); }
2086 
2087  const_reverse_iterator
2088  const_rend() const
2089  { return const_reverse_iterator(begin()); }
2090 
2091  template<class _CharT2, class _Alloc2>
2092  friend rope<_CharT2, _Alloc2>
2093  operator+(const rope<_CharT2, _Alloc2>& __left,
2094  const rope<_CharT2, _Alloc2>& __right);
2095 
2096  template<class _CharT2, class _Alloc2>
2097  friend rope<_CharT2, _Alloc2>
2098  operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right);
2099 
2100  template<class _CharT2, class _Alloc2>
2101  friend rope<_CharT2, _Alloc2>
2102  operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right);
2103 
2104  // The symmetric cases are intentionally omitted, since they're
2105  // presumed to be less common, and we don't handle them as well.
2106 
2107  // The following should really be templatized. The first
2108  // argument should be an input iterator or forward iterator with
2109  // value_type _CharT.
2110  rope&
2111  append(const _CharT* __iter, size_t __n)
2112  {
2113  _RopeRep* __result =
2114  _S_destr_concat_char_iter(this->_M_tree_ptr, __iter, __n);
2115  _S_unref(this->_M_tree_ptr);
2116  this->_M_tree_ptr = __result;
2117  return *this;
2118  }
2119 
2120  rope&
2121  append(const _CharT* __c_string)
2122  {
2123  size_t __len = _S_char_ptr_len(__c_string);
2124  append(__c_string, __len);
2125  return(*this);
2126  }
2127 
2128  rope&
2129  append(const _CharT* __s, const _CharT* __e)
2130  {
2131  _RopeRep* __result =
2132  _S_destr_concat_char_iter(this->_M_tree_ptr, __s, __e - __s);
2133  _S_unref(this->_M_tree_ptr);
2134  this->_M_tree_ptr = __result;
2135  return *this;
2136  }
2137 
2138  rope&
2139  append(const_iterator __s, const_iterator __e)
2140  {
2141  _Self_destruct_ptr __appendee(_S_substring(__s._M_root,
2142  __s._M_current_pos,
2143  __e._M_current_pos));
2144  _RopeRep* __result = _S_concat(this->_M_tree_ptr,
2145  (_RopeRep*)__appendee);
2146  _S_unref(this->_M_tree_ptr);
2147  this->_M_tree_ptr = __result;
2148  return *this;
2149  }
2150 
2151  rope&
2152  append(_CharT __c)
2153  {
2154  _RopeRep* __result =
2155  _S_destr_concat_char_iter(this->_M_tree_ptr, &__c, 1);
2156  _S_unref(this->_M_tree_ptr);
2157  this->_M_tree_ptr = __result;
2158  return *this;
2159  }
2160 
2161  rope&
2162  append()
2163  { return append(_CharT()); } // XXX why?
2164 
2165  rope&
2166  append(const rope& __y)
2167  {
2168  _RopeRep* __result = _S_concat(this->_M_tree_ptr, __y._M_tree_ptr);
2169  _S_unref(this->_M_tree_ptr);
2170  this->_M_tree_ptr = __result;
2171  return *this;
2172  }
2173 
2174  rope&
2175  append(size_t __n, _CharT __c)
2176  {
2177  rope<_CharT,_Alloc> __last(__n, __c);
2178  return append(__last);
2179  }
2180 
2181  void
2182  swap(rope& __b)
2183  {
2184  _RopeRep* __tmp = this->_M_tree_ptr;
2185  this->_M_tree_ptr = __b._M_tree_ptr;
2186  __b._M_tree_ptr = __tmp;
2187  }
2188 
2189  protected:
2190  // Result is included in refcount.
2191  static _RopeRep*
2192  replace(_RopeRep* __old, size_t __pos1,
2193  size_t __pos2, _RopeRep* __r)
2194  {
2195  if (0 == __old)
2196  {
2197  _S_ref(__r);
2198  return __r;
2199  }
2200  _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
2201  _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size));
2202  _RopeRep* __result;
2203 
2204  if (0 == __r)
2205  __result = _S_concat(__left, __right);
2206  else
2207  {
2208  _Self_destruct_ptr __left_result(_S_concat(__left, __r));
2209  __result = _S_concat(__left_result, __right);
2210  }
2211  return __result;
2212  }
2213 
2214  public:
2215  void
2216  insert(size_t __p, const rope& __r)
2217  {
2218  _RopeRep* __result =
2219  replace(this->_M_tree_ptr, __p, __p, __r._M_tree_ptr);
2220  _S_unref(this->_M_tree_ptr);
2221  this->_M_tree_ptr = __result;
2222  }
2223 
2224  void
2225  insert(size_t __p, size_t __n, _CharT __c)
2226  {
2227  rope<_CharT,_Alloc> __r(__n,__c);
2228  insert(__p, __r);
2229  }
2230 
2231  void
2232  insert(size_t __p, const _CharT* __i, size_t __n)
2233  {
2234  _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p));
2235  _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr,
2236  __p, size()));
2237  _Self_destruct_ptr __left_result(_S_concat_char_iter(__left, __i, __n));
2238  // _S_ destr_concat_char_iter should be safe here.
2239  // But as it stands it's probably not a win, since __left
2240  // is likely to have additional references.
2241  _RopeRep* __result = _S_concat(__left_result, __right);
2242  _S_unref(this->_M_tree_ptr);
2243  this->_M_tree_ptr = __result;
2244  }
2245 
2246  void
2247  insert(size_t __p, const _CharT* __c_string)
2248  { insert(__p, __c_string, _S_char_ptr_len(__c_string)); }
2249 
2250  void
2251  insert(size_t __p, _CharT __c)
2252  { insert(__p, &__c, 1); }
2253 
2254  void
2255  insert(size_t __p)
2256  {
2257  _CharT __c = _CharT();
2258  insert(__p, &__c, 1);
2259  }
2260 
2261  void
2262  insert(size_t __p, const _CharT* __i, const _CharT* __j)
2263  {
2264  rope __r(__i, __j);
2265  insert(__p, __r);
2266  }
2267 
2268  void
2269  insert(size_t __p, const const_iterator& __i,
2270  const const_iterator& __j)
2271  {
2272  rope __r(__i, __j);
2273  insert(__p, __r);
2274  }
2275 
2276  void
2277  insert(size_t __p, const iterator& __i,
2278  const iterator& __j)
2279  {
2280  rope __r(__i, __j);
2281  insert(__p, __r);
2282  }
2283 
2284  // (position, length) versions of replace operations:
2285 
2286  void
2287  replace(size_t __p, size_t __n, const rope& __r)
2288  {
2289  _RopeRep* __result =
2290  replace(this->_M_tree_ptr, __p, __p + __n, __r._M_tree_ptr);
2291  _S_unref(this->_M_tree_ptr);
2292  this->_M_tree_ptr = __result;
2293  }
2294 
2295  void
2296  replace(size_t __p, size_t __n,
2297  const _CharT* __i, size_t __i_len)
2298  {
2299  rope __r(__i, __i_len);
2300  replace(__p, __n, __r);
2301  }
2302 
2303  void
2304  replace(size_t __p, size_t __n, _CharT __c)
2305  {
2306  rope __r(__c);
2307  replace(__p, __n, __r);
2308  }
2309 
2310  void
2311  replace(size_t __p, size_t __n, const _CharT* __c_string)
2312  {
2313  rope __r(__c_string);
2314  replace(__p, __n, __r);
2315  }
2316 
2317  void
2318  replace(size_t __p, size_t __n,
2319  const _CharT* __i, const _CharT* __j)
2320  {
2321  rope __r(__i, __j);
2322  replace(__p, __n, __r);
2323  }
2324 
2325  void
2326  replace(size_t __p, size_t __n,
2327  const const_iterator& __i, const const_iterator& __j)
2328  {
2329  rope __r(__i, __j);
2330  replace(__p, __n, __r);
2331  }
2332 
2333  void
2334  replace(size_t __p, size_t __n,
2335  const iterator& __i, const iterator& __j)
2336  {
2337  rope __r(__i, __j);
2338  replace(__p, __n, __r);
2339  }
2340 
2341  // Single character variants:
2342  void
2343  replace(size_t __p, _CharT __c)
2344  {
2345  iterator __i(this, __p);
2346  *__i = __c;
2347  }
2348 
2349  void
2350  replace(size_t __p, const rope& __r)
2351  { replace(__p, 1, __r); }
2352 
2353  void
2354  replace(size_t __p, const _CharT* __i, size_t __i_len)
2355  { replace(__p, 1, __i, __i_len); }
2356 
2357  void
2358  replace(size_t __p, const _CharT* __c_string)
2359  { replace(__p, 1, __c_string); }
2360 
2361  void
2362  replace(size_t __p, const _CharT* __i, const _CharT* __j)
2363  { replace(__p, 1, __i, __j); }
2364 
2365  void
2366  replace(size_t __p, const const_iterator& __i,
2367  const const_iterator& __j)
2368  { replace(__p, 1, __i, __j); }
2369 
2370  void
2371  replace(size_t __p, const iterator& __i,
2372  const iterator& __j)
2373  { replace(__p, 1, __i, __j); }
2374 
2375  // Erase, (position, size) variant.
2376  void
2377  erase(size_t __p, size_t __n)
2378  {
2379  _RopeRep* __result = replace(this->_M_tree_ptr, __p,
2380  __p + __n, 0);
2381  _S_unref(this->_M_tree_ptr);
2382  this->_M_tree_ptr = __result;
2383  }
2384 
2385  // Erase, single character
2386  void
2387  erase(size_t __p)
2388  { erase(__p, __p + 1); }
2389 
2390  // Insert, iterator variants.
2391  iterator
2392  insert(const iterator& __p, const rope& __r)
2393  {
2394  insert(__p.index(), __r);
2395  return __p;
2396  }
2397 
2398  iterator
2399  insert(const iterator& __p, size_t __n, _CharT __c)
2400  {
2401  insert(__p.index(), __n, __c);
2402  return __p;
2403  }
2404 
2405  iterator insert(const iterator& __p, _CharT __c)
2406  {
2407  insert(__p.index(), __c);
2408  return __p;
2409  }
2410 
2411  iterator
2412  insert(const iterator& __p )
2413  {
2414  insert(__p.index());
2415  return __p;
2416  }
2417 
2418  iterator
2419  insert(const iterator& __p, const _CharT* c_string)
2420  {
2421  insert(__p.index(), c_string);
2422  return __p;
2423  }
2424 
2425  iterator
2426  insert(const iterator& __p, const _CharT* __i, size_t __n)
2427  {
2428  insert(__p.index(), __i, __n);
2429  return __p;
2430  }
2431 
2432  iterator
2433  insert(const iterator& __p, const _CharT* __i,
2434  const _CharT* __j)
2435  {
2436  insert(__p.index(), __i, __j);
2437  return __p;
2438  }
2439 
2440  iterator
2441  insert(const iterator& __p,
2442  const const_iterator& __i, const const_iterator& __j)
2443  {
2444  insert(__p.index(), __i, __j);
2445  return __p;
2446  }
2447 
2448  iterator
2449  insert(const iterator& __p,
2450  const iterator& __i, const iterator& __j)
2451  {
2452  insert(__p.index(), __i, __j);
2453  return __p;
2454  }
2455 
2456  // Replace, range variants.
2457  void
2458  replace(const iterator& __p, const iterator& __q, const rope& __r)
2459  { replace(__p.index(), __q.index() - __p.index(), __r); }
2460 
2461  void
2462  replace(const iterator& __p, const iterator& __q, _CharT __c)
2463  { replace(__p.index(), __q.index() - __p.index(), __c); }
2464 
2465  void
2466  replace(const iterator& __p, const iterator& __q,
2467  const _CharT* __c_string)
2468  { replace(__p.index(), __q.index() - __p.index(), __c_string); }
2469 
2470  void
2471  replace(const iterator& __p, const iterator& __q,
2472  const _CharT* __i, size_t __n)
2473  { replace(__p.index(), __q.index() - __p.index(), __i, __n); }
2474 
2475  void
2476  replace(const iterator& __p, const iterator& __q,
2477  const _CharT* __i, const _CharT* __j)
2478  { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2479 
2480  void
2481  replace(const iterator& __p, const iterator& __q,
2482  const const_iterator& __i, const const_iterator& __j)
2483  { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2484 
2485  void
2486  replace(const iterator& __p, const iterator& __q,
2487  const iterator& __i, const iterator& __j)
2488  { replace(__p.index(), __q.index() - __p.index(), __i, __j); }
2489 
2490  // Replace, iterator variants.
2491  void
2492  replace(const iterator& __p, const rope& __r)
2493  { replace(__p.index(), __r); }
2494 
2495  void
2496  replace(const iterator& __p, _CharT __c)
2497  { replace(__p.index(), __c); }
2498 
2499  void
2500  replace(const iterator& __p, const _CharT* __c_string)
2501  { replace(__p.index(), __c_string); }
2502 
2503  void
2504  replace(const iterator& __p, const _CharT* __i, size_t __n)
2505  { replace(__p.index(), __i, __n); }
2506 
2507  void
2508  replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
2509  { replace(__p.index(), __i, __j); }
2510 
2511  void
2512  replace(const iterator& __p, const_iterator __i, const_iterator __j)
2513  { replace(__p.index(), __i, __j); }
2514 
2515  void
2516  replace(const iterator& __p, iterator __i, iterator __j)
2517  { replace(__p.index(), __i, __j); }
2518 
2519  // Iterator and range variants of erase
2520  iterator
2521  erase(const iterator& __p, const iterator& __q)
2522  {
2523  size_t __p_index = __p.index();
2524  erase(__p_index, __q.index() - __p_index);
2525  return iterator(this, __p_index);
2526  }
2527 
2528  iterator
2529  erase(const iterator& __p)
2530  {
2531  size_t __p_index = __p.index();
2532  erase(__p_index, 1);
2533  return iterator(this, __p_index);
2534  }
2535 
2536  rope
2537  substr(size_t __start, size_t __len = 1) const
2538  {
2539  return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2540  __start,
2541  __start + __len));
2542  }
2543 
2544  rope
2545  substr(iterator __start, iterator __end) const
2546  {
2547  return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2548  __start.index(),
2549  __end.index()));
2550  }
2551 
2552  rope
2553  substr(iterator __start) const
2554  {
2555  size_t __pos = __start.index();
2556  return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2557  __pos, __pos + 1));
2558  }
2559 
2560  rope
2561  substr(const_iterator __start, const_iterator __end) const
2562  {
2563  // This might eventually take advantage of the cache in the
2564  // iterator.
2565  return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2566  __start.index(),
2567  __end.index()));
2568  }
2569 
2570  rope<_CharT, _Alloc>
2571  substr(const_iterator __start)
2572  {
2573  size_t __pos = __start.index();
2574  return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2575  __pos, __pos + 1));
2576  }
2577 
2578  static const size_type npos;
2579 
2580  size_type find(_CharT __c, size_type __pos = 0) const;
2581 
2582  size_type
2583  find(const _CharT* __s, size_type __pos = 0) const
2584  {
2585  size_type __result_pos;
2586  const_iterator __result =
2587  std::search(const_begin() + __pos, const_end(),
2588  __s, __s + _S_char_ptr_len(__s));
2589  __result_pos = __result.index();
2590 #ifndef __STL_OLD_ROPE_SEMANTICS
2591  if (__result_pos == size())
2592  __result_pos = npos;
2593 #endif
2594  return __result_pos;
2595  }
2596 
2597  iterator
2598  mutable_begin()
2599  { return(iterator(this, 0)); }
2600 
2601  iterator
2602  mutable_end()
2603  { return(iterator(this, size())); }
2604 
2605  typedef std::reverse_iterator<iterator> reverse_iterator;
2606 
2607  reverse_iterator
2608  mutable_rbegin()
2609  { return reverse_iterator(mutable_end()); }
2610 
2611  reverse_iterator
2612  mutable_rend()
2613  { return reverse_iterator(mutable_begin()); }
2614 
2615  reference
2616  mutable_reference_at(size_type __pos)
2617  { return reference(this, __pos); }
2618 
2619 #ifdef __STD_STUFF
2620  reference
2621  operator[] (size_type __pos)
2622  { return _char_ref_proxy(this, __pos); }
2623 
2624  reference
2625  at(size_type __pos)
2626  {
2627  // if (__pos >= size()) throw out_of_range; // XXX
2628  return (*this)[__pos];
2629  }
2630 
2631  void resize(size_type __n, _CharT __c) { }
2632  void resize(size_type __n) { }
2633  void reserve(size_type __res_arg = 0) { }
2634 
2635  size_type
2636  capacity() const
2637  { return max_size(); }
2638 
2639  // Stuff below this line is dangerous because it's error prone.
2640  // I would really like to get rid of it.
2641  // copy function with funny arg ordering.
2642  size_type
2643  copy(_CharT* __buffer, size_type __n,
2644  size_type __pos = 0) const
2645  { return copy(__pos, __n, __buffer); }
2646 
2647  iterator
2648  end()
2649  { return mutable_end(); }
2650 
2651  iterator
2652  begin()
2653  { return mutable_begin(); }
2654 
2655  reverse_iterator
2656  rend()
2657  { return mutable_rend(); }
2658 
2659  reverse_iterator
2660  rbegin()
2661  { return mutable_rbegin(); }
2662 
2663 #else
2664  const_iterator
2665  end()
2666  { return const_end(); }
2667 
2668  const_iterator
2669  begin()
2670  { return const_begin(); }
2671 
2672  const_reverse_iterator
2673  rend()
2674  { return const_rend(); }
2675 
2676  const_reverse_iterator
2677  rbegin()
2678  { return const_rbegin(); }
2679 
2680 #endif
2681  };
2682 
2683  template <class _CharT, class _Alloc>
2684  const typename rope<_CharT, _Alloc>::size_type
2685  rope<_CharT, _Alloc>::npos = (size_type)(-1);
2686 
2687  template <class _CharT, class _Alloc>
2688  inline bool operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2689  const _Rope_const_iterator<_CharT, _Alloc>& __y)
2690  { return (__x._M_current_pos == __y._M_current_pos
2691  && __x._M_root == __y._M_root); }
2692 
2693  template <class _CharT, class _Alloc>
2694  inline bool operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2695  const _Rope_const_iterator<_CharT, _Alloc>& __y)
2696  { return (__x._M_current_pos < __y._M_current_pos); }
2697 
2698  template <class _CharT, class _Alloc>
2699  inline bool operator!=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2700  const _Rope_const_iterator<_CharT, _Alloc>& __y)
2701  { return !(__x == __y); }
2702 
2703  template <class _CharT, class _Alloc>
2704  inline bool operator>(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2705  const _Rope_const_iterator<_CharT, _Alloc>& __y)
2706  { return __y < __x; }
2707 
2708  template <class _CharT, class _Alloc>
2709  inline bool
2710  operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2711  const _Rope_const_iterator<_CharT, _Alloc>& __y)
2712  { return !(__y < __x); }
2713 
2714  template <class _CharT, class _Alloc>
2715  inline bool
2716  operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2717  const _Rope_const_iterator<_CharT, _Alloc>& __y)
2718  { return !(__x < __y); }
2719 
2720  template <class _CharT, class _Alloc>
2721  inline ptrdiff_t
2722  operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2723  const _Rope_const_iterator<_CharT, _Alloc>& __y)
2724  { return (ptrdiff_t)__x._M_current_pos - (ptrdiff_t)__y._M_current_pos; }
2725 
2726  template <class _CharT, class _Alloc>
2727  inline _Rope_const_iterator<_CharT, _Alloc>
2728  operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2729  { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2730  __x._M_current_pos - __n); }
2731 
2732  template <class _CharT, class _Alloc>
2733  inline _Rope_const_iterator<_CharT, _Alloc>
2734  operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2735  { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2736  __x._M_current_pos + __n); }
2737 
2738  template <class _CharT, class _Alloc>
2739  inline _Rope_const_iterator<_CharT, _Alloc>
2740  operator+(ptrdiff_t __n, const _Rope_const_iterator<_CharT, _Alloc>& __x)
2741  { return _Rope_const_iterator<_CharT, _Alloc>(__x._M_root,
2742  __x._M_current_pos + __n); }
2743 
2744  template <class _CharT, class _Alloc>
2745  inline bool
2746  operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
2747  const _Rope_iterator<_CharT, _Alloc>& __y)
2748  {return (__x._M_current_pos == __y._M_current_pos
2749  && __x._M_root_rope == __y._M_root_rope); }
2750 
2751  template <class _CharT, class _Alloc>
2752  inline bool
2753  operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
2754  const _Rope_iterator<_CharT, _Alloc>& __y)
2755  { return (__x._M_current_pos < __y._M_current_pos); }
2756 
2757  template <class _CharT, class _Alloc>
2758  inline bool
2759  operator!=(const _Rope_iterator<_CharT, _Alloc>& __x,
2760  const _Rope_iterator<_CharT, _Alloc>& __y)
2761  { return !(__x == __y); }
2762 
2763  template <class _CharT, class _Alloc>
2764  inline bool
2765  operator>(const _Rope_iterator<_CharT, _Alloc>& __x,
2766  const _Rope_iterator<_CharT, _Alloc>& __y)
2767  { return __y < __x; }
2768 
2769  template <class _CharT, class _Alloc>
2770  inline bool
2771  operator<=(const _Rope_iterator<_CharT, _Alloc>& __x,
2772  const _Rope_iterator<_CharT, _Alloc>& __y)
2773  { return !(__y < __x); }
2774 
2775  template <class _CharT, class _Alloc>
2776  inline bool
2777  operator>=(const _Rope_iterator<_CharT, _Alloc>& __x,
2778  const _Rope_iterator<_CharT, _Alloc>& __y)
2779  { return !(__x < __y); }
2780 
2781  template <class _CharT, class _Alloc>
2782  inline ptrdiff_t
2783  operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
2784  const _Rope_iterator<_CharT, _Alloc>& __y)
2785  { return ((ptrdiff_t)__x._M_current_pos
2786  - (ptrdiff_t)__y._M_current_pos); }
2787 
2788  template <class _CharT, class _Alloc>
2789  inline _Rope_iterator<_CharT, _Alloc>
2790  operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
2791  ptrdiff_t __n)
2792  { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2793  __x._M_current_pos - __n); }
2794 
2795  template <class _CharT, class _Alloc>
2796  inline _Rope_iterator<_CharT, _Alloc>
2797  operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n)
2798  { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2799  __x._M_current_pos + __n); }
2800 
2801  template <class _CharT, class _Alloc>
2802  inline _Rope_iterator<_CharT, _Alloc>
2803  operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x)
2804  { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2805  __x._M_current_pos + __n); }
2806 
2807  template <class _CharT, class _Alloc>
2808  inline rope<_CharT, _Alloc>
2809  operator+(const rope<_CharT, _Alloc>& __left,
2810  const rope<_CharT, _Alloc>& __right)
2811  {
2812  // Inlining this should make it possible to keep __left and
2813  // __right in registers.
2814  typedef rope<_CharT, _Alloc> rope_type;
2815  return rope_type(rope_type::_S_concat(__left._M_tree_ptr,
2816  __right._M_tree_ptr));
2817  }
2818 
2819  template <class _CharT, class _Alloc>
2820  inline rope<_CharT, _Alloc>&
2821  operator+=(rope<_CharT, _Alloc>& __left,
2822  const rope<_CharT, _Alloc>& __right)
2823  {
2824  __left.append(__right);
2825  return __left;
2826  }
2827 
2828  template <class _CharT, class _Alloc>
2829  inline rope<_CharT, _Alloc>
2830  operator+(const rope<_CharT, _Alloc>& __left,
2831  const _CharT* __right)
2832  {
2833  typedef rope<_CharT, _Alloc> rope_type;
2834  size_t __rlen = rope_type::_S_char_ptr_len(__right);
2835  return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2836  __right, __rlen));
2837  }
2838 
2839  template <class _CharT, class _Alloc>
2840  inline rope<_CharT, _Alloc>&
2841  operator+=(rope<_CharT, _Alloc>& __left,
2842  const _CharT* __right)
2843  {
2844  __left.append(__right);
2845  return __left;
2846  }
2847 
2848  template <class _CharT, class _Alloc>
2849  inline rope<_CharT, _Alloc>
2850  operator+(const rope<_CharT, _Alloc>& __left, _CharT __right)
2851  {
2852  typedef rope<_CharT, _Alloc> rope_type;
2853  return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2854  &__right, 1));
2855  }
2856 
2857  template <class _CharT, class _Alloc>
2858  inline rope<_CharT, _Alloc>&
2859  operator+=(rope<_CharT, _Alloc>& __left, _CharT __right)
2860  {
2861  __left.append(__right);
2862  return __left;
2863  }
2864 
2865  template <class _CharT, class _Alloc>
2866  bool
2867  operator<(const rope<_CharT, _Alloc>& __left,
2868  const rope<_CharT, _Alloc>& __right)
2869  { return __left.compare(__right) < 0; }
2870 
2871  template <class _CharT, class _Alloc>
2872  bool
2873  operator==(const rope<_CharT, _Alloc>& __left,
2874  const rope<_CharT, _Alloc>& __right)
2875  { return __left.compare(__right) == 0; }
2876 
2877  template <class _CharT, class _Alloc>
2878  inline bool
2879  operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2880  const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2881  { return (__x._M_pos == __y._M_pos && __x._M_root == __y._M_root); }
2882 
2883  template <class _CharT, class _Alloc>
2884  inline bool
2885  operator!=(const rope<_CharT, _Alloc>& __x,
2886  const rope<_CharT, _Alloc>& __y)
2887  { return !(__x == __y); }
2888 
2889  template <class _CharT, class _Alloc>
2890  inline bool
2891  operator>(const rope<_CharT, _Alloc>& __x,
2892  const rope<_CharT, _Alloc>& __y)
2893  { return __y < __x; }
2894 
2895  template <class _CharT, class _Alloc>
2896  inline bool
2897  operator<=(const rope<_CharT, _Alloc>& __x,
2898  const rope<_CharT, _Alloc>& __y)
2899  { return !(__y < __x); }
2900 
2901  template <class _CharT, class _Alloc>
2902  inline bool
2903  operator>=(const rope<_CharT, _Alloc>& __x,
2904  const rope<_CharT, _Alloc>& __y)
2905  { return !(__x < __y); }
2906 
2907  template <class _CharT, class _Alloc>
2908  inline bool
2909  operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2910  const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2911  { return !(__x == __y); }
2912 
2913  template<class _CharT, class _Traits, class _Alloc>
2914  std::basic_ostream<_CharT, _Traits>&
2915  operator<<(std::basic_ostream<_CharT, _Traits>& __o,
2916  const rope<_CharT, _Alloc>& __r);
2917 
2918  typedef rope<char> crope;
2919  typedef rope<wchar_t> wrope;
2920 
2921  inline crope::reference
2922  __mutable_reference_at(crope& __c, size_t __i)
2923  { return __c.mutable_reference_at(__i); }
2924 
2925  inline wrope::reference
2926  __mutable_reference_at(wrope& __c, size_t __i)
2927  { return __c.mutable_reference_at(__i); }
2928 
2929  template <class _CharT, class _Alloc>
2930  inline void
2931  swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
2932  { __x.swap(__y); }
2933 
2934 _GLIBCXX_END_NAMESPACE_VERSION
2935 } // namespace
2936 
2937 
2938 namespace std _GLIBCXX_VISIBILITY(default)
2939 {
2940 namespace tr1
2941 {
2942 _GLIBCXX_BEGIN_NAMESPACE_VERSION
2943 
2944  template<>
2945  struct hash<__gnu_cxx::crope>
2946  {
2947  size_t
2948  operator()(const __gnu_cxx::crope& __str) const
2949  {
2950  size_t __size = __str.size();
2951  if (0 == __size)
2952  return 0;
2953  return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2954  }
2955  };
2956 
2957 
2958  template<>
2959  struct hash<__gnu_cxx::wrope>
2960  {
2961  size_t
2962  operator()(const __gnu_cxx::wrope& __str) const
2963  {
2964  size_t __size = __str.size();
2965  if (0 == __size)
2966  return 0;
2967  return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2968  }
2969  };
2970 
2971 _GLIBCXX_END_NAMESPACE_VERSION
2972 } // namespace tr1
2973 } // namespace std
2974 
2975 # include <ext/ropeimpl.h>
2976 
2977 #endif