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