1 // SGI's rope class -*- C++ -*-
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009
4 // Free Software Foundation, Inc.
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)
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.
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.
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/>.
28 * Silicon Graphics Computer Systems, Inc.
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.
40 * This file is a GNU extension to the Standard C++ Library (possibly
41 * containing extensions from the HP/SGI STL subset).
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>
58 # define __GC_CONST const
60 # define __GC_CONST // constant except for deallocation
63 #include <ext/memory> // For uninitialized_copy_n
65 _GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx)
69 enum { _S_max_rope_depth = 45 };
70 enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
71 } // namespace __detail
78 // See libstdc++/36832.
79 template<typename _ForwardIterator, typename _Allocator>
81 _Destroy_const(_ForwardIterator __first,
82 _ForwardIterator __last, _Allocator __alloc)
84 for (; __first != __last; ++__first)
85 __alloc.destroy(&*__first);
88 template<typename _ForwardIterator, typename _Tp>
90 _Destroy_const(_ForwardIterator __first,
91 _ForwardIterator __last, allocator<_Tp>)
92 { _Destroy(__first, __last); }
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.
97 // The end-of-C-string character.
98 // This is what the draft standard says it should be.
99 template <class _CharT>
104 // Test for basic character types.
105 // For basic character types leaves having a trailing eos.
106 template <class _CharT>
108 _S_is_basic_char_type(_CharT*)
111 template <class _CharT>
113 _S_is_one_byte_char_type(_CharT*)
117 _S_is_basic_char_type(char*)
121 _S_is_one_byte_char_type(char*)
125 _S_is_basic_char_type(wchar_t*)
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>
132 _S_cond_store_eos(_CharT&) { }
135 _S_cond_store_eos(char& __c)
139 _S_cond_store_eos(wchar_t& __c)
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>
150 virtual ~char_producer() { };
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.
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.
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.
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>
180 typedef typename _Sequence::value_type value_type;
182 _Sequence* _M_prefix;
183 value_type _M_buffer[_Buf_sz];
190 _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
198 : _M_prefix(0), _M_buf_count(0) { }
200 sequence_buffer(const sequence_buffer& __x)
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);
207 sequence_buffer(sequence_buffer& __x)
210 _M_prefix = __x._M_prefix;
214 sequence_buffer(_Sequence& __s)
215 : _M_prefix(&__s), _M_buf_count(0) { }
218 operator=(sequence_buffer& __x)
221 _M_prefix = __x._M_prefix;
227 operator=(const sequence_buffer& __x)
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);
236 push_back(value_type __x)
238 if (_M_buf_count < _Buf_sz)
240 _M_buffer[_M_buf_count] = __x;
252 append(value_type* __s, size_t __len)
254 if (__len + _M_buf_count <= _Buf_sz)
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;
261 else if (0 == _M_buf_count)
262 _M_prefix->append(__s, __s + __len);
271 write(value_type* __s, size_t __len)
285 operator=(const value_type& __rhs)
304 // The following should be treated as private, at least for now.
305 template<class _CharT>
306 class _Rope_char_consumer
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
313 // The symmetry with char_producer is accidental and temporary.
314 virtual ~_Rope_char_consumer() { };
317 operator()(const _CharT* __buffer, size_t __len) = 0;
320 // First a lot of forward declarations. The standard seems to require
321 // much stricter "declaration before use" than many of the implementations
323 template<class _CharT, class _Alloc = allocator<_CharT> >
326 template<class _CharT, class _Alloc>
327 struct _Rope_RopeConcatenation;
329 template<class _CharT, class _Alloc>
330 struct _Rope_RopeLeaf;
332 template<class _CharT, class _Alloc>
333 struct _Rope_RopeFunction;
335 template<class _CharT, class _Alloc>
336 struct _Rope_RopeSubstring;
338 template<class _CharT, class _Alloc>
339 class _Rope_iterator;
341 template<class _CharT, class _Alloc>
342 class _Rope_const_iterator;
344 template<class _CharT, class _Alloc>
345 class _Rope_char_ref_proxy;
347 template<class _CharT, class _Alloc>
348 class _Rope_char_ptr_proxy;
350 template<class _CharT, class _Alloc>
352 operator==(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
353 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y);
355 template<class _CharT, class _Alloc>
356 _Rope_const_iterator<_CharT, _Alloc>
357 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
360 template<class _CharT, class _Alloc>
361 _Rope_const_iterator<_CharT, _Alloc>
362 operator+(const _Rope_const_iterator<_CharT, _Alloc>& __x,
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);
370 template<class _CharT, class _Alloc>
372 operator==(const _Rope_const_iterator<_CharT, _Alloc>& __x,
373 const _Rope_const_iterator<_CharT, _Alloc>& __y);
375 template<class _CharT, class _Alloc>
377 operator<(const _Rope_const_iterator<_CharT, _Alloc>& __x,
378 const _Rope_const_iterator<_CharT, _Alloc>& __y);
380 template<class _CharT, class _Alloc>
382 operator-(const _Rope_const_iterator<_CharT, _Alloc>& __x,
383 const _Rope_const_iterator<_CharT, _Alloc>& __y);
385 template<class _CharT, class _Alloc>
386 _Rope_iterator<_CharT, _Alloc>
387 operator-(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
389 template<class _CharT, class _Alloc>
390 _Rope_iterator<_CharT, _Alloc>
391 operator+(const _Rope_iterator<_CharT, _Alloc>& __x, ptrdiff_t __n);
393 template<class _CharT, class _Alloc>
394 _Rope_iterator<_CharT, _Alloc>
395 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT, _Alloc>& __x);
397 template<class _CharT, class _Alloc>
399 operator==(const _Rope_iterator<_CharT, _Alloc>& __x,
400 const _Rope_iterator<_CharT, _Alloc>& __y);
402 template<class _CharT, class _Alloc>
404 operator<(const _Rope_iterator<_CharT, _Alloc>& __x,
405 const _Rope_iterator<_CharT, _Alloc>& __y);
407 template<class _CharT, class _Alloc>
409 operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
410 const _Rope_iterator<_CharT, _Alloc>& __y);
412 template<class _CharT, class _Alloc>
414 operator+(const rope<_CharT, _Alloc>& __left,
415 const rope<_CharT, _Alloc>& __right);
417 template<class _CharT, class _Alloc>
419 operator+(const rope<_CharT, _Alloc>& __left, const _CharT* __right);
421 template<class _CharT, class _Alloc>
423 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right);
425 // Some helpers, so we can use power on ropes.
426 // See below for why this isn't local to the implementation.
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> >
436 operator()(const rope<_CharT, _Alloc>& __x,
437 const rope<_CharT, _Alloc>& __y)
438 { return __x + __y; }
441 template <class _CharT, class _Alloc>
442 inline rope<_CharT, _Alloc>
443 identity_element(_Rope_Concat_fn<_CharT, _Alloc>)
444 { return rope<_CharT, _Alloc>(); }
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
450 struct _Refcount_Base
453 typedef size_t _RC_t;
455 // The data member _M_ref_count
456 volatile _RC_t _M_ref_count;
459 __gthread_mutex_t _M_ref_count_lock;
461 _Refcount_Base(_RC_t __n) : _M_ref_count(__n), _M_ref_count_lock()
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);
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.
476 __gthread_mutex_lock(&_M_ref_count_lock);
478 __gthread_mutex_unlock(&_M_ref_count_lock);
484 __gthread_mutex_lock(&_M_ref_count_lock);
485 volatile _RC_t __tmp = --_M_ref_count;
486 __gthread_mutex_unlock(&_M_ref_count_lock);
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
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.
505 // The internal data structure for representing a rope. This is
506 // private to the implementation. A rope is really just a pointer
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.
513 // Some of the static member functions of _RopeRep have identically
514 // named functions in rope that simply invoke the _RopeRep versions.
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)
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
534 #define __STATIC_IF_SGI_ALLOC /* not static */
536 template <class _CharT, class _Alloc>
537 struct _Rope_rep_base
540 typedef _Alloc allocator_type;
543 get_allocator() const
544 { return *static_cast<const _Alloc*>(this); }
548 { return *static_cast<_Alloc*>(this); }
550 const allocator_type&
551 _M_get_allocator() const
552 { return *static_cast<const _Alloc*>(this); }
554 _Rope_rep_base(size_t __size, const allocator_type&)
555 : _M_size(__size) { }
559 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
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
570 template<class _CharT, class _Alloc>
572 : public _Rope_rep_base<_CharT, _Alloc>
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. */
585 /* If it's not 0, then the memory is owned */
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
592 using _Rope_rep_base<_CharT, _Alloc>::get_allocator;
593 using _Rope_rep_base<_CharT, _Alloc>::_M_get_allocator;
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),
601 _M_tag(__t), _M_is_balanced(__b), _M_depth(__d), _M_c_string(0)
602 #ifdef __GTHREAD_MUTEX_INIT
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;
609 { __GTHREAD_MUTEX_INIT_FUNCTION (&_M_c_string_lock); }
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.
624 // Does nothing if __GC is defined.
626 void _M_free_c_string();
628 // Deallocate t. Assumes t is not 0.
641 _S_unref(_Rope_RopeRep* __t)
644 __t->_M_unref_nonnil();
648 _S_ref(_Rope_RopeRep* __t)
655 _S_free_if_unref(_Rope_RopeRep* __t)
657 if (0 != __t && 0 == __t->_M_ref_count)
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*) { }
669 operator=(const _Rope_RopeRep&);
671 _Rope_RopeRep(const _Rope_RopeRep&);
674 template<class _CharT, class _Alloc>
675 struct _Rope_RopeLeaf
676 : public _Rope_RopeRep<_CharT, _Alloc>
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 };
686 _S_rounded_up_size(size_t __n)
688 size_t __size_with_eos;
690 if (_S_is_basic_char_type((_CharT*)0))
691 __size_with_eos = __n + 1;
693 __size_with_eos = __n;
695 return __size_with_eos;
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));
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
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)
715 if (_S_is_basic_char_type((_CharT *)0))
717 // already eos terminated.
718 this->_M_c_string = __d;
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:
725 ~_Rope_RopeLeaf() throw()
727 if (_M_data != this->_M_c_string)
728 this->_M_free_c_string();
730 __STL_FREE_STRING(_M_data, this->_M_size, this->_M_get_allocator());
735 operator=(const _Rope_RopeLeaf&);
737 _Rope_RopeLeaf(const _Rope_RopeLeaf&);
740 template<class _CharT, class _Alloc>
741 struct _Rope_RopeConcatenation
742 : public _Rope_RopeRep<_CharT, _Alloc>
745 _Rope_RopeRep<_CharT, _Alloc>* _M_left;
746 _Rope_RopeRep<_CharT, _Alloc>* _M_right;
748 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
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,
758 __l->_M_size + __r->_M_size, __a),
759 _M_left(__l), _M_right(__r)
762 ~_Rope_RopeConcatenation() throw()
764 this->_M_free_c_string();
765 _M_left->_M_unref_nonnil();
766 _M_right->_M_unref_nonnil();
770 _Rope_RopeConcatenation&
771 operator=(const _Rope_RopeConcatenation&);
773 _Rope_RopeConcatenation(const _Rope_RopeConcatenation&);
776 template<class _CharT, class _Alloc>
777 struct _Rope_RopeFunction
778 : public _Rope_RopeRep<_CharT, _Alloc>
781 char_producer<_CharT>* _M_fn;
783 bool _M_delete_when_done; // Char_producer is owned by the
784 // rope and should be explicitly
785 // deleted when the rope becomes
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
794 _S_fn_finalization_proc(void * __tree, void *)
795 { delete ((_Rope_RopeFunction *)__tree) -> _M_fn; }
797 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
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)
805 , _M_delete_when_done(__d)
811 GC_REGISTER_FINALIZER(this, _Rope_RopeFunction::
812 _S_fn_finalization_proc, 0, 0, 0);
817 ~_Rope_RopeFunction() throw()
819 this->_M_free_c_string();
820 if (_M_delete_when_done)
826 operator=(const _Rope_RopeFunction&);
828 _Rope_RopeFunction(const _Rope_RopeFunction&);
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>
843 // XXX this whole class should be rewritten.
844 _Rope_RopeRep<_CharT,_Alloc>* _M_base; // not 0
848 operator()(size_t __start_pos, size_t __req_len,
851 switch(_M_base->_M_tag)
853 case __detail::_S_function:
854 case __detail::_S_substringfn:
856 char_producer<_CharT>* __fn =
857 ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
858 (*__fn)(__start_pos + _M_start, __req_len, __buffer);
861 case __detail::_S_leaf:
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,
874 typedef typename _Rope_rep_base<_CharT, _Alloc>::allocator_type
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)
883 _M_base->_M_ref_nonnil();
885 this->_M_tag = __detail::_S_substringfn;
887 virtual ~_Rope_RopeSubstring() throw()
890 _M_base->_M_unref_nonnil();
891 // _M_free_c_string(); -- done by parent class
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
906 template<class _CharT, class _Alloc>
907 struct _Rope_self_destruct_ptr
909 _Rope_RopeRep<_CharT, _Alloc>* _M_ptr;
911 ~_Rope_self_destruct_ptr()
912 { _Rope_RopeRep<_CharT, _Alloc>::_S_unref(_M_ptr); }
914 _Rope_self_destruct_ptr() : _M_ptr(0) { };
916 _Rope_self_destruct_ptr() { };
918 _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT, _Alloc>* __p)
921 _Rope_RopeRep<_CharT, _Alloc>&
925 _Rope_RopeRep<_CharT, _Alloc>*
929 operator _Rope_RopeRep<_CharT, _Alloc>*()
932 _Rope_self_destruct_ptr&
933 operator=(_Rope_RopeRep<_CharT, _Alloc>* __x)
934 { _M_ptr = __x; return *this; }
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
946 friend class rope<_CharT, _Alloc>;
947 friend class _Rope_iterator<_CharT, _Alloc>;
948 friend class _Rope_char_ptr_proxy<_CharT, _Alloc>;
950 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
952 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
954 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
955 typedef rope<_CharT, _Alloc> _My_rope;
958 bool _M_current_valid;
959 _My_rope* _M_root; // The whole rope.
961 _Rope_char_ref_proxy(_My_rope* __r, size_t __p)
962 : _M_pos(__p), _M_current(), _M_current_valid(false), _M_root(__r) { }
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) { }
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) { }
975 inline operator _CharT () const;
977 _Rope_char_ref_proxy&
978 operator=(_CharT __c);
980 _Rope_char_ptr_proxy<_CharT, _Alloc> operator&() const;
982 _Rope_char_ref_proxy&
983 operator=(const _Rope_char_ref_proxy& __c)
984 { return operator=((_CharT)__c); }
987 template<class _CharT, class __Alloc>
989 swap(_Rope_char_ref_proxy <_CharT, __Alloc > __a,
990 _Rope_char_ref_proxy <_CharT, __Alloc > __b)
997 template<class _CharT, class _Alloc>
998 class _Rope_char_ptr_proxy
1000 // XXX this class should be rewritten.
1001 friend class _Rope_char_ref_proxy<_CharT, _Alloc>;
1003 rope<_CharT,_Alloc>* _M_root; // The whole rope.
1005 _Rope_char_ptr_proxy(const _Rope_char_ref_proxy<_CharT,_Alloc>& __x)
1006 : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
1008 _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy& __x)
1009 : _M_pos(__x._M_pos), _M_root(__x._M_root) { }
1011 _Rope_char_ptr_proxy() { }
1013 _Rope_char_ptr_proxy(_CharT* __x)
1014 : _M_root(0), _M_pos(0) { }
1016 _Rope_char_ptr_proxy&
1017 operator=(const _Rope_char_ptr_proxy& __x)
1019 _M_pos = __x._M_pos;
1020 _M_root = __x._M_root;
1024 template<class _CharT2, class _Alloc2>
1026 operator==(const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __x,
1027 const _Rope_char_ptr_proxy<_CharT2, _Alloc2>& __y);
1029 _Rope_char_ref_proxy<_CharT, _Alloc> operator*() const
1030 { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root, _M_pos); }
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
1038 // Pointers from iterators are not included in reference counts.
1039 // Iterators are assumed to be thread private. Ropes can
1042 template<class _CharT, class _Alloc>
1043 class _Rope_iterator_base
1044 : public std::iterator<std::random_access_iterator_tag, _CharT>
1046 friend class rope<_CharT, _Alloc>;
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.
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;
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
1089 static void _S_setcache(_Rope_iterator_base& __x);
1090 // Set buffer contents and
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() { }
1097 _Rope_iterator_base(_RopeRep* __root, size_t __pos)
1098 : _M_current_pos(__pos), _M_root(__root), _M_buf_ptr(0) { }
1100 void _M_incr(size_t __n);
1101 void _M_decr(size_t __n);
1105 { return _M_current_pos; }
1107 _Rope_iterator_base(const _Rope_iterator_base& __x)
1109 if (0 != __x._M_buf_ptr)
1113 _M_current_pos = __x._M_current_pos;
1114 _M_root = __x._M_root;
1120 template<class _CharT, class _Alloc>
1121 class _Rope_iterator;
1123 template<class _CharT, class _Alloc>
1124 class _Rope_const_iterator
1125 : public _Rope_iterator_base<_CharT, _Alloc>
1127 friend class rope<_CharT, _Alloc>;
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),
1134 // Only nonconst iterators modify root ref count
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;
1143 _Rope_const_iterator() { };
1145 _Rope_const_iterator(const _Rope_const_iterator& __x)
1146 : _Rope_iterator_base<_CharT,_Alloc>(__x) { }
1148 _Rope_const_iterator(const _Rope_iterator<_CharT,_Alloc>& __x);
1150 _Rope_const_iterator(const rope<_CharT, _Alloc>& __r, size_t __pos)
1151 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos) { }
1153 _Rope_const_iterator&
1154 operator=(const _Rope_const_iterator& __x)
1156 if (0 != __x._M_buf_ptr)
1157 *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
1160 this->_M_current_pos = __x._M_current_pos;
1161 this->_M_root = __x._M_root;
1162 this->_M_buf_ptr = 0;
1170 if (0 == this->_M_buf_ptr)
1172 return *this->_M_buf_ptr;
1175 // Without this const version, Rope iterators do not meet the
1176 // requirements of an Input Iterator.
1180 return *const_cast<_Rope_const_iterator&>(*this);
1183 _Rope_const_iterator&
1186 __GC_CONST _CharT* __next;
1187 if (0 != this->_M_buf_ptr
1188 && (__next = this->_M_buf_ptr + 1) < this->_M_buf_end)
1190 this->_M_buf_ptr = __next;
1191 ++this->_M_current_pos;
1198 _Rope_const_iterator&
1199 operator+=(ptrdiff_t __n)
1204 this->_M_decr(-__n);
1208 _Rope_const_iterator&
1215 _Rope_const_iterator&
1216 operator-=(ptrdiff_t __n)
1221 this->_M_incr(-__n);
1225 _Rope_const_iterator
1228 size_t __old_pos = this->_M_current_pos;
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?
1236 _Rope_const_iterator
1239 size_t __old_pos = this->_M_current_pos;
1241 return _Rope_const_iterator<_CharT,_Alloc>(this->_M_root, __old_pos);
1244 template<class _CharT2, class _Alloc2>
1245 friend _Rope_const_iterator<_CharT2, _Alloc2>
1246 operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1249 template<class _CharT2, class _Alloc2>
1250 friend _Rope_const_iterator<_CharT2, _Alloc2>
1251 operator+(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
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);
1260 operator[](size_t __n)
1261 { return rope<_CharT, _Alloc>::_S_fetch(this->_M_root,
1262 this->_M_current_pos + __n); }
1264 template<class _CharT2, class _Alloc2>
1266 operator==(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1267 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1269 template<class _CharT2, class _Alloc2>
1271 operator<(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1272 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1274 template<class _CharT2, class _Alloc2>
1276 operator-(const _Rope_const_iterator<_CharT2, _Alloc2>& __x,
1277 const _Rope_const_iterator<_CharT2, _Alloc2>& __y);
1280 template<class _CharT, class _Alloc>
1281 class _Rope_iterator
1282 : public _Rope_iterator_base<_CharT, _Alloc>
1284 friend class rope<_CharT, _Alloc>;
1286 typedef typename _Rope_iterator_base<_CharT, _Alloc>::_RopeRep _RopeRep;
1287 rope<_CharT, _Alloc>* _M_root_rope;
1289 // root is treated as a cached version of this, and is used to
1290 // detect changes to the underlying rope.
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),
1298 { _RopeRep::_S_ref(this->_M_root);
1299 if (!(__r -> empty()))
1305 typedef _Rope_char_ref_proxy<_CharT, _Alloc> reference;
1306 typedef _Rope_char_ref_proxy<_CharT, _Alloc>* pointer;
1308 rope<_CharT, _Alloc>&
1310 { return *_M_root_rope; }
1314 this->_M_root = 0; // Needed for reference counting.
1317 _Rope_iterator(const _Rope_iterator& __x)
1318 : _Rope_iterator_base<_CharT, _Alloc>(__x)
1320 _M_root_rope = __x._M_root_rope;
1321 _RopeRep::_S_ref(this->_M_root);
1324 _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos);
1327 { _RopeRep::_S_unref(this->_M_root); }
1330 operator=(const _Rope_iterator& __x)
1332 _RopeRep* __old = this->_M_root;
1334 _RopeRep::_S_ref(__x._M_root);
1335 if (0 != __x._M_buf_ptr)
1337 _M_root_rope = __x._M_root_rope;
1338 *(static_cast<_Rope_iterator_base<_CharT, _Alloc>*>(this)) = __x;
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;
1347 _RopeRep::_S_unref(__old);
1355 if (0 == this->_M_buf_ptr)
1356 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1357 this->_M_current_pos);
1359 return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1360 this->_M_current_pos,
1364 // See above comment.
1368 return *const_cast<_Rope_iterator&>(*this);
1379 operator+=(ptrdiff_t __n)
1384 this->_M_decr(-__n);
1396 operator-=(ptrdiff_t __n)
1401 this->_M_incr(-__n);
1408 size_t __old_pos = this->_M_current_pos;
1410 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
1416 size_t __old_pos = this->_M_current_pos;
1418 return _Rope_iterator<_CharT,_Alloc>(_M_root_rope, __old_pos);
1422 operator[](ptrdiff_t __n)
1423 { return _Rope_char_ref_proxy<_CharT, _Alloc>(_M_root_rope,
1424 this->_M_current_pos
1427 template<class _CharT2, class _Alloc2>
1429 operator==(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1430 const _Rope_iterator<_CharT2, _Alloc2>& __y);
1432 template<class _CharT2, class _Alloc2>
1434 operator<(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1435 const _Rope_iterator<_CharT2, _Alloc2>& __y);
1437 template<class _CharT2, class _Alloc2>
1439 operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x,
1440 const _Rope_iterator<_CharT2, _Alloc2>& __y);
1442 template<class _CharT2, class _Alloc2>
1443 friend _Rope_iterator<_CharT2, _Alloc2>
1444 operator-(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
1446 template<class _CharT2, class _Alloc2>
1447 friend _Rope_iterator<_CharT2, _Alloc2>
1448 operator+(const _Rope_iterator<_CharT2, _Alloc2>& __x, ptrdiff_t __n);
1450 template<class _CharT2, class _Alloc2>
1451 friend _Rope_iterator<_CharT2, _Alloc2>
1452 operator+(ptrdiff_t __n, const _Rope_iterator<_CharT2, _Alloc2>& __x);
1456 template <class _CharT, class _Alloc>
1460 typedef _Alloc allocator_type;
1463 get_allocator() const
1464 { return *static_cast<const _Alloc*>(this); }
1468 { return *static_cast<_Alloc*>(this); }
1470 const allocator_type&
1471 _M_get_allocator() const
1472 { return *static_cast<const _Alloc*>(this); }
1474 typedef _Rope_RopeRep<_CharT, _Alloc> _RopeRep;
1475 // The one in _Base may not be visible due to template rules.
1477 _Rope_base(_RopeRep* __t, const allocator_type&)
1478 : _M_tree_ptr(__t) { }
1480 _Rope_base(const allocator_type&) { }
1482 // The only data member of a rope:
1483 _RopeRep *_M_tree_ptr;
1485 #define __ROPE_DEFINE_ALLOC(_Tp, __name) \
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
1497 operator=(const _Rope_base&);
1499 _Rope_base(const _Rope_base&);
1503 * This is an SGI extension.
1504 * @ingroup SGIextensions
1507 template <class _CharT, class _Alloc>
1508 class rope : public _Rope_base<_CharT, _Alloc>
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;
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>;
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;
1537 static _CharT _S_empty_c_str[1];
1541 { return __c == _S_eos((_CharT*)0); }
1543 enum { _S_copy_max = 23 };
1544 // For strings shorter than _S_copy_max, we copy to
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;
1553 // Retrieve a character at the indicated position.
1554 static _CharT _S_fetch(_RopeRep* __r, size_type __pos);
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
1563 static _CharT* _S_fetch_ptr(_RopeRep* __r, size_type __pos);
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.
1575 _S_unref(_RopeRep* __t)
1576 { _RopeRep::_S_unref(__t); }
1579 _S_ref(_RopeRep* __t)
1580 { _RopeRep::_S_ref(__t); }
1583 static void _S_unref(_RopeRep*) { }
1584 static void _S_ref(_RopeRep*) { }
1588 typedef _Rope_RopeRep<_CharT, _Alloc>* _Self_destruct_ptr;
1590 typedef _Rope_self_destruct_ptr<_CharT, _Alloc> _Self_destruct_ptr;
1593 // _Result is counted in refcount.
1594 static _RopeRep* _S_substring(_RopeRep* __base,
1595 size_t __start, size_t __endp1);
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,
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.
1609 // We can't really do anything since refcounts are unavailable.
1610 { return _S_concat_char_iter(__r, __iter, __slen); }
1615 static _RopeRep* _S_concat(_RopeRep* __left, _RopeRep* __right);
1616 // General concatenation on _RopeRep. _Result
1617 // has refcount of 1. Adjusts argument refcounts.
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); }
1628 _S_rounded_up_size(size_t __n)
1629 { return _RopeLeaf::_S_rounded_up_size(__n); }
1632 _S_allocated_capacity(size_t __n)
1634 if (_S_is_basic_char_type((_CharT*)0))
1635 return _S_rounded_up_size(__n) - 1;
1637 return _S_rounded_up_size(__n);
1641 // Allocate and construct a RopeLeaf using the supplied allocator
1642 // Takes ownership of s instead of copying.
1644 _S_new_RopeLeaf(__GC_CONST _CharT *__s,
1645 size_t __size, allocator_type& __a)
1647 _RopeLeaf* __space = typename _Base::_LAlloc(__a).allocate(1);
1648 return new(__space) _RopeLeaf(__s, __size, __a);
1651 static _RopeConcatenation*
1652 _S_new_RopeConcatenation(_RopeRep* __left, _RopeRep* __right,
1653 allocator_type& __a)
1655 _RopeConcatenation* __space = typename _Base::_CAlloc(__a).allocate(1);
1656 return new(__space) _RopeConcatenation(__left, __right, __a);
1659 static _RopeFunction*
1660 _S_new_RopeFunction(char_producer<_CharT>* __f,
1661 size_t __size, bool __d, allocator_type& __a)
1663 _RopeFunction* __space = typename _Base::_FAlloc(__a).allocate(1);
1664 return new(__space) _RopeFunction(__f, __size, __d, __a);
1667 static _RopeSubstring*
1668 _S_new_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
1669 size_t __l, allocator_type& __a)
1671 _RopeSubstring* __space = typename _Base::_SAlloc(__a).allocate(1);
1672 return new(__space) _RopeSubstring(__b, __s, __l, __a);
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)
1683 _CharT* __buf = __a.allocate(_S_rounded_up_size(__size));
1685 __uninitialized_copy_n_a(__s, __size, __buf, __a);
1686 _S_cond_store_eos(__buf[__size]);
1688 { return _S_new_RopeLeaf(__buf, __size, __a); }
1691 _RopeRep::__STL_FREE_STRING(__buf, __size, __a);
1692 __throw_exception_again;
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.
1703 _S_tree_concat(_RopeRep* __left, _RopeRep* __right);
1705 // Concatenation helper functions
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.
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.
1721 static size_t _S_char_ptr_len(const _CharT* __s);
1722 // slightly generalized strlen
1724 rope(_RopeRep* __t, const allocator_type& __a = allocator_type())
1725 : _Base(__t, __a) { }
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);
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,
1739 static const unsigned long
1740 _S_min_len[__detail::_S_max_rope_depth + 1];
1743 _S_is_balanced(_RopeRep* __r)
1744 { return (__r->_M_size >= _S_min_len[__r->_M_depth]); }
1747 _S_is_almost_balanced(_RopeRep* __r)
1748 { return (__r->_M_depth == 0
1749 || __r->_M_size >= _S_min_len[__r->_M_depth - 1]); }
1752 _S_is_roughly_balanced(_RopeRep* __r)
1753 { return (__r->_M_depth <= 1
1754 || __r->_M_size >= _S_min_len[__r->_M_depth - 2]); }
1756 // Assumes the result is not empty.
1758 _S_concat_and_set_balanced(_RopeRep* __left, _RopeRep* __right)
1760 _RopeRep* __result = _S_concat(__left, __right);
1761 if (_S_is_balanced(__result))
1762 __result->_M_is_balanced = true;
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
1771 static _RopeRep* _S_balance(_RopeRep* __r);
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);
1777 // Add __r to forest, assuming __r is already balanced.
1778 static void _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest);
1780 // Print to stdout, exposing structure
1781 static void _S_dump(_RopeRep* __r, int __indent = 0);
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);
1789 { return 0 == this->_M_tree_ptr; }
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.
1795 compare(const rope& __y) const
1796 { return _S_compare(this->_M_tree_ptr, __y._M_tree_ptr); }
1798 rope(const _CharT* __s, const allocator_type& __a = allocator_type())
1802 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, _S_char_ptr_len(__s),
1803 _M_get_allocator());
1806 rope(const _CharT* __s, size_t __len,
1807 const allocator_type& __a = allocator_type())
1811 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __len, _M_get_allocator());
1814 // Should perhaps be templatized with respect to the iterator type
1815 // and use Sequence_buffer. (It should perhaps use sequence_buffer
1817 rope(const _CharT* __s, const _CharT* __e,
1818 const allocator_type& __a = allocator_type())
1822 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __e - __s, _M_get_allocator());
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)
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)
1837 rope(_CharT __c, const allocator_type& __a = allocator_type())
1840 _CharT* __buf = this->_Data_allocate(_S_rounded_up_size(1));
1842 _M_get_allocator().construct(__buf, __c);
1845 this->_M_tree_ptr = _S_new_RopeLeaf(__buf, 1,
1846 _M_get_allocator());
1850 _RopeRep::__STL_FREE_STRING(__buf, 1, _M_get_allocator());
1851 __throw_exception_again;
1855 rope(size_t __n, _CharT __c,
1856 const allocator_type& __a = allocator_type());
1858 rope(const allocator_type& __a = allocator_type())
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())
1866 this->_M_tree_ptr = (0 == __len) ?
1867 0 : _S_new_RopeFunction(__fn, __len, __delete_fn, __a);
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); }
1875 { _S_unref(this->_M_tree_ptr); }
1878 operator=(const rope& __x)
1880 _RopeRep* __old = this->_M_tree_ptr;
1881 this->_M_tree_ptr = __x._M_tree_ptr;
1882 _S_ref(this->_M_tree_ptr);
1890 _S_unref(this->_M_tree_ptr);
1891 this->_M_tree_ptr = 0;
1895 push_back(_CharT __x)
1897 _RopeRep* __old = this->_M_tree_ptr;
1899 = _S_destr_concat_char_iter(this->_M_tree_ptr, &__x, 1);
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);
1914 { return _S_fetch(this->_M_tree_ptr, this->_M_tree_ptr->_M_size - 1); }
1917 push_front(_CharT __x)
1919 _RopeRep* __old = this->_M_tree_ptr;
1921 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x, 1, _M_get_allocator());
1924 this->_M_tree_ptr = _S_concat(__left, this->_M_tree_ptr);
1931 __throw_exception_again;
1938 _RopeRep* __old = this->_M_tree_ptr;
1940 = _S_substring(this->_M_tree_ptr, 1, this->_M_tree_ptr->_M_size);
1946 { return _S_fetch(this->_M_tree_ptr, 0); }
1951 _RopeRep* __old = this->_M_tree_ptr;
1952 this->_M_tree_ptr = _S_balance(this->_M_tree_ptr);
1957 copy(_CharT* __buffer) const
1959 _Destroy_const(__buffer, __buffer + size(), _M_get_allocator());
1960 _S_flatten(this->_M_tree_ptr, __buffer);
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.
1969 copy(size_type __pos, size_type __n, _CharT* __buffer) const
1971 size_t __size = size();
1972 size_t __len = (__pos + __n > __size? __size - __pos : __n);
1974 _Destroy_const(__buffer, __buffer + __len, _M_get_allocator());
1975 _S_flatten(this->_M_tree_ptr, __pos, __len, __buffer);
1979 // Print to stdout, exposing structure. May be useful for
1980 // performance debugging.
1983 { _S_dump(this->_M_tree_ptr); }
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;
1989 // As above, but also use the flattened representation as
1990 // the new rope representation.
1991 const _CharT* replace_with_c_str();
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.
1999 if (0 == this->_M_tree_ptr)
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)
2005 // Representation shared
2009 this->_M_tree_ptr->_M_free_c_string();
2011 this->_M_tree_ptr->_M_c_string = 0;
2015 operator[] (size_type __pos) const
2016 { return _S_fetch(this->_M_tree_ptr, __pos); }
2019 at(size_type __pos) const
2021 // if (__pos >= size()) throw out_of_range; // XXX
2022 return (*this)[__pos];
2027 { return(const_iterator(this->_M_tree_ptr, 0)); }
2029 // An easy way to get a const iterator from a non-const container.
2032 { return(const_iterator(this->_M_tree_ptr, 0)); }
2036 { return(const_iterator(this->_M_tree_ptr, size())); }
2040 { return(const_iterator(this->_M_tree_ptr, size())); }
2044 { return(0 == this->_M_tree_ptr? 0 : this->_M_tree_ptr->_M_size); }
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.
2059 typedef std::reverse_iterator<const_iterator> const_reverse_iterator;
2061 const_reverse_iterator
2063 { return const_reverse_iterator(end()); }
2065 const_reverse_iterator
2066 const_rbegin() const
2067 { return const_reverse_iterator(end()); }
2069 const_reverse_iterator
2071 { return const_reverse_iterator(begin()); }
2073 const_reverse_iterator
2075 { return const_reverse_iterator(begin()); }
2077 template<class _CharT2, class _Alloc2>
2078 friend rope<_CharT2, _Alloc2>
2079 operator+(const rope<_CharT2, _Alloc2>& __left,
2080 const rope<_CharT2, _Alloc2>& __right);
2082 template<class _CharT2, class _Alloc2>
2083 friend rope<_CharT2, _Alloc2>
2084 operator+(const rope<_CharT2, _Alloc2>& __left, const _CharT2* __right);
2086 template<class _CharT2, class _Alloc2>
2087 friend rope<_CharT2, _Alloc2>
2088 operator+(const rope<_CharT2, _Alloc2>& __left, _CharT2 __right);
2090 // The symmetric cases are intentionally omitted, since they're
2091 // presumed to be less common, and we don't handle them as well.
2093 // The following should really be templatized. The first
2094 // argument should be an input iterator or forward iterator with
2095 // value_type _CharT.
2097 append(const _CharT* __iter, size_t __n)
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;
2107 append(const _CharT* __c_string)
2109 size_t __len = _S_char_ptr_len(__c_string);
2110 append(__c_string, __len);
2115 append(const _CharT* __s, const _CharT* __e)
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;
2125 append(const_iterator __s, const_iterator __e)
2127 _Self_destruct_ptr __appendee(_S_substring(__s._M_root,
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;
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;
2149 { return append(_CharT()); } // XXX why?
2152 append(const rope& __y)
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;
2161 append(size_t __n, _CharT __c)
2163 rope<_CharT,_Alloc> __last(__n, __c);
2164 return append(__last);
2170 _RopeRep* __tmp = this->_M_tree_ptr;
2171 this->_M_tree_ptr = __b._M_tree_ptr;
2172 __b._M_tree_ptr = __tmp;
2176 // Result is included in refcount.
2178 replace(_RopeRep* __old, size_t __pos1,
2179 size_t __pos2, _RopeRep* __r)
2186 _Self_destruct_ptr __left(_S_substring(__old, 0, __pos1));
2187 _Self_destruct_ptr __right(_S_substring(__old, __pos2, __old->_M_size));
2191 __result = _S_concat(__left, __right);
2194 _Self_destruct_ptr __left_result(_S_concat(__left, __r));
2195 __result = _S_concat(__left_result, __right);
2202 insert(size_t __p, const rope& __r)
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;
2211 insert(size_t __p, size_t __n, _CharT __c)
2213 rope<_CharT,_Alloc> __r(__n,__c);
2218 insert(size_t __p, const _CharT* __i, size_t __n)
2220 _Self_destruct_ptr __left(_S_substring(this->_M_tree_ptr, 0, __p));
2221 _Self_destruct_ptr __right(_S_substring(this->_M_tree_ptr,
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;
2233 insert(size_t __p, const _CharT* __c_string)
2234 { insert(__p, __c_string, _S_char_ptr_len(__c_string)); }
2237 insert(size_t __p, _CharT __c)
2238 { insert(__p, &__c, 1); }
2243 _CharT __c = _CharT();
2244 insert(__p, &__c, 1);
2248 insert(size_t __p, const _CharT* __i, const _CharT* __j)
2255 insert(size_t __p, const const_iterator& __i,
2256 const const_iterator& __j)
2263 insert(size_t __p, const iterator& __i,
2264 const iterator& __j)
2270 // (position, length) versions of replace operations:
2273 replace(size_t __p, size_t __n, const rope& __r)
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;
2282 replace(size_t __p, size_t __n,
2283 const _CharT* __i, size_t __i_len)
2285 rope __r(__i, __i_len);
2286 replace(__p, __n, __r);
2290 replace(size_t __p, size_t __n, _CharT __c)
2293 replace(__p, __n, __r);
2297 replace(size_t __p, size_t __n, const _CharT* __c_string)
2299 rope __r(__c_string);
2300 replace(__p, __n, __r);
2304 replace(size_t __p, size_t __n,
2305 const _CharT* __i, const _CharT* __j)
2308 replace(__p, __n, __r);
2312 replace(size_t __p, size_t __n,
2313 const const_iterator& __i, const const_iterator& __j)
2316 replace(__p, __n, __r);
2320 replace(size_t __p, size_t __n,
2321 const iterator& __i, const iterator& __j)
2324 replace(__p, __n, __r);
2327 // Single character variants:
2329 replace(size_t __p, _CharT __c)
2331 iterator __i(this, __p);
2336 replace(size_t __p, const rope& __r)
2337 { replace(__p, 1, __r); }
2340 replace(size_t __p, const _CharT* __i, size_t __i_len)
2341 { replace(__p, 1, __i, __i_len); }
2344 replace(size_t __p, const _CharT* __c_string)
2345 { replace(__p, 1, __c_string); }
2348 replace(size_t __p, const _CharT* __i, const _CharT* __j)
2349 { replace(__p, 1, __i, __j); }
2352 replace(size_t __p, const const_iterator& __i,
2353 const const_iterator& __j)
2354 { replace(__p, 1, __i, __j); }
2357 replace(size_t __p, const iterator& __i,
2358 const iterator& __j)
2359 { replace(__p, 1, __i, __j); }
2361 // Erase, (position, size) variant.
2363 erase(size_t __p, size_t __n)
2365 _RopeRep* __result = replace(this->_M_tree_ptr, __p,
2367 _S_unref(this->_M_tree_ptr);
2368 this->_M_tree_ptr = __result;
2371 // Erase, single character
2374 { erase(__p, __p + 1); }
2376 // Insert, iterator variants.
2378 insert(const iterator& __p, const rope& __r)
2380 insert(__p.index(), __r);
2385 insert(const iterator& __p, size_t __n, _CharT __c)
2387 insert(__p.index(), __n, __c);
2391 iterator insert(const iterator& __p, _CharT __c)
2393 insert(__p.index(), __c);
2398 insert(const iterator& __p )
2400 insert(__p.index());
2405 insert(const iterator& __p, const _CharT* c_string)
2407 insert(__p.index(), c_string);
2412 insert(const iterator& __p, const _CharT* __i, size_t __n)
2414 insert(__p.index(), __i, __n);
2419 insert(const iterator& __p, const _CharT* __i,
2422 insert(__p.index(), __i, __j);
2427 insert(const iterator& __p,
2428 const const_iterator& __i, const const_iterator& __j)
2430 insert(__p.index(), __i, __j);
2435 insert(const iterator& __p,
2436 const iterator& __i, const iterator& __j)
2438 insert(__p.index(), __i, __j);
2442 // Replace, range variants.
2444 replace(const iterator& __p, const iterator& __q, const rope& __r)
2445 { replace(__p.index(), __q.index() - __p.index(), __r); }
2448 replace(const iterator& __p, const iterator& __q, _CharT __c)
2449 { replace(__p.index(), __q.index() - __p.index(), __c); }
2452 replace(const iterator& __p, const iterator& __q,
2453 const _CharT* __c_string)
2454 { replace(__p.index(), __q.index() - __p.index(), __c_string); }
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); }
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); }
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); }
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); }
2476 // Replace, iterator variants.
2478 replace(const iterator& __p, const rope& __r)
2479 { replace(__p.index(), __r); }
2482 replace(const iterator& __p, _CharT __c)
2483 { replace(__p.index(), __c); }
2486 replace(const iterator& __p, const _CharT* __c_string)
2487 { replace(__p.index(), __c_string); }
2490 replace(const iterator& __p, const _CharT* __i, size_t __n)
2491 { replace(__p.index(), __i, __n); }
2494 replace(const iterator& __p, const _CharT* __i, const _CharT* __j)
2495 { replace(__p.index(), __i, __j); }
2498 replace(const iterator& __p, const_iterator __i, const_iterator __j)
2499 { replace(__p.index(), __i, __j); }
2502 replace(const iterator& __p, iterator __i, iterator __j)
2503 { replace(__p.index(), __i, __j); }
2505 // Iterator and range variants of erase
2507 erase(const iterator& __p, const iterator& __q)
2509 size_t __p_index = __p.index();
2510 erase(__p_index, __q.index() - __p_index);
2511 return iterator(this, __p_index);
2515 erase(const iterator& __p)
2517 size_t __p_index = __p.index();
2518 erase(__p_index, 1);
2519 return iterator(this, __p_index);
2523 substr(size_t __start, size_t __len = 1) const
2525 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2531 substr(iterator __start, iterator __end) const
2533 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2539 substr(iterator __start) const
2541 size_t __pos = __start.index();
2542 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2547 substr(const_iterator __start, const_iterator __end) const
2549 // This might eventually take advantage of the cache in the
2551 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2556 rope<_CharT, _Alloc>
2557 substr(const_iterator __start)
2559 size_t __pos = __start.index();
2560 return rope<_CharT, _Alloc>(_S_substring(this->_M_tree_ptr,
2564 static const size_type npos;
2566 size_type find(_CharT __c, size_type __pos = 0) const;
2569 find(const _CharT* __s, size_type __pos = 0) const
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;
2580 return __result_pos;
2585 { return(iterator(this, 0)); }
2589 { return(iterator(this, size())); }
2591 typedef std::reverse_iterator<iterator> reverse_iterator;
2595 { return reverse_iterator(mutable_end()); }
2599 { return reverse_iterator(mutable_begin()); }
2602 mutable_reference_at(size_type __pos)
2603 { return reference(this, __pos); }
2607 operator[] (size_type __pos)
2608 { return _char_ref_proxy(this, __pos); }
2613 // if (__pos >= size()) throw out_of_range; // XXX
2614 return (*this)[__pos];
2617 void resize(size_type __n, _CharT __c) { }
2618 void resize(size_type __n) { }
2619 void reserve(size_type __res_arg = 0) { }
2623 { return max_size(); }
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.
2629 copy(_CharT* __buffer, size_type __n,
2630 size_type __pos = 0) const
2631 { return copy(__pos, __n, __buffer); }
2635 { return mutable_end(); }
2639 { return mutable_begin(); }
2643 { return mutable_rend(); }
2647 { return mutable_rbegin(); }
2652 { return const_end(); }
2656 { return const_begin(); }
2658 const_reverse_iterator
2660 { return const_rend(); }
2662 const_reverse_iterator
2664 { return const_rbegin(); }
2669 template <class _CharT, class _Alloc>
2670 const typename rope<_CharT, _Alloc>::size_type
2671 rope<_CharT, _Alloc>::npos = (size_type)(-1);
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); }
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); }
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); }
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; }
2694 template <class _CharT, class _Alloc>
2696 operator<=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2697 const _Rope_const_iterator<_CharT, _Alloc>& __y)
2698 { return !(__y < __x); }
2700 template <class _CharT, class _Alloc>
2702 operator>=(const _Rope_const_iterator<_CharT, _Alloc>& __x,
2703 const _Rope_const_iterator<_CharT, _Alloc>& __y)
2704 { return !(__x < __y); }
2706 template <class _CharT, class _Alloc>
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; }
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); }
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); }
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); }
2730 template <class _CharT, class _Alloc>
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); }
2737 template <class _CharT, class _Alloc>
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); }
2743 template <class _CharT, class _Alloc>
2745 operator!=(const _Rope_iterator<_CharT, _Alloc>& __x,
2746 const _Rope_iterator<_CharT, _Alloc>& __y)
2747 { return !(__x == __y); }
2749 template <class _CharT, class _Alloc>
2751 operator>(const _Rope_iterator<_CharT, _Alloc>& __x,
2752 const _Rope_iterator<_CharT, _Alloc>& __y)
2753 { return __y < __x; }
2755 template <class _CharT, class _Alloc>
2757 operator<=(const _Rope_iterator<_CharT, _Alloc>& __x,
2758 const _Rope_iterator<_CharT, _Alloc>& __y)
2759 { return !(__y < __x); }
2761 template <class _CharT, class _Alloc>
2763 operator>=(const _Rope_iterator<_CharT, _Alloc>& __x,
2764 const _Rope_iterator<_CharT, _Alloc>& __y)
2765 { return !(__x < __y); }
2767 template <class _CharT, class _Alloc>
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); }
2774 template <class _CharT, class _Alloc>
2775 inline _Rope_iterator<_CharT, _Alloc>
2776 operator-(const _Rope_iterator<_CharT, _Alloc>& __x,
2778 { return _Rope_iterator<_CharT, _Alloc>(__x._M_root_rope,
2779 __x._M_current_pos - __n); }
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); }
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); }
2793 template <class _CharT, class _Alloc>
2794 inline rope<_CharT, _Alloc>
2795 operator+(const rope<_CharT, _Alloc>& __left,
2796 const rope<_CharT, _Alloc>& __right)
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));
2805 template <class _CharT, class _Alloc>
2806 inline rope<_CharT, _Alloc>&
2807 operator+=(rope<_CharT, _Alloc>& __left,
2808 const rope<_CharT, _Alloc>& __right)
2810 __left.append(__right);
2814 template <class _CharT, class _Alloc>
2815 inline rope<_CharT, _Alloc>
2816 operator+(const rope<_CharT, _Alloc>& __left,
2817 const _CharT* __right)
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,
2825 template <class _CharT, class _Alloc>
2826 inline rope<_CharT, _Alloc>&
2827 operator+=(rope<_CharT, _Alloc>& __left,
2828 const _CharT* __right)
2830 __left.append(__right);
2834 template <class _CharT, class _Alloc>
2835 inline rope<_CharT, _Alloc>
2836 operator+(const rope<_CharT, _Alloc>& __left, _CharT __right)
2838 typedef rope<_CharT, _Alloc> rope_type;
2839 return rope_type(rope_type::_S_concat_char_iter(__left._M_tree_ptr,
2843 template <class _CharT, class _Alloc>
2844 inline rope<_CharT, _Alloc>&
2845 operator+=(rope<_CharT, _Alloc>& __left, _CharT __right)
2847 __left.append(__right);
2851 template <class _CharT, class _Alloc>
2853 operator<(const rope<_CharT, _Alloc>& __left,
2854 const rope<_CharT, _Alloc>& __right)
2855 { return __left.compare(__right) < 0; }
2857 template <class _CharT, class _Alloc>
2859 operator==(const rope<_CharT, _Alloc>& __left,
2860 const rope<_CharT, _Alloc>& __right)
2861 { return __left.compare(__right) == 0; }
2863 template <class _CharT, class _Alloc>
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); }
2869 template <class _CharT, class _Alloc>
2871 operator!=(const rope<_CharT, _Alloc>& __x,
2872 const rope<_CharT, _Alloc>& __y)
2873 { return !(__x == __y); }
2875 template <class _CharT, class _Alloc>
2877 operator>(const rope<_CharT, _Alloc>& __x,
2878 const rope<_CharT, _Alloc>& __y)
2879 { return __y < __x; }
2881 template <class _CharT, class _Alloc>
2883 operator<=(const rope<_CharT, _Alloc>& __x,
2884 const rope<_CharT, _Alloc>& __y)
2885 { return !(__y < __x); }
2887 template <class _CharT, class _Alloc>
2889 operator>=(const rope<_CharT, _Alloc>& __x,
2890 const rope<_CharT, _Alloc>& __y)
2891 { return !(__x < __y); }
2893 template <class _CharT, class _Alloc>
2895 operator!=(const _Rope_char_ptr_proxy<_CharT, _Alloc>& __x,
2896 const _Rope_char_ptr_proxy<_CharT, _Alloc>& __y)
2897 { return !(__x == __y); }
2899 template<class _CharT, class _Traits, class _Alloc>
2900 std::basic_ostream<_CharT, _Traits>&
2901 operator<<(std::basic_ostream<_CharT, _Traits>& __o,
2902 const rope<_CharT, _Alloc>& __r);
2904 typedef rope<char> crope;
2905 typedef rope<wchar_t> wrope;
2907 inline crope::reference
2908 __mutable_reference_at(crope& __c, size_t __i)
2909 { return __c.mutable_reference_at(__i); }
2911 inline wrope::reference
2912 __mutable_reference_at(wrope& __c, size_t __i)
2913 { return __c.mutable_reference_at(__i); }
2915 template <class _CharT, class _Alloc>
2917 swap(rope<_CharT, _Alloc>& __x, rope<_CharT, _Alloc>& __y)
2920 _GLIBCXX_END_NAMESPACE
2928 struct hash<__gnu_cxx::crope>
2931 operator()(const __gnu_cxx::crope& __str) const
2933 size_t __size = __str.size();
2936 return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2942 struct hash<__gnu_cxx::wrope>
2945 operator()(const __gnu_cxx::wrope& __str) const
2947 size_t __size = __str.size();
2950 return 13 * __str[0] + 5 * __str[__size - 1] + __size;
2956 # include <ext/ropeimpl.h>