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