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