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.
43 /* NOTE: This is an internal header file, included by other STL headers.
44 * You should not attempt to use it directly.
47 // rope<_CharT,_Alloc> is a sequence of _CharT.
48 // Ropes appear to be mutable, but update operations
49 // really copy enough of the data structure to leave the original
50 // valid. Thus ropes can be logically copied by just copying
53 #ifndef __SGI_STL_INTERNAL_ROPE_H
54 # define __SGI_STL_INTERNAL_ROPE_H
57 # define __GC_CONST const
59 # include <bits/stl_threads.h>
60 # define __GC_CONST // constant except for deallocation
62 # ifdef __STL_SGI_THREADS
69 // The _S_eos function is used for those functions that
70 // convert to/from C-like strings to detect the end of the string.
72 // The end-of-C-string character.
73 // This is what the draft standard says it should be.
74 template <class _CharT
>
75 inline _CharT
_S_eos(_CharT
*) { return _CharT(); }
77 // Test for basic character types.
78 // For basic character types leaves having a trailing eos.
79 template <class _CharT
>
80 inline bool _S_is_basic_char_type(_CharT
*) { return false; }
81 template <class _CharT
>
82 inline bool _S_is_one_byte_char_type(_CharT
*) { return false; }
84 inline bool _S_is_basic_char_type(char*) { return true; }
85 inline bool _S_is_one_byte_char_type(char*) { return true; }
86 inline bool _S_is_basic_char_type(wchar_t*) { return true; }
88 // Store an eos iff _CharT is a basic character type.
89 // Do not reference _S_eos if it isn't.
90 template <class _CharT
>
91 inline void _S_cond_store_eos(_CharT
&) {}
93 inline void _S_cond_store_eos(char& __c
) { __c
= 0; }
94 inline void _S_cond_store_eos(wchar_t& __c
) { __c
= 0; }
96 // char_producers are logically functions that generate a section of
97 // a string. These can be convereted to ropes. The resulting rope
98 // invokes the char_producer on demand. This allows, for example,
99 // files to be viewed as ropes without reading the entire file.
100 template <class _CharT
>
101 class char_producer
{
103 virtual ~char_producer() {};
104 virtual void operator()(size_t __start_pos
, size_t __len
,
105 _CharT
* __buffer
) = 0;
106 // Buffer should really be an arbitrary output iterator.
107 // That way we could flatten directly into an ostream, etc.
108 // This is thoroughly impossible, since iterator types don't
109 // have runtime descriptions.
114 // Sequence must provide an append operation that appends an
115 // array to the sequence. Sequence buffers are useful only if
116 // appending an entire array is cheaper than appending element by element.
117 // This is true for many string representations.
118 // This should perhaps inherit from ostream<sequence::value_type>
119 // and be implemented correspondingly, so that they can be used
120 // for formatted. For the sake of portability, we don't do this yet.
122 // For now, sequence buffers behave as output iterators. But they also
123 // behave a little like basic_ostringstream<sequence::value_type> and a
124 // little like containers.
126 template<class _Sequence
, size_t _Buf_sz
= 100>
127 class sequence_buffer
: public output_iterator
{
129 typedef typename
_Sequence::value_type value_type
;
131 _Sequence
* _M_prefix
;
132 value_type _M_buffer
[_Buf_sz
];
136 _M_prefix
->append(_M_buffer
, _M_buffer
+ _M_buf_count
);
139 ~sequence_buffer() { flush(); }
140 sequence_buffer() : _M_prefix(0), _M_buf_count(0) {}
141 sequence_buffer(const sequence_buffer
& __x
) {
142 _M_prefix
= __x
._M_prefix
;
143 _M_buf_count
= __x
._M_buf_count
;
144 copy(__x
._M_buffer
, __x
._M_buffer
+ __x
._M_buf_count
, _M_buffer
);
146 sequence_buffer(sequence_buffer
& __x
) {
148 _M_prefix
= __x
._M_prefix
;
151 sequence_buffer(_Sequence
& __s
) : _M_prefix(&__s
), _M_buf_count(0) {}
152 sequence_buffer
& operator= (sequence_buffer
& __x
) {
154 _M_prefix
= __x
._M_prefix
;
158 sequence_buffer
& operator= (const sequence_buffer
& __x
) {
159 _M_prefix
= __x
._M_prefix
;
160 _M_buf_count
= __x
._M_buf_count
;
161 copy(__x
._M_buffer
, __x
._M_buffer
+ __x
._M_buf_count
, _M_buffer
);
164 void push_back(value_type __x
)
166 if (_M_buf_count
< _Buf_sz
) {
167 _M_buffer
[_M_buf_count
] = __x
;
175 void append(value_type
* __s
, size_t __len
)
177 if (__len
+ _M_buf_count
<= _Buf_sz
) {
178 size_t __i
= _M_buf_count
;
180 for (; __j
< __len
; __i
++, __j
++) {
181 _M_buffer
[__i
] = __s
[__j
];
183 _M_buf_count
+= __len
;
184 } else if (0 == _M_buf_count
) {
185 _M_prefix
->append(__s
, __s
+ __len
);
191 sequence_buffer
& write(value_type
* __s
, size_t __len
)
196 sequence_buffer
& put(value_type __x
)
201 sequence_buffer
& operator=(const value_type
& __rhs
)
206 sequence_buffer
& operator*() { return *this; }
207 sequence_buffer
& operator++() { return *this; }
208 sequence_buffer
& operator++(int) { return *this; }
211 // The following should be treated as private, at least for now.
212 template<class _CharT
>
213 class _Rope_char_consumer
{
215 // If we had member templates, these should not be virtual.
216 // For now we need to use run-time parametrization where
217 // compile-time would do. Hence this should all be private
219 // The symmetry with char_producer is accidental and temporary.
220 virtual ~_Rope_char_consumer() {};
221 virtual bool operator()(const _CharT
* __buffer
, size_t __len
) = 0;
224 // First a lot of forward declarations. The standard seems to require
225 // much stricter "declaration before use" than many of the implementations
227 template<class _CharT
, class _Alloc
=allocator
<_CharT
> > class rope
;
228 template<class _CharT
, class _Alloc
> struct _Rope_RopeConcatenation
;
229 template<class _CharT
, class _Alloc
> struct _Rope_RopeLeaf
;
230 template<class _CharT
, class _Alloc
> struct _Rope_RopeFunction
;
231 template<class _CharT
, class _Alloc
> struct _Rope_RopeSubstring
;
232 template<class _CharT
, class _Alloc
> class _Rope_iterator
;
233 template<class _CharT
, class _Alloc
> class _Rope_const_iterator
;
234 template<class _CharT
, class _Alloc
> class _Rope_char_ref_proxy
;
235 template<class _CharT
, class _Alloc
> class _Rope_char_ptr_proxy
;
237 template<class _CharT
, class _Alloc
>
238 bool operator== (const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __x
,
239 const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __y
);
241 template<class _CharT
, class _Alloc
>
242 _Rope_const_iterator
<_CharT
,_Alloc
> operator-
243 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
246 template<class _CharT
, class _Alloc
>
247 _Rope_const_iterator
<_CharT
,_Alloc
> operator+
248 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
251 template<class _CharT
, class _Alloc
>
252 _Rope_const_iterator
<_CharT
,_Alloc
> operator+
254 const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
);
256 template<class _CharT
, class _Alloc
>
258 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
259 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
);
261 template<class _CharT
, class _Alloc
>
263 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
264 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
);
266 template<class _CharT
, class _Alloc
>
268 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
269 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
);
271 template<class _CharT
, class _Alloc
>
272 _Rope_iterator
<_CharT
,_Alloc
> operator-
273 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
276 template<class _CharT
, class _Alloc
>
277 _Rope_iterator
<_CharT
,_Alloc
> operator+
278 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
281 template<class _CharT
, class _Alloc
>
282 _Rope_iterator
<_CharT
,_Alloc
> operator+
284 const _Rope_iterator
<_CharT
,_Alloc
>& __x
);
286 template<class _CharT
, class _Alloc
>
288 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
289 const _Rope_iterator
<_CharT
,_Alloc
>& __y
);
291 template<class _CharT
, class _Alloc
>
293 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
294 const _Rope_iterator
<_CharT
,_Alloc
>& __y
);
296 template<class _CharT
, class _Alloc
>
298 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
299 const _Rope_iterator
<_CharT
,_Alloc
>& __y
);
301 template<class _CharT
, class _Alloc
>
302 rope
<_CharT
,_Alloc
> operator+ (const rope
<_CharT
,_Alloc
>& __left
,
303 const rope
<_CharT
,_Alloc
>& __right
);
305 template<class _CharT
, class _Alloc
>
306 rope
<_CharT
,_Alloc
> operator+ (const rope
<_CharT
,_Alloc
>& __left
,
307 const _CharT
* __right
);
309 template<class _CharT
, class _Alloc
>
310 rope
<_CharT
,_Alloc
> operator+ (const rope
<_CharT
,_Alloc
>& __left
,
313 // Some helpers, so we can use power on ropes.
314 // See below for why this isn't local to the implementation.
316 // This uses a nonstandard refcount convention.
317 // The result has refcount 0.
318 template<class _CharT
, class _Alloc
>
319 struct _Rope_Concat_fn
320 : public binary_function
<rope
<_CharT
,_Alloc
>, rope
<_CharT
,_Alloc
>,
321 rope
<_CharT
,_Alloc
> > {
322 rope
<_CharT
,_Alloc
> operator() (const rope
<_CharT
,_Alloc
>& __x
,
323 const rope
<_CharT
,_Alloc
>& __y
) {
328 template <class _CharT
, class _Alloc
>
331 identity_element(_Rope_Concat_fn
<_CharT
, _Alloc
>)
333 return rope
<_CharT
,_Alloc
>();
338 // What follows should really be local to rope. Unfortunately,
339 // that doesn't work, since it makes it impossible to define generic
340 // equality on rope iterators. According to the draft standard, the
341 // template parameters for such an equality operator cannot be inferred
342 // from the occurence of a member class as a parameter.
343 // (SGI compilers in fact allow this, but the __result wouldn't be
345 // Similarly, some of the static member functions are member functions
346 // only to avoid polluting the global namespace, and to circumvent
347 // restrictions on type inference for template functions.
351 // The internal data structure for representing a rope. This is
352 // private to the implementation. A rope is really just a pointer
355 // A few basic functions for manipulating this data structure
356 // are members of _RopeRep. Most of the more complex algorithms
357 // are implemented as rope members.
359 // Some of the static member functions of _RopeRep have identically
360 // named functions in rope that simply invoke the _RopeRep versions.
362 // A macro to introduce various allocation and deallocation functions
363 // These need to be defined differently depending on whether or not
364 // we are using standard conforming allocators, and whether the allocator
365 // instances have real state. Thus this macro is invoked repeatedly
366 // with different definitions of __ROPE_DEFINE_ALLOC.
367 // __ROPE_DEFINE_ALLOC(type,name) defines
368 // type * name_allocate(size_t) and
369 // void name_deallocate(tipe *, size_t)
370 // Both functions may or may not be static.
372 #define __ROPE_DEFINE_ALLOCS(__a) \
373 __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \
374 typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
375 __ROPE_DEFINE_ALLOC(__C,_C) \
376 typedef _Rope_RopeLeaf<_CharT,__a> __L; \
377 __ROPE_DEFINE_ALLOC(__L,_L) \
378 typedef _Rope_RopeFunction<_CharT,__a> __F; \
379 __ROPE_DEFINE_ALLOC(__F,_F) \
380 typedef _Rope_RopeSubstring<_CharT,__a> __S; \
381 __ROPE_DEFINE_ALLOC(__S,_S)
383 // Internal rope nodes potentially store a copy of the allocator
384 // instance used to allocate them. This is mostly redundant.
385 // But the alternative would be to pass allocator instances around
386 // in some form to nearly all internal functions, since any pointer
387 // assignment may result in a zero reference count and thus require
389 // The _Rope_rep_base class encapsulates
390 // the differences between SGI-style allocators and standard-conforming
393 #define __STATIC_IF_SGI_ALLOC /* not static */
395 // Base class for ordinary allocators.
396 template <class _CharT
, class _Allocator
, bool _IsStatic
>
397 class _Rope_rep_alloc_base
{
399 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
401 allocator_type
get_allocator() const { return _M_data_allocator
; }
402 _Rope_rep_alloc_base(size_t __size
, const allocator_type
& __a
)
403 : _M_size(__size
), _M_data_allocator(__a
) {}
404 size_t _M_size
; // This is here only to avoid wasting space
405 // for an otherwise empty base class.
409 allocator_type _M_data_allocator
;
411 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
413 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
414 /*static*/ _Tp * __name##_allocate(size_t __n) \
415 { return __name##Allocator(_M_data_allocator).allocate(__n); } \
416 void __name##_deallocate(_Tp* __p, size_t __n) \
417 { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
418 __ROPE_DEFINE_ALLOCS(_Allocator
);
419 # undef __ROPE_DEFINE_ALLOC
422 // Specialization for allocators that have the property that we don't
423 // actually have to store an allocator object.
424 template <class _CharT
, class _Allocator
>
425 class _Rope_rep_alloc_base
<_CharT
,_Allocator
,true> {
427 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
429 allocator_type
get_allocator() const { return allocator_type(); }
430 _Rope_rep_alloc_base(size_t __size
, const allocator_type
&)
436 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
438 _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \
440 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
441 static _Tp* __name##_allocate(size_t __n) \
442 { return __name##Alloc::allocate(__n); } \
443 void __name##_deallocate(_Tp *__p, size_t __n) \
444 { __name##Alloc::deallocate(__p, __n); }
445 __ROPE_DEFINE_ALLOCS(_Allocator
);
446 # undef __ROPE_DEFINE_ALLOC
449 template <class _CharT
, class _Alloc
>
450 struct _Rope_rep_base
451 : public _Rope_rep_alloc_base
<_CharT
,_Alloc
,
452 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
454 typedef _Rope_rep_alloc_base
<_CharT
,_Alloc
,
455 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
457 typedef typename
_Base::allocator_type allocator_type
;
458 _Rope_rep_base(size_t __size
, const allocator_type
& __a
)
459 : _Base(__size
, __a
) {}
463 template<class _CharT
, class _Alloc
>
464 struct _Rope_RopeRep
: public _Rope_rep_base
<_CharT
,_Alloc
>
470 enum { _S_max_rope_depth
= 45 };
471 enum _Tag
{_S_leaf
, _S_concat
, _S_substringfn
, _S_function
};
473 bool _M_is_balanced
:8;
474 unsigned char _M_depth
;
475 __GC_CONST _CharT
* _M_c_string
;
476 /* Flattened version of string, if needed. */
478 /* If it's not 0, then the memory is owned */
480 /* In the case of a leaf, this may point to */
481 /* the same memory as the data field. */
482 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
484 _Rope_RopeRep(_Tag __t
, int __d
, bool __b
, size_t __size
,
486 : _Rope_rep_base
<_CharT
,_Alloc
>(__size
, __a
),
490 _M_tag(__t
), _M_is_balanced(__b
), _M_depth(__d
), _M_c_string(0)
495 static void _S_free_string(__GC_CONST _CharT
*, size_t __len
,
497 # define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
498 // Deallocate data section of a leaf.
499 // This shouldn't be a member function.
500 // But its hard to do anything else at the
501 // moment, because it's templatized w.r.t.
503 // Does nothing if __GC is defined.
505 void _M_free_c_string();
507 // Deallocate t. Assumes t is not 0.
508 void _M_unref_nonnil()
510 if (0 == _M_decr()) _M_free_tree();
516 static void _S_unref(_Rope_RopeRep
* __t
)
519 __t
->_M_unref_nonnil();
522 static void _S_ref(_Rope_RopeRep
* __t
)
524 if (0 != __t
) __t
->_M_incr();
526 static void _S_free_if_unref(_Rope_RopeRep
* __t
)
528 if (0 != __t
&& 0 == __t
->_M_ref_count
) __t
->_M_free_tree();
531 void _M_unref_nonnil() {}
532 void _M_ref_nonnil() {}
533 static void _S_unref(_Rope_RopeRep
*) {}
534 static void _S_ref(_Rope_RopeRep
*) {}
535 static void _S_free_if_unref(_Rope_RopeRep
*) {}
540 template<class _CharT
, class _Alloc
>
541 struct _Rope_RopeLeaf
: public _Rope_RopeRep
<_CharT
,_Alloc
> {
543 // Apparently needed by VC++
544 // The data fields of leaves are allocated with some
545 // extra space, to accomodate future growth and for basic
546 // character types, to hold a trailing eos character.
547 enum { _S_alloc_granularity
= 8 };
548 static size_t _S_rounded_up_size(size_t __n
) {
549 size_t __size_with_eos
;
551 if (_S_is_basic_char_type((_CharT
*)0)) {
552 __size_with_eos
= __n
+ 1;
554 __size_with_eos
= __n
;
557 return __size_with_eos
;
559 // Allow slop for in-place expansion.
560 return (__size_with_eos
+ _S_alloc_granularity
-1)
561 &~ (_S_alloc_granularity
-1);
564 __GC_CONST _CharT
* _M_data
; /* Not necessarily 0 terminated. */
565 /* The allocated size is */
566 /* _S_rounded_up_size(size), except */
567 /* in the GC case, in which it */
568 /* doesn't matter. */
569 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
571 _Rope_RopeLeaf(__GC_CONST _CharT
* __d
, size_t __size
, allocator_type __a
)
572 : _Rope_RopeRep
<_CharT
,_Alloc
>(_S_leaf
, 0, true, __size
, __a
),
575 if (_S_is_basic_char_type((_CharT
*)0)) {
576 // already eos terminated.
580 // The constructor assumes that d has been allocated with
581 // the proper allocator and the properly padded size.
582 // In contrast, the destructor deallocates the data:
585 if (_M_data
!= _M_c_string
) {
588 __STL_FREE_STRING(_M_data
, _M_size
, get_allocator());
593 template<class _CharT
, class _Alloc
>
594 struct _Rope_RopeConcatenation
: public _Rope_RopeRep
<_CharT
,_Alloc
> {
596 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_left
;
597 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_right
;
598 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
600 _Rope_RopeConcatenation(_Rope_RopeRep
<_CharT
,_Alloc
>* __l
,
601 _Rope_RopeRep
<_CharT
,_Alloc
>* __r
,
604 : _Rope_RopeRep
<_CharT
,_Alloc
>(_S_concat
,
605 max(__l
->_M_depth
, __r
->_M_depth
) + 1,
607 __l
->_M_size
+ __r
->_M_size
, __a
),
608 _M_left(__l
), _M_right(__r
)
611 ~_Rope_RopeConcatenation() {
613 _M_left
->_M_unref_nonnil();
614 _M_right
->_M_unref_nonnil();
619 template<class _CharT
, class _Alloc
>
620 struct _Rope_RopeFunction
: public _Rope_RopeRep
<_CharT
,_Alloc
> {
622 char_producer
<_CharT
>* _M_fn
;
624 bool _M_delete_when_done
; // Char_producer is owned by the
625 // rope and should be explicitly
626 // deleted when the rope becomes
629 // In the GC case, we either register the rope for
630 // finalization, or not. Thus the field is unnecessary;
631 // the information is stored in the collector data structures.
632 // We do need a finalization procedure to be invoked by the
634 static void _S_fn_finalization_proc(void * __tree
, void *) {
635 delete ((_Rope_RopeFunction
*)__tree
) -> _M_fn
;
638 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
640 _Rope_RopeFunction(char_producer
<_CharT
>* __f
, size_t __size
,
641 bool __d
, allocator_type __a
)
642 : _Rope_RopeRep
<_CharT
,_Alloc
>(_S_function
, 0, true, __size
, __a
)
645 , _M_delete_when_done(__d
)
650 GC_REGISTER_FINALIZER(
651 this, _Rope_RopeFunction::_S_fn_finalization_proc
, 0, 0, 0);
656 ~_Rope_RopeFunction() {
658 if (_M_delete_when_done
) {
664 // Substring results are usually represented using just
665 // concatenation nodes. But in the case of very long flat ropes
666 // or ropes with a functional representation that isn't practical.
667 // In that case, we represent the __result as a special case of
668 // RopeFunction, whose char_producer points back to the rope itself.
669 // In all cases except repeated substring operations and
670 // deallocation, we treat the __result as a RopeFunction.
671 template<class _CharT
, class _Alloc
>
672 struct _Rope_RopeSubstring
: public _Rope_RopeFunction
<_CharT
,_Alloc
>,
673 public char_producer
<_CharT
> {
675 // XXX this whole class should be rewritten.
676 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_base
; // not 0
678 virtual void operator()(size_t __start_pos
, size_t __req_len
,
680 switch(_M_base
->_M_tag
) {
684 char_producer
<_CharT
>* __fn
=
685 ((_Rope_RopeFunction
<_CharT
,_Alloc
>*)_M_base
)->_M_fn
;
686 (*__fn
)(__start_pos
+ _M_start
, __req_len
, __buffer
);
691 __GC_CONST _CharT
* __s
=
692 ((_Rope_RopeLeaf
<_CharT
,_Alloc
>*)_M_base
)->_M_data
;
693 uninitialized_copy_n(__s
+ __start_pos
+ _M_start
, __req_len
,
701 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
703 _Rope_RopeSubstring(_Rope_RopeRep
<_CharT
,_Alloc
>* __b
, size_t __s
,
704 size_t __l
, allocator_type __a
)
705 : _Rope_RopeFunction
<_CharT
,_Alloc
>(this, __l
, false, __a
),
706 char_producer
<_CharT
>(),
711 _M_base
->_M_ref_nonnil();
713 _M_tag
= _S_substringfn
;
715 virtual ~_Rope_RopeSubstring()
718 _M_base
->_M_unref_nonnil();
719 // _M_free_c_string(); -- done by parent class
725 // Self-destructing pointers to Rope_rep.
726 // These are not conventional smart pointers. Their
727 // only purpose in life is to ensure that unref is called
728 // on the pointer either at normal exit or if an exception
729 // is raised. It is the caller's responsibility to
730 // adjust reference counts when these pointers are initialized
731 // or assigned to. (This convention significantly reduces
732 // the number of potentially expensive reference count
735 template<class _CharT
, class _Alloc
>
736 struct _Rope_self_destruct_ptr
{
737 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_ptr
;
738 ~_Rope_self_destruct_ptr()
739 { _Rope_RopeRep
<_CharT
,_Alloc
>::_S_unref(_M_ptr
); }
741 _Rope_self_destruct_ptr() : _M_ptr(0) {};
743 _Rope_self_destruct_ptr() {};
745 _Rope_self_destruct_ptr(_Rope_RopeRep
<_CharT
,_Alloc
>* __p
) : _M_ptr(__p
) {}
746 _Rope_RopeRep
<_CharT
,_Alloc
>& operator*() { return *_M_ptr
; }
747 _Rope_RopeRep
<_CharT
,_Alloc
>* operator->() { return _M_ptr
; }
748 operator _Rope_RopeRep
<_CharT
,_Alloc
>*() { return _M_ptr
; }
749 _Rope_self_destruct_ptr
& operator= (_Rope_RopeRep
<_CharT
,_Alloc
>* __x
)
750 { _M_ptr
= __x
; return *this; }
754 // Dereferencing a nonconst iterator has to return something
755 // that behaves almost like a reference. It's not possible to
756 // return an actual reference since assignment requires extra
757 // work. And we would get into the same problems as with the
758 // CD2 version of basic_string.
759 template<class _CharT
, class _Alloc
>
760 class _Rope_char_ref_proxy
{
761 friend class rope
<_CharT
,_Alloc
>;
762 friend class _Rope_iterator
<_CharT
,_Alloc
>;
763 friend class _Rope_char_ptr_proxy
<_CharT
,_Alloc
>;
765 typedef _Rope_RopeRep
<_CharT
,_Alloc
>* _Self_destruct_ptr
;
767 typedef _Rope_self_destruct_ptr
<_CharT
,_Alloc
> _Self_destruct_ptr
;
769 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
770 typedef rope
<_CharT
,_Alloc
> _My_rope
;
773 bool _M_current_valid
;
774 _My_rope
* _M_root
; // The whole rope.
776 _Rope_char_ref_proxy(_My_rope
* __r
, size_t __p
)
777 : _M_pos(__p
), _M_current_valid(false), _M_root(__r
) {}
778 _Rope_char_ref_proxy(const _Rope_char_ref_proxy
& __x
)
779 : _M_pos(__x
._M_pos
), _M_current_valid(false), _M_root(__x
._M_root
) {}
780 // Don't preserve cache if the reference can outlive the
781 // expression. We claim that's not possible without calling
782 // a copy constructor or generating reference to a proxy
783 // reference. We declare the latter to have undefined semantics.
784 _Rope_char_ref_proxy(_My_rope
* __r
, size_t __p
, _CharT __c
)
785 : _M_pos(__p
), _M_current(__c
), _M_current_valid(true), _M_root(__r
) {}
786 inline operator _CharT () const;
787 _Rope_char_ref_proxy
& operator= (_CharT __c
);
788 _Rope_char_ptr_proxy
<_CharT
,_Alloc
> operator& () const;
789 _Rope_char_ref_proxy
& operator= (const _Rope_char_ref_proxy
& __c
) {
790 return operator=((_CharT
)__c
);
794 template<class _CharT
, class __Alloc
>
795 inline void swap(_Rope_char_ref_proxy
<_CharT
, __Alloc
> __a
,
796 _Rope_char_ref_proxy
<_CharT
, __Alloc
> __b
) {
802 template<class _CharT
, class _Alloc
>
803 class _Rope_char_ptr_proxy
{
804 // XXX this class should be rewritten.
805 friend class _Rope_char_ref_proxy
<_CharT
,_Alloc
>;
807 rope
<_CharT
,_Alloc
>* _M_root
; // The whole rope.
809 _Rope_char_ptr_proxy(const _Rope_char_ref_proxy
<_CharT
,_Alloc
>& __x
)
810 : _M_pos(__x
._M_pos
), _M_root(__x
._M_root
) {}
811 _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy
& __x
)
812 : _M_pos(__x
._M_pos
), _M_root(__x
._M_root
) {}
813 _Rope_char_ptr_proxy() {}
814 _Rope_char_ptr_proxy(_CharT
* __x
) : _M_root(0), _M_pos(0) {
816 _Rope_char_ptr_proxy
&
817 operator= (const _Rope_char_ptr_proxy
& __x
) {
819 _M_root
= __x
._M_root
;
822 template<class _CharT2
, class _Alloc2
>
823 friend bool operator== (const _Rope_char_ptr_proxy
<_CharT2
,_Alloc2
>& __x
,
824 const _Rope_char_ptr_proxy
<_CharT2
,_Alloc2
>& __y
);
825 _Rope_char_ref_proxy
<_CharT
,_Alloc
> operator*() const {
826 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(_M_root
, _M_pos
);
832 // Unlike in the C version, we cache only part of the stack
833 // for rope iterators, since they must be efficiently copyable.
834 // When we run out of cache, we have to reconstruct the iterator
836 // Pointers from iterators are not included in reference counts.
837 // Iterators are assumed to be thread private. Ropes can
840 template<class _CharT
, class _Alloc
>
841 class _Rope_iterator_base
842 : public random_access_iterator
<_CharT
, ptrdiff_t> {
843 friend class rope
<_CharT
,_Alloc
>;
845 typedef _Alloc _allocator_type
; // used in _Rope_rotate, VC++ workaround
846 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
847 // Borland doesnt want this to be protected.
849 enum { _S_path_cache_len
= 4 }; // Must be <= 9.
850 enum { _S_iterator_buf_len
= 15 };
851 size_t _M_current_pos
;
852 _RopeRep
* _M_root
; // The whole rope.
853 size_t _M_leaf_pos
; // Starting position for current leaf
854 __GC_CONST _CharT
* _M_buf_start
;
856 // containing current char.
857 __GC_CONST _CharT
* _M_buf_ptr
;
858 // Pointer to current char in buffer.
859 // != 0 ==> buffer valid.
860 __GC_CONST _CharT
* _M_buf_end
;
861 // One past __last valid char in buffer.
862 // What follows is the path cache. We go out of our
863 // way to make this compact.
864 // Path_end contains the bottom section of the path from
865 // the root to the current leaf.
866 const _RopeRep
* _M_path_end
[_S_path_cache_len
];
867 int _M_leaf_index
; // Last valid __pos in path_end;
868 // _M_path_end[0] ... _M_path_end[leaf_index-1]
869 // point to concatenation nodes.
870 unsigned char _M_path_directions
;
871 // (path_directions >> __i) & 1 is 1
872 // iff we got from _M_path_end[leaf_index - __i - 1]
873 // to _M_path_end[leaf_index - __i] by going to the
874 // __right. Assumes path_cache_len <= 9.
875 _CharT _M_tmp_buf
[_S_iterator_buf_len
];
876 // Short buffer for surrounding chars.
877 // This is useful primarily for
878 // RopeFunctions. We put the buffer
879 // here to avoid locking in the
880 // multithreaded case.
881 // The cached path is generally assumed to be valid
882 // only if the buffer is valid.
883 static void _S_setbuf(_Rope_iterator_base
& __x
);
884 // Set buffer contents given
886 static void _S_setcache(_Rope_iterator_base
& __x
);
887 // Set buffer contents and
889 static void _S_setcache_for_incr(_Rope_iterator_base
& __x
);
890 // As above, but assumes path
891 // cache is valid for previous posn.
892 _Rope_iterator_base() {}
893 _Rope_iterator_base(_RopeRep
* __root
, size_t __pos
)
894 : _M_current_pos(__pos
), _M_root(__root
), _M_buf_ptr(0) {}
895 void _M_incr(size_t __n
);
896 void _M_decr(size_t __n
);
898 size_t index() const { return _M_current_pos
; }
899 _Rope_iterator_base(const _Rope_iterator_base
& __x
) {
900 if (0 != __x
._M_buf_ptr
) {
903 _M_current_pos
= __x
._M_current_pos
;
904 _M_root
= __x
._M_root
;
910 template<class _CharT
, class _Alloc
> class _Rope_iterator
;
912 template<class _CharT
, class _Alloc
>
913 class _Rope_const_iterator
: public _Rope_iterator_base
<_CharT
,_Alloc
> {
914 friend class rope
<_CharT
,_Alloc
>;
916 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
917 // The one from the base class may not be directly visible.
918 _Rope_const_iterator(const _RopeRep
* __root
, size_t __pos
):
919 _Rope_iterator_base
<_CharT
,_Alloc
>(
920 const_cast<_RopeRep
*>(__root
), __pos
)
921 // Only nonconst iterators modify root ref count
924 typedef _CharT reference
; // Really a value. Returning a reference
925 // Would be a mess, since it would have
926 // to be included in refcount.
927 typedef const _CharT
* pointer
;
930 _Rope_const_iterator() {};
931 _Rope_const_iterator(const _Rope_const_iterator
& __x
) :
932 _Rope_iterator_base
<_CharT
,_Alloc
>(__x
) { }
933 _Rope_const_iterator(const _Rope_iterator
<_CharT
,_Alloc
>& __x
);
934 _Rope_const_iterator(const rope
<_CharT
,_Alloc
>& __r
, size_t __pos
) :
935 _Rope_iterator_base
<_CharT
,_Alloc
>(__r
._M_tree_ptr
, __pos
) {}
936 _Rope_const_iterator
& operator= (const _Rope_const_iterator
& __x
) {
937 if (0 != __x
._M_buf_ptr
) {
938 *(static_cast<_Rope_iterator_base
<_CharT
,_Alloc
>*>(this)) = __x
;
940 _M_current_pos
= __x
._M_current_pos
;
941 _M_root
= __x
._M_root
;
946 reference
operator*() {
947 if (0 == _M_buf_ptr
) _S_setcache(*this);
950 _Rope_const_iterator
& operator++() {
951 __GC_CONST _CharT
* __next
;
952 if (0 != _M_buf_ptr
&& (__next
= _M_buf_ptr
+ 1) < _M_buf_end
) {
960 _Rope_const_iterator
& operator+=(ptrdiff_t __n
) {
968 _Rope_const_iterator
& operator--() {
972 _Rope_const_iterator
& operator-=(ptrdiff_t __n
) {
980 _Rope_const_iterator
operator++(int) {
981 size_t __old_pos
= _M_current_pos
;
983 return _Rope_const_iterator
<_CharT
,_Alloc
>(_M_root
, __old_pos
);
984 // This makes a subsequent dereference expensive.
985 // Perhaps we should instead copy the iterator
986 // if it has a valid cache?
988 _Rope_const_iterator
operator--(int) {
989 size_t __old_pos
= _M_current_pos
;
991 return _Rope_const_iterator
<_CharT
,_Alloc
>(_M_root
, __old_pos
);
993 template<class _CharT2
, class _Alloc2
>
994 friend _Rope_const_iterator
<_CharT2
,_Alloc2
> operator-
995 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
997 template<class _CharT2
, class _Alloc2
>
998 friend _Rope_const_iterator
<_CharT2
,_Alloc2
> operator+
999 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1001 template<class _CharT2
, class _Alloc2
>
1002 friend _Rope_const_iterator
<_CharT2
,_Alloc2
> operator+
1004 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
);
1005 reference
operator[](size_t __n
) {
1006 return rope
<_CharT
,_Alloc
>::_S_fetch(_M_root
, _M_current_pos
+ __n
);
1009 template<class _CharT2
, class _Alloc2
>
1010 friend bool operator==
1011 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1012 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __y
);
1013 template<class _CharT2
, class _Alloc2
>
1014 friend bool operator<
1015 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1016 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __y
);
1017 template<class _CharT2
, class _Alloc2
>
1018 friend ptrdiff_t operator-
1019 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1020 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __y
);
1023 template<class _CharT
, class _Alloc
>
1024 class _Rope_iterator
: public _Rope_iterator_base
<_CharT
,_Alloc
> {
1025 friend class rope
<_CharT
,_Alloc
>;
1027 rope
<_CharT
,_Alloc
>* _M_root_rope
;
1028 // root is treated as a cached version of this,
1029 // and is used to detect changes to the underlying
1031 // Root is included in the reference count.
1032 // This is necessary so that we can detect changes reliably.
1033 // Unfortunately, it requires careful bookkeeping for the
1035 _Rope_iterator(rope
<_CharT
,_Alloc
>* __r
, size_t __pos
)
1036 : _Rope_iterator_base
<_CharT
,_Alloc
>(__r
->_M_tree_ptr
, __pos
),
1038 { _RopeRep::_S_ref(_M_root
); if (!(__r
-> empty()))_S_setcache(*this); }
1042 typedef _Rope_char_ref_proxy
<_CharT
,_Alloc
> reference
;
1043 typedef _Rope_char_ref_proxy
<_CharT
,_Alloc
>* pointer
;
1046 rope
<_CharT
,_Alloc
>& container() { return *_M_root_rope
; }
1048 _M_root
= 0; // Needed for reference counting.
1050 _Rope_iterator(const _Rope_iterator
& __x
) :
1051 _Rope_iterator_base
<_CharT
,_Alloc
>(__x
) {
1052 _M_root_rope
= __x
._M_root_rope
;
1053 _RopeRep::_S_ref(_M_root
);
1055 _Rope_iterator(rope
<_CharT
,_Alloc
>& __r
, size_t __pos
);
1057 _RopeRep::_S_unref(_M_root
);
1059 _Rope_iterator
& operator= (const _Rope_iterator
& __x
) {
1060 _RopeRep
* __old
= _M_root
;
1062 _RopeRep::_S_ref(__x
._M_root
);
1063 if (0 != __x
._M_buf_ptr
) {
1064 _M_root_rope
= __x
._M_root_rope
;
1065 *(static_cast<_Rope_iterator_base
<_CharT
,_Alloc
>*>(this)) = __x
;
1067 _M_current_pos
= __x
._M_current_pos
;
1068 _M_root
= __x
._M_root
;
1069 _M_root_rope
= __x
._M_root_rope
;
1072 _RopeRep::_S_unref(__old
);
1075 reference
operator*() {
1077 if (0 == _M_buf_ptr
) {
1078 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(
1079 _M_root_rope
, _M_current_pos
);
1081 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(
1082 _M_root_rope
, _M_current_pos
, *_M_buf_ptr
);
1085 _Rope_iterator
& operator++() {
1089 _Rope_iterator
& operator+=(ptrdiff_t __n
) {
1097 _Rope_iterator
& operator--() {
1101 _Rope_iterator
& operator-=(ptrdiff_t __n
) {
1109 _Rope_iterator
operator++(int) {
1110 size_t __old_pos
= _M_current_pos
;
1112 return _Rope_iterator
<_CharT
,_Alloc
>(_M_root_rope
, __old_pos
);
1114 _Rope_iterator
operator--(int) {
1115 size_t __old_pos
= _M_current_pos
;
1117 return _Rope_iterator
<_CharT
,_Alloc
>(_M_root_rope
, __old_pos
);
1119 reference
operator[](ptrdiff_t __n
) {
1120 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(
1121 _M_root_rope
, _M_current_pos
+ __n
);
1124 template<class _CharT2
, class _Alloc2
>
1125 friend bool operator==
1126 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1127 const _Rope_iterator
<_CharT2
,_Alloc2
>& __y
);
1128 template<class _CharT2
, class _Alloc2
>
1129 friend bool operator<
1130 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1131 const _Rope_iterator
<_CharT2
,_Alloc2
>& __y
);
1132 template<class _CharT2
, class _Alloc2
>
1133 friend ptrdiff_t operator-
1134 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1135 const _Rope_iterator
<_CharT2
,_Alloc2
>& __y
);
1136 template<class _CharT2
, class _Alloc2
>
1137 friend _Rope_iterator
<_CharT2
,_Alloc2
> operator-
1138 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1140 template<class _CharT2
, class _Alloc2
>
1141 friend _Rope_iterator
<_CharT2
,_Alloc2
> operator+
1142 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1144 template<class _CharT2
, class _Alloc2
>
1145 friend _Rope_iterator
<_CharT2
,_Alloc2
> operator+
1147 const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
);
1150 // The rope base class encapsulates
1151 // the differences between SGI-style allocators and standard-conforming
1154 // Base class for ordinary allocators.
1155 template <class _CharT
, class _Allocator
, bool _IsStatic
>
1156 class _Rope_alloc_base
{
1158 typedef _Rope_RopeRep
<_CharT
,_Allocator
> _RopeRep
;
1159 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
1161 allocator_type
get_allocator() const { return _M_data_allocator
; }
1162 _Rope_alloc_base(_RopeRep
*__t
, const allocator_type
& __a
)
1163 : _M_tree_ptr(__t
), _M_data_allocator(__a
) {}
1164 _Rope_alloc_base(const allocator_type
& __a
)
1165 : _M_data_allocator(__a
) {}
1168 // The only data members of a rope:
1169 allocator_type _M_data_allocator
;
1170 _RopeRep
* _M_tree_ptr
;
1172 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
1174 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
1175 _Tp* __name##_allocate(size_t __n) const \
1176 { return __name##Allocator(_M_data_allocator).allocate(__n); } \
1177 void __name##_deallocate(_Tp *__p, size_t __n) const \
1178 { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
1179 __ROPE_DEFINE_ALLOCS(_Allocator
)
1180 # undef __ROPE_DEFINE_ALLOC
1183 // Specialization for allocators that have the property that we don't
1184 // actually have to store an allocator object.
1185 template <class _CharT
, class _Allocator
>
1186 class _Rope_alloc_base
<_CharT
,_Allocator
,true> {
1188 typedef _Rope_RopeRep
<_CharT
,_Allocator
> _RopeRep
;
1189 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
1191 allocator_type
get_allocator() const { return allocator_type(); }
1192 _Rope_alloc_base(_RopeRep
*__t
, const allocator_type
&)
1193 : _M_tree_ptr(__t
) {}
1194 _Rope_alloc_base(const allocator_type
&) {}
1197 // The only data member of a rope:
1198 _RopeRep
*_M_tree_ptr
;
1200 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
1202 _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \
1204 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
1205 static _Tp* __name##_allocate(size_t __n) \
1206 { return __name##Alloc::allocate(__n); } \
1207 static void __name##_deallocate(_Tp *__p, size_t __n) \
1208 { __name##Alloc::deallocate(__p, __n); }
1209 __ROPE_DEFINE_ALLOCS(_Allocator
)
1210 # undef __ROPE_DEFINE_ALLOC
1213 template <class _CharT
, class _Alloc
>
1215 : public _Rope_alloc_base
<_CharT
,_Alloc
,
1216 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
1218 typedef _Rope_alloc_base
<_CharT
,_Alloc
,
1219 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
1221 typedef typename
_Base::allocator_type allocator_type
;
1222 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
1223 // The one in _Base may not be visible due to template rules.
1224 _Rope_base(_RopeRep
* __t
, const allocator_type
& __a
) : _Base(__t
, __a
) {}
1225 _Rope_base(const allocator_type
& __a
) : _Base(__a
) {}
1229 template <class _CharT
, class _Alloc
>
1230 class rope
: public _Rope_base
<_CharT
,_Alloc
> {
1232 typedef _CharT value_type
;
1233 typedef ptrdiff_t difference_type
;
1234 typedef size_t size_type
;
1235 typedef _CharT const_reference
;
1236 typedef const _CharT
* const_pointer
;
1237 typedef _Rope_iterator
<_CharT
,_Alloc
> iterator
;
1238 typedef _Rope_const_iterator
<_CharT
,_Alloc
> const_iterator
;
1239 typedef _Rope_char_ref_proxy
<_CharT
,_Alloc
> reference
;
1240 typedef _Rope_char_ptr_proxy
<_CharT
,_Alloc
> pointer
;
1242 friend class _Rope_iterator
<_CharT
,_Alloc
>;
1243 friend class _Rope_const_iterator
<_CharT
,_Alloc
>;
1244 friend struct _Rope_RopeRep
<_CharT
,_Alloc
>;
1245 friend class _Rope_iterator_base
<_CharT
,_Alloc
>;
1246 friend class _Rope_char_ptr_proxy
<_CharT
,_Alloc
>;
1247 friend class _Rope_char_ref_proxy
<_CharT
,_Alloc
>;
1248 friend struct _Rope_RopeSubstring
<_CharT
,_Alloc
>;
1251 typedef _Rope_base
<_CharT
,_Alloc
> _Base
;
1252 typedef typename
_Base::allocator_type allocator_type
;
1253 using _Base::_M_tree_ptr
;
1254 typedef __GC_CONST _CharT
* _Cstrptr
;
1256 static _CharT _S_empty_c_str
[1];
1258 static bool _S_is0(_CharT __c
) { return __c
== _S_eos((_CharT
*)0); }
1259 enum { _S_copy_max
= 23 };
1260 // For strings shorter than _S_copy_max, we copy to
1263 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
1264 typedef _Rope_RopeConcatenation
<_CharT
,_Alloc
> _RopeConcatenation
;
1265 typedef _Rope_RopeLeaf
<_CharT
,_Alloc
> _RopeLeaf
;
1266 typedef _Rope_RopeFunction
<_CharT
,_Alloc
> _RopeFunction
;
1267 typedef _Rope_RopeSubstring
<_CharT
,_Alloc
> _RopeSubstring
;
1269 // Retrieve a character at the indicated position.
1270 static _CharT
_S_fetch(_RopeRep
* __r
, size_type __pos
);
1273 // Obtain a pointer to the character at the indicated position.
1274 // The pointer can be used to change the character.
1275 // If such a pointer cannot be produced, as is frequently the
1276 // case, 0 is returned instead.
1277 // (Returns nonzero only if all nodes in the path have a refcount
1279 static _CharT
* _S_fetch_ptr(_RopeRep
* __r
, size_type __pos
);
1282 static bool _S_apply_to_pieces(
1283 // should be template parameter
1284 _Rope_char_consumer
<_CharT
>& __c
,
1285 const _RopeRep
* __r
,
1286 size_t __begin
, size_t __end
);
1287 // begin and end are assumed to be in range.
1290 static void _S_unref(_RopeRep
* __t
)
1292 _RopeRep::_S_unref(__t
);
1294 static void _S_ref(_RopeRep
* __t
)
1296 _RopeRep::_S_ref(__t
);
1299 static void _S_unref(_RopeRep
*) {}
1300 static void _S_ref(_RopeRep
*) {}
1305 typedef _Rope_RopeRep
<_CharT
,_Alloc
>* _Self_destruct_ptr
;
1307 typedef _Rope_self_destruct_ptr
<_CharT
,_Alloc
> _Self_destruct_ptr
;
1310 // _Result is counted in refcount.
1311 static _RopeRep
* _S_substring(_RopeRep
* __base
,
1312 size_t __start
, size_t __endp1
);
1314 static _RopeRep
* _S_concat_char_iter(_RopeRep
* __r
,
1315 const _CharT
* __iter
, size_t __slen
);
1316 // Concatenate rope and char ptr, copying __s.
1317 // Should really take an arbitrary iterator.
1318 // Result is counted in refcount.
1319 static _RopeRep
* _S_destr_concat_char_iter(_RopeRep
* __r
,
1320 const _CharT
* __iter
, size_t __slen
)
1321 // As above, but one reference to __r is about to be
1322 // destroyed. Thus the pieces may be recycled if all
1323 // relevent reference counts are 1.
1325 // We can't really do anything since refcounts are unavailable.
1326 { return _S_concat_char_iter(__r
, __iter
, __slen
); }
1331 static _RopeRep
* _S_concat(_RopeRep
* __left
, _RopeRep
* __right
);
1332 // General concatenation on _RopeRep. _Result
1333 // has refcount of 1. Adjusts argument refcounts.
1336 void apply_to_pieces( size_t __begin
, size_t __end
,
1337 _Rope_char_consumer
<_CharT
>& __c
) const {
1338 _S_apply_to_pieces(__c
, _M_tree_ptr
, __begin
, __end
);
1344 static size_t _S_rounded_up_size(size_t __n
) {
1345 return _RopeLeaf::_S_rounded_up_size(__n
);
1348 static size_t _S_allocated_capacity(size_t __n
) {
1349 if (_S_is_basic_char_type((_CharT
*)0)) {
1350 return _S_rounded_up_size(__n
) - 1;
1352 return _S_rounded_up_size(__n
);
1356 // Allocate and construct a RopeLeaf using the supplied allocator
1357 // Takes ownership of s instead of copying.
1358 static _RopeLeaf
* _S_new_RopeLeaf(__GC_CONST _CharT
*__s
,
1359 size_t __size
, allocator_type __a
)
1361 _RopeLeaf
* __space
= _LAllocator(__a
).allocate(1);
1362 return new(__space
) _RopeLeaf(__s
, __size
, __a
);
1365 static _RopeConcatenation
* _S_new_RopeConcatenation(
1366 _RopeRep
* __left
, _RopeRep
* __right
,
1369 _RopeConcatenation
* __space
= _CAllocator(__a
).allocate(1);
1370 return new(__space
) _RopeConcatenation(__left
, __right
, __a
);
1373 static _RopeFunction
* _S_new_RopeFunction(char_producer
<_CharT
>* __f
,
1374 size_t __size
, bool __d
, allocator_type __a
)
1376 _RopeFunction
* __space
= _FAllocator(__a
).allocate(1);
1377 return new(__space
) _RopeFunction(__f
, __size
, __d
, __a
);
1380 static _RopeSubstring
* _S_new_RopeSubstring(
1381 _Rope_RopeRep
<_CharT
,_Alloc
>* __b
, size_t __s
,
1382 size_t __l
, allocator_type __a
)
1384 _RopeSubstring
* __space
= _SAllocator(__a
).allocate(1);
1385 return new(__space
) _RopeSubstring(__b
, __s
, __l
, __a
);
1389 _RopeLeaf
* _S_RopeLeaf_from_unowned_char_ptr(const _CharT
*__s
,
1390 size_t __size
, allocator_type __a
)
1391 # define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
1392 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
1394 if (0 == __size
) return 0;
1395 _CharT
* __buf
= __a
.allocate(_S_rounded_up_size(__size
));
1397 uninitialized_copy_n(__s
, __size
, __buf
);
1398 _S_cond_store_eos(__buf
[__size
]);
1400 return _S_new_RopeLeaf(__buf
, __size
, __a
);
1404 _RopeRep::__STL_FREE_STRING(__buf
, __size
, __a
);
1405 __throw_exception_again
;
1410 // Concatenation of nonempty strings.
1411 // Always builds a concatenation node.
1412 // Rebalances if the result is too deep.
1413 // Result has refcount 1.
1414 // Does not increment left and right ref counts even though
1415 // they are referenced.
1417 _S_tree_concat(_RopeRep
* __left
, _RopeRep
* __right
);
1419 // Concatenation helper functions
1421 _S_leaf_concat_char_iter(_RopeLeaf
* __r
,
1422 const _CharT
* __iter
, size_t __slen
);
1423 // Concatenate by copying leaf.
1424 // should take an arbitrary iterator
1425 // result has refcount 1.
1427 static _RopeLeaf
* _S_destr_leaf_concat_char_iter
1428 (_RopeLeaf
* __r
, const _CharT
* __iter
, size_t __slen
);
1429 // A version that potentially clobbers __r if __r->_M_ref_count == 1.
1434 static size_t _S_char_ptr_len(const _CharT
* __s
);
1435 // slightly generalized strlen
1437 rope(_RopeRep
* __t
, const allocator_type
& __a
= allocator_type())
1438 : _Base(__t
,__a
) { }
1441 // Copy __r to the _CharT buffer.
1442 // Returns __buffer + __r->_M_size.
1443 // Assumes that buffer is uninitialized.
1444 static _CharT
* _S_flatten(_RopeRep
* __r
, _CharT
* __buffer
);
1446 // Again, with explicit starting position and length.
1447 // Assumes that buffer is uninitialized.
1448 static _CharT
* _S_flatten(_RopeRep
* __r
,
1449 size_t __start
, size_t __len
,
1452 static const unsigned long
1453 _S_min_len
[_RopeRep::_S_max_rope_depth
+ 1];
1455 static bool _S_is_balanced(_RopeRep
* __r
)
1456 { return (__r
->_M_size
>= _S_min_len
[__r
->_M_depth
]); }
1458 static bool _S_is_almost_balanced(_RopeRep
* __r
)
1459 { return (__r
->_M_depth
== 0 ||
1460 __r
->_M_size
>= _S_min_len
[__r
->_M_depth
- 1]); }
1462 static bool _S_is_roughly_balanced(_RopeRep
* __r
)
1463 { return (__r
->_M_depth
<= 1 ||
1464 __r
->_M_size
>= _S_min_len
[__r
->_M_depth
- 2]); }
1466 // Assumes the result is not empty.
1467 static _RopeRep
* _S_concat_and_set_balanced(_RopeRep
* __left
,
1470 _RopeRep
* __result
= _S_concat(__left
, __right
);
1471 if (_S_is_balanced(__result
)) __result
->_M_is_balanced
= true;
1475 // The basic rebalancing operation. Logically copies the
1476 // rope. The result has refcount of 1. The client will
1477 // usually decrement the reference count of __r.
1478 // The result is within height 2 of balanced by the above
1480 static _RopeRep
* _S_balance(_RopeRep
* __r
);
1482 // Add all unbalanced subtrees to the forest of balanceed trees.
1483 // Used only by balance.
1484 static void _S_add_to_forest(_RopeRep
*__r
, _RopeRep
** __forest
);
1486 // Add __r to forest, assuming __r is already balanced.
1487 static void _S_add_leaf_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
);
1489 // Print to stdout, exposing structure
1490 static void _S_dump(_RopeRep
* __r
, int __indent
= 0);
1492 // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
1493 static int _S_compare(const _RopeRep
* __x
, const _RopeRep
* __y
);
1496 bool empty() const { return 0 == _M_tree_ptr
; }
1498 // Comparison member function. This is public only for those
1499 // clients that need a ternary comparison. Others
1500 // should use the comparison operators below.
1501 int compare(const rope
& __y
) const {
1502 return _S_compare(_M_tree_ptr
, __y
._M_tree_ptr
);
1505 rope(const _CharT
* __s
, const allocator_type
& __a
= allocator_type())
1506 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, _S_char_ptr_len(__s
),
1510 rope(const _CharT
* __s
, size_t __len
,
1511 const allocator_type
& __a
= allocator_type())
1512 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __len
, __a
), __a
)
1515 // Should perhaps be templatized with respect to the iterator type
1516 // and use Sequence_buffer. (It should perhaps use sequence_buffer
1518 rope(const _CharT
*__s
, const _CharT
*__e
,
1519 const allocator_type
& __a
= allocator_type())
1520 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __e
- __s
, __a
), __a
)
1523 rope(const const_iterator
& __s
, const const_iterator
& __e
,
1524 const allocator_type
& __a
= allocator_type())
1525 : _Base(_S_substring(__s
._M_root
, __s
._M_current_pos
,
1526 __e
._M_current_pos
), __a
)
1529 rope(const iterator
& __s
, const iterator
& __e
,
1530 const allocator_type
& __a
= allocator_type())
1531 : _Base(_S_substring(__s
._M_root
, __s
._M_current_pos
,
1532 __e
._M_current_pos
), __a
)
1535 rope(_CharT __c
, const allocator_type
& __a
= allocator_type())
1538 _CharT
* __buf
= _Data_allocate(_S_rounded_up_size(1));
1540 _Construct(__buf
, __c
);
1542 _M_tree_ptr
= _S_new_RopeLeaf(__buf
, 1, __a
);
1546 _RopeRep::__STL_FREE_STRING(__buf
, 1, __a
);
1547 __throw_exception_again
;
1551 rope(size_t __n
, _CharT __c
,
1552 const allocator_type
& __a
= allocator_type());
1554 rope(const allocator_type
& __a
= allocator_type())
1557 // Construct a rope from a function that can compute its members
1558 rope(char_producer
<_CharT
> *__fn
, size_t __len
, bool __delete_fn
,
1559 const allocator_type
& __a
= allocator_type())
1562 _M_tree_ptr
= (0 == __len
) ?
1563 0 : _S_new_RopeFunction(__fn
, __len
, __delete_fn
, __a
);
1566 rope(const rope
& __x
, const allocator_type
& __a
= allocator_type())
1567 : _Base(__x
._M_tree_ptr
, __a
)
1569 _S_ref(_M_tree_ptr
);
1574 _S_unref(_M_tree_ptr
);
1577 rope
& operator=(const rope
& __x
)
1579 _RopeRep
* __old
= _M_tree_ptr
;
1580 _M_tree_ptr
= __x
._M_tree_ptr
;
1581 _S_ref(_M_tree_ptr
);
1588 _S_unref(_M_tree_ptr
);
1592 void push_back(_CharT __x
)
1594 _RopeRep
* __old
= _M_tree_ptr
;
1595 _M_tree_ptr
= _S_destr_concat_char_iter(_M_tree_ptr
, &__x
, 1);
1601 _RopeRep
* __old
= _M_tree_ptr
;
1603 _S_substring(_M_tree_ptr
, 0, _M_tree_ptr
->_M_size
- 1);
1609 return _S_fetch(_M_tree_ptr
, _M_tree_ptr
->_M_size
- 1);
1612 void push_front(_CharT __x
)
1614 _RopeRep
* __old
= _M_tree_ptr
;
1616 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x
, 1, get_allocator());
1618 _M_tree_ptr
= _S_concat(__left
, _M_tree_ptr
);
1625 __throw_exception_again
;
1631 _RopeRep
* __old
= _M_tree_ptr
;
1632 _M_tree_ptr
= _S_substring(_M_tree_ptr
, 1, _M_tree_ptr
->_M_size
);
1636 _CharT
front() const
1638 return _S_fetch(_M_tree_ptr
, 0);
1643 _RopeRep
* __old
= _M_tree_ptr
;
1644 _M_tree_ptr
= _S_balance(_M_tree_ptr
);
1648 void copy(_CharT
* __buffer
) const {
1649 _Destroy(__buffer
, __buffer
+ size());
1650 _S_flatten(_M_tree_ptr
, __buffer
);
1653 // This is the copy function from the standard, but
1654 // with the arguments reordered to make it consistent with the
1655 // rest of the interface.
1656 // Note that this guaranteed not to compile if the draft standard
1657 // order is assumed.
1658 size_type
copy(size_type __pos
, size_type __n
, _CharT
* __buffer
) const
1660 size_t __size
= size();
1661 size_t __len
= (__pos
+ __n
> __size
? __size
- __pos
: __n
);
1663 _Destroy(__buffer
, __buffer
+ __len
);
1664 _S_flatten(_M_tree_ptr
, __pos
, __len
, __buffer
);
1668 // Print to stdout, exposing structure. May be useful for
1669 // performance debugging.
1671 _S_dump(_M_tree_ptr
);
1674 // Convert to 0 terminated string in new allocated memory.
1675 // Embedded 0s in the input do not terminate the copy.
1676 const _CharT
* c_str() const;
1678 // As above, but lso use the flattened representation as the
1679 // the new rope representation.
1680 const _CharT
* replace_with_c_str();
1682 // Reclaim memory for the c_str generated flattened string.
1683 // Intentionally undocumented, since it's hard to say when this
1684 // is safe for multiple threads.
1685 void delete_c_str () {
1686 if (0 == _M_tree_ptr
) return;
1687 if (_RopeRep::_S_leaf
== _M_tree_ptr
->_M_tag
&&
1688 ((_RopeLeaf
*)_M_tree_ptr
)->_M_data
==
1689 _M_tree_ptr
->_M_c_string
) {
1690 // Representation shared
1694 _M_tree_ptr
->_M_free_c_string();
1696 _M_tree_ptr
->_M_c_string
= 0;
1699 _CharT
operator[] (size_type __pos
) const {
1700 return _S_fetch(_M_tree_ptr
, __pos
);
1703 _CharT
at(size_type __pos
) const {
1704 // if (__pos >= size()) throw out_of_range; // XXX
1705 return (*this)[__pos
];
1708 const_iterator
begin() const {
1709 return(const_iterator(_M_tree_ptr
, 0));
1712 // An easy way to get a const iterator from a non-const container.
1713 const_iterator
const_begin() const {
1714 return(const_iterator(_M_tree_ptr
, 0));
1717 const_iterator
end() const {
1718 return(const_iterator(_M_tree_ptr
, size()));
1721 const_iterator
const_end() const {
1722 return(const_iterator(_M_tree_ptr
, size()));
1725 size_type
size() const {
1726 return(0 == _M_tree_ptr
? 0 : _M_tree_ptr
->_M_size
);
1729 size_type
length() const {
1733 size_type
max_size() const {
1734 return _S_min_len
[_RopeRep::_S_max_rope_depth
-1] - 1;
1735 // Guarantees that the result can be sufficirntly
1736 // balanced. Longer ropes will probably still work,
1737 // but it's harder to make guarantees.
1740 typedef reverse_iterator
<const_iterator
> const_reverse_iterator
;
1742 const_reverse_iterator
rbegin() const {
1743 return const_reverse_iterator(end());
1746 const_reverse_iterator
const_rbegin() const {
1747 return const_reverse_iterator(end());
1750 const_reverse_iterator
rend() const {
1751 return const_reverse_iterator(begin());
1754 const_reverse_iterator
const_rend() const {
1755 return const_reverse_iterator(begin());
1758 template<class _CharT2
, class _Alloc2
>
1759 friend rope
<_CharT2
,_Alloc2
>
1760 operator+ (const rope
<_CharT2
,_Alloc2
>& __left
,
1761 const rope
<_CharT2
,_Alloc2
>& __right
);
1763 template<class _CharT2
, class _Alloc2
>
1764 friend rope
<_CharT2
,_Alloc2
>
1765 operator+ (const rope
<_CharT2
,_Alloc2
>& __left
,
1766 const _CharT2
* __right
);
1768 template<class _CharT2
, class _Alloc2
>
1769 friend rope
<_CharT2
,_Alloc2
>
1770 operator+ (const rope
<_CharT2
,_Alloc2
>& __left
, _CharT2 __right
);
1771 // The symmetric cases are intentionally omitted, since they're presumed
1772 // to be less common, and we don't handle them as well.
1774 // The following should really be templatized.
1775 // The first argument should be an input iterator or
1776 // forward iterator with value_type _CharT.
1777 rope
& append(const _CharT
* __iter
, size_t __n
) {
1778 _RopeRep
* __result
=
1779 _S_destr_concat_char_iter(_M_tree_ptr
, __iter
, __n
);
1780 _S_unref(_M_tree_ptr
);
1781 _M_tree_ptr
= __result
;
1785 rope
& append(const _CharT
* __c_string
) {
1786 size_t __len
= _S_char_ptr_len(__c_string
);
1787 append(__c_string
, __len
);
1791 rope
& append(const _CharT
* __s
, const _CharT
* __e
) {
1792 _RopeRep
* __result
=
1793 _S_destr_concat_char_iter(_M_tree_ptr
, __s
, __e
- __s
);
1794 _S_unref(_M_tree_ptr
);
1795 _M_tree_ptr
= __result
;
1799 rope
& append(const_iterator __s
, const_iterator __e
) {
1800 _Self_destruct_ptr
__appendee(_S_substring(
1801 __s
._M_root
, __s
._M_current_pos
, __e
._M_current_pos
));
1802 _RopeRep
* __result
=
1803 _S_concat(_M_tree_ptr
, (_RopeRep
*)__appendee
);
1804 _S_unref(_M_tree_ptr
);
1805 _M_tree_ptr
= __result
;
1809 rope
& append(_CharT __c
) {
1810 _RopeRep
* __result
=
1811 _S_destr_concat_char_iter(_M_tree_ptr
, &__c
, 1);
1812 _S_unref(_M_tree_ptr
);
1813 _M_tree_ptr
= __result
;
1817 rope
& append() { return append(_CharT()); } // XXX why?
1819 rope
& append(const rope
& __y
) {
1820 _RopeRep
* __result
= _S_concat(_M_tree_ptr
, __y
._M_tree_ptr
);
1821 _S_unref(_M_tree_ptr
);
1822 _M_tree_ptr
= __result
;
1826 rope
& append(size_t __n
, _CharT __c
) {
1827 rope
<_CharT
,_Alloc
> __last(__n
, __c
);
1828 return append(__last
);
1831 void swap(rope
& __b
) {
1832 _RopeRep
* __tmp
= _M_tree_ptr
;
1833 _M_tree_ptr
= __b
._M_tree_ptr
;
1834 __b
._M_tree_ptr
= __tmp
;
1839 // Result is included in refcount.
1840 static _RopeRep
* replace(_RopeRep
* __old
, size_t __pos1
,
1841 size_t __pos2
, _RopeRep
* __r
) {
1842 if (0 == __old
) { _S_ref(__r
); return __r
; }
1843 _Self_destruct_ptr
__left(
1844 _S_substring(__old
, 0, __pos1
));
1845 _Self_destruct_ptr
__right(
1846 _S_substring(__old
, __pos2
, __old
->_M_size
));
1850 __result
= _S_concat(__left
, __right
);
1852 _Self_destruct_ptr
__left_result(_S_concat(__left
, __r
));
1853 __result
= _S_concat(__left_result
, __right
);
1859 void insert(size_t __p
, const rope
& __r
) {
1860 _RopeRep
* __result
=
1861 replace(_M_tree_ptr
, __p
, __p
, __r
._M_tree_ptr
);
1862 _S_unref(_M_tree_ptr
);
1863 _M_tree_ptr
= __result
;
1866 void insert(size_t __p
, size_t __n
, _CharT __c
) {
1867 rope
<_CharT
,_Alloc
> __r(__n
,__c
);
1871 void insert(size_t __p
, const _CharT
* __i
, size_t __n
) {
1872 _Self_destruct_ptr
__left(_S_substring(_M_tree_ptr
, 0, __p
));
1873 _Self_destruct_ptr
__right(_S_substring(_M_tree_ptr
, __p
, size()));
1874 _Self_destruct_ptr
__left_result(
1875 _S_concat_char_iter(__left
, __i
, __n
));
1876 // _S_ destr_concat_char_iter should be safe here.
1877 // But as it stands it's probably not a win, since __left
1878 // is likely to have additional references.
1879 _RopeRep
* __result
= _S_concat(__left_result
, __right
);
1880 _S_unref(_M_tree_ptr
);
1881 _M_tree_ptr
= __result
;
1884 void insert(size_t __p
, const _CharT
* __c_string
) {
1885 insert(__p
, __c_string
, _S_char_ptr_len(__c_string
));
1888 void insert(size_t __p
, _CharT __c
) {
1889 insert(__p
, &__c
, 1);
1892 void insert(size_t __p
) {
1893 _CharT __c
= _CharT();
1894 insert(__p
, &__c
, 1);
1897 void insert(size_t __p
, const _CharT
* __i
, const _CharT
* __j
) {
1902 void insert(size_t __p
, const const_iterator
& __i
,
1903 const const_iterator
& __j
) {
1908 void insert(size_t __p
, const iterator
& __i
,
1909 const iterator
& __j
) {
1914 // (position, length) versions of replace operations:
1916 void replace(size_t __p
, size_t __n
, const rope
& __r
) {
1917 _RopeRep
* __result
=
1918 replace(_M_tree_ptr
, __p
, __p
+ __n
, __r
._M_tree_ptr
);
1919 _S_unref(_M_tree_ptr
);
1920 _M_tree_ptr
= __result
;
1923 void replace(size_t __p
, size_t __n
,
1924 const _CharT
* __i
, size_t __i_len
) {
1925 rope
__r(__i
, __i_len
);
1926 replace(__p
, __n
, __r
);
1929 void replace(size_t __p
, size_t __n
, _CharT __c
) {
1931 replace(__p
, __n
, __r
);
1934 void replace(size_t __p
, size_t __n
, const _CharT
* __c_string
) {
1935 rope
__r(__c_string
);
1936 replace(__p
, __n
, __r
);
1939 void replace(size_t __p
, size_t __n
,
1940 const _CharT
* __i
, const _CharT
* __j
) {
1942 replace(__p
, __n
, __r
);
1945 void replace(size_t __p
, size_t __n
,
1946 const const_iterator
& __i
, const const_iterator
& __j
) {
1948 replace(__p
, __n
, __r
);
1951 void replace(size_t __p
, size_t __n
,
1952 const iterator
& __i
, const iterator
& __j
) {
1954 replace(__p
, __n
, __r
);
1957 // Single character variants:
1958 void replace(size_t __p
, _CharT __c
) {
1959 iterator
__i(this, __p
);
1963 void replace(size_t __p
, const rope
& __r
) {
1964 replace(__p
, 1, __r
);
1967 void replace(size_t __p
, const _CharT
* __i
, size_t __i_len
) {
1968 replace(__p
, 1, __i
, __i_len
);
1971 void replace(size_t __p
, const _CharT
* __c_string
) {
1972 replace(__p
, 1, __c_string
);
1975 void replace(size_t __p
, const _CharT
* __i
, const _CharT
* __j
) {
1976 replace(__p
, 1, __i
, __j
);
1979 void replace(size_t __p
, const const_iterator
& __i
,
1980 const const_iterator
& __j
) {
1981 replace(__p
, 1, __i
, __j
);
1984 void replace(size_t __p
, const iterator
& __i
,
1985 const iterator
& __j
) {
1986 replace(__p
, 1, __i
, __j
);
1989 // Erase, (position, size) variant.
1990 void erase(size_t __p
, size_t __n
) {
1991 _RopeRep
* __result
= replace(_M_tree_ptr
, __p
, __p
+ __n
, 0);
1992 _S_unref(_M_tree_ptr
);
1993 _M_tree_ptr
= __result
;
1996 // Erase, single character
1997 void erase(size_t __p
) {
1998 erase(__p
, __p
+ 1);
2001 // Insert, iterator variants.
2002 iterator
insert(const iterator
& __p
, const rope
& __r
)
2003 { insert(__p
.index(), __r
); return __p
; }
2004 iterator
insert(const iterator
& __p
, size_t __n
, _CharT __c
)
2005 { insert(__p
.index(), __n
, __c
); return __p
; }
2006 iterator
insert(const iterator
& __p
, _CharT __c
)
2007 { insert(__p
.index(), __c
); return __p
; }
2008 iterator
insert(const iterator
& __p
)
2009 { insert(__p
.index()); return __p
; }
2010 iterator
insert(const iterator
& __p
, const _CharT
* c_string
)
2011 { insert(__p
.index(), c_string
); return __p
; }
2012 iterator
insert(const iterator
& __p
, const _CharT
* __i
, size_t __n
)
2013 { insert(__p
.index(), __i
, __n
); return __p
; }
2014 iterator
insert(const iterator
& __p
, const _CharT
* __i
,
2016 { insert(__p
.index(), __i
, __j
); return __p
; }
2017 iterator
insert(const iterator
& __p
,
2018 const const_iterator
& __i
, const const_iterator
& __j
)
2019 { insert(__p
.index(), __i
, __j
); return __p
; }
2020 iterator
insert(const iterator
& __p
,
2021 const iterator
& __i
, const iterator
& __j
)
2022 { insert(__p
.index(), __i
, __j
); return __p
; }
2024 // Replace, range variants.
2025 void replace(const iterator
& __p
, const iterator
& __q
,
2027 { replace(__p
.index(), __q
.index() - __p
.index(), __r
); }
2028 void replace(const iterator
& __p
, const iterator
& __q
, _CharT __c
)
2029 { replace(__p
.index(), __q
.index() - __p
.index(), __c
); }
2030 void replace(const iterator
& __p
, const iterator
& __q
,
2031 const _CharT
* __c_string
)
2032 { replace(__p
.index(), __q
.index() - __p
.index(), __c_string
); }
2033 void replace(const iterator
& __p
, const iterator
& __q
,
2034 const _CharT
* __i
, size_t __n
)
2035 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __n
); }
2036 void replace(const iterator
& __p
, const iterator
& __q
,
2037 const _CharT
* __i
, const _CharT
* __j
)
2038 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __j
); }
2039 void replace(const iterator
& __p
, const iterator
& __q
,
2040 const const_iterator
& __i
, const const_iterator
& __j
)
2041 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __j
); }
2042 void replace(const iterator
& __p
, const iterator
& __q
,
2043 const iterator
& __i
, const iterator
& __j
)
2044 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __j
); }
2046 // Replace, iterator variants.
2047 void replace(const iterator
& __p
, const rope
& __r
)
2048 { replace(__p
.index(), __r
); }
2049 void replace(const iterator
& __p
, _CharT __c
)
2050 { replace(__p
.index(), __c
); }
2051 void replace(const iterator
& __p
, const _CharT
* __c_string
)
2052 { replace(__p
.index(), __c_string
); }
2053 void replace(const iterator
& __p
, const _CharT
* __i
, size_t __n
)
2054 { replace(__p
.index(), __i
, __n
); }
2055 void replace(const iterator
& __p
, const _CharT
* __i
, const _CharT
* __j
)
2056 { replace(__p
.index(), __i
, __j
); }
2057 void replace(const iterator
& __p
, const_iterator __i
,
2059 { replace(__p
.index(), __i
, __j
); }
2060 void replace(const iterator
& __p
, iterator __i
, iterator __j
)
2061 { replace(__p
.index(), __i
, __j
); }
2063 // Iterator and range variants of erase
2064 iterator
erase(const iterator
& __p
, const iterator
& __q
) {
2065 size_t __p_index
= __p
.index();
2066 erase(__p_index
, __q
.index() - __p_index
);
2067 return iterator(this, __p_index
);
2069 iterator
erase(const iterator
& __p
) {
2070 size_t __p_index
= __p
.index();
2071 erase(__p_index
, 1);
2072 return iterator(this, __p_index
);
2075 rope
substr(size_t __start
, size_t __len
= 1) const {
2076 return rope
<_CharT
,_Alloc
>(
2077 _S_substring(_M_tree_ptr
, __start
, __start
+ __len
));
2080 rope
substr(iterator __start
, iterator __end
) const {
2081 return rope
<_CharT
,_Alloc
>(
2082 _S_substring(_M_tree_ptr
, __start
.index(), __end
.index()));
2085 rope
substr(iterator __start
) const {
2086 size_t __pos
= __start
.index();
2087 return rope
<_CharT
,_Alloc
>(
2088 _S_substring(_M_tree_ptr
, __pos
, __pos
+ 1));
2091 rope
substr(const_iterator __start
, const_iterator __end
) const {
2092 // This might eventually take advantage of the cache in the
2094 return rope
<_CharT
,_Alloc
>(
2095 _S_substring(_M_tree_ptr
, __start
.index(), __end
.index()));
2098 rope
<_CharT
,_Alloc
> substr(const_iterator __start
) {
2099 size_t __pos
= __start
.index();
2100 return rope
<_CharT
,_Alloc
>(
2101 _S_substring(_M_tree_ptr
, __pos
, __pos
+ 1));
2104 static const size_type npos
;
2106 size_type
find(_CharT __c
, size_type __pos
= 0) const;
2107 size_type
find(const _CharT
* __s
, size_type __pos
= 0) const {
2108 size_type __result_pos
;
2109 const_iterator __result
= search(const_begin() + __pos
, const_end(),
2110 __s
, __s
+ _S_char_ptr_len(__s
));
2111 __result_pos
= __result
.index();
2112 # ifndef __STL_OLD_ROPE_SEMANTICS
2113 if (__result_pos
== size()) __result_pos
= npos
;
2115 return __result_pos
;
2118 iterator
mutable_begin() {
2119 return(iterator(this, 0));
2122 iterator
mutable_end() {
2123 return(iterator(this, size()));
2126 typedef reverse_iterator
<iterator
> reverse_iterator
;
2128 reverse_iterator
mutable_rbegin() {
2129 return reverse_iterator(mutable_end());
2132 reverse_iterator
mutable_rend() {
2133 return reverse_iterator(mutable_begin());
2136 reference
mutable_reference_at(size_type __pos
) {
2137 return reference(this, __pos
);
2141 reference
operator[] (size_type __pos
) {
2142 return _char_ref_proxy(this, __pos
);
2145 reference
at(size_type __pos
) {
2146 // if (__pos >= size()) throw out_of_range; // XXX
2147 return (*this)[__pos
];
2150 void resize(size_type __n
, _CharT __c
) {}
2151 void resize(size_type __n
) {}
2152 void reserve(size_type __res_arg
= 0) {}
2153 size_type
capacity() const {
2157 // Stuff below this line is dangerous because it's error prone.
2158 // I would really like to get rid of it.
2159 // copy function with funny arg ordering.
2160 size_type
copy(_CharT
* __buffer
, size_type __n
,
2161 size_type __pos
= 0) const {
2162 return copy(__pos
, __n
, __buffer
);
2165 iterator
end() { return mutable_end(); }
2167 iterator
begin() { return mutable_begin(); }
2169 reverse_iterator
rend() { return mutable_rend(); }
2171 reverse_iterator
rbegin() { return mutable_rbegin(); }
2175 const_iterator
end() { return const_end(); }
2177 const_iterator
begin() { return const_begin(); }
2179 const_reverse_iterator
rend() { return const_rend(); }
2181 const_reverse_iterator
rbegin() { return const_rbegin(); }
2187 template <class _CharT
, class _Alloc
>
2188 const rope
<_CharT
, _Alloc
>::size_type rope
<_CharT
, _Alloc
>::npos
=
2191 template <class _CharT
, class _Alloc
>
2192 inline bool operator== (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2193 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2194 return (__x
._M_current_pos
== __y
._M_current_pos
&&
2195 __x
._M_root
== __y
._M_root
);
2198 template <class _CharT
, class _Alloc
>
2199 inline bool operator< (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2200 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2201 return (__x
._M_current_pos
< __y
._M_current_pos
);
2204 template <class _CharT
, class _Alloc
>
2205 inline bool operator!= (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2206 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2207 return !(__x
== __y
);
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
) {
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 !(__y
< __x
);
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
) {
2225 return !(__x
< __y
);
2228 template <class _CharT
, class _Alloc
>
2229 inline ptrdiff_t operator-(const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2230 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2231 return (ptrdiff_t)__x
._M_current_pos
- (ptrdiff_t)__y
._M_current_pos
;
2234 template <class _CharT
, class _Alloc
>
2235 inline _Rope_const_iterator
<_CharT
,_Alloc
>
2236 operator-(const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
, ptrdiff_t __n
) {
2237 return _Rope_const_iterator
<_CharT
,_Alloc
>(
2238 __x
._M_root
, __x
._M_current_pos
- __n
);
2241 template <class _CharT
, class _Alloc
>
2242 inline _Rope_const_iterator
<_CharT
,_Alloc
>
2243 operator+(const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
, ptrdiff_t __n
) {
2244 return _Rope_const_iterator
<_CharT
,_Alloc
>(
2245 __x
._M_root
, __x
._M_current_pos
+ __n
);
2248 template <class _CharT
, class _Alloc
>
2249 inline _Rope_const_iterator
<_CharT
,_Alloc
>
2250 operator+(ptrdiff_t __n
, const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
) {
2251 return _Rope_const_iterator
<_CharT
,_Alloc
>(
2252 __x
._M_root
, __x
._M_current_pos
+ __n
);
2255 template <class _CharT
, class _Alloc
>
2256 inline bool operator== (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2257 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2258 return (__x
._M_current_pos
== __y
._M_current_pos
&&
2259 __x
._M_root_rope
== __y
._M_root_rope
);
2262 template <class _CharT
, class _Alloc
>
2263 inline bool operator< (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2264 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2265 return (__x
._M_current_pos
< __y
._M_current_pos
);
2268 template <class _CharT
, class _Alloc
>
2269 inline bool operator!= (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2270 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2271 return !(__x
== __y
);
2274 template <class _CharT
, class _Alloc
>
2275 inline bool operator> (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2276 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
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 !(__y
< __x
);
2286 template <class _CharT
, class _Alloc
>
2287 inline bool operator>= (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2288 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2289 return !(__x
< __y
);
2292 template <class _CharT
, class _Alloc
>
2293 inline ptrdiff_t operator-(const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2294 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2295 return (ptrdiff_t)__x
._M_current_pos
- (ptrdiff_t)__y
._M_current_pos
;
2298 template <class _CharT
, class _Alloc
>
2299 inline _Rope_iterator
<_CharT
,_Alloc
>
2300 operator-(const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2302 return _Rope_iterator
<_CharT
,_Alloc
>(
2303 __x
._M_root_rope
, __x
._M_current_pos
- __n
);
2306 template <class _CharT
, class _Alloc
>
2307 inline _Rope_iterator
<_CharT
,_Alloc
>
2308 operator+(const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2310 return _Rope_iterator
<_CharT
,_Alloc
>(
2311 __x
._M_root_rope
, __x
._M_current_pos
+ __n
);
2314 template <class _CharT
, class _Alloc
>
2315 inline _Rope_iterator
<_CharT
,_Alloc
>
2316 operator+(ptrdiff_t __n
, const _Rope_iterator
<_CharT
,_Alloc
>& __x
) {
2317 return _Rope_iterator
<_CharT
,_Alloc
>(
2318 __x
._M_root_rope
, __x
._M_current_pos
+ __n
);
2321 template <class _CharT
, class _Alloc
>
2324 operator+ (const rope
<_CharT
,_Alloc
>& __left
,
2325 const rope
<_CharT
,_Alloc
>& __right
)
2327 return rope
<_CharT
,_Alloc
>(
2328 rope
<_CharT
,_Alloc
>::_S_concat(__left
._M_tree_ptr
, __right
._M_tree_ptr
));
2329 // Inlining this should make it possible to keep __left and
2330 // __right in registers.
2333 template <class _CharT
, class _Alloc
>
2335 rope
<_CharT
,_Alloc
>&
2336 operator+= (rope
<_CharT
,_Alloc
>& __left
,
2337 const rope
<_CharT
,_Alloc
>& __right
)
2339 __left
.append(__right
);
2343 template <class _CharT
, class _Alloc
>
2346 operator+ (const rope
<_CharT
,_Alloc
>& __left
,
2347 const _CharT
* __right
) {
2348 size_t __rlen
= rope
<_CharT
,_Alloc
>::_S_char_ptr_len(__right
);
2349 return rope
<_CharT
,_Alloc
>(
2350 rope
<_CharT
,_Alloc
>::_S_concat_char_iter(
2351 __left
._M_tree_ptr
, __right
, __rlen
));
2354 template <class _CharT
, class _Alloc
>
2356 rope
<_CharT
,_Alloc
>&
2357 operator+= (rope
<_CharT
,_Alloc
>& __left
,
2358 const _CharT
* __right
) {
2359 __left
.append(__right
);
2363 template <class _CharT
, class _Alloc
>
2366 operator+ (const rope
<_CharT
,_Alloc
>& __left
, _CharT __right
) {
2367 return rope
<_CharT
,_Alloc
>(
2368 rope
<_CharT
,_Alloc
>::_S_concat_char_iter(
2369 __left
._M_tree_ptr
, &__right
, 1));
2372 template <class _CharT
, class _Alloc
>
2374 rope
<_CharT
,_Alloc
>&
2375 operator+= (rope
<_CharT
,_Alloc
>& __left
, _CharT __right
) {
2376 __left
.append(__right
);
2380 template <class _CharT
, class _Alloc
>
2382 operator< (const rope
<_CharT
,_Alloc
>& __left
,
2383 const rope
<_CharT
,_Alloc
>& __right
) {
2384 return __left
.compare(__right
) < 0;
2387 template <class _CharT
, class _Alloc
>
2389 operator== (const rope
<_CharT
,_Alloc
>& __left
,
2390 const rope
<_CharT
,_Alloc
>& __right
) {
2391 return __left
.compare(__right
) == 0;
2394 template <class _CharT
, class _Alloc
>
2395 inline bool operator== (const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __x
,
2396 const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __y
) {
2397 return (__x
._M_pos
== __y
._M_pos
&& __x
._M_root
== __y
._M_root
);
2400 template <class _CharT
, class _Alloc
>
2402 operator!= (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2403 return !(__x
== __y
);
2406 template <class _CharT
, class _Alloc
>
2408 operator> (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2412 template <class _CharT
, class _Alloc
>
2414 operator<= (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2415 return !(__y
< __x
);
2418 template <class _CharT
, class _Alloc
>
2420 operator>= (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2421 return !(__x
< __y
);
2424 template <class _CharT
, class _Alloc
>
2425 inline bool operator!= (const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __x
,
2426 const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __y
) {
2427 return !(__x
== __y
);
2430 template<class _CharT
, class _Traits
, class _Alloc
>
2431 basic_ostream
<_CharT
, _Traits
>& operator<<
2432 (basic_ostream
<_CharT
, _Traits
>& __o
,
2433 const rope
<_CharT
, _Alloc
>& __r
);
2435 typedef rope
<char> crope
;
2436 typedef rope
<wchar_t> wrope
;
2438 inline crope::reference
__mutable_reference_at(crope
& __c
, size_t __i
)
2440 return __c
.mutable_reference_at(__i
);
2443 inline wrope::reference
__mutable_reference_at(wrope
& __c
, size_t __i
)
2445 return __c
.mutable_reference_at(__i
);
2448 template <class _CharT
, class _Alloc
>
2449 inline void swap(rope
<_CharT
,_Alloc
>& __x
, rope
<_CharT
,_Alloc
>& __y
) {
2453 // Hash functions should probably be revisited later:
2454 template<> struct hash
<crope
>
2456 size_t operator()(const crope
& __str
) const
2458 size_t __size
= __str
.size();
2460 if (0 == __size
) return 0;
2461 return 13*__str
[0] + 5*__str
[__size
- 1] + __size
;
2466 template<> struct hash
<wrope
>
2468 size_t operator()(const wrope
& __str
) const
2470 size_t __size
= __str
.size();
2472 if (0 == __size
) return 0;
2473 return 13*__str
[0] + 5*__str
[__size
- 1] + __size
;
2479 # include <ext/ropeimpl.h>
2481 # endif /* __SGI_STL_INTERNAL_ROPE_H */