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