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