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