1 // SGI's rope implementation -*- C++ -*-
3 // Copyright (C) 2001 Free Software Foundation, Inc.
5 // This file is part of the GNU ISO C++ Library. This library is free
6 // software; you can redistribute it and/or modify it under the
7 // terms of the GNU General Public License as published by the
8 // Free Software Foundation; either version 2, or (at your option)
11 // This library is distributed in the hope that it will be useful,
12 // but WITHOUT ANY WARRANTY; without even the implied warranty of
13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 // GNU General Public License for more details.
16 // You should have received a copy of the GNU General Public License along
17 // with this library; see the file COPYING. If not, write to the Free
18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
21 // As a special exception, you may use this file as part of a free software
22 // library without restriction. Specifically, if other files instantiate
23 // templates or use macros or inline functions from this file, or you compile
24 // this file and link it with other files to produce an executable, this
25 // file does not by itself cause the resulting executable to be covered by
26 // the GNU General Public License. This exception does not however
27 // invalidate any other reasons why the executable file might be covered by
28 // the GNU General Public License.
31 * Copyright (c) 1997-1998
32 * Silicon Graphics Computer Systems, Inc.
34 * Permission to use, copy, modify, distribute and sell this software
35 * and its documentation for any purpose is hereby granted without fee,
36 * provided that the above copyright notice appear in all copies and
37 * that both that copyright notice and this permission notice appear
38 * in supporting documentation. Silicon Graphics makes no
39 * representations about the suitability of this software for any
40 * purpose. It is provided "as is" without express or implied warranty.
44 * This is an internal header file, included by other library headers.
45 * You should not attempt to use it directly.
48 // rope<_CharT,_Alloc> is a sequence of _CharT.
49 // Ropes appear to be mutable, but update operations
50 // really copy enough of the data structure to leave the original
51 // valid. Thus ropes can be logically copied by just copying
54 #ifndef __SGI_STL_INTERNAL_ROPE_H
55 # define __SGI_STL_INTERNAL_ROPE_H
58 # define __GC_CONST const
60 # include <bits/stl_threads.h>
61 # define __GC_CONST // constant except for deallocation
64 #include <ext/memory> // For uninitialized_copy_n
72 using std::reverse_iterator
;
73 using std::_Alloc_traits
;
75 using std::_Refcount_Base
;
77 // The _S_eos function is used for those functions that
78 // convert to/from C-like strings to detect the end of the string.
80 // The end-of-C-string character.
81 // This is what the draft standard says it should be.
82 template <class _CharT
>
83 inline _CharT
_S_eos(_CharT
*) { return _CharT(); }
85 // Test for basic character types.
86 // For basic character types leaves having a trailing eos.
87 template <class _CharT
>
88 inline bool _S_is_basic_char_type(_CharT
*) { return false; }
89 template <class _CharT
>
90 inline bool _S_is_one_byte_char_type(_CharT
*) { return false; }
92 inline bool _S_is_basic_char_type(char*) { return true; }
93 inline bool _S_is_one_byte_char_type(char*) { return true; }
94 inline bool _S_is_basic_char_type(wchar_t*) { return true; }
96 // Store an eos iff _CharT is a basic character type.
97 // Do not reference _S_eos if it isn't.
98 template <class _CharT
>
99 inline void _S_cond_store_eos(_CharT
&) {}
101 inline void _S_cond_store_eos(char& __c
) { __c
= 0; }
102 inline void _S_cond_store_eos(wchar_t& __c
) { __c
= 0; }
104 // char_producers are logically functions that generate a section of
105 // a string. These can be convereted to ropes. The resulting rope
106 // invokes the char_producer on demand. This allows, for example,
107 // files to be viewed as ropes without reading the entire file.
108 template <class _CharT
>
109 class char_producer
{
111 virtual ~char_producer() {};
112 virtual void operator()(size_t __start_pos
, size_t __len
,
113 _CharT
* __buffer
) = 0;
114 // Buffer should really be an arbitrary output iterator.
115 // That way we could flatten directly into an ostream, etc.
116 // This is thoroughly impossible, since iterator types don't
117 // have runtime descriptions.
122 // Sequence must provide an append operation that appends an
123 // array to the sequence. Sequence buffers are useful only if
124 // appending an entire array is cheaper than appending element by element.
125 // This is true for many string representations.
126 // This should perhaps inherit from ostream<sequence::value_type>
127 // and be implemented correspondingly, so that they can be used
128 // for formatted. For the sake of portability, we don't do this yet.
130 // For now, sequence buffers behave as output iterators. But they also
131 // behave a little like basic_ostringstream<sequence::value_type> and a
132 // little like containers.
134 template<class _Sequence
, size_t _Buf_sz
= 100>
135 class sequence_buffer
: public iterator
<std::output_iterator_tag
,void,void,void,void>
138 typedef typename
_Sequence::value_type value_type
;
140 _Sequence
* _M_prefix
;
141 value_type _M_buffer
[_Buf_sz
];
145 _M_prefix
->append(_M_buffer
, _M_buffer
+ _M_buf_count
);
148 ~sequence_buffer() { flush(); }
149 sequence_buffer() : _M_prefix(0), _M_buf_count(0) {}
150 sequence_buffer(const sequence_buffer
& __x
) {
151 _M_prefix
= __x
._M_prefix
;
152 _M_buf_count
= __x
._M_buf_count
;
153 copy(__x
._M_buffer
, __x
._M_buffer
+ __x
._M_buf_count
, _M_buffer
);
155 sequence_buffer(sequence_buffer
& __x
) {
157 _M_prefix
= __x
._M_prefix
;
160 sequence_buffer(_Sequence
& __s
) : _M_prefix(&__s
), _M_buf_count(0) {}
161 sequence_buffer
& operator= (sequence_buffer
& __x
) {
163 _M_prefix
= __x
._M_prefix
;
167 sequence_buffer
& operator= (const sequence_buffer
& __x
) {
168 _M_prefix
= __x
._M_prefix
;
169 _M_buf_count
= __x
._M_buf_count
;
170 copy(__x
._M_buffer
, __x
._M_buffer
+ __x
._M_buf_count
, _M_buffer
);
173 void push_back(value_type __x
)
175 if (_M_buf_count
< _Buf_sz
) {
176 _M_buffer
[_M_buf_count
] = __x
;
184 void append(value_type
* __s
, size_t __len
)
186 if (__len
+ _M_buf_count
<= _Buf_sz
) {
187 size_t __i
= _M_buf_count
;
189 for (; __j
< __len
; __i
++, __j
++) {
190 _M_buffer
[__i
] = __s
[__j
];
192 _M_buf_count
+= __len
;
193 } else if (0 == _M_buf_count
) {
194 _M_prefix
->append(__s
, __s
+ __len
);
200 sequence_buffer
& write(value_type
* __s
, size_t __len
)
205 sequence_buffer
& put(value_type __x
)
210 sequence_buffer
& operator=(const value_type
& __rhs
)
215 sequence_buffer
& operator*() { return *this; }
216 sequence_buffer
& operator++() { return *this; }
217 sequence_buffer
& operator++(int) { return *this; }
220 // The following should be treated as private, at least for now.
221 template<class _CharT
>
222 class _Rope_char_consumer
{
224 // If we had member templates, these should not be virtual.
225 // For now we need to use run-time parametrization where
226 // compile-time would do. Hence this should all be private
228 // The symmetry with char_producer is accidental and temporary.
229 virtual ~_Rope_char_consumer() {};
230 virtual bool operator()(const _CharT
* __buffer
, size_t __len
) = 0;
233 // First a lot of forward declarations. The standard seems to require
234 // much stricter "declaration before use" than many of the implementations
236 template<class _CharT
, class _Alloc
=allocator
<_CharT
> > class rope
;
237 template<class _CharT
, class _Alloc
> struct _Rope_RopeConcatenation
;
238 template<class _CharT
, class _Alloc
> struct _Rope_RopeLeaf
;
239 template<class _CharT
, class _Alloc
> struct _Rope_RopeFunction
;
240 template<class _CharT
, class _Alloc
> struct _Rope_RopeSubstring
;
241 template<class _CharT
, class _Alloc
> class _Rope_iterator
;
242 template<class _CharT
, class _Alloc
> class _Rope_const_iterator
;
243 template<class _CharT
, class _Alloc
> class _Rope_char_ref_proxy
;
244 template<class _CharT
, class _Alloc
> class _Rope_char_ptr_proxy
;
246 template<class _CharT
, class _Alloc
>
247 bool operator== (const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __x
,
248 const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __y
);
250 template<class _CharT
, class _Alloc
>
251 _Rope_const_iterator
<_CharT
,_Alloc
> operator-
252 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
255 template<class _CharT
, class _Alloc
>
256 _Rope_const_iterator
<_CharT
,_Alloc
> operator+
257 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
260 template<class _CharT
, class _Alloc
>
261 _Rope_const_iterator
<_CharT
,_Alloc
> operator+
263 const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
);
265 template<class _CharT
, class _Alloc
>
267 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
268 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
);
270 template<class _CharT
, class _Alloc
>
272 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
273 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
);
275 template<class _CharT
, class _Alloc
>
277 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
278 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
);
280 template<class _CharT
, class _Alloc
>
281 _Rope_iterator
<_CharT
,_Alloc
> operator-
282 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
285 template<class _CharT
, class _Alloc
>
286 _Rope_iterator
<_CharT
,_Alloc
> operator+
287 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
290 template<class _CharT
, class _Alloc
>
291 _Rope_iterator
<_CharT
,_Alloc
> operator+
293 const _Rope_iterator
<_CharT
,_Alloc
>& __x
);
295 template<class _CharT
, class _Alloc
>
297 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
298 const _Rope_iterator
<_CharT
,_Alloc
>& __y
);
300 template<class _CharT
, class _Alloc
>
302 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
303 const _Rope_iterator
<_CharT
,_Alloc
>& __y
);
305 template<class _CharT
, class _Alloc
>
307 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
308 const _Rope_iterator
<_CharT
,_Alloc
>& __y
);
310 template<class _CharT
, class _Alloc
>
311 rope
<_CharT
,_Alloc
> operator+ (const rope
<_CharT
,_Alloc
>& __left
,
312 const rope
<_CharT
,_Alloc
>& __right
);
314 template<class _CharT
, class _Alloc
>
315 rope
<_CharT
,_Alloc
> operator+ (const rope
<_CharT
,_Alloc
>& __left
,
316 const _CharT
* __right
);
318 template<class _CharT
, class _Alloc
>
319 rope
<_CharT
,_Alloc
> operator+ (const rope
<_CharT
,_Alloc
>& __left
,
322 // Some helpers, so we can use power on ropes.
323 // See below for why this isn't local to the implementation.
325 // This uses a nonstandard refcount convention.
326 // The result has refcount 0.
327 template<class _CharT
, class _Alloc
>
328 struct _Rope_Concat_fn
329 : public std::binary_function
<rope
<_CharT
,_Alloc
>, rope
<_CharT
,_Alloc
>,
330 rope
<_CharT
,_Alloc
> > {
331 rope
<_CharT
,_Alloc
> operator() (const rope
<_CharT
,_Alloc
>& __x
,
332 const rope
<_CharT
,_Alloc
>& __y
) {
337 template <class _CharT
, class _Alloc
>
340 identity_element(_Rope_Concat_fn
<_CharT
, _Alloc
>)
342 return rope
<_CharT
,_Alloc
>();
347 // What follows should really be local to rope. Unfortunately,
348 // that doesn't work, since it makes it impossible to define generic
349 // equality on rope iterators. According to the draft standard, the
350 // template parameters for such an equality operator cannot be inferred
351 // from the occurrence of a member class as a parameter.
352 // (SGI compilers in fact allow this, but the __result wouldn't be
354 // Similarly, some of the static member functions are member functions
355 // only to avoid polluting the global namespace, and to circumvent
356 // restrictions on type inference for template functions.
360 // The internal data structure for representing a rope. This is
361 // private to the implementation. A rope is really just a pointer
364 // A few basic functions for manipulating this data structure
365 // are members of _RopeRep. Most of the more complex algorithms
366 // are implemented as rope members.
368 // Some of the static member functions of _RopeRep have identically
369 // named functions in rope that simply invoke the _RopeRep versions.
371 // A macro to introduce various allocation and deallocation functions
372 // These need to be defined differently depending on whether or not
373 // we are using standard conforming allocators, and whether the allocator
374 // instances have real state. Thus this macro is invoked repeatedly
375 // with different definitions of __ROPE_DEFINE_ALLOC.
376 // __ROPE_DEFINE_ALLOC(type,name) defines
377 // type * name_allocate(size_t) and
378 // void name_deallocate(tipe *, size_t)
379 // Both functions may or may not be static.
381 #define __ROPE_DEFINE_ALLOCS(__a) \
382 __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \
383 typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
384 __ROPE_DEFINE_ALLOC(__C,_C) \
385 typedef _Rope_RopeLeaf<_CharT,__a> __L; \
386 __ROPE_DEFINE_ALLOC(__L,_L) \
387 typedef _Rope_RopeFunction<_CharT,__a> __F; \
388 __ROPE_DEFINE_ALLOC(__F,_F) \
389 typedef _Rope_RopeSubstring<_CharT,__a> __S; \
390 __ROPE_DEFINE_ALLOC(__S,_S)
392 // Internal rope nodes potentially store a copy of the allocator
393 // instance used to allocate them. This is mostly redundant.
394 // But the alternative would be to pass allocator instances around
395 // in some form to nearly all internal functions, since any pointer
396 // assignment may result in a zero reference count and thus require
398 // The _Rope_rep_base class encapsulates
399 // the differences between SGI-style allocators and standard-conforming
402 #define __STATIC_IF_SGI_ALLOC /* not static */
404 // Base class for ordinary allocators.
405 template <class _CharT
, class _Allocator
, bool _IsStatic
>
406 class _Rope_rep_alloc_base
{
408 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
410 allocator_type
get_allocator() const { return _M_data_allocator
; }
411 _Rope_rep_alloc_base(size_t __size
, const allocator_type
& __a
)
412 : _M_size(__size
), _M_data_allocator(__a
) {}
413 size_t _M_size
; // This is here only to avoid wasting space
414 // for an otherwise empty base class.
418 allocator_type _M_data_allocator
;
420 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
422 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
423 /*static*/ _Tp * __name##_allocate(size_t __n) \
424 { return __name##Allocator(_M_data_allocator).allocate(__n); } \
425 void __name##_deallocate(_Tp* __p, size_t __n) \
426 { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
427 __ROPE_DEFINE_ALLOCS(_Allocator
);
428 # undef __ROPE_DEFINE_ALLOC
431 // Specialization for allocators that have the property that we don't
432 // actually have to store an allocator object.
433 template <class _CharT
, class _Allocator
>
434 class _Rope_rep_alloc_base
<_CharT
,_Allocator
,true> {
436 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
438 allocator_type
get_allocator() const { return allocator_type(); }
439 _Rope_rep_alloc_base(size_t __size
, const allocator_type
&)
445 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
447 _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \
449 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
450 static _Tp* __name##_allocate(size_t __n) \
451 { return __name##Alloc::allocate(__n); } \
452 void __name##_deallocate(_Tp *__p, size_t __n) \
453 { __name##Alloc::deallocate(__p, __n); }
454 __ROPE_DEFINE_ALLOCS(_Allocator
);
455 # undef __ROPE_DEFINE_ALLOC
458 template <class _CharT
, class _Alloc
>
459 struct _Rope_rep_base
460 : public _Rope_rep_alloc_base
<_CharT
,_Alloc
,
461 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
463 typedef _Rope_rep_alloc_base
<_CharT
,_Alloc
,
464 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
466 typedef typename
_Base::allocator_type allocator_type
;
467 _Rope_rep_base(size_t __size
, const allocator_type
& __a
)
468 : _Base(__size
, __a
) {}
472 template<class _CharT
, class _Alloc
>
473 struct _Rope_RopeRep
: public _Rope_rep_base
<_CharT
,_Alloc
>
479 enum { _S_max_rope_depth
= 45 };
480 enum _Tag
{_S_leaf
, _S_concat
, _S_substringfn
, _S_function
};
482 bool _M_is_balanced
:8;
483 unsigned char _M_depth
;
484 __GC_CONST _CharT
* _M_c_string
;
485 /* Flattened version of string, if needed. */
487 /* If it's not 0, then the memory is owned */
489 /* In the case of a leaf, this may point to */
490 /* the same memory as the data field. */
491 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
493 _Rope_RopeRep(_Tag __t
, int __d
, bool __b
, size_t __size
,
495 : _Rope_rep_base
<_CharT
,_Alloc
>(__size
, __a
),
499 _M_tag(__t
), _M_is_balanced(__b
), _M_depth(__d
), _M_c_string(0)
504 static void _S_free_string(__GC_CONST _CharT
*, size_t __len
,
506 # define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
507 // Deallocate data section of a leaf.
508 // This shouldn't be a member function.
509 // But its hard to do anything else at the
510 // moment, because it's templatized w.r.t.
512 // Does nothing if __GC is defined.
514 void _M_free_c_string();
516 // Deallocate t. Assumes t is not 0.
517 void _M_unref_nonnil()
519 if (0 == _M_decr()) _M_free_tree();
525 static void _S_unref(_Rope_RopeRep
* __t
)
528 __t
->_M_unref_nonnil();
531 static void _S_ref(_Rope_RopeRep
* __t
)
533 if (0 != __t
) __t
->_M_incr();
535 static void _S_free_if_unref(_Rope_RopeRep
* __t
)
537 if (0 != __t
&& 0 == __t
->_M_ref_count
) __t
->_M_free_tree();
540 void _M_unref_nonnil() {}
541 void _M_ref_nonnil() {}
542 static void _S_unref(_Rope_RopeRep
*) {}
543 static void _S_ref(_Rope_RopeRep
*) {}
544 static void _S_free_if_unref(_Rope_RopeRep
*) {}
549 template<class _CharT
, class _Alloc
>
550 struct _Rope_RopeLeaf
: public _Rope_RopeRep
<_CharT
,_Alloc
> {
552 // Apparently needed by VC++
553 // The data fields of leaves are allocated with some
554 // extra space, to accommodate future growth and for basic
555 // character types, to hold a trailing eos character.
556 enum { _S_alloc_granularity
= 8 };
557 static size_t _S_rounded_up_size(size_t __n
) {
558 size_t __size_with_eos
;
560 if (_S_is_basic_char_type((_CharT
*)0)) {
561 __size_with_eos
= __n
+ 1;
563 __size_with_eos
= __n
;
566 return __size_with_eos
;
568 // Allow slop for in-place expansion.
569 return (__size_with_eos
+ _S_alloc_granularity
-1)
570 &~ (_S_alloc_granularity
-1);
573 __GC_CONST _CharT
* _M_data
; /* Not necessarily 0 terminated. */
574 /* The allocated size is */
575 /* _S_rounded_up_size(size), except */
576 /* in the GC case, in which it */
577 /* doesn't matter. */
578 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
580 _Rope_RopeLeaf(__GC_CONST _CharT
* __d
, size_t __size
, allocator_type __a
)
581 : _Rope_RopeRep
<_CharT
,_Alloc
>(_S_leaf
, 0, true, __size
, __a
),
584 if (_S_is_basic_char_type((_CharT
*)0)) {
585 // already eos terminated.
589 // The constructor assumes that d has been allocated with
590 // the proper allocator and the properly padded size.
591 // In contrast, the destructor deallocates the data:
594 if (_M_data
!= _M_c_string
) {
597 __STL_FREE_STRING(_M_data
, _M_size
, get_allocator());
602 template<class _CharT
, class _Alloc
>
603 struct _Rope_RopeConcatenation
: public _Rope_RopeRep
<_CharT
,_Alloc
> {
605 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_left
;
606 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_right
;
607 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
609 _Rope_RopeConcatenation(_Rope_RopeRep
<_CharT
,_Alloc
>* __l
,
610 _Rope_RopeRep
<_CharT
,_Alloc
>* __r
,
613 : _Rope_RopeRep
<_CharT
,_Alloc
>(_S_concat
,
614 std::max(__l
->_M_depth
, __r
->_M_depth
) + 1,
616 __l
->_M_size
+ __r
->_M_size
, __a
),
617 _M_left(__l
), _M_right(__r
)
620 ~_Rope_RopeConcatenation() {
622 _M_left
->_M_unref_nonnil();
623 _M_right
->_M_unref_nonnil();
628 template<class _CharT
, class _Alloc
>
629 struct _Rope_RopeFunction
: public _Rope_RopeRep
<_CharT
,_Alloc
> {
631 char_producer
<_CharT
>* _M_fn
;
633 bool _M_delete_when_done
; // Char_producer is owned by the
634 // rope and should be explicitly
635 // deleted when the rope becomes
638 // In the GC case, we either register the rope for
639 // finalization, or not. Thus the field is unnecessary;
640 // the information is stored in the collector data structures.
641 // We do need a finalization procedure to be invoked by the
643 static void _S_fn_finalization_proc(void * __tree
, void *) {
644 delete ((_Rope_RopeFunction
*)__tree
) -> _M_fn
;
647 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
649 _Rope_RopeFunction(char_producer
<_CharT
>* __f
, size_t __size
,
650 bool __d
, allocator_type __a
)
651 : _Rope_RopeRep
<_CharT
,_Alloc
>(_S_function
, 0, true, __size
, __a
)
654 , _M_delete_when_done(__d
)
659 GC_REGISTER_FINALIZER(
660 this, _Rope_RopeFunction::_S_fn_finalization_proc
, 0, 0, 0);
665 ~_Rope_RopeFunction() {
667 if (_M_delete_when_done
) {
673 // Substring results are usually represented using just
674 // concatenation nodes. But in the case of very long flat ropes
675 // or ropes with a functional representation that isn't practical.
676 // In that case, we represent the __result as a special case of
677 // RopeFunction, whose char_producer points back to the rope itself.
678 // In all cases except repeated substring operations and
679 // deallocation, we treat the __result as a RopeFunction.
680 template<class _CharT
, class _Alloc
>
681 struct _Rope_RopeSubstring
: public _Rope_RopeFunction
<_CharT
,_Alloc
>,
682 public char_producer
<_CharT
> {
684 // XXX this whole class should be rewritten.
685 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_base
; // not 0
687 virtual void operator()(size_t __start_pos
, size_t __req_len
,
689 switch(_M_base
->_M_tag
) {
693 char_producer
<_CharT
>* __fn
=
694 ((_Rope_RopeFunction
<_CharT
,_Alloc
>*)_M_base
)->_M_fn
;
695 (*__fn
)(__start_pos
+ _M_start
, __req_len
, __buffer
);
700 __GC_CONST _CharT
* __s
=
701 ((_Rope_RopeLeaf
<_CharT
,_Alloc
>*)_M_base
)->_M_data
;
702 uninitialized_copy_n(__s
+ __start_pos
+ _M_start
, __req_len
,
710 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
712 _Rope_RopeSubstring(_Rope_RopeRep
<_CharT
,_Alloc
>* __b
, size_t __s
,
713 size_t __l
, allocator_type __a
)
714 : _Rope_RopeFunction
<_CharT
,_Alloc
>(this, __l
, false, __a
),
715 char_producer
<_CharT
>(),
720 _M_base
->_M_ref_nonnil();
722 _M_tag
= _S_substringfn
;
724 virtual ~_Rope_RopeSubstring()
727 _M_base
->_M_unref_nonnil();
728 // _M_free_c_string(); -- done by parent class
734 // Self-destructing pointers to Rope_rep.
735 // These are not conventional smart pointers. Their
736 // only purpose in life is to ensure that unref is called
737 // on the pointer either at normal exit or if an exception
738 // is raised. It is the caller's responsibility to
739 // adjust reference counts when these pointers are initialized
740 // or assigned to. (This convention significantly reduces
741 // the number of potentially expensive reference count
744 template<class _CharT
, class _Alloc
>
745 struct _Rope_self_destruct_ptr
{
746 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_ptr
;
747 ~_Rope_self_destruct_ptr()
748 { _Rope_RopeRep
<_CharT
,_Alloc
>::_S_unref(_M_ptr
); }
750 _Rope_self_destruct_ptr() : _M_ptr(0) {};
752 _Rope_self_destruct_ptr() {};
754 _Rope_self_destruct_ptr(_Rope_RopeRep
<_CharT
,_Alloc
>* __p
) : _M_ptr(__p
) {}
755 _Rope_RopeRep
<_CharT
,_Alloc
>& operator*() { return *_M_ptr
; }
756 _Rope_RopeRep
<_CharT
,_Alloc
>* operator->() { return _M_ptr
; }
757 operator _Rope_RopeRep
<_CharT
,_Alloc
>*() { return _M_ptr
; }
758 _Rope_self_destruct_ptr
& operator= (_Rope_RopeRep
<_CharT
,_Alloc
>* __x
)
759 { _M_ptr
= __x
; return *this; }
763 // Dereferencing a nonconst iterator has to return something
764 // that behaves almost like a reference. It's not possible to
765 // return an actual reference since assignment requires extra
766 // work. And we would get into the same problems as with the
767 // CD2 version of basic_string.
768 template<class _CharT
, class _Alloc
>
769 class _Rope_char_ref_proxy
{
770 friend class rope
<_CharT
,_Alloc
>;
771 friend class _Rope_iterator
<_CharT
,_Alloc
>;
772 friend class _Rope_char_ptr_proxy
<_CharT
,_Alloc
>;
774 typedef _Rope_RopeRep
<_CharT
,_Alloc
>* _Self_destruct_ptr
;
776 typedef _Rope_self_destruct_ptr
<_CharT
,_Alloc
> _Self_destruct_ptr
;
778 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
779 typedef rope
<_CharT
,_Alloc
> _My_rope
;
782 bool _M_current_valid
;
783 _My_rope
* _M_root
; // The whole rope.
785 _Rope_char_ref_proxy(_My_rope
* __r
, size_t __p
)
786 : _M_pos(__p
), _M_current_valid(false), _M_root(__r
) {}
787 _Rope_char_ref_proxy(const _Rope_char_ref_proxy
& __x
)
788 : _M_pos(__x
._M_pos
), _M_current_valid(false), _M_root(__x
._M_root
) {}
789 // Don't preserve cache if the reference can outlive the
790 // expression. We claim that's not possible without calling
791 // a copy constructor or generating reference to a proxy
792 // reference. We declare the latter to have undefined semantics.
793 _Rope_char_ref_proxy(_My_rope
* __r
, size_t __p
, _CharT __c
)
794 : _M_pos(__p
), _M_current(__c
), _M_current_valid(true), _M_root(__r
) {}
795 inline operator _CharT () const;
796 _Rope_char_ref_proxy
& operator= (_CharT __c
);
797 _Rope_char_ptr_proxy
<_CharT
,_Alloc
> operator& () const;
798 _Rope_char_ref_proxy
& operator= (const _Rope_char_ref_proxy
& __c
) {
799 return operator=((_CharT
)__c
);
803 template<class _CharT
, class __Alloc
>
804 inline void swap(_Rope_char_ref_proxy
<_CharT
, __Alloc
> __a
,
805 _Rope_char_ref_proxy
<_CharT
, __Alloc
> __b
) {
811 template<class _CharT
, class _Alloc
>
812 class _Rope_char_ptr_proxy
{
813 // XXX this class should be rewritten.
814 friend class _Rope_char_ref_proxy
<_CharT
,_Alloc
>;
816 rope
<_CharT
,_Alloc
>* _M_root
; // The whole rope.
818 _Rope_char_ptr_proxy(const _Rope_char_ref_proxy
<_CharT
,_Alloc
>& __x
)
819 : _M_pos(__x
._M_pos
), _M_root(__x
._M_root
) {}
820 _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy
& __x
)
821 : _M_pos(__x
._M_pos
), _M_root(__x
._M_root
) {}
822 _Rope_char_ptr_proxy() {}
823 _Rope_char_ptr_proxy(_CharT
* __x
) : _M_root(0), _M_pos(0) {
825 _Rope_char_ptr_proxy
&
826 operator= (const _Rope_char_ptr_proxy
& __x
) {
828 _M_root
= __x
._M_root
;
831 template<class _CharT2
, class _Alloc2
>
832 friend bool operator== (const _Rope_char_ptr_proxy
<_CharT2
,_Alloc2
>& __x
,
833 const _Rope_char_ptr_proxy
<_CharT2
,_Alloc2
>& __y
);
834 _Rope_char_ref_proxy
<_CharT
,_Alloc
> operator*() const {
835 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(_M_root
, _M_pos
);
841 // Unlike in the C version, we cache only part of the stack
842 // for rope iterators, since they must be efficiently copyable.
843 // When we run out of cache, we have to reconstruct the iterator
845 // Pointers from iterators are not included in reference counts.
846 // Iterators are assumed to be thread private. Ropes can
849 template<class _CharT
, class _Alloc
>
850 class _Rope_iterator_base
851 : public iterator
<std::random_access_iterator_tag
, _CharT
>
853 friend class rope
<_CharT
,_Alloc
>;
855 typedef _Alloc _allocator_type
; // used in _Rope_rotate, VC++ workaround
856 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
857 // Borland doesn't want this to be protected.
859 enum { _S_path_cache_len
= 4 }; // Must be <= 9.
860 enum { _S_iterator_buf_len
= 15 };
861 size_t _M_current_pos
;
862 _RopeRep
* _M_root
; // The whole rope.
863 size_t _M_leaf_pos
; // Starting position for current leaf
864 __GC_CONST _CharT
* _M_buf_start
;
866 // containing current char.
867 __GC_CONST _CharT
* _M_buf_ptr
;
868 // Pointer to current char in buffer.
869 // != 0 ==> buffer valid.
870 __GC_CONST _CharT
* _M_buf_end
;
871 // One past __last valid char in buffer.
872 // What follows is the path cache. We go out of our
873 // way to make this compact.
874 // Path_end contains the bottom section of the path from
875 // the root to the current leaf.
876 const _RopeRep
* _M_path_end
[_S_path_cache_len
];
877 int _M_leaf_index
; // Last valid __pos in path_end;
878 // _M_path_end[0] ... _M_path_end[leaf_index-1]
879 // point to concatenation nodes.
880 unsigned char _M_path_directions
;
881 // (path_directions >> __i) & 1 is 1
882 // iff we got from _M_path_end[leaf_index - __i - 1]
883 // to _M_path_end[leaf_index - __i] by going to the
884 // __right. Assumes path_cache_len <= 9.
885 _CharT _M_tmp_buf
[_S_iterator_buf_len
];
886 // Short buffer for surrounding chars.
887 // This is useful primarily for
888 // RopeFunctions. We put the buffer
889 // here to avoid locking in the
890 // multithreaded case.
891 // The cached path is generally assumed to be valid
892 // only if the buffer is valid.
893 static void _S_setbuf(_Rope_iterator_base
& __x
);
894 // Set buffer contents given
896 static void _S_setcache(_Rope_iterator_base
& __x
);
897 // Set buffer contents and
899 static void _S_setcache_for_incr(_Rope_iterator_base
& __x
);
900 // As above, but assumes path
901 // cache is valid for previous posn.
902 _Rope_iterator_base() {}
903 _Rope_iterator_base(_RopeRep
* __root
, size_t __pos
)
904 : _M_current_pos(__pos
), _M_root(__root
), _M_buf_ptr(0) {}
905 void _M_incr(size_t __n
);
906 void _M_decr(size_t __n
);
908 size_t index() const { return _M_current_pos
; }
909 _Rope_iterator_base(const _Rope_iterator_base
& __x
) {
910 if (0 != __x
._M_buf_ptr
) {
913 _M_current_pos
= __x
._M_current_pos
;
914 _M_root
= __x
._M_root
;
920 template<class _CharT
, class _Alloc
> class _Rope_iterator
;
922 template<class _CharT
, class _Alloc
>
923 class _Rope_const_iterator
: public _Rope_iterator_base
<_CharT
,_Alloc
> {
924 friend class rope
<_CharT
,_Alloc
>;
926 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
927 // The one from the base class may not be directly visible.
928 _Rope_const_iterator(const _RopeRep
* __root
, size_t __pos
):
929 _Rope_iterator_base
<_CharT
,_Alloc
>(
930 const_cast<_RopeRep
*>(__root
), __pos
)
931 // Only nonconst iterators modify root ref count
934 typedef _CharT reference
; // Really a value. Returning a reference
935 // Would be a mess, since it would have
936 // to be included in refcount.
937 typedef const _CharT
* pointer
;
940 _Rope_const_iterator() {};
941 _Rope_const_iterator(const _Rope_const_iterator
& __x
) :
942 _Rope_iterator_base
<_CharT
,_Alloc
>(__x
) { }
943 _Rope_const_iterator(const _Rope_iterator
<_CharT
,_Alloc
>& __x
);
944 _Rope_const_iterator(const rope
<_CharT
,_Alloc
>& __r
, size_t __pos
) :
945 _Rope_iterator_base
<_CharT
,_Alloc
>(__r
._M_tree_ptr
, __pos
) {}
946 _Rope_const_iterator
& operator= (const _Rope_const_iterator
& __x
) {
947 if (0 != __x
._M_buf_ptr
) {
948 *(static_cast<_Rope_iterator_base
<_CharT
,_Alloc
>*>(this)) = __x
;
950 _M_current_pos
= __x
._M_current_pos
;
951 _M_root
= __x
._M_root
;
956 reference
operator*() {
957 if (0 == _M_buf_ptr
) _S_setcache(*this);
960 _Rope_const_iterator
& operator++() {
961 __GC_CONST _CharT
* __next
;
962 if (0 != _M_buf_ptr
&& (__next
= _M_buf_ptr
+ 1) < _M_buf_end
) {
970 _Rope_const_iterator
& operator+=(ptrdiff_t __n
) {
978 _Rope_const_iterator
& operator--() {
982 _Rope_const_iterator
& operator-=(ptrdiff_t __n
) {
990 _Rope_const_iterator
operator++(int) {
991 size_t __old_pos
= _M_current_pos
;
993 return _Rope_const_iterator
<_CharT
,_Alloc
>(_M_root
, __old_pos
);
994 // This makes a subsequent dereference expensive.
995 // Perhaps we should instead copy the iterator
996 // if it has a valid cache?
998 _Rope_const_iterator
operator--(int) {
999 size_t __old_pos
= _M_current_pos
;
1001 return _Rope_const_iterator
<_CharT
,_Alloc
>(_M_root
, __old_pos
);
1003 template<class _CharT2
, class _Alloc2
>
1004 friend _Rope_const_iterator
<_CharT2
,_Alloc2
> operator-
1005 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1007 template<class _CharT2
, class _Alloc2
>
1008 friend _Rope_const_iterator
<_CharT2
,_Alloc2
> operator+
1009 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1011 template<class _CharT2
, class _Alloc2
>
1012 friend _Rope_const_iterator
<_CharT2
,_Alloc2
> operator+
1014 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
);
1015 reference
operator[](size_t __n
) {
1016 return rope
<_CharT
,_Alloc
>::_S_fetch(_M_root
, _M_current_pos
+ __n
);
1019 template<class _CharT2
, class _Alloc2
>
1020 friend bool operator==
1021 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1022 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __y
);
1023 template<class _CharT2
, class _Alloc2
>
1024 friend bool operator<
1025 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1026 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __y
);
1027 template<class _CharT2
, class _Alloc2
>
1028 friend ptrdiff_t operator-
1029 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1030 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __y
);
1033 template<class _CharT
, class _Alloc
>
1034 class _Rope_iterator
: public _Rope_iterator_base
<_CharT
,_Alloc
> {
1035 friend class rope
<_CharT
,_Alloc
>;
1037 typedef typename _Rope_iterator_base
<_CharT
,_Alloc
>::_RopeRep _RopeRep
;
1038 rope
<_CharT
,_Alloc
>* _M_root_rope
;
1039 // root is treated as a cached version of this,
1040 // and is used to detect changes to the underlying
1042 // Root is included in the reference count.
1043 // This is necessary so that we can detect changes reliably.
1044 // Unfortunately, it requires careful bookkeeping for the
1046 _Rope_iterator(rope
<_CharT
,_Alloc
>* __r
, size_t __pos
)
1047 : _Rope_iterator_base
<_CharT
,_Alloc
>(__r
->_M_tree_ptr
, __pos
),
1049 { _RopeRep::_S_ref(_M_root
); if (!(__r
-> empty()))_S_setcache(*this); }
1053 typedef _Rope_char_ref_proxy
<_CharT
,_Alloc
> reference
;
1054 typedef _Rope_char_ref_proxy
<_CharT
,_Alloc
>* pointer
;
1057 rope
<_CharT
,_Alloc
>& container() { return *_M_root_rope
; }
1059 _M_root
= 0; // Needed for reference counting.
1061 _Rope_iterator(const _Rope_iterator
& __x
) :
1062 _Rope_iterator_base
<_CharT
,_Alloc
>(__x
) {
1063 _M_root_rope
= __x
._M_root_rope
;
1064 _RopeRep::_S_ref(_M_root
);
1066 _Rope_iterator(rope
<_CharT
,_Alloc
>& __r
, size_t __pos
);
1068 _RopeRep::_S_unref(_M_root
);
1070 _Rope_iterator
& operator= (const _Rope_iterator
& __x
) {
1071 _RopeRep
* __old
= _M_root
;
1073 _RopeRep::_S_ref(__x
._M_root
);
1074 if (0 != __x
._M_buf_ptr
) {
1075 _M_root_rope
= __x
._M_root_rope
;
1076 *(static_cast<_Rope_iterator_base
<_CharT
,_Alloc
>*>(this)) = __x
;
1078 _M_current_pos
= __x
._M_current_pos
;
1079 _M_root
= __x
._M_root
;
1080 _M_root_rope
= __x
._M_root_rope
;
1083 _RopeRep::_S_unref(__old
);
1086 reference
operator*() {
1088 if (0 == _M_buf_ptr
) {
1089 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(
1090 _M_root_rope
, _M_current_pos
);
1092 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(
1093 _M_root_rope
, _M_current_pos
, *_M_buf_ptr
);
1096 _Rope_iterator
& operator++() {
1100 _Rope_iterator
& operator+=(ptrdiff_t __n
) {
1108 _Rope_iterator
& operator--() {
1112 _Rope_iterator
& operator-=(ptrdiff_t __n
) {
1120 _Rope_iterator
operator++(int) {
1121 size_t __old_pos
= _M_current_pos
;
1123 return _Rope_iterator
<_CharT
,_Alloc
>(_M_root_rope
, __old_pos
);
1125 _Rope_iterator
operator--(int) {
1126 size_t __old_pos
= _M_current_pos
;
1128 return _Rope_iterator
<_CharT
,_Alloc
>(_M_root_rope
, __old_pos
);
1130 reference
operator[](ptrdiff_t __n
) {
1131 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(
1132 _M_root_rope
, _M_current_pos
+ __n
);
1135 template<class _CharT2
, class _Alloc2
>
1136 friend bool operator==
1137 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1138 const _Rope_iterator
<_CharT2
,_Alloc2
>& __y
);
1139 template<class _CharT2
, class _Alloc2
>
1140 friend bool operator<
1141 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1142 const _Rope_iterator
<_CharT2
,_Alloc2
>& __y
);
1143 template<class _CharT2
, class _Alloc2
>
1144 friend ptrdiff_t operator-
1145 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1146 const _Rope_iterator
<_CharT2
,_Alloc2
>& __y
);
1147 template<class _CharT2
, class _Alloc2
>
1148 friend _Rope_iterator
<_CharT2
,_Alloc2
> operator-
1149 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1151 template<class _CharT2
, class _Alloc2
>
1152 friend _Rope_iterator
<_CharT2
,_Alloc2
> operator+
1153 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1155 template<class _CharT2
, class _Alloc2
>
1156 friend _Rope_iterator
<_CharT2
,_Alloc2
> operator+
1158 const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
);
1161 // The rope base class encapsulates
1162 // the differences between SGI-style allocators and standard-conforming
1165 // Base class for ordinary allocators.
1166 template <class _CharT
, class _Allocator
, bool _IsStatic
>
1167 class _Rope_alloc_base
{
1169 typedef _Rope_RopeRep
<_CharT
,_Allocator
> _RopeRep
;
1170 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
1172 allocator_type
get_allocator() const { return _M_data_allocator
; }
1173 _Rope_alloc_base(_RopeRep
*__t
, const allocator_type
& __a
)
1174 : _M_tree_ptr(__t
), _M_data_allocator(__a
) {}
1175 _Rope_alloc_base(const allocator_type
& __a
)
1176 : _M_data_allocator(__a
) {}
1179 // The only data members of a rope:
1180 allocator_type _M_data_allocator
;
1181 _RopeRep
* _M_tree_ptr
;
1183 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
1185 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
1186 _Tp* __name##_allocate(size_t __n) const \
1187 { return __name##Allocator(_M_data_allocator).allocate(__n); } \
1188 void __name##_deallocate(_Tp *__p, size_t __n) const \
1189 { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
1190 __ROPE_DEFINE_ALLOCS(_Allocator
)
1191 # undef __ROPE_DEFINE_ALLOC
1194 // Specialization for allocators that have the property that we don't
1195 // actually have to store an allocator object.
1196 template <class _CharT
, class _Allocator
>
1197 class _Rope_alloc_base
<_CharT
,_Allocator
,true> {
1199 typedef _Rope_RopeRep
<_CharT
,_Allocator
> _RopeRep
;
1200 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
1202 allocator_type
get_allocator() const { return allocator_type(); }
1203 _Rope_alloc_base(_RopeRep
*__t
, const allocator_type
&)
1204 : _M_tree_ptr(__t
) {}
1205 _Rope_alloc_base(const allocator_type
&) {}
1208 // The only data member of a rope:
1209 _RopeRep
*_M_tree_ptr
;
1211 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
1213 _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \
1215 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
1216 static _Tp* __name##_allocate(size_t __n) \
1217 { return __name##Alloc::allocate(__n); } \
1218 static void __name##_deallocate(_Tp *__p, size_t __n) \
1219 { __name##Alloc::deallocate(__p, __n); }
1220 __ROPE_DEFINE_ALLOCS(_Allocator
)
1221 # undef __ROPE_DEFINE_ALLOC
1224 template <class _CharT
, class _Alloc
>
1226 : public _Rope_alloc_base
<_CharT
,_Alloc
,
1227 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
1229 typedef _Rope_alloc_base
<_CharT
,_Alloc
,
1230 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
1232 typedef typename
_Base::allocator_type allocator_type
;
1233 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
1234 // The one in _Base may not be visible due to template rules.
1235 _Rope_base(_RopeRep
* __t
, const allocator_type
& __a
) : _Base(__t
, __a
) {}
1236 _Rope_base(const allocator_type
& __a
) : _Base(__a
) {}
1240 template <class _CharT
, class _Alloc
>
1241 class rope
: public _Rope_base
<_CharT
,_Alloc
> {
1243 typedef _CharT value_type
;
1244 typedef ptrdiff_t difference_type
;
1245 typedef size_t size_type
;
1246 typedef _CharT const_reference
;
1247 typedef const _CharT
* const_pointer
;
1248 typedef _Rope_iterator
<_CharT
,_Alloc
> iterator
;
1249 typedef _Rope_const_iterator
<_CharT
,_Alloc
> const_iterator
;
1250 typedef _Rope_char_ref_proxy
<_CharT
,_Alloc
> reference
;
1251 typedef _Rope_char_ptr_proxy
<_CharT
,_Alloc
> pointer
;
1253 friend class _Rope_iterator
<_CharT
,_Alloc
>;
1254 friend class _Rope_const_iterator
<_CharT
,_Alloc
>;
1255 friend struct _Rope_RopeRep
<_CharT
,_Alloc
>;
1256 friend class _Rope_iterator_base
<_CharT
,_Alloc
>;
1257 friend class _Rope_char_ptr_proxy
<_CharT
,_Alloc
>;
1258 friend class _Rope_char_ref_proxy
<_CharT
,_Alloc
>;
1259 friend struct _Rope_RopeSubstring
<_CharT
,_Alloc
>;
1262 typedef _Rope_base
<_CharT
,_Alloc
> _Base
;
1263 typedef typename
_Base::allocator_type allocator_type
;
1264 using _Base::_M_tree_ptr
;
1265 typedef __GC_CONST _CharT
* _Cstrptr
;
1267 static _CharT _S_empty_c_str
[1];
1269 static bool _S_is0(_CharT __c
) { return __c
== _S_eos((_CharT
*)0); }
1270 enum { _S_copy_max
= 23 };
1271 // For strings shorter than _S_copy_max, we copy to
1274 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
1275 typedef _Rope_RopeConcatenation
<_CharT
,_Alloc
> _RopeConcatenation
;
1276 typedef _Rope_RopeLeaf
<_CharT
,_Alloc
> _RopeLeaf
;
1277 typedef _Rope_RopeFunction
<_CharT
,_Alloc
> _RopeFunction
;
1278 typedef _Rope_RopeSubstring
<_CharT
,_Alloc
> _RopeSubstring
;
1280 // Retrieve a character at the indicated position.
1281 static _CharT
_S_fetch(_RopeRep
* __r
, size_type __pos
);
1284 // Obtain a pointer to the character at the indicated position.
1285 // The pointer can be used to change the character.
1286 // If such a pointer cannot be produced, as is frequently the
1287 // case, 0 is returned instead.
1288 // (Returns nonzero only if all nodes in the path have a refcount
1290 static _CharT
* _S_fetch_ptr(_RopeRep
* __r
, size_type __pos
);
1293 static bool _S_apply_to_pieces(
1294 // should be template parameter
1295 _Rope_char_consumer
<_CharT
>& __c
,
1296 const _RopeRep
* __r
,
1297 size_t __begin
, size_t __end
);
1298 // begin and end are assumed to be in range.
1301 static void _S_unref(_RopeRep
* __t
)
1303 _RopeRep::_S_unref(__t
);
1305 static void _S_ref(_RopeRep
* __t
)
1307 _RopeRep::_S_ref(__t
);
1310 static void _S_unref(_RopeRep
*) {}
1311 static void _S_ref(_RopeRep
*) {}
1316 typedef _Rope_RopeRep
<_CharT
,_Alloc
>* _Self_destruct_ptr
;
1318 typedef _Rope_self_destruct_ptr
<_CharT
,_Alloc
> _Self_destruct_ptr
;
1321 // _Result is counted in refcount.
1322 static _RopeRep
* _S_substring(_RopeRep
* __base
,
1323 size_t __start
, size_t __endp1
);
1325 static _RopeRep
* _S_concat_char_iter(_RopeRep
* __r
,
1326 const _CharT
* __iter
, size_t __slen
);
1327 // Concatenate rope and char ptr, copying __s.
1328 // Should really take an arbitrary iterator.
1329 // Result is counted in refcount.
1330 static _RopeRep
* _S_destr_concat_char_iter(_RopeRep
* __r
,
1331 const _CharT
* __iter
, size_t __slen
)
1332 // As above, but one reference to __r is about to be
1333 // destroyed. Thus the pieces may be recycled if all
1334 // relevant reference counts are 1.
1336 // We can't really do anything since refcounts are unavailable.
1337 { return _S_concat_char_iter(__r
, __iter
, __slen
); }
1342 static _RopeRep
* _S_concat(_RopeRep
* __left
, _RopeRep
* __right
);
1343 // General concatenation on _RopeRep. _Result
1344 // has refcount of 1. Adjusts argument refcounts.
1347 void apply_to_pieces( size_t __begin
, size_t __end
,
1348 _Rope_char_consumer
<_CharT
>& __c
) const {
1349 _S_apply_to_pieces(__c
, _M_tree_ptr
, __begin
, __end
);
1355 static size_t _S_rounded_up_size(size_t __n
) {
1356 return _RopeLeaf::_S_rounded_up_size(__n
);
1359 static size_t _S_allocated_capacity(size_t __n
) {
1360 if (_S_is_basic_char_type((_CharT
*)0)) {
1361 return _S_rounded_up_size(__n
) - 1;
1363 return _S_rounded_up_size(__n
);
1367 // Allocate and construct a RopeLeaf using the supplied allocator
1368 // Takes ownership of s instead of copying.
1369 static _RopeLeaf
* _S_new_RopeLeaf(__GC_CONST _CharT
*__s
,
1370 size_t __size
, allocator_type __a
)
1372 _RopeLeaf
* __space
= _LAllocator(__a
).allocate(1);
1373 return new(__space
) _RopeLeaf(__s
, __size
, __a
);
1376 static _RopeConcatenation
* _S_new_RopeConcatenation(
1377 _RopeRep
* __left
, _RopeRep
* __right
,
1380 _RopeConcatenation
* __space
= _CAllocator(__a
).allocate(1);
1381 return new(__space
) _RopeConcatenation(__left
, __right
, __a
);
1384 static _RopeFunction
* _S_new_RopeFunction(char_producer
<_CharT
>* __f
,
1385 size_t __size
, bool __d
, allocator_type __a
)
1387 _RopeFunction
* __space
= _FAllocator(__a
).allocate(1);
1388 return new(__space
) _RopeFunction(__f
, __size
, __d
, __a
);
1391 static _RopeSubstring
* _S_new_RopeSubstring(
1392 _Rope_RopeRep
<_CharT
,_Alloc
>* __b
, size_t __s
,
1393 size_t __l
, allocator_type __a
)
1395 _RopeSubstring
* __space
= _SAllocator(__a
).allocate(1);
1396 return new(__space
) _RopeSubstring(__b
, __s
, __l
, __a
);
1400 _RopeLeaf
* _S_RopeLeaf_from_unowned_char_ptr(const _CharT
*__s
,
1401 size_t __size
, allocator_type __a
)
1402 # define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
1403 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
1405 if (0 == __size
) return 0;
1406 _CharT
* __buf
= __a
.allocate(_S_rounded_up_size(__size
));
1408 uninitialized_copy_n(__s
, __size
, __buf
);
1409 _S_cond_store_eos(__buf
[__size
]);
1411 return _S_new_RopeLeaf(__buf
, __size
, __a
);
1415 _RopeRep::__STL_FREE_STRING(__buf
, __size
, __a
);
1416 __throw_exception_again
;
1421 // Concatenation of nonempty strings.
1422 // Always builds a concatenation node.
1423 // Rebalances if the result is too deep.
1424 // Result has refcount 1.
1425 // Does not increment left and right ref counts even though
1426 // they are referenced.
1428 _S_tree_concat(_RopeRep
* __left
, _RopeRep
* __right
);
1430 // Concatenation helper functions
1432 _S_leaf_concat_char_iter(_RopeLeaf
* __r
,
1433 const _CharT
* __iter
, size_t __slen
);
1434 // Concatenate by copying leaf.
1435 // should take an arbitrary iterator
1436 // result has refcount 1.
1438 static _RopeLeaf
* _S_destr_leaf_concat_char_iter
1439 (_RopeLeaf
* __r
, const _CharT
* __iter
, size_t __slen
);
1440 // A version that potentially clobbers __r if __r->_M_ref_count == 1.
1445 static size_t _S_char_ptr_len(const _CharT
* __s
);
1446 // slightly generalized strlen
1448 rope(_RopeRep
* __t
, const allocator_type
& __a
= allocator_type())
1449 : _Base(__t
,__a
) { }
1452 // Copy __r to the _CharT buffer.
1453 // Returns __buffer + __r->_M_size.
1454 // Assumes that buffer is uninitialized.
1455 static _CharT
* _S_flatten(_RopeRep
* __r
, _CharT
* __buffer
);
1457 // Again, with explicit starting position and length.
1458 // Assumes that buffer is uninitialized.
1459 static _CharT
* _S_flatten(_RopeRep
* __r
,
1460 size_t __start
, size_t __len
,
1463 static const unsigned long
1464 _S_min_len
[_RopeRep::_S_max_rope_depth
+ 1];
1466 static bool _S_is_balanced(_RopeRep
* __r
)
1467 { return (__r
->_M_size
>= _S_min_len
[__r
->_M_depth
]); }
1469 static bool _S_is_almost_balanced(_RopeRep
* __r
)
1470 { return (__r
->_M_depth
== 0 ||
1471 __r
->_M_size
>= _S_min_len
[__r
->_M_depth
- 1]); }
1473 static bool _S_is_roughly_balanced(_RopeRep
* __r
)
1474 { return (__r
->_M_depth
<= 1 ||
1475 __r
->_M_size
>= _S_min_len
[__r
->_M_depth
- 2]); }
1477 // Assumes the result is not empty.
1478 static _RopeRep
* _S_concat_and_set_balanced(_RopeRep
* __left
,
1481 _RopeRep
* __result
= _S_concat(__left
, __right
);
1482 if (_S_is_balanced(__result
)) __result
->_M_is_balanced
= true;
1486 // The basic rebalancing operation. Logically copies the
1487 // rope. The result has refcount of 1. The client will
1488 // usually decrement the reference count of __r.
1489 // The result is within height 2 of balanced by the above
1491 static _RopeRep
* _S_balance(_RopeRep
* __r
);
1493 // Add all unbalanced subtrees to the forest of balanceed trees.
1494 // Used only by balance.
1495 static void _S_add_to_forest(_RopeRep
*__r
, _RopeRep
** __forest
);
1497 // Add __r to forest, assuming __r is already balanced.
1498 static void _S_add_leaf_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
);
1500 // Print to stdout, exposing structure
1501 static void _S_dump(_RopeRep
* __r
, int __indent
= 0);
1503 // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
1504 static int _S_compare(const _RopeRep
* __x
, const _RopeRep
* __y
);
1507 bool empty() const { return 0 == _M_tree_ptr
; }
1509 // Comparison member function. This is public only for those
1510 // clients that need a ternary comparison. Others
1511 // should use the comparison operators below.
1512 int compare(const rope
& __y
) const {
1513 return _S_compare(_M_tree_ptr
, __y
._M_tree_ptr
);
1516 rope(const _CharT
* __s
, const allocator_type
& __a
= allocator_type())
1517 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, _S_char_ptr_len(__s
),
1521 rope(const _CharT
* __s
, size_t __len
,
1522 const allocator_type
& __a
= allocator_type())
1523 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __len
, __a
), __a
)
1526 // Should perhaps be templatized with respect to the iterator type
1527 // and use Sequence_buffer. (It should perhaps use sequence_buffer
1529 rope(const _CharT
*__s
, const _CharT
*__e
,
1530 const allocator_type
& __a
= allocator_type())
1531 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __e
- __s
, __a
), __a
)
1534 rope(const const_iterator
& __s
, const const_iterator
& __e
,
1535 const allocator_type
& __a
= allocator_type())
1536 : _Base(_S_substring(__s
._M_root
, __s
._M_current_pos
,
1537 __e
._M_current_pos
), __a
)
1540 rope(const iterator
& __s
, const iterator
& __e
,
1541 const allocator_type
& __a
= allocator_type())
1542 : _Base(_S_substring(__s
._M_root
, __s
._M_current_pos
,
1543 __e
._M_current_pos
), __a
)
1546 rope(_CharT __c
, const allocator_type
& __a
= allocator_type())
1549 _CharT
* __buf
= _Data_allocate(_S_rounded_up_size(1));
1551 std::_Construct(__buf
, __c
);
1553 _M_tree_ptr
= _S_new_RopeLeaf(__buf
, 1, __a
);
1557 _RopeRep::__STL_FREE_STRING(__buf
, 1, __a
);
1558 __throw_exception_again
;
1562 rope(size_t __n
, _CharT __c
,
1563 const allocator_type
& __a
= allocator_type());
1565 rope(const allocator_type
& __a
= allocator_type())
1568 // Construct a rope from a function that can compute its members
1569 rope(char_producer
<_CharT
> *__fn
, size_t __len
, bool __delete_fn
,
1570 const allocator_type
& __a
= allocator_type())
1573 _M_tree_ptr
= (0 == __len
) ?
1574 0 : _S_new_RopeFunction(__fn
, __len
, __delete_fn
, __a
);
1577 rope(const rope
& __x
, const allocator_type
& __a
= allocator_type())
1578 : _Base(__x
._M_tree_ptr
, __a
)
1580 _S_ref(_M_tree_ptr
);
1585 _S_unref(_M_tree_ptr
);
1588 rope
& operator=(const rope
& __x
)
1590 _RopeRep
* __old
= _M_tree_ptr
;
1591 _M_tree_ptr
= __x
._M_tree_ptr
;
1592 _S_ref(_M_tree_ptr
);
1599 _S_unref(_M_tree_ptr
);
1603 void push_back(_CharT __x
)
1605 _RopeRep
* __old
= _M_tree_ptr
;
1606 _M_tree_ptr
= _S_destr_concat_char_iter(_M_tree_ptr
, &__x
, 1);
1612 _RopeRep
* __old
= _M_tree_ptr
;
1614 _S_substring(_M_tree_ptr
, 0, _M_tree_ptr
->_M_size
- 1);
1620 return _S_fetch(_M_tree_ptr
, _M_tree_ptr
->_M_size
- 1);
1623 void push_front(_CharT __x
)
1625 _RopeRep
* __old
= _M_tree_ptr
;
1627 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x
, 1, get_allocator());
1629 _M_tree_ptr
= _S_concat(__left
, _M_tree_ptr
);
1636 __throw_exception_again
;
1642 _RopeRep
* __old
= _M_tree_ptr
;
1643 _M_tree_ptr
= _S_substring(_M_tree_ptr
, 1, _M_tree_ptr
->_M_size
);
1647 _CharT
front() const
1649 return _S_fetch(_M_tree_ptr
, 0);
1654 _RopeRep
* __old
= _M_tree_ptr
;
1655 _M_tree_ptr
= _S_balance(_M_tree_ptr
);
1659 void copy(_CharT
* __buffer
) const {
1660 _Destroy(__buffer
, __buffer
+ size());
1661 _S_flatten(_M_tree_ptr
, __buffer
);
1664 // This is the copy function from the standard, but
1665 // with the arguments reordered to make it consistent with the
1666 // rest of the interface.
1667 // Note that this guaranteed not to compile if the draft standard
1668 // order is assumed.
1669 size_type
copy(size_type __pos
, size_type __n
, _CharT
* __buffer
) const
1671 size_t __size
= size();
1672 size_t __len
= (__pos
+ __n
> __size
? __size
- __pos
: __n
);
1674 _Destroy(__buffer
, __buffer
+ __len
);
1675 _S_flatten(_M_tree_ptr
, __pos
, __len
, __buffer
);
1679 // Print to stdout, exposing structure. May be useful for
1680 // performance debugging.
1682 _S_dump(_M_tree_ptr
);
1685 // Convert to 0 terminated string in new allocated memory.
1686 // Embedded 0s in the input do not terminate the copy.
1687 const _CharT
* c_str() const;
1689 // As above, but lso use the flattened representation as the
1690 // the new rope representation.
1691 const _CharT
* replace_with_c_str();
1693 // Reclaim memory for the c_str generated flattened string.
1694 // Intentionally undocumented, since it's hard to say when this
1695 // is safe for multiple threads.
1696 void delete_c_str () {
1697 if (0 == _M_tree_ptr
) return;
1698 if (_RopeRep::_S_leaf
== _M_tree_ptr
->_M_tag
&&
1699 ((_RopeLeaf
*)_M_tree_ptr
)->_M_data
==
1700 _M_tree_ptr
->_M_c_string
) {
1701 // Representation shared
1705 _M_tree_ptr
->_M_free_c_string();
1707 _M_tree_ptr
->_M_c_string
= 0;
1710 _CharT
operator[] (size_type __pos
) const {
1711 return _S_fetch(_M_tree_ptr
, __pos
);
1714 _CharT
at(size_type __pos
) const {
1715 // if (__pos >= size()) throw out_of_range; // XXX
1716 return (*this)[__pos
];
1719 const_iterator
begin() const {
1720 return(const_iterator(_M_tree_ptr
, 0));
1723 // An easy way to get a const iterator from a non-const container.
1724 const_iterator
const_begin() const {
1725 return(const_iterator(_M_tree_ptr
, 0));
1728 const_iterator
end() const {
1729 return(const_iterator(_M_tree_ptr
, size()));
1732 const_iterator
const_end() const {
1733 return(const_iterator(_M_tree_ptr
, size()));
1736 size_type
size() const {
1737 return(0 == _M_tree_ptr
? 0 : _M_tree_ptr
->_M_size
);
1740 size_type
length() const {
1744 size_type
max_size() const {
1745 return _S_min_len
[_RopeRep::_S_max_rope_depth
-1] - 1;
1746 // Guarantees that the result can be sufficirntly
1747 // balanced. Longer ropes will probably still work,
1748 // but it's harder to make guarantees.
1751 typedef reverse_iterator
<const_iterator
> const_reverse_iterator
;
1753 const_reverse_iterator
rbegin() const {
1754 return const_reverse_iterator(end());
1757 const_reverse_iterator
const_rbegin() const {
1758 return const_reverse_iterator(end());
1761 const_reverse_iterator
rend() const {
1762 return const_reverse_iterator(begin());
1765 const_reverse_iterator
const_rend() const {
1766 return const_reverse_iterator(begin());
1769 template<class _CharT2
, class _Alloc2
>
1770 friend rope
<_CharT2
,_Alloc2
>
1771 operator+ (const rope
<_CharT2
,_Alloc2
>& __left
,
1772 const rope
<_CharT2
,_Alloc2
>& __right
);
1774 template<class _CharT2
, class _Alloc2
>
1775 friend rope
<_CharT2
,_Alloc2
>
1776 operator+ (const rope
<_CharT2
,_Alloc2
>& __left
,
1777 const _CharT2
* __right
);
1779 template<class _CharT2
, class _Alloc2
>
1780 friend rope
<_CharT2
,_Alloc2
>
1781 operator+ (const rope
<_CharT2
,_Alloc2
>& __left
, _CharT2 __right
);
1782 // The symmetric cases are intentionally omitted, since they're presumed
1783 // to be less common, and we don't handle them as well.
1785 // The following should really be templatized.
1786 // The first argument should be an input iterator or
1787 // forward iterator with value_type _CharT.
1788 rope
& append(const _CharT
* __iter
, size_t __n
) {
1789 _RopeRep
* __result
=
1790 _S_destr_concat_char_iter(_M_tree_ptr
, __iter
, __n
);
1791 _S_unref(_M_tree_ptr
);
1792 _M_tree_ptr
= __result
;
1796 rope
& append(const _CharT
* __c_string
) {
1797 size_t __len
= _S_char_ptr_len(__c_string
);
1798 append(__c_string
, __len
);
1802 rope
& append(const _CharT
* __s
, const _CharT
* __e
) {
1803 _RopeRep
* __result
=
1804 _S_destr_concat_char_iter(_M_tree_ptr
, __s
, __e
- __s
);
1805 _S_unref(_M_tree_ptr
);
1806 _M_tree_ptr
= __result
;
1810 rope
& append(const_iterator __s
, const_iterator __e
) {
1811 _Self_destruct_ptr
__appendee(_S_substring(
1812 __s
._M_root
, __s
._M_current_pos
, __e
._M_current_pos
));
1813 _RopeRep
* __result
=
1814 _S_concat(_M_tree_ptr
, (_RopeRep
*)__appendee
);
1815 _S_unref(_M_tree_ptr
);
1816 _M_tree_ptr
= __result
;
1820 rope
& append(_CharT __c
) {
1821 _RopeRep
* __result
=
1822 _S_destr_concat_char_iter(_M_tree_ptr
, &__c
, 1);
1823 _S_unref(_M_tree_ptr
);
1824 _M_tree_ptr
= __result
;
1828 rope
& append() { return append(_CharT()); } // XXX why?
1830 rope
& append(const rope
& __y
) {
1831 _RopeRep
* __result
= _S_concat(_M_tree_ptr
, __y
._M_tree_ptr
);
1832 _S_unref(_M_tree_ptr
);
1833 _M_tree_ptr
= __result
;
1837 rope
& append(size_t __n
, _CharT __c
) {
1838 rope
<_CharT
,_Alloc
> __last(__n
, __c
);
1839 return append(__last
);
1842 void swap(rope
& __b
) {
1843 _RopeRep
* __tmp
= _M_tree_ptr
;
1844 _M_tree_ptr
= __b
._M_tree_ptr
;
1845 __b
._M_tree_ptr
= __tmp
;
1850 // Result is included in refcount.
1851 static _RopeRep
* replace(_RopeRep
* __old
, size_t __pos1
,
1852 size_t __pos2
, _RopeRep
* __r
) {
1853 if (0 == __old
) { _S_ref(__r
); return __r
; }
1854 _Self_destruct_ptr
__left(
1855 _S_substring(__old
, 0, __pos1
));
1856 _Self_destruct_ptr
__right(
1857 _S_substring(__old
, __pos2
, __old
->_M_size
));
1861 __result
= _S_concat(__left
, __right
);
1863 _Self_destruct_ptr
__left_result(_S_concat(__left
, __r
));
1864 __result
= _S_concat(__left_result
, __right
);
1870 void insert(size_t __p
, const rope
& __r
) {
1871 _RopeRep
* __result
=
1872 replace(_M_tree_ptr
, __p
, __p
, __r
._M_tree_ptr
);
1873 _S_unref(_M_tree_ptr
);
1874 _M_tree_ptr
= __result
;
1877 void insert(size_t __p
, size_t __n
, _CharT __c
) {
1878 rope
<_CharT
,_Alloc
> __r(__n
,__c
);
1882 void insert(size_t __p
, const _CharT
* __i
, size_t __n
) {
1883 _Self_destruct_ptr
__left(_S_substring(_M_tree_ptr
, 0, __p
));
1884 _Self_destruct_ptr
__right(_S_substring(_M_tree_ptr
, __p
, size()));
1885 _Self_destruct_ptr
__left_result(
1886 _S_concat_char_iter(__left
, __i
, __n
));
1887 // _S_ destr_concat_char_iter should be safe here.
1888 // But as it stands it's probably not a win, since __left
1889 // is likely to have additional references.
1890 _RopeRep
* __result
= _S_concat(__left_result
, __right
);
1891 _S_unref(_M_tree_ptr
);
1892 _M_tree_ptr
= __result
;
1895 void insert(size_t __p
, const _CharT
* __c_string
) {
1896 insert(__p
, __c_string
, _S_char_ptr_len(__c_string
));
1899 void insert(size_t __p
, _CharT __c
) {
1900 insert(__p
, &__c
, 1);
1903 void insert(size_t __p
) {
1904 _CharT __c
= _CharT();
1905 insert(__p
, &__c
, 1);
1908 void insert(size_t __p
, const _CharT
* __i
, const _CharT
* __j
) {
1913 void insert(size_t __p
, const const_iterator
& __i
,
1914 const const_iterator
& __j
) {
1919 void insert(size_t __p
, const iterator
& __i
,
1920 const iterator
& __j
) {
1925 // (position, length) versions of replace operations:
1927 void replace(size_t __p
, size_t __n
, const rope
& __r
) {
1928 _RopeRep
* __result
=
1929 replace(_M_tree_ptr
, __p
, __p
+ __n
, __r
._M_tree_ptr
);
1930 _S_unref(_M_tree_ptr
);
1931 _M_tree_ptr
= __result
;
1934 void replace(size_t __p
, size_t __n
,
1935 const _CharT
* __i
, size_t __i_len
) {
1936 rope
__r(__i
, __i_len
);
1937 replace(__p
, __n
, __r
);
1940 void replace(size_t __p
, size_t __n
, _CharT __c
) {
1942 replace(__p
, __n
, __r
);
1945 void replace(size_t __p
, size_t __n
, const _CharT
* __c_string
) {
1946 rope
__r(__c_string
);
1947 replace(__p
, __n
, __r
);
1950 void replace(size_t __p
, size_t __n
,
1951 const _CharT
* __i
, const _CharT
* __j
) {
1953 replace(__p
, __n
, __r
);
1956 void replace(size_t __p
, size_t __n
,
1957 const const_iterator
& __i
, const const_iterator
& __j
) {
1959 replace(__p
, __n
, __r
);
1962 void replace(size_t __p
, size_t __n
,
1963 const iterator
& __i
, const iterator
& __j
) {
1965 replace(__p
, __n
, __r
);
1968 // Single character variants:
1969 void replace(size_t __p
, _CharT __c
) {
1970 iterator
__i(this, __p
);
1974 void replace(size_t __p
, const rope
& __r
) {
1975 replace(__p
, 1, __r
);
1978 void replace(size_t __p
, const _CharT
* __i
, size_t __i_len
) {
1979 replace(__p
, 1, __i
, __i_len
);
1982 void replace(size_t __p
, const _CharT
* __c_string
) {
1983 replace(__p
, 1, __c_string
);
1986 void replace(size_t __p
, const _CharT
* __i
, const _CharT
* __j
) {
1987 replace(__p
, 1, __i
, __j
);
1990 void replace(size_t __p
, const const_iterator
& __i
,
1991 const const_iterator
& __j
) {
1992 replace(__p
, 1, __i
, __j
);
1995 void replace(size_t __p
, const iterator
& __i
,
1996 const iterator
& __j
) {
1997 replace(__p
, 1, __i
, __j
);
2000 // Erase, (position, size) variant.
2001 void erase(size_t __p
, size_t __n
) {
2002 _RopeRep
* __result
= replace(_M_tree_ptr
, __p
, __p
+ __n
, 0);
2003 _S_unref(_M_tree_ptr
);
2004 _M_tree_ptr
= __result
;
2007 // Erase, single character
2008 void erase(size_t __p
) {
2009 erase(__p
, __p
+ 1);
2012 // Insert, iterator variants.
2013 iterator
insert(const iterator
& __p
, const rope
& __r
)
2014 { insert(__p
.index(), __r
); return __p
; }
2015 iterator
insert(const iterator
& __p
, size_t __n
, _CharT __c
)
2016 { insert(__p
.index(), __n
, __c
); return __p
; }
2017 iterator
insert(const iterator
& __p
, _CharT __c
)
2018 { insert(__p
.index(), __c
); return __p
; }
2019 iterator
insert(const iterator
& __p
)
2020 { insert(__p
.index()); return __p
; }
2021 iterator
insert(const iterator
& __p
, const _CharT
* c_string
)
2022 { insert(__p
.index(), c_string
); return __p
; }
2023 iterator
insert(const iterator
& __p
, const _CharT
* __i
, size_t __n
)
2024 { insert(__p
.index(), __i
, __n
); return __p
; }
2025 iterator
insert(const iterator
& __p
, const _CharT
* __i
,
2027 { insert(__p
.index(), __i
, __j
); return __p
; }
2028 iterator
insert(const iterator
& __p
,
2029 const const_iterator
& __i
, const const_iterator
& __j
)
2030 { insert(__p
.index(), __i
, __j
); return __p
; }
2031 iterator
insert(const iterator
& __p
,
2032 const iterator
& __i
, const iterator
& __j
)
2033 { insert(__p
.index(), __i
, __j
); return __p
; }
2035 // Replace, range variants.
2036 void replace(const iterator
& __p
, const iterator
& __q
,
2038 { replace(__p
.index(), __q
.index() - __p
.index(), __r
); }
2039 void replace(const iterator
& __p
, const iterator
& __q
, _CharT __c
)
2040 { replace(__p
.index(), __q
.index() - __p
.index(), __c
); }
2041 void replace(const iterator
& __p
, const iterator
& __q
,
2042 const _CharT
* __c_string
)
2043 { replace(__p
.index(), __q
.index() - __p
.index(), __c_string
); }
2044 void replace(const iterator
& __p
, const iterator
& __q
,
2045 const _CharT
* __i
, size_t __n
)
2046 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __n
); }
2047 void replace(const iterator
& __p
, const iterator
& __q
,
2048 const _CharT
* __i
, const _CharT
* __j
)
2049 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __j
); }
2050 void replace(const iterator
& __p
, const iterator
& __q
,
2051 const const_iterator
& __i
, const const_iterator
& __j
)
2052 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __j
); }
2053 void replace(const iterator
& __p
, const iterator
& __q
,
2054 const iterator
& __i
, const iterator
& __j
)
2055 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __j
); }
2057 // Replace, iterator variants.
2058 void replace(const iterator
& __p
, const rope
& __r
)
2059 { replace(__p
.index(), __r
); }
2060 void replace(const iterator
& __p
, _CharT __c
)
2061 { replace(__p
.index(), __c
); }
2062 void replace(const iterator
& __p
, const _CharT
* __c_string
)
2063 { replace(__p
.index(), __c_string
); }
2064 void replace(const iterator
& __p
, const _CharT
* __i
, size_t __n
)
2065 { replace(__p
.index(), __i
, __n
); }
2066 void replace(const iterator
& __p
, const _CharT
* __i
, const _CharT
* __j
)
2067 { replace(__p
.index(), __i
, __j
); }
2068 void replace(const iterator
& __p
, const_iterator __i
,
2070 { replace(__p
.index(), __i
, __j
); }
2071 void replace(const iterator
& __p
, iterator __i
, iterator __j
)
2072 { replace(__p
.index(), __i
, __j
); }
2074 // Iterator and range variants of erase
2075 iterator
erase(const iterator
& __p
, const iterator
& __q
) {
2076 size_t __p_index
= __p
.index();
2077 erase(__p_index
, __q
.index() - __p_index
);
2078 return iterator(this, __p_index
);
2080 iterator
erase(const iterator
& __p
) {
2081 size_t __p_index
= __p
.index();
2082 erase(__p_index
, 1);
2083 return iterator(this, __p_index
);
2086 rope
substr(size_t __start
, size_t __len
= 1) const {
2087 return rope
<_CharT
,_Alloc
>(
2088 _S_substring(_M_tree_ptr
, __start
, __start
+ __len
));
2091 rope
substr(iterator __start
, iterator __end
) const {
2092 return rope
<_CharT
,_Alloc
>(
2093 _S_substring(_M_tree_ptr
, __start
.index(), __end
.index()));
2096 rope
substr(iterator __start
) const {
2097 size_t __pos
= __start
.index();
2098 return rope
<_CharT
,_Alloc
>(
2099 _S_substring(_M_tree_ptr
, __pos
, __pos
+ 1));
2102 rope
substr(const_iterator __start
, const_iterator __end
) const {
2103 // This might eventually take advantage of the cache in the
2105 return rope
<_CharT
,_Alloc
>(
2106 _S_substring(_M_tree_ptr
, __start
.index(), __end
.index()));
2109 rope
<_CharT
,_Alloc
> substr(const_iterator __start
) {
2110 size_t __pos
= __start
.index();
2111 return rope
<_CharT
,_Alloc
>(
2112 _S_substring(_M_tree_ptr
, __pos
, __pos
+ 1));
2115 static const size_type npos
;
2117 size_type
find(_CharT __c
, size_type __pos
= 0) const;
2118 size_type
find(const _CharT
* __s
, size_type __pos
= 0) const {
2119 size_type __result_pos
;
2120 const_iterator __result
=
2121 std::search(const_begin() + __pos
, const_end(),
2122 __s
, __s
+ _S_char_ptr_len(__s
));
2123 __result_pos
= __result
.index();
2124 # ifndef __STL_OLD_ROPE_SEMANTICS
2125 if (__result_pos
== size()) __result_pos
= npos
;
2127 return __result_pos
;
2130 iterator
mutable_begin() {
2131 return(iterator(this, 0));
2134 iterator
mutable_end() {
2135 return(iterator(this, size()));
2138 typedef reverse_iterator
<iterator
> reverse_iterator
;
2140 reverse_iterator
mutable_rbegin() {
2141 return reverse_iterator(mutable_end());
2144 reverse_iterator
mutable_rend() {
2145 return reverse_iterator(mutable_begin());
2148 reference
mutable_reference_at(size_type __pos
) {
2149 return reference(this, __pos
);
2153 reference
operator[] (size_type __pos
) {
2154 return _char_ref_proxy(this, __pos
);
2157 reference
at(size_type __pos
) {
2158 // if (__pos >= size()) throw out_of_range; // XXX
2159 return (*this)[__pos
];
2162 void resize(size_type __n
, _CharT __c
) {}
2163 void resize(size_type __n
) {}
2164 void reserve(size_type __res_arg
= 0) {}
2165 size_type
capacity() const {
2169 // Stuff below this line is dangerous because it's error prone.
2170 // I would really like to get rid of it.
2171 // copy function with funny arg ordering.
2172 size_type
copy(_CharT
* __buffer
, size_type __n
,
2173 size_type __pos
= 0) const {
2174 return copy(__pos
, __n
, __buffer
);
2177 iterator
end() { return mutable_end(); }
2179 iterator
begin() { return mutable_begin(); }
2181 reverse_iterator
rend() { return mutable_rend(); }
2183 reverse_iterator
rbegin() { return mutable_rbegin(); }
2187 const_iterator
end() { return const_end(); }
2189 const_iterator
begin() { return const_begin(); }
2191 const_reverse_iterator
rend() { return const_rend(); }
2193 const_reverse_iterator
rbegin() { return const_rbegin(); }
2199 template <class _CharT
, class _Alloc
>
2200 const typename rope
<_CharT
, _Alloc
>::size_type rope
<_CharT
, _Alloc
>::npos
=
2203 template <class _CharT
, class _Alloc
>
2204 inline bool operator== (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2205 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2206 return (__x
._M_current_pos
== __y
._M_current_pos
&&
2207 __x
._M_root
== __y
._M_root
);
2210 template <class _CharT
, class _Alloc
>
2211 inline bool operator< (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2212 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2213 return (__x
._M_current_pos
< __y
._M_current_pos
);
2216 template <class _CharT
, class _Alloc
>
2217 inline bool operator!= (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2218 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2219 return !(__x
== __y
);
2222 template <class _CharT
, class _Alloc
>
2223 inline bool operator> (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2224 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2228 template <class _CharT
, class _Alloc
>
2229 inline bool operator<= (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2230 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2231 return !(__y
< __x
);
2234 template <class _CharT
, class _Alloc
>
2235 inline bool operator>= (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2236 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2237 return !(__x
< __y
);
2240 template <class _CharT
, class _Alloc
>
2241 inline ptrdiff_t operator-(const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2242 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2243 return (ptrdiff_t)__x
._M_current_pos
- (ptrdiff_t)__y
._M_current_pos
;
2246 template <class _CharT
, class _Alloc
>
2247 inline _Rope_const_iterator
<_CharT
,_Alloc
>
2248 operator-(const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
, ptrdiff_t __n
) {
2249 return _Rope_const_iterator
<_CharT
,_Alloc
>(
2250 __x
._M_root
, __x
._M_current_pos
- __n
);
2253 template <class _CharT
, class _Alloc
>
2254 inline _Rope_const_iterator
<_CharT
,_Alloc
>
2255 operator+(const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
, ptrdiff_t __n
) {
2256 return _Rope_const_iterator
<_CharT
,_Alloc
>(
2257 __x
._M_root
, __x
._M_current_pos
+ __n
);
2260 template <class _CharT
, class _Alloc
>
2261 inline _Rope_const_iterator
<_CharT
,_Alloc
>
2262 operator+(ptrdiff_t __n
, const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
) {
2263 return _Rope_const_iterator
<_CharT
,_Alloc
>(
2264 __x
._M_root
, __x
._M_current_pos
+ __n
);
2267 template <class _CharT
, class _Alloc
>
2268 inline bool operator== (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2269 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2270 return (__x
._M_current_pos
== __y
._M_current_pos
&&
2271 __x
._M_root_rope
== __y
._M_root_rope
);
2274 template <class _CharT
, class _Alloc
>
2275 inline bool operator< (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2276 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2277 return (__x
._M_current_pos
< __y
._M_current_pos
);
2280 template <class _CharT
, class _Alloc
>
2281 inline bool operator!= (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2282 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2283 return !(__x
== __y
);
2286 template <class _CharT
, class _Alloc
>
2287 inline bool operator> (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2288 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2292 template <class _CharT
, class _Alloc
>
2293 inline bool operator<= (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2294 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2295 return !(__y
< __x
);
2298 template <class _CharT
, class _Alloc
>
2299 inline bool operator>= (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2300 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2301 return !(__x
< __y
);
2304 template <class _CharT
, class _Alloc
>
2305 inline ptrdiff_t operator-(const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2306 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2307 return (ptrdiff_t)__x
._M_current_pos
- (ptrdiff_t)__y
._M_current_pos
;
2310 template <class _CharT
, class _Alloc
>
2311 inline _Rope_iterator
<_CharT
,_Alloc
>
2312 operator-(const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2314 return _Rope_iterator
<_CharT
,_Alloc
>(
2315 __x
._M_root_rope
, __x
._M_current_pos
- __n
);
2318 template <class _CharT
, class _Alloc
>
2319 inline _Rope_iterator
<_CharT
,_Alloc
>
2320 operator+(const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2322 return _Rope_iterator
<_CharT
,_Alloc
>(
2323 __x
._M_root_rope
, __x
._M_current_pos
+ __n
);
2326 template <class _CharT
, class _Alloc
>
2327 inline _Rope_iterator
<_CharT
,_Alloc
>
2328 operator+(ptrdiff_t __n
, const _Rope_iterator
<_CharT
,_Alloc
>& __x
) {
2329 return _Rope_iterator
<_CharT
,_Alloc
>(
2330 __x
._M_root_rope
, __x
._M_current_pos
+ __n
);
2333 template <class _CharT
, class _Alloc
>
2336 operator+ (const rope
<_CharT
,_Alloc
>& __left
,
2337 const rope
<_CharT
,_Alloc
>& __right
)
2339 return rope
<_CharT
,_Alloc
>(
2340 rope
<_CharT
,_Alloc
>::_S_concat(__left
._M_tree_ptr
, __right
._M_tree_ptr
));
2341 // Inlining this should make it possible to keep __left and
2342 // __right in registers.
2345 template <class _CharT
, class _Alloc
>
2347 rope
<_CharT
,_Alloc
>&
2348 operator+= (rope
<_CharT
,_Alloc
>& __left
,
2349 const rope
<_CharT
,_Alloc
>& __right
)
2351 __left
.append(__right
);
2355 template <class _CharT
, class _Alloc
>
2358 operator+ (const rope
<_CharT
,_Alloc
>& __left
,
2359 const _CharT
* __right
) {
2360 size_t __rlen
= rope
<_CharT
,_Alloc
>::_S_char_ptr_len(__right
);
2361 return rope
<_CharT
,_Alloc
>(
2362 rope
<_CharT
,_Alloc
>::_S_concat_char_iter(
2363 __left
._M_tree_ptr
, __right
, __rlen
));
2366 template <class _CharT
, class _Alloc
>
2368 rope
<_CharT
,_Alloc
>&
2369 operator+= (rope
<_CharT
,_Alloc
>& __left
,
2370 const _CharT
* __right
) {
2371 __left
.append(__right
);
2375 template <class _CharT
, class _Alloc
>
2378 operator+ (const rope
<_CharT
,_Alloc
>& __left
, _CharT __right
) {
2379 return rope
<_CharT
,_Alloc
>(
2380 rope
<_CharT
,_Alloc
>::_S_concat_char_iter(
2381 __left
._M_tree_ptr
, &__right
, 1));
2384 template <class _CharT
, class _Alloc
>
2386 rope
<_CharT
,_Alloc
>&
2387 operator+= (rope
<_CharT
,_Alloc
>& __left
, _CharT __right
) {
2388 __left
.append(__right
);
2392 template <class _CharT
, class _Alloc
>
2394 operator< (const rope
<_CharT
,_Alloc
>& __left
,
2395 const rope
<_CharT
,_Alloc
>& __right
) {
2396 return __left
.compare(__right
) < 0;
2399 template <class _CharT
, class _Alloc
>
2401 operator== (const rope
<_CharT
,_Alloc
>& __left
,
2402 const rope
<_CharT
,_Alloc
>& __right
) {
2403 return __left
.compare(__right
) == 0;
2406 template <class _CharT
, class _Alloc
>
2407 inline bool operator== (const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __x
,
2408 const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __y
) {
2409 return (__x
._M_pos
== __y
._M_pos
&& __x
._M_root
== __y
._M_root
);
2412 template <class _CharT
, class _Alloc
>
2414 operator!= (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2415 return !(__x
== __y
);
2418 template <class _CharT
, class _Alloc
>
2420 operator> (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2424 template <class _CharT
, class _Alloc
>
2426 operator<= (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2427 return !(__y
< __x
);
2430 template <class _CharT
, class _Alloc
>
2432 operator>= (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2433 return !(__x
< __y
);
2436 template <class _CharT
, class _Alloc
>
2437 inline bool operator!= (const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __x
,
2438 const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __y
) {
2439 return !(__x
== __y
);
2442 template<class _CharT
, class _Traits
, class _Alloc
>
2443 std::basic_ostream
<_CharT
, _Traits
>& operator<<
2444 (std::basic_ostream
<_CharT
, _Traits
>& __o
,
2445 const rope
<_CharT
, _Alloc
>& __r
);
2447 typedef rope
<char> crope
;
2448 typedef rope
<wchar_t> wrope
;
2450 inline crope::reference
__mutable_reference_at(crope
& __c
, size_t __i
)
2452 return __c
.mutable_reference_at(__i
);
2455 inline wrope::reference
__mutable_reference_at(wrope
& __c
, size_t __i
)
2457 return __c
.mutable_reference_at(__i
);
2460 template <class _CharT
, class _Alloc
>
2461 inline void swap(rope
<_CharT
,_Alloc
>& __x
, rope
<_CharT
,_Alloc
>& __y
) {
2465 // Hash functions should probably be revisited later:
2466 template<> struct hash
<crope
>
2468 size_t operator()(const crope
& __str
) const
2470 size_t __size
= __str
.size();
2472 if (0 == __size
) return 0;
2473 return 13*__str
[0] + 5*__str
[__size
- 1] + __size
;
2478 template<> struct hash
<wrope
>
2480 size_t operator()(const wrope
& __str
) const
2482 size_t __size
= __str
.size();
2484 if (0 == __size
) return 0;
2485 return 13*__str
[0] + 5*__str
[__size
- 1] + __size
;
2489 } // namespace __gnu_cxx
2491 # include <ext/ropeimpl.h>
2493 # endif /* __SGI_STL_INTERNAL_ROPE_H */