1 // SGI's rope implementation -*- C++ -*-
3 // Copyright (C) 2001, 2002 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 /** @file ext/stl_rope.h
44 * This file is a GNU extension to the Standard C++ Library (possibly
45 * containing extensions from the HP/SGI STL subset). You should only
46 * include this header if you are using GCC 3 or later.
49 // rope<_CharT,_Alloc> is a sequence of _CharT.
50 // Ropes appear to be mutable, but update operations
51 // really copy enough of the data structure to leave the original
52 // valid. Thus ropes can be logically copied by just copying
55 #ifndef __SGI_STL_INTERNAL_ROPE_H
56 # define __SGI_STL_INTERNAL_ROPE_H
59 # define __GC_CONST const
61 # include <bits/stl_threads.h>
62 # define __GC_CONST // constant except for deallocation
65 #include <ext/memory> // For uninitialized_copy_n
73 using std::reverse_iterator
;
74 using std::_Alloc_traits
;
76 using std::_Refcount_Base
;
78 // The _S_eos function is used for those functions that
79 // convert to/from C-like strings to detect the end of the string.
81 // The end-of-C-string character.
82 // This is what the draft standard says it should be.
83 template <class _CharT
>
84 inline _CharT
_S_eos(_CharT
*) { return _CharT(); }
86 // Test for basic character types.
87 // For basic character types leaves having a trailing eos.
88 template <class _CharT
>
89 inline bool _S_is_basic_char_type(_CharT
*) { return false; }
90 template <class _CharT
>
91 inline bool _S_is_one_byte_char_type(_CharT
*) { return false; }
93 inline bool _S_is_basic_char_type(char*) { return true; }
94 inline bool _S_is_one_byte_char_type(char*) { return true; }
95 inline bool _S_is_basic_char_type(wchar_t*) { return true; }
97 // Store an eos iff _CharT is a basic character type.
98 // Do not reference _S_eos if it isn't.
99 template <class _CharT
>
100 inline void _S_cond_store_eos(_CharT
&) {}
102 inline void _S_cond_store_eos(char& __c
) { __c
= 0; }
103 inline void _S_cond_store_eos(wchar_t& __c
) { __c
= 0; }
105 // char_producers are logically functions that generate a section of
106 // a string. These can be convereted to ropes. The resulting rope
107 // invokes the char_producer on demand. This allows, for example,
108 // files to be viewed as ropes without reading the entire file.
109 template <class _CharT
>
110 class char_producer
{
112 virtual ~char_producer() {};
113 virtual void operator()(size_t __start_pos
, size_t __len
,
114 _CharT
* __buffer
) = 0;
115 // Buffer should really be an arbitrary output iterator.
116 // That way we could flatten directly into an ostream, etc.
117 // This is thoroughly impossible, since iterator types don't
118 // have runtime descriptions.
123 // Sequence must provide an append operation that appends an
124 // array to the sequence. Sequence buffers are useful only if
125 // appending an entire array is cheaper than appending element by element.
126 // This is true for many string representations.
127 // This should perhaps inherit from ostream<sequence::value_type>
128 // and be implemented correspondingly, so that they can be used
129 // for formatted. For the sake of portability, we don't do this yet.
131 // For now, sequence buffers behave as output iterators. But they also
132 // behave a little like basic_ostringstream<sequence::value_type> and a
133 // little like containers.
135 template<class _Sequence
, size_t _Buf_sz
= 100>
136 class sequence_buffer
: public iterator
<std::output_iterator_tag
,void,void,void,void>
139 typedef typename
_Sequence::value_type value_type
;
141 _Sequence
* _M_prefix
;
142 value_type _M_buffer
[_Buf_sz
];
146 _M_prefix
->append(_M_buffer
, _M_buffer
+ _M_buf_count
);
149 ~sequence_buffer() { flush(); }
150 sequence_buffer() : _M_prefix(0), _M_buf_count(0) {}
151 sequence_buffer(const sequence_buffer
& __x
) {
152 _M_prefix
= __x
._M_prefix
;
153 _M_buf_count
= __x
._M_buf_count
;
154 copy(__x
._M_buffer
, __x
._M_buffer
+ __x
._M_buf_count
, _M_buffer
);
156 sequence_buffer(sequence_buffer
& __x
) {
158 _M_prefix
= __x
._M_prefix
;
161 sequence_buffer(_Sequence
& __s
) : _M_prefix(&__s
), _M_buf_count(0) {}
162 sequence_buffer
& operator= (sequence_buffer
& __x
) {
164 _M_prefix
= __x
._M_prefix
;
168 sequence_buffer
& operator= (const sequence_buffer
& __x
) {
169 _M_prefix
= __x
._M_prefix
;
170 _M_buf_count
= __x
._M_buf_count
;
171 copy(__x
._M_buffer
, __x
._M_buffer
+ __x
._M_buf_count
, _M_buffer
);
174 void push_back(value_type __x
)
176 if (_M_buf_count
< _Buf_sz
) {
177 _M_buffer
[_M_buf_count
] = __x
;
185 void append(value_type
* __s
, size_t __len
)
187 if (__len
+ _M_buf_count
<= _Buf_sz
) {
188 size_t __i
= _M_buf_count
;
190 for (; __j
< __len
; __i
++, __j
++) {
191 _M_buffer
[__i
] = __s
[__j
];
193 _M_buf_count
+= __len
;
194 } else if (0 == _M_buf_count
) {
195 _M_prefix
->append(__s
, __s
+ __len
);
201 sequence_buffer
& write(value_type
* __s
, size_t __len
)
206 sequence_buffer
& put(value_type __x
)
211 sequence_buffer
& operator=(const value_type
& __rhs
)
216 sequence_buffer
& operator*() { return *this; }
217 sequence_buffer
& operator++() { return *this; }
218 sequence_buffer
& operator++(int) { return *this; }
221 // The following should be treated as private, at least for now.
222 template<class _CharT
>
223 class _Rope_char_consumer
{
225 // If we had member templates, these should not be virtual.
226 // For now we need to use run-time parametrization where
227 // compile-time would do. Hence this should all be private
229 // The symmetry with char_producer is accidental and temporary.
230 virtual ~_Rope_char_consumer() {};
231 virtual bool operator()(const _CharT
* __buffer
, size_t __len
) = 0;
234 // First a lot of forward declarations. The standard seems to require
235 // much stricter "declaration before use" than many of the implementations
237 template<class _CharT
, class _Alloc
=allocator
<_CharT
> > class rope
;
238 template<class _CharT
, class _Alloc
> struct _Rope_RopeConcatenation
;
239 template<class _CharT
, class _Alloc
> struct _Rope_RopeLeaf
;
240 template<class _CharT
, class _Alloc
> struct _Rope_RopeFunction
;
241 template<class _CharT
, class _Alloc
> struct _Rope_RopeSubstring
;
242 template<class _CharT
, class _Alloc
> class _Rope_iterator
;
243 template<class _CharT
, class _Alloc
> class _Rope_const_iterator
;
244 template<class _CharT
, class _Alloc
> class _Rope_char_ref_proxy
;
245 template<class _CharT
, class _Alloc
> class _Rope_char_ptr_proxy
;
247 template<class _CharT
, class _Alloc
>
248 bool operator== (const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __x
,
249 const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __y
);
251 template<class _CharT
, class _Alloc
>
252 _Rope_const_iterator
<_CharT
,_Alloc
> operator-
253 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
256 template<class _CharT
, class _Alloc
>
257 _Rope_const_iterator
<_CharT
,_Alloc
> operator+
258 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
261 template<class _CharT
, class _Alloc
>
262 _Rope_const_iterator
<_CharT
,_Alloc
> operator+
264 const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
);
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
>
273 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
274 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
);
276 template<class _CharT
, class _Alloc
>
278 (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
279 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
);
281 template<class _CharT
, class _Alloc
>
282 _Rope_iterator
<_CharT
,_Alloc
> operator-
283 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
286 template<class _CharT
, class _Alloc
>
287 _Rope_iterator
<_CharT
,_Alloc
> operator+
288 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
291 template<class _CharT
, class _Alloc
>
292 _Rope_iterator
<_CharT
,_Alloc
> operator+
294 const _Rope_iterator
<_CharT
,_Alloc
>& __x
);
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
>
303 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
304 const _Rope_iterator
<_CharT
,_Alloc
>& __y
);
306 template<class _CharT
, class _Alloc
>
308 (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
309 const _Rope_iterator
<_CharT
,_Alloc
>& __y
);
311 template<class _CharT
, class _Alloc
>
312 rope
<_CharT
,_Alloc
> operator+ (const rope
<_CharT
,_Alloc
>& __left
,
313 const rope
<_CharT
,_Alloc
>& __right
);
315 template<class _CharT
, class _Alloc
>
316 rope
<_CharT
,_Alloc
> operator+ (const rope
<_CharT
,_Alloc
>& __left
,
317 const _CharT
* __right
);
319 template<class _CharT
, class _Alloc
>
320 rope
<_CharT
,_Alloc
> operator+ (const rope
<_CharT
,_Alloc
>& __left
,
323 // Some helpers, so we can use power on ropes.
324 // See below for why this isn't local to the implementation.
326 // This uses a nonstandard refcount convention.
327 // The result has refcount 0.
328 template<class _CharT
, class _Alloc
>
329 struct _Rope_Concat_fn
330 : public std::binary_function
<rope
<_CharT
,_Alloc
>, rope
<_CharT
,_Alloc
>,
331 rope
<_CharT
,_Alloc
> > {
332 rope
<_CharT
,_Alloc
> operator() (const rope
<_CharT
,_Alloc
>& __x
,
333 const rope
<_CharT
,_Alloc
>& __y
) {
338 template <class _CharT
, class _Alloc
>
341 identity_element(_Rope_Concat_fn
<_CharT
, _Alloc
>)
343 return rope
<_CharT
,_Alloc
>();
348 // What follows should really be local to rope. Unfortunately,
349 // that doesn't work, since it makes it impossible to define generic
350 // equality on rope iterators. According to the draft standard, the
351 // template parameters for such an equality operator cannot be inferred
352 // from the occurrence of a member class as a parameter.
353 // (SGI compilers in fact allow this, but the __result wouldn't be
355 // Similarly, some of the static member functions are member functions
356 // only to avoid polluting the global namespace, and to circumvent
357 // restrictions on type inference for template functions.
361 // The internal data structure for representing a rope. This is
362 // private to the implementation. A rope is really just a pointer
365 // A few basic functions for manipulating this data structure
366 // are members of _RopeRep. Most of the more complex algorithms
367 // are implemented as rope members.
369 // Some of the static member functions of _RopeRep have identically
370 // named functions in rope that simply invoke the _RopeRep versions.
372 // A macro to introduce various allocation and deallocation functions
373 // These need to be defined differently depending on whether or not
374 // we are using standard conforming allocators, and whether the allocator
375 // instances have real state. Thus this macro is invoked repeatedly
376 // with different definitions of __ROPE_DEFINE_ALLOC.
377 // __ROPE_DEFINE_ALLOC(type,name) defines
378 // type * name_allocate(size_t) and
379 // void name_deallocate(tipe *, size_t)
380 // Both functions may or may not be static.
382 #define __ROPE_DEFINE_ALLOCS(__a) \
383 __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \
384 typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
385 __ROPE_DEFINE_ALLOC(__C,_C) \
386 typedef _Rope_RopeLeaf<_CharT,__a> __L; \
387 __ROPE_DEFINE_ALLOC(__L,_L) \
388 typedef _Rope_RopeFunction<_CharT,__a> __F; \
389 __ROPE_DEFINE_ALLOC(__F,_F) \
390 typedef _Rope_RopeSubstring<_CharT,__a> __S; \
391 __ROPE_DEFINE_ALLOC(__S,_S)
393 // Internal rope nodes potentially store a copy of the allocator
394 // instance used to allocate them. This is mostly redundant.
395 // But the alternative would be to pass allocator instances around
396 // in some form to nearly all internal functions, since any pointer
397 // assignment may result in a zero reference count and thus require
399 // The _Rope_rep_base class encapsulates
400 // the differences between SGI-style allocators and standard-conforming
403 #define __STATIC_IF_SGI_ALLOC /* not static */
405 // Base class for ordinary allocators.
406 template <class _CharT
, class _Allocator
, bool _IsStatic
>
407 class _Rope_rep_alloc_base
{
409 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
411 allocator_type
get_allocator() const { return _M_data_allocator
; }
412 _Rope_rep_alloc_base(size_t __size
, const allocator_type
& __a
)
413 : _M_size(__size
), _M_data_allocator(__a
) {}
414 size_t _M_size
; // This is here only to avoid wasting space
415 // for an otherwise empty base class.
419 allocator_type _M_data_allocator
;
421 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
423 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
424 /*static*/ _Tp * __name##_allocate(size_t __n) \
425 { return __name##Allocator(_M_data_allocator).allocate(__n); } \
426 void __name##_deallocate(_Tp* __p, size_t __n) \
427 { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
428 __ROPE_DEFINE_ALLOCS(_Allocator
);
429 # undef __ROPE_DEFINE_ALLOC
432 // Specialization for allocators that have the property that we don't
433 // actually have to store an allocator object.
434 template <class _CharT
, class _Allocator
>
435 class _Rope_rep_alloc_base
<_CharT
,_Allocator
,true> {
437 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
439 allocator_type
get_allocator() const { return allocator_type(); }
440 _Rope_rep_alloc_base(size_t __size
, const allocator_type
&)
446 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
448 _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \
450 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
451 static _Tp* __name##_allocate(size_t __n) \
452 { return __name##Alloc::allocate(__n); } \
453 void __name##_deallocate(_Tp *__p, size_t __n) \
454 { __name##Alloc::deallocate(__p, __n); }
455 __ROPE_DEFINE_ALLOCS(_Allocator
);
456 # undef __ROPE_DEFINE_ALLOC
459 template <class _CharT
, class _Alloc
>
460 struct _Rope_rep_base
461 : public _Rope_rep_alloc_base
<_CharT
,_Alloc
,
462 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
464 typedef _Rope_rep_alloc_base
<_CharT
,_Alloc
,
465 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
467 typedef typename
_Base::allocator_type allocator_type
;
468 _Rope_rep_base(size_t __size
, const allocator_type
& __a
)
469 : _Base(__size
, __a
) {}
473 template<class _CharT
, class _Alloc
>
474 struct _Rope_RopeRep
: public _Rope_rep_base
<_CharT
,_Alloc
>
480 enum { _S_max_rope_depth
= 45 };
481 enum _Tag
{_S_leaf
, _S_concat
, _S_substringfn
, _S_function
};
483 bool _M_is_balanced
:8;
484 unsigned char _M_depth
;
485 __GC_CONST _CharT
* _M_c_string
;
486 /* Flattened version of string, if needed. */
488 /* If it's not 0, then the memory is owned */
490 /* In the case of a leaf, this may point to */
491 /* the same memory as the data field. */
492 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
494 _Rope_RopeRep(_Tag __t
, int __d
, bool __b
, size_t __size
,
496 : _Rope_rep_base
<_CharT
,_Alloc
>(__size
, __a
),
500 _M_tag(__t
), _M_is_balanced(__b
), _M_depth(__d
), _M_c_string(0)
505 static void _S_free_string(__GC_CONST _CharT
*, size_t __len
,
507 # define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
508 // Deallocate data section of a leaf.
509 // This shouldn't be a member function.
510 // But its hard to do anything else at the
511 // moment, because it's templatized w.r.t.
513 // Does nothing if __GC is defined.
515 void _M_free_c_string();
517 // Deallocate t. Assumes t is not 0.
518 void _M_unref_nonnil()
520 if (0 == _M_decr()) _M_free_tree();
526 static void _S_unref(_Rope_RopeRep
* __t
)
529 __t
->_M_unref_nonnil();
532 static void _S_ref(_Rope_RopeRep
* __t
)
534 if (0 != __t
) __t
->_M_incr();
536 static void _S_free_if_unref(_Rope_RopeRep
* __t
)
538 if (0 != __t
&& 0 == __t
->_M_ref_count
) __t
->_M_free_tree();
541 void _M_unref_nonnil() {}
542 void _M_ref_nonnil() {}
543 static void _S_unref(_Rope_RopeRep
*) {}
544 static void _S_ref(_Rope_RopeRep
*) {}
545 static void _S_free_if_unref(_Rope_RopeRep
*) {}
550 template<class _CharT
, class _Alloc
>
551 struct _Rope_RopeLeaf
: public _Rope_RopeRep
<_CharT
,_Alloc
> {
553 // Apparently needed by VC++
554 // The data fields of leaves are allocated with some
555 // extra space, to accommodate future growth and for basic
556 // character types, to hold a trailing eos character.
557 enum { _S_alloc_granularity
= 8 };
558 static size_t _S_rounded_up_size(size_t __n
) {
559 size_t __size_with_eos
;
561 if (_S_is_basic_char_type((_CharT
*)0)) {
562 __size_with_eos
= __n
+ 1;
564 __size_with_eos
= __n
;
567 return __size_with_eos
;
569 // Allow slop for in-place expansion.
570 return (__size_with_eos
+ _S_alloc_granularity
-1)
571 &~ (_S_alloc_granularity
-1);
574 __GC_CONST _CharT
* _M_data
; /* Not necessarily 0 terminated. */
575 /* The allocated size is */
576 /* _S_rounded_up_size(size), except */
577 /* in the GC case, in which it */
578 /* doesn't matter. */
579 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
581 _Rope_RopeLeaf(__GC_CONST _CharT
* __d
, size_t __size
, allocator_type __a
)
582 : _Rope_RopeRep
<_CharT
,_Alloc
>(_S_leaf
, 0, true, __size
, __a
),
585 if (_S_is_basic_char_type((_CharT
*)0)) {
586 // already eos terminated.
590 // The constructor assumes that d has been allocated with
591 // the proper allocator and the properly padded size.
592 // In contrast, the destructor deallocates the data:
595 if (_M_data
!= _M_c_string
) {
598 __STL_FREE_STRING(_M_data
, _M_size
, get_allocator());
603 template<class _CharT
, class _Alloc
>
604 struct _Rope_RopeConcatenation
: public _Rope_RopeRep
<_CharT
,_Alloc
> {
606 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_left
;
607 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_right
;
608 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
610 _Rope_RopeConcatenation(_Rope_RopeRep
<_CharT
,_Alloc
>* __l
,
611 _Rope_RopeRep
<_CharT
,_Alloc
>* __r
,
614 : _Rope_RopeRep
<_CharT
,_Alloc
>(_S_concat
,
615 std::max(__l
->_M_depth
, __r
->_M_depth
) + 1,
617 __l
->_M_size
+ __r
->_M_size
, __a
),
618 _M_left(__l
), _M_right(__r
)
621 ~_Rope_RopeConcatenation() {
623 _M_left
->_M_unref_nonnil();
624 _M_right
->_M_unref_nonnil();
629 template<class _CharT
, class _Alloc
>
630 struct _Rope_RopeFunction
: public _Rope_RopeRep
<_CharT
,_Alloc
> {
632 char_producer
<_CharT
>* _M_fn
;
634 bool _M_delete_when_done
; // Char_producer is owned by the
635 // rope and should be explicitly
636 // deleted when the rope becomes
639 // In the GC case, we either register the rope for
640 // finalization, or not. Thus the field is unnecessary;
641 // the information is stored in the collector data structures.
642 // We do need a finalization procedure to be invoked by the
644 static void _S_fn_finalization_proc(void * __tree
, void *) {
645 delete ((_Rope_RopeFunction
*)__tree
) -> _M_fn
;
648 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
650 _Rope_RopeFunction(char_producer
<_CharT
>* __f
, size_t __size
,
651 bool __d
, allocator_type __a
)
652 : _Rope_RopeRep
<_CharT
,_Alloc
>(_S_function
, 0, true, __size
, __a
)
655 , _M_delete_when_done(__d
)
660 GC_REGISTER_FINALIZER(
661 this, _Rope_RopeFunction::_S_fn_finalization_proc
, 0, 0, 0);
666 ~_Rope_RopeFunction() {
668 if (_M_delete_when_done
) {
674 // Substring results are usually represented using just
675 // concatenation nodes. But in the case of very long flat ropes
676 // or ropes with a functional representation that isn't practical.
677 // In that case, we represent the __result as a special case of
678 // RopeFunction, whose char_producer points back to the rope itself.
679 // In all cases except repeated substring operations and
680 // deallocation, we treat the __result as a RopeFunction.
681 template<class _CharT
, class _Alloc
>
682 struct _Rope_RopeSubstring
: public _Rope_RopeFunction
<_CharT
,_Alloc
>,
683 public char_producer
<_CharT
> {
685 // XXX this whole class should be rewritten.
686 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_base
; // not 0
688 virtual void operator()(size_t __start_pos
, size_t __req_len
,
690 switch(_M_base
->_M_tag
) {
694 char_producer
<_CharT
>* __fn
=
695 ((_Rope_RopeFunction
<_CharT
,_Alloc
>*)_M_base
)->_M_fn
;
696 (*__fn
)(__start_pos
+ _M_start
, __req_len
, __buffer
);
701 __GC_CONST _CharT
* __s
=
702 ((_Rope_RopeLeaf
<_CharT
,_Alloc
>*)_M_base
)->_M_data
;
703 uninitialized_copy_n(__s
+ __start_pos
+ _M_start
, __req_len
,
711 typedef typename _Rope_rep_base
<_CharT
,_Alloc
>::allocator_type
713 _Rope_RopeSubstring(_Rope_RopeRep
<_CharT
,_Alloc
>* __b
, size_t __s
,
714 size_t __l
, allocator_type __a
)
715 : _Rope_RopeFunction
<_CharT
,_Alloc
>(this, __l
, false, __a
),
716 char_producer
<_CharT
>(),
721 _M_base
->_M_ref_nonnil();
723 _M_tag
= _S_substringfn
;
725 virtual ~_Rope_RopeSubstring()
728 _M_base
->_M_unref_nonnil();
729 // _M_free_c_string(); -- done by parent class
735 // Self-destructing pointers to Rope_rep.
736 // These are not conventional smart pointers. Their
737 // only purpose in life is to ensure that unref is called
738 // on the pointer either at normal exit or if an exception
739 // is raised. It is the caller's responsibility to
740 // adjust reference counts when these pointers are initialized
741 // or assigned to. (This convention significantly reduces
742 // the number of potentially expensive reference count
745 template<class _CharT
, class _Alloc
>
746 struct _Rope_self_destruct_ptr
{
747 _Rope_RopeRep
<_CharT
,_Alloc
>* _M_ptr
;
748 ~_Rope_self_destruct_ptr()
749 { _Rope_RopeRep
<_CharT
,_Alloc
>::_S_unref(_M_ptr
); }
751 _Rope_self_destruct_ptr() : _M_ptr(0) {};
753 _Rope_self_destruct_ptr() {};
755 _Rope_self_destruct_ptr(_Rope_RopeRep
<_CharT
,_Alloc
>* __p
) : _M_ptr(__p
) {}
756 _Rope_RopeRep
<_CharT
,_Alloc
>& operator*() { return *_M_ptr
; }
757 _Rope_RopeRep
<_CharT
,_Alloc
>* operator->() { return _M_ptr
; }
758 operator _Rope_RopeRep
<_CharT
,_Alloc
>*() { return _M_ptr
; }
759 _Rope_self_destruct_ptr
& operator= (_Rope_RopeRep
<_CharT
,_Alloc
>* __x
)
760 { _M_ptr
= __x
; return *this; }
764 // Dereferencing a nonconst iterator has to return something
765 // that behaves almost like a reference. It's not possible to
766 // return an actual reference since assignment requires extra
767 // work. And we would get into the same problems as with the
768 // CD2 version of basic_string.
769 template<class _CharT
, class _Alloc
>
770 class _Rope_char_ref_proxy
{
771 friend class rope
<_CharT
,_Alloc
>;
772 friend class _Rope_iterator
<_CharT
,_Alloc
>;
773 friend class _Rope_char_ptr_proxy
<_CharT
,_Alloc
>;
775 typedef _Rope_RopeRep
<_CharT
,_Alloc
>* _Self_destruct_ptr
;
777 typedef _Rope_self_destruct_ptr
<_CharT
,_Alloc
> _Self_destruct_ptr
;
779 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
780 typedef rope
<_CharT
,_Alloc
> _My_rope
;
783 bool _M_current_valid
;
784 _My_rope
* _M_root
; // The whole rope.
786 _Rope_char_ref_proxy(_My_rope
* __r
, size_t __p
)
787 : _M_pos(__p
), _M_current_valid(false), _M_root(__r
) {}
788 _Rope_char_ref_proxy(const _Rope_char_ref_proxy
& __x
)
789 : _M_pos(__x
._M_pos
), _M_current_valid(false), _M_root(__x
._M_root
) {}
790 // Don't preserve cache if the reference can outlive the
791 // expression. We claim that's not possible without calling
792 // a copy constructor or generating reference to a proxy
793 // reference. We declare the latter to have undefined semantics.
794 _Rope_char_ref_proxy(_My_rope
* __r
, size_t __p
, _CharT __c
)
795 : _M_pos(__p
), _M_current(__c
), _M_current_valid(true), _M_root(__r
) {}
796 inline operator _CharT () const;
797 _Rope_char_ref_proxy
& operator= (_CharT __c
);
798 _Rope_char_ptr_proxy
<_CharT
,_Alloc
> operator& () const;
799 _Rope_char_ref_proxy
& operator= (const _Rope_char_ref_proxy
& __c
) {
800 return operator=((_CharT
)__c
);
804 template<class _CharT
, class __Alloc
>
805 inline void swap(_Rope_char_ref_proxy
<_CharT
, __Alloc
> __a
,
806 _Rope_char_ref_proxy
<_CharT
, __Alloc
> __b
) {
812 template<class _CharT
, class _Alloc
>
813 class _Rope_char_ptr_proxy
{
814 // XXX this class should be rewritten.
815 friend class _Rope_char_ref_proxy
<_CharT
,_Alloc
>;
817 rope
<_CharT
,_Alloc
>* _M_root
; // The whole rope.
819 _Rope_char_ptr_proxy(const _Rope_char_ref_proxy
<_CharT
,_Alloc
>& __x
)
820 : _M_pos(__x
._M_pos
), _M_root(__x
._M_root
) {}
821 _Rope_char_ptr_proxy(const _Rope_char_ptr_proxy
& __x
)
822 : _M_pos(__x
._M_pos
), _M_root(__x
._M_root
) {}
823 _Rope_char_ptr_proxy() {}
824 _Rope_char_ptr_proxy(_CharT
* __x
) : _M_root(0), _M_pos(0) {
826 _Rope_char_ptr_proxy
&
827 operator= (const _Rope_char_ptr_proxy
& __x
) {
829 _M_root
= __x
._M_root
;
832 template<class _CharT2
, class _Alloc2
>
833 friend bool operator== (const _Rope_char_ptr_proxy
<_CharT2
,_Alloc2
>& __x
,
834 const _Rope_char_ptr_proxy
<_CharT2
,_Alloc2
>& __y
);
835 _Rope_char_ref_proxy
<_CharT
,_Alloc
> operator*() const {
836 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(_M_root
, _M_pos
);
842 // Unlike in the C version, we cache only part of the stack
843 // for rope iterators, since they must be efficiently copyable.
844 // When we run out of cache, we have to reconstruct the iterator
846 // Pointers from iterators are not included in reference counts.
847 // Iterators are assumed to be thread private. Ropes can
850 template<class _CharT
, class _Alloc
>
851 class _Rope_iterator_base
852 : public iterator
<std::random_access_iterator_tag
, _CharT
>
854 friend class rope
<_CharT
,_Alloc
>;
856 typedef _Alloc _allocator_type
; // used in _Rope_rotate, VC++ workaround
857 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
858 // Borland doesn't want this to be protected.
860 enum { _S_path_cache_len
= 4 }; // Must be <= 9.
861 enum { _S_iterator_buf_len
= 15 };
862 size_t _M_current_pos
;
863 _RopeRep
* _M_root
; // The whole rope.
864 size_t _M_leaf_pos
; // Starting position for current leaf
865 __GC_CONST _CharT
* _M_buf_start
;
867 // containing current char.
868 __GC_CONST _CharT
* _M_buf_ptr
;
869 // Pointer to current char in buffer.
870 // != 0 ==> buffer valid.
871 __GC_CONST _CharT
* _M_buf_end
;
872 // One past __last valid char in buffer.
873 // What follows is the path cache. We go out of our
874 // way to make this compact.
875 // Path_end contains the bottom section of the path from
876 // the root to the current leaf.
877 const _RopeRep
* _M_path_end
[_S_path_cache_len
];
878 int _M_leaf_index
; // Last valid __pos in path_end;
879 // _M_path_end[0] ... _M_path_end[leaf_index-1]
880 // point to concatenation nodes.
881 unsigned char _M_path_directions
;
882 // (path_directions >> __i) & 1 is 1
883 // iff we got from _M_path_end[leaf_index - __i - 1]
884 // to _M_path_end[leaf_index - __i] by going to the
885 // __right. Assumes path_cache_len <= 9.
886 _CharT _M_tmp_buf
[_S_iterator_buf_len
];
887 // Short buffer for surrounding chars.
888 // This is useful primarily for
889 // RopeFunctions. We put the buffer
890 // here to avoid locking in the
891 // multithreaded case.
892 // The cached path is generally assumed to be valid
893 // only if the buffer is valid.
894 static void _S_setbuf(_Rope_iterator_base
& __x
);
895 // Set buffer contents given
897 static void _S_setcache(_Rope_iterator_base
& __x
);
898 // Set buffer contents and
900 static void _S_setcache_for_incr(_Rope_iterator_base
& __x
);
901 // As above, but assumes path
902 // cache is valid for previous posn.
903 _Rope_iterator_base() {}
904 _Rope_iterator_base(_RopeRep
* __root
, size_t __pos
)
905 : _M_current_pos(__pos
), _M_root(__root
), _M_buf_ptr(0) {}
906 void _M_incr(size_t __n
);
907 void _M_decr(size_t __n
);
909 size_t index() const { return _M_current_pos
; }
910 _Rope_iterator_base(const _Rope_iterator_base
& __x
) {
911 if (0 != __x
._M_buf_ptr
) {
914 _M_current_pos
= __x
._M_current_pos
;
915 _M_root
= __x
._M_root
;
921 template<class _CharT
, class _Alloc
> class _Rope_iterator
;
923 template<class _CharT
, class _Alloc
>
924 class _Rope_const_iterator
: public _Rope_iterator_base
<_CharT
,_Alloc
> {
925 friend class rope
<_CharT
,_Alloc
>;
927 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
928 // The one from the base class may not be directly visible.
929 _Rope_const_iterator(const _RopeRep
* __root
, size_t __pos
):
930 _Rope_iterator_base
<_CharT
,_Alloc
>(
931 const_cast<_RopeRep
*>(__root
), __pos
)
932 // Only nonconst iterators modify root ref count
935 typedef _CharT reference
; // Really a value. Returning a reference
936 // Would be a mess, since it would have
937 // to be included in refcount.
938 typedef const _CharT
* pointer
;
941 _Rope_const_iterator() {};
942 _Rope_const_iterator(const _Rope_const_iterator
& __x
) :
943 _Rope_iterator_base
<_CharT
,_Alloc
>(__x
) { }
944 _Rope_const_iterator(const _Rope_iterator
<_CharT
,_Alloc
>& __x
);
945 _Rope_const_iterator(const rope
<_CharT
,_Alloc
>& __r
, size_t __pos
) :
946 _Rope_iterator_base
<_CharT
,_Alloc
>(__r
._M_tree_ptr
, __pos
) {}
947 _Rope_const_iterator
& operator= (const _Rope_const_iterator
& __x
) {
948 if (0 != __x
._M_buf_ptr
) {
949 *(static_cast<_Rope_iterator_base
<_CharT
,_Alloc
>*>(this)) = __x
;
951 _M_current_pos
= __x
._M_current_pos
;
952 _M_root
= __x
._M_root
;
957 reference
operator*() {
958 if (0 == _M_buf_ptr
) _S_setcache(*this);
961 _Rope_const_iterator
& operator++() {
962 __GC_CONST _CharT
* __next
;
963 if (0 != _M_buf_ptr
&& (__next
= _M_buf_ptr
+ 1) < _M_buf_end
) {
971 _Rope_const_iterator
& operator+=(ptrdiff_t __n
) {
979 _Rope_const_iterator
& operator--() {
983 _Rope_const_iterator
& operator-=(ptrdiff_t __n
) {
991 _Rope_const_iterator
operator++(int) {
992 size_t __old_pos
= _M_current_pos
;
994 return _Rope_const_iterator
<_CharT
,_Alloc
>(_M_root
, __old_pos
);
995 // This makes a subsequent dereference expensive.
996 // Perhaps we should instead copy the iterator
997 // if it has a valid cache?
999 _Rope_const_iterator
operator--(int) {
1000 size_t __old_pos
= _M_current_pos
;
1002 return _Rope_const_iterator
<_CharT
,_Alloc
>(_M_root
, __old_pos
);
1004 template<class _CharT2
, class _Alloc2
>
1005 friend _Rope_const_iterator
<_CharT2
,_Alloc2
> operator-
1006 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1008 template<class _CharT2
, class _Alloc2
>
1009 friend _Rope_const_iterator
<_CharT2
,_Alloc2
> operator+
1010 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1012 template<class _CharT2
, class _Alloc2
>
1013 friend _Rope_const_iterator
<_CharT2
,_Alloc2
> operator+
1015 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
);
1016 reference
operator[](size_t __n
) {
1017 return rope
<_CharT
,_Alloc
>::_S_fetch(_M_root
, _M_current_pos
+ __n
);
1020 template<class _CharT2
, class _Alloc2
>
1021 friend bool operator==
1022 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1023 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __y
);
1024 template<class _CharT2
, class _Alloc2
>
1025 friend bool operator<
1026 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1027 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __y
);
1028 template<class _CharT2
, class _Alloc2
>
1029 friend ptrdiff_t operator-
1030 (const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __x
,
1031 const _Rope_const_iterator
<_CharT2
,_Alloc2
>& __y
);
1034 template<class _CharT
, class _Alloc
>
1035 class _Rope_iterator
: public _Rope_iterator_base
<_CharT
,_Alloc
> {
1036 friend class rope
<_CharT
,_Alloc
>;
1038 typedef typename _Rope_iterator_base
<_CharT
,_Alloc
>::_RopeRep _RopeRep
;
1039 rope
<_CharT
,_Alloc
>* _M_root_rope
;
1040 // root is treated as a cached version of this,
1041 // and is used to detect changes to the underlying
1043 // Root is included in the reference count.
1044 // This is necessary so that we can detect changes reliably.
1045 // Unfortunately, it requires careful bookkeeping for the
1047 _Rope_iterator(rope
<_CharT
,_Alloc
>* __r
, size_t __pos
)
1048 : _Rope_iterator_base
<_CharT
,_Alloc
>(__r
->_M_tree_ptr
, __pos
),
1050 { _RopeRep::_S_ref(_M_root
); if (!(__r
-> empty()))_S_setcache(*this); }
1054 typedef _Rope_char_ref_proxy
<_CharT
,_Alloc
> reference
;
1055 typedef _Rope_char_ref_proxy
<_CharT
,_Alloc
>* pointer
;
1058 rope
<_CharT
,_Alloc
>& container() { return *_M_root_rope
; }
1060 _M_root
= 0; // Needed for reference counting.
1062 _Rope_iterator(const _Rope_iterator
& __x
) :
1063 _Rope_iterator_base
<_CharT
,_Alloc
>(__x
) {
1064 _M_root_rope
= __x
._M_root_rope
;
1065 _RopeRep::_S_ref(_M_root
);
1067 _Rope_iterator(rope
<_CharT
,_Alloc
>& __r
, size_t __pos
);
1069 _RopeRep::_S_unref(_M_root
);
1071 _Rope_iterator
& operator= (const _Rope_iterator
& __x
) {
1072 _RopeRep
* __old
= _M_root
;
1074 _RopeRep::_S_ref(__x
._M_root
);
1075 if (0 != __x
._M_buf_ptr
) {
1076 _M_root_rope
= __x
._M_root_rope
;
1077 *(static_cast<_Rope_iterator_base
<_CharT
,_Alloc
>*>(this)) = __x
;
1079 _M_current_pos
= __x
._M_current_pos
;
1080 _M_root
= __x
._M_root
;
1081 _M_root_rope
= __x
._M_root_rope
;
1084 _RopeRep::_S_unref(__old
);
1087 reference
operator*() {
1089 if (0 == _M_buf_ptr
) {
1090 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(
1091 _M_root_rope
, _M_current_pos
);
1093 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(
1094 _M_root_rope
, _M_current_pos
, *_M_buf_ptr
);
1097 _Rope_iterator
& operator++() {
1101 _Rope_iterator
& operator+=(ptrdiff_t __n
) {
1109 _Rope_iterator
& operator--() {
1113 _Rope_iterator
& operator-=(ptrdiff_t __n
) {
1121 _Rope_iterator
operator++(int) {
1122 size_t __old_pos
= _M_current_pos
;
1124 return _Rope_iterator
<_CharT
,_Alloc
>(_M_root_rope
, __old_pos
);
1126 _Rope_iterator
operator--(int) {
1127 size_t __old_pos
= _M_current_pos
;
1129 return _Rope_iterator
<_CharT
,_Alloc
>(_M_root_rope
, __old_pos
);
1131 reference
operator[](ptrdiff_t __n
) {
1132 return _Rope_char_ref_proxy
<_CharT
,_Alloc
>(
1133 _M_root_rope
, _M_current_pos
+ __n
);
1136 template<class _CharT2
, class _Alloc2
>
1137 friend bool operator==
1138 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1139 const _Rope_iterator
<_CharT2
,_Alloc2
>& __y
);
1140 template<class _CharT2
, class _Alloc2
>
1141 friend bool operator<
1142 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1143 const _Rope_iterator
<_CharT2
,_Alloc2
>& __y
);
1144 template<class _CharT2
, class _Alloc2
>
1145 friend ptrdiff_t operator-
1146 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1147 const _Rope_iterator
<_CharT2
,_Alloc2
>& __y
);
1148 template<class _CharT2
, class _Alloc2
>
1149 friend _Rope_iterator
<_CharT2
,_Alloc2
> operator-
1150 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1152 template<class _CharT2
, class _Alloc2
>
1153 friend _Rope_iterator
<_CharT2
,_Alloc2
> operator+
1154 (const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
,
1156 template<class _CharT2
, class _Alloc2
>
1157 friend _Rope_iterator
<_CharT2
,_Alloc2
> operator+
1159 const _Rope_iterator
<_CharT2
,_Alloc2
>& __x
);
1162 // The rope base class encapsulates
1163 // the differences between SGI-style allocators and standard-conforming
1166 // Base class for ordinary allocators.
1167 template <class _CharT
, class _Allocator
, bool _IsStatic
>
1168 class _Rope_alloc_base
{
1170 typedef _Rope_RopeRep
<_CharT
,_Allocator
> _RopeRep
;
1171 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
1173 allocator_type
get_allocator() const { return _M_data_allocator
; }
1174 _Rope_alloc_base(_RopeRep
*__t
, const allocator_type
& __a
)
1175 : _M_tree_ptr(__t
), _M_data_allocator(__a
) {}
1176 _Rope_alloc_base(const allocator_type
& __a
)
1177 : _M_data_allocator(__a
) {}
1180 // The only data members of a rope:
1181 allocator_type _M_data_allocator
;
1182 _RopeRep
* _M_tree_ptr
;
1184 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
1186 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
1187 _Tp* __name##_allocate(size_t __n) const \
1188 { return __name##Allocator(_M_data_allocator).allocate(__n); } \
1189 void __name##_deallocate(_Tp *__p, size_t __n) const \
1190 { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
1191 __ROPE_DEFINE_ALLOCS(_Allocator
)
1192 # undef __ROPE_DEFINE_ALLOC
1195 // Specialization for allocators that have the property that we don't
1196 // actually have to store an allocator object.
1197 template <class _CharT
, class _Allocator
>
1198 class _Rope_alloc_base
<_CharT
,_Allocator
,true> {
1200 typedef _Rope_RopeRep
<_CharT
,_Allocator
> _RopeRep
;
1201 typedef typename _Alloc_traits
<_CharT
,_Allocator
>::allocator_type
1203 allocator_type
get_allocator() const { return allocator_type(); }
1204 _Rope_alloc_base(_RopeRep
*__t
, const allocator_type
&)
1205 : _M_tree_ptr(__t
) {}
1206 _Rope_alloc_base(const allocator_type
&) {}
1209 // The only data member of a rope:
1210 _RopeRep
*_M_tree_ptr
;
1212 # define __ROPE_DEFINE_ALLOC(_Tp, __name) \
1214 _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \
1216 _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
1217 static _Tp* __name##_allocate(size_t __n) \
1218 { return __name##Alloc::allocate(__n); } \
1219 static void __name##_deallocate(_Tp *__p, size_t __n) \
1220 { __name##Alloc::deallocate(__p, __n); }
1221 __ROPE_DEFINE_ALLOCS(_Allocator
)
1222 # undef __ROPE_DEFINE_ALLOC
1225 template <class _CharT
, class _Alloc
>
1227 : public _Rope_alloc_base
<_CharT
,_Alloc
,
1228 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
1230 typedef _Rope_alloc_base
<_CharT
,_Alloc
,
1231 _Alloc_traits
<_CharT
,_Alloc
>::_S_instanceless
>
1233 typedef typename
_Base::allocator_type allocator_type
;
1234 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
1235 // The one in _Base may not be visible due to template rules.
1236 _Rope_base(_RopeRep
* __t
, const allocator_type
& __a
) : _Base(__t
, __a
) {}
1237 _Rope_base(const allocator_type
& __a
) : _Base(__a
) {}
1242 * This is an SGI extension.
1243 * @ingroup SGIextensions
1246 template <class _CharT
, class _Alloc
>
1247 class rope
: public _Rope_base
<_CharT
,_Alloc
> {
1249 typedef _CharT value_type
;
1250 typedef ptrdiff_t difference_type
;
1251 typedef size_t size_type
;
1252 typedef _CharT const_reference
;
1253 typedef const _CharT
* const_pointer
;
1254 typedef _Rope_iterator
<_CharT
,_Alloc
> iterator
;
1255 typedef _Rope_const_iterator
<_CharT
,_Alloc
> const_iterator
;
1256 typedef _Rope_char_ref_proxy
<_CharT
,_Alloc
> reference
;
1257 typedef _Rope_char_ptr_proxy
<_CharT
,_Alloc
> pointer
;
1259 friend class _Rope_iterator
<_CharT
,_Alloc
>;
1260 friend class _Rope_const_iterator
<_CharT
,_Alloc
>;
1261 friend struct _Rope_RopeRep
<_CharT
,_Alloc
>;
1262 friend class _Rope_iterator_base
<_CharT
,_Alloc
>;
1263 friend class _Rope_char_ptr_proxy
<_CharT
,_Alloc
>;
1264 friend class _Rope_char_ref_proxy
<_CharT
,_Alloc
>;
1265 friend struct _Rope_RopeSubstring
<_CharT
,_Alloc
>;
1268 typedef _Rope_base
<_CharT
,_Alloc
> _Base
;
1269 typedef typename
_Base::allocator_type allocator_type
;
1270 using _Base::_M_tree_ptr
;
1271 typedef __GC_CONST _CharT
* _Cstrptr
;
1273 static _CharT _S_empty_c_str
[1];
1275 static bool _S_is0(_CharT __c
) { return __c
== _S_eos((_CharT
*)0); }
1276 enum { _S_copy_max
= 23 };
1277 // For strings shorter than _S_copy_max, we copy to
1280 typedef _Rope_RopeRep
<_CharT
,_Alloc
> _RopeRep
;
1281 typedef _Rope_RopeConcatenation
<_CharT
,_Alloc
> _RopeConcatenation
;
1282 typedef _Rope_RopeLeaf
<_CharT
,_Alloc
> _RopeLeaf
;
1283 typedef _Rope_RopeFunction
<_CharT
,_Alloc
> _RopeFunction
;
1284 typedef _Rope_RopeSubstring
<_CharT
,_Alloc
> _RopeSubstring
;
1286 // Retrieve a character at the indicated position.
1287 static _CharT
_S_fetch(_RopeRep
* __r
, size_type __pos
);
1290 // Obtain a pointer to the character at the indicated position.
1291 // The pointer can be used to change the character.
1292 // If such a pointer cannot be produced, as is frequently the
1293 // case, 0 is returned instead.
1294 // (Returns nonzero only if all nodes in the path have a refcount
1296 static _CharT
* _S_fetch_ptr(_RopeRep
* __r
, size_type __pos
);
1299 static bool _S_apply_to_pieces(
1300 // should be template parameter
1301 _Rope_char_consumer
<_CharT
>& __c
,
1302 const _RopeRep
* __r
,
1303 size_t __begin
, size_t __end
);
1304 // begin and end are assumed to be in range.
1307 static void _S_unref(_RopeRep
* __t
)
1309 _RopeRep::_S_unref(__t
);
1311 static void _S_ref(_RopeRep
* __t
)
1313 _RopeRep::_S_ref(__t
);
1316 static void _S_unref(_RopeRep
*) {}
1317 static void _S_ref(_RopeRep
*) {}
1322 typedef _Rope_RopeRep
<_CharT
,_Alloc
>* _Self_destruct_ptr
;
1324 typedef _Rope_self_destruct_ptr
<_CharT
,_Alloc
> _Self_destruct_ptr
;
1327 // _Result is counted in refcount.
1328 static _RopeRep
* _S_substring(_RopeRep
* __base
,
1329 size_t __start
, size_t __endp1
);
1331 static _RopeRep
* _S_concat_char_iter(_RopeRep
* __r
,
1332 const _CharT
* __iter
, size_t __slen
);
1333 // Concatenate rope and char ptr, copying __s.
1334 // Should really take an arbitrary iterator.
1335 // Result is counted in refcount.
1336 static _RopeRep
* _S_destr_concat_char_iter(_RopeRep
* __r
,
1337 const _CharT
* __iter
, size_t __slen
)
1338 // As above, but one reference to __r is about to be
1339 // destroyed. Thus the pieces may be recycled if all
1340 // relevant reference counts are 1.
1342 // We can't really do anything since refcounts are unavailable.
1343 { return _S_concat_char_iter(__r
, __iter
, __slen
); }
1348 static _RopeRep
* _S_concat(_RopeRep
* __left
, _RopeRep
* __right
);
1349 // General concatenation on _RopeRep. _Result
1350 // has refcount of 1. Adjusts argument refcounts.
1353 void apply_to_pieces( size_t __begin
, size_t __end
,
1354 _Rope_char_consumer
<_CharT
>& __c
) const {
1355 _S_apply_to_pieces(__c
, _M_tree_ptr
, __begin
, __end
);
1361 static size_t _S_rounded_up_size(size_t __n
) {
1362 return _RopeLeaf::_S_rounded_up_size(__n
);
1365 static size_t _S_allocated_capacity(size_t __n
) {
1366 if (_S_is_basic_char_type((_CharT
*)0)) {
1367 return _S_rounded_up_size(__n
) - 1;
1369 return _S_rounded_up_size(__n
);
1373 // Allocate and construct a RopeLeaf using the supplied allocator
1374 // Takes ownership of s instead of copying.
1375 static _RopeLeaf
* _S_new_RopeLeaf(__GC_CONST _CharT
*__s
,
1376 size_t __size
, allocator_type __a
)
1378 _RopeLeaf
* __space
= _LAllocator(__a
).allocate(1);
1379 return new(__space
) _RopeLeaf(__s
, __size
, __a
);
1382 static _RopeConcatenation
* _S_new_RopeConcatenation(
1383 _RopeRep
* __left
, _RopeRep
* __right
,
1386 _RopeConcatenation
* __space
= _CAllocator(__a
).allocate(1);
1387 return new(__space
) _RopeConcatenation(__left
, __right
, __a
);
1390 static _RopeFunction
* _S_new_RopeFunction(char_producer
<_CharT
>* __f
,
1391 size_t __size
, bool __d
, allocator_type __a
)
1393 _RopeFunction
* __space
= _FAllocator(__a
).allocate(1);
1394 return new(__space
) _RopeFunction(__f
, __size
, __d
, __a
);
1397 static _RopeSubstring
* _S_new_RopeSubstring(
1398 _Rope_RopeRep
<_CharT
,_Alloc
>* __b
, size_t __s
,
1399 size_t __l
, allocator_type __a
)
1401 _RopeSubstring
* __space
= _SAllocator(__a
).allocate(1);
1402 return new(__space
) _RopeSubstring(__b
, __s
, __l
, __a
);
1406 _RopeLeaf
* _S_RopeLeaf_from_unowned_char_ptr(const _CharT
*__s
,
1407 size_t __size
, allocator_type __a
)
1408 # define __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __size, __a) \
1409 _S_RopeLeaf_from_unowned_char_ptr(__s, __size, __a)
1411 if (0 == __size
) return 0;
1412 _CharT
* __buf
= __a
.allocate(_S_rounded_up_size(__size
));
1414 uninitialized_copy_n(__s
, __size
, __buf
);
1415 _S_cond_store_eos(__buf
[__size
]);
1417 return _S_new_RopeLeaf(__buf
, __size
, __a
);
1421 _RopeRep::__STL_FREE_STRING(__buf
, __size
, __a
);
1422 __throw_exception_again
;
1427 // Concatenation of nonempty strings.
1428 // Always builds a concatenation node.
1429 // Rebalances if the result is too deep.
1430 // Result has refcount 1.
1431 // Does not increment left and right ref counts even though
1432 // they are referenced.
1434 _S_tree_concat(_RopeRep
* __left
, _RopeRep
* __right
);
1436 // Concatenation helper functions
1438 _S_leaf_concat_char_iter(_RopeLeaf
* __r
,
1439 const _CharT
* __iter
, size_t __slen
);
1440 // Concatenate by copying leaf.
1441 // should take an arbitrary iterator
1442 // result has refcount 1.
1444 static _RopeLeaf
* _S_destr_leaf_concat_char_iter
1445 (_RopeLeaf
* __r
, const _CharT
* __iter
, size_t __slen
);
1446 // A version that potentially clobbers __r if __r->_M_ref_count == 1.
1451 static size_t _S_char_ptr_len(const _CharT
* __s
);
1452 // slightly generalized strlen
1454 rope(_RopeRep
* __t
, const allocator_type
& __a
= allocator_type())
1455 : _Base(__t
,__a
) { }
1458 // Copy __r to the _CharT buffer.
1459 // Returns __buffer + __r->_M_size.
1460 // Assumes that buffer is uninitialized.
1461 static _CharT
* _S_flatten(_RopeRep
* __r
, _CharT
* __buffer
);
1463 // Again, with explicit starting position and length.
1464 // Assumes that buffer is uninitialized.
1465 static _CharT
* _S_flatten(_RopeRep
* __r
,
1466 size_t __start
, size_t __len
,
1469 static const unsigned long
1470 _S_min_len
[_RopeRep::_S_max_rope_depth
+ 1];
1472 static bool _S_is_balanced(_RopeRep
* __r
)
1473 { return (__r
->_M_size
>= _S_min_len
[__r
->_M_depth
]); }
1475 static bool _S_is_almost_balanced(_RopeRep
* __r
)
1476 { return (__r
->_M_depth
== 0 ||
1477 __r
->_M_size
>= _S_min_len
[__r
->_M_depth
- 1]); }
1479 static bool _S_is_roughly_balanced(_RopeRep
* __r
)
1480 { return (__r
->_M_depth
<= 1 ||
1481 __r
->_M_size
>= _S_min_len
[__r
->_M_depth
- 2]); }
1483 // Assumes the result is not empty.
1484 static _RopeRep
* _S_concat_and_set_balanced(_RopeRep
* __left
,
1487 _RopeRep
* __result
= _S_concat(__left
, __right
);
1488 if (_S_is_balanced(__result
)) __result
->_M_is_balanced
= true;
1492 // The basic rebalancing operation. Logically copies the
1493 // rope. The result has refcount of 1. The client will
1494 // usually decrement the reference count of __r.
1495 // The result is within height 2 of balanced by the above
1497 static _RopeRep
* _S_balance(_RopeRep
* __r
);
1499 // Add all unbalanced subtrees to the forest of balanceed trees.
1500 // Used only by balance.
1501 static void _S_add_to_forest(_RopeRep
*__r
, _RopeRep
** __forest
);
1503 // Add __r to forest, assuming __r is already balanced.
1504 static void _S_add_leaf_to_forest(_RopeRep
* __r
, _RopeRep
** __forest
);
1506 // Print to stdout, exposing structure
1507 static void _S_dump(_RopeRep
* __r
, int __indent
= 0);
1509 // Return -1, 0, or 1 if __x < __y, __x == __y, or __x > __y resp.
1510 static int _S_compare(const _RopeRep
* __x
, const _RopeRep
* __y
);
1513 bool empty() const { return 0 == _M_tree_ptr
; }
1515 // Comparison member function. This is public only for those
1516 // clients that need a ternary comparison. Others
1517 // should use the comparison operators below.
1518 int compare(const rope
& __y
) const {
1519 return _S_compare(_M_tree_ptr
, __y
._M_tree_ptr
);
1522 rope(const _CharT
* __s
, const allocator_type
& __a
= allocator_type())
1523 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, _S_char_ptr_len(__s
),
1527 rope(const _CharT
* __s
, size_t __len
,
1528 const allocator_type
& __a
= allocator_type())
1529 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __len
, __a
), __a
)
1532 // Should perhaps be templatized with respect to the iterator type
1533 // and use Sequence_buffer. (It should perhaps use sequence_buffer
1535 rope(const _CharT
*__s
, const _CharT
*__e
,
1536 const allocator_type
& __a
= allocator_type())
1537 : _Base(__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s
, __e
- __s
, __a
), __a
)
1540 rope(const const_iterator
& __s
, const 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(const iterator
& __s
, const iterator
& __e
,
1547 const allocator_type
& __a
= allocator_type())
1548 : _Base(_S_substring(__s
._M_root
, __s
._M_current_pos
,
1549 __e
._M_current_pos
), __a
)
1552 rope(_CharT __c
, const allocator_type
& __a
= allocator_type())
1555 _CharT
* __buf
= _Data_allocate(_S_rounded_up_size(1));
1557 std::_Construct(__buf
, __c
);
1559 _M_tree_ptr
= _S_new_RopeLeaf(__buf
, 1, __a
);
1563 _RopeRep::__STL_FREE_STRING(__buf
, 1, __a
);
1564 __throw_exception_again
;
1568 rope(size_t __n
, _CharT __c
,
1569 const allocator_type
& __a
= allocator_type());
1571 rope(const allocator_type
& __a
= allocator_type())
1574 // Construct a rope from a function that can compute its members
1575 rope(char_producer
<_CharT
> *__fn
, size_t __len
, bool __delete_fn
,
1576 const allocator_type
& __a
= allocator_type())
1579 _M_tree_ptr
= (0 == __len
) ?
1580 0 : _S_new_RopeFunction(__fn
, __len
, __delete_fn
, __a
);
1583 rope(const rope
& __x
, const allocator_type
& __a
= allocator_type())
1584 : _Base(__x
._M_tree_ptr
, __a
)
1586 _S_ref(_M_tree_ptr
);
1591 _S_unref(_M_tree_ptr
);
1594 rope
& operator=(const rope
& __x
)
1596 _RopeRep
* __old
= _M_tree_ptr
;
1597 _M_tree_ptr
= __x
._M_tree_ptr
;
1598 _S_ref(_M_tree_ptr
);
1605 _S_unref(_M_tree_ptr
);
1609 void push_back(_CharT __x
)
1611 _RopeRep
* __old
= _M_tree_ptr
;
1612 _M_tree_ptr
= _S_destr_concat_char_iter(_M_tree_ptr
, &__x
, 1);
1618 _RopeRep
* __old
= _M_tree_ptr
;
1620 _S_substring(_M_tree_ptr
, 0, _M_tree_ptr
->_M_size
- 1);
1626 return _S_fetch(_M_tree_ptr
, _M_tree_ptr
->_M_size
- 1);
1629 void push_front(_CharT __x
)
1631 _RopeRep
* __old
= _M_tree_ptr
;
1633 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(&__x
, 1, get_allocator());
1635 _M_tree_ptr
= _S_concat(__left
, _M_tree_ptr
);
1642 __throw_exception_again
;
1648 _RopeRep
* __old
= _M_tree_ptr
;
1649 _M_tree_ptr
= _S_substring(_M_tree_ptr
, 1, _M_tree_ptr
->_M_size
);
1653 _CharT
front() const
1655 return _S_fetch(_M_tree_ptr
, 0);
1660 _RopeRep
* __old
= _M_tree_ptr
;
1661 _M_tree_ptr
= _S_balance(_M_tree_ptr
);
1665 void copy(_CharT
* __buffer
) const {
1666 _Destroy(__buffer
, __buffer
+ size());
1667 _S_flatten(_M_tree_ptr
, __buffer
);
1670 // This is the copy function from the standard, but
1671 // with the arguments reordered to make it consistent with the
1672 // rest of the interface.
1673 // Note that this guaranteed not to compile if the draft standard
1674 // order is assumed.
1675 size_type
copy(size_type __pos
, size_type __n
, _CharT
* __buffer
) const
1677 size_t __size
= size();
1678 size_t __len
= (__pos
+ __n
> __size
? __size
- __pos
: __n
);
1680 _Destroy(__buffer
, __buffer
+ __len
);
1681 _S_flatten(_M_tree_ptr
, __pos
, __len
, __buffer
);
1685 // Print to stdout, exposing structure. May be useful for
1686 // performance debugging.
1688 _S_dump(_M_tree_ptr
);
1691 // Convert to 0 terminated string in new allocated memory.
1692 // Embedded 0s in the input do not terminate the copy.
1693 const _CharT
* c_str() const;
1695 // As above, but lso use the flattened representation as the
1696 // the new rope representation.
1697 const _CharT
* replace_with_c_str();
1699 // Reclaim memory for the c_str generated flattened string.
1700 // Intentionally undocumented, since it's hard to say when this
1701 // is safe for multiple threads.
1702 void delete_c_str () {
1703 if (0 == _M_tree_ptr
) return;
1704 if (_RopeRep::_S_leaf
== _M_tree_ptr
->_M_tag
&&
1705 ((_RopeLeaf
*)_M_tree_ptr
)->_M_data
==
1706 _M_tree_ptr
->_M_c_string
) {
1707 // Representation shared
1711 _M_tree_ptr
->_M_free_c_string();
1713 _M_tree_ptr
->_M_c_string
= 0;
1716 _CharT
operator[] (size_type __pos
) const {
1717 return _S_fetch(_M_tree_ptr
, __pos
);
1720 _CharT
at(size_type __pos
) const {
1721 // if (__pos >= size()) throw out_of_range; // XXX
1722 return (*this)[__pos
];
1725 const_iterator
begin() const {
1726 return(const_iterator(_M_tree_ptr
, 0));
1729 // An easy way to get a const iterator from a non-const container.
1730 const_iterator
const_begin() const {
1731 return(const_iterator(_M_tree_ptr
, 0));
1734 const_iterator
end() const {
1735 return(const_iterator(_M_tree_ptr
, size()));
1738 const_iterator
const_end() const {
1739 return(const_iterator(_M_tree_ptr
, size()));
1742 size_type
size() const {
1743 return(0 == _M_tree_ptr
? 0 : _M_tree_ptr
->_M_size
);
1746 size_type
length() const {
1750 size_type
max_size() const {
1751 return _S_min_len
[_RopeRep::_S_max_rope_depth
-1] - 1;
1752 // Guarantees that the result can be sufficirntly
1753 // balanced. Longer ropes will probably still work,
1754 // but it's harder to make guarantees.
1757 typedef reverse_iterator
<const_iterator
> const_reverse_iterator
;
1759 const_reverse_iterator
rbegin() const {
1760 return const_reverse_iterator(end());
1763 const_reverse_iterator
const_rbegin() const {
1764 return const_reverse_iterator(end());
1767 const_reverse_iterator
rend() const {
1768 return const_reverse_iterator(begin());
1771 const_reverse_iterator
const_rend() const {
1772 return const_reverse_iterator(begin());
1775 template<class _CharT2
, class _Alloc2
>
1776 friend rope
<_CharT2
,_Alloc2
>
1777 operator+ (const rope
<_CharT2
,_Alloc2
>& __left
,
1778 const rope
<_CharT2
,_Alloc2
>& __right
);
1780 template<class _CharT2
, class _Alloc2
>
1781 friend rope
<_CharT2
,_Alloc2
>
1782 operator+ (const rope
<_CharT2
,_Alloc2
>& __left
,
1783 const _CharT2
* __right
);
1785 template<class _CharT2
, class _Alloc2
>
1786 friend rope
<_CharT2
,_Alloc2
>
1787 operator+ (const rope
<_CharT2
,_Alloc2
>& __left
, _CharT2 __right
);
1788 // The symmetric cases are intentionally omitted, since they're presumed
1789 // to be less common, and we don't handle them as well.
1791 // The following should really be templatized.
1792 // The first argument should be an input iterator or
1793 // forward iterator with value_type _CharT.
1794 rope
& append(const _CharT
* __iter
, size_t __n
) {
1795 _RopeRep
* __result
=
1796 _S_destr_concat_char_iter(_M_tree_ptr
, __iter
, __n
);
1797 _S_unref(_M_tree_ptr
);
1798 _M_tree_ptr
= __result
;
1802 rope
& append(const _CharT
* __c_string
) {
1803 size_t __len
= _S_char_ptr_len(__c_string
);
1804 append(__c_string
, __len
);
1808 rope
& append(const _CharT
* __s
, const _CharT
* __e
) {
1809 _RopeRep
* __result
=
1810 _S_destr_concat_char_iter(_M_tree_ptr
, __s
, __e
- __s
);
1811 _S_unref(_M_tree_ptr
);
1812 _M_tree_ptr
= __result
;
1816 rope
& append(const_iterator __s
, const_iterator __e
) {
1817 _Self_destruct_ptr
__appendee(_S_substring(
1818 __s
._M_root
, __s
._M_current_pos
, __e
._M_current_pos
));
1819 _RopeRep
* __result
=
1820 _S_concat(_M_tree_ptr
, (_RopeRep
*)__appendee
);
1821 _S_unref(_M_tree_ptr
);
1822 _M_tree_ptr
= __result
;
1826 rope
& append(_CharT __c
) {
1827 _RopeRep
* __result
=
1828 _S_destr_concat_char_iter(_M_tree_ptr
, &__c
, 1);
1829 _S_unref(_M_tree_ptr
);
1830 _M_tree_ptr
= __result
;
1834 rope
& append() { return append(_CharT()); } // XXX why?
1836 rope
& append(const rope
& __y
) {
1837 _RopeRep
* __result
= _S_concat(_M_tree_ptr
, __y
._M_tree_ptr
);
1838 _S_unref(_M_tree_ptr
);
1839 _M_tree_ptr
= __result
;
1843 rope
& append(size_t __n
, _CharT __c
) {
1844 rope
<_CharT
,_Alloc
> __last(__n
, __c
);
1845 return append(__last
);
1848 void swap(rope
& __b
) {
1849 _RopeRep
* __tmp
= _M_tree_ptr
;
1850 _M_tree_ptr
= __b
._M_tree_ptr
;
1851 __b
._M_tree_ptr
= __tmp
;
1856 // Result is included in refcount.
1857 static _RopeRep
* replace(_RopeRep
* __old
, size_t __pos1
,
1858 size_t __pos2
, _RopeRep
* __r
) {
1859 if (0 == __old
) { _S_ref(__r
); return __r
; }
1860 _Self_destruct_ptr
__left(
1861 _S_substring(__old
, 0, __pos1
));
1862 _Self_destruct_ptr
__right(
1863 _S_substring(__old
, __pos2
, __old
->_M_size
));
1867 __result
= _S_concat(__left
, __right
);
1869 _Self_destruct_ptr
__left_result(_S_concat(__left
, __r
));
1870 __result
= _S_concat(__left_result
, __right
);
1876 void insert(size_t __p
, const rope
& __r
) {
1877 _RopeRep
* __result
=
1878 replace(_M_tree_ptr
, __p
, __p
, __r
._M_tree_ptr
);
1879 _S_unref(_M_tree_ptr
);
1880 _M_tree_ptr
= __result
;
1883 void insert(size_t __p
, size_t __n
, _CharT __c
) {
1884 rope
<_CharT
,_Alloc
> __r(__n
,__c
);
1888 void insert(size_t __p
, const _CharT
* __i
, size_t __n
) {
1889 _Self_destruct_ptr
__left(_S_substring(_M_tree_ptr
, 0, __p
));
1890 _Self_destruct_ptr
__right(_S_substring(_M_tree_ptr
, __p
, size()));
1891 _Self_destruct_ptr
__left_result(
1892 _S_concat_char_iter(__left
, __i
, __n
));
1893 // _S_ destr_concat_char_iter should be safe here.
1894 // But as it stands it's probably not a win, since __left
1895 // is likely to have additional references.
1896 _RopeRep
* __result
= _S_concat(__left_result
, __right
);
1897 _S_unref(_M_tree_ptr
);
1898 _M_tree_ptr
= __result
;
1901 void insert(size_t __p
, const _CharT
* __c_string
) {
1902 insert(__p
, __c_string
, _S_char_ptr_len(__c_string
));
1905 void insert(size_t __p
, _CharT __c
) {
1906 insert(__p
, &__c
, 1);
1909 void insert(size_t __p
) {
1910 _CharT __c
= _CharT();
1911 insert(__p
, &__c
, 1);
1914 void insert(size_t __p
, const _CharT
* __i
, const _CharT
* __j
) {
1919 void insert(size_t __p
, const const_iterator
& __i
,
1920 const const_iterator
& __j
) {
1925 void insert(size_t __p
, const iterator
& __i
,
1926 const iterator
& __j
) {
1931 // (position, length) versions of replace operations:
1933 void replace(size_t __p
, size_t __n
, const rope
& __r
) {
1934 _RopeRep
* __result
=
1935 replace(_M_tree_ptr
, __p
, __p
+ __n
, __r
._M_tree_ptr
);
1936 _S_unref(_M_tree_ptr
);
1937 _M_tree_ptr
= __result
;
1940 void replace(size_t __p
, size_t __n
,
1941 const _CharT
* __i
, size_t __i_len
) {
1942 rope
__r(__i
, __i_len
);
1943 replace(__p
, __n
, __r
);
1946 void replace(size_t __p
, size_t __n
, _CharT __c
) {
1948 replace(__p
, __n
, __r
);
1951 void replace(size_t __p
, size_t __n
, const _CharT
* __c_string
) {
1952 rope
__r(__c_string
);
1953 replace(__p
, __n
, __r
);
1956 void replace(size_t __p
, size_t __n
,
1957 const _CharT
* __i
, const _CharT
* __j
) {
1959 replace(__p
, __n
, __r
);
1962 void replace(size_t __p
, size_t __n
,
1963 const const_iterator
& __i
, const const_iterator
& __j
) {
1965 replace(__p
, __n
, __r
);
1968 void replace(size_t __p
, size_t __n
,
1969 const iterator
& __i
, const iterator
& __j
) {
1971 replace(__p
, __n
, __r
);
1974 // Single character variants:
1975 void replace(size_t __p
, _CharT __c
) {
1976 iterator
__i(this, __p
);
1980 void replace(size_t __p
, const rope
& __r
) {
1981 replace(__p
, 1, __r
);
1984 void replace(size_t __p
, const _CharT
* __i
, size_t __i_len
) {
1985 replace(__p
, 1, __i
, __i_len
);
1988 void replace(size_t __p
, const _CharT
* __c_string
) {
1989 replace(__p
, 1, __c_string
);
1992 void replace(size_t __p
, const _CharT
* __i
, const _CharT
* __j
) {
1993 replace(__p
, 1, __i
, __j
);
1996 void replace(size_t __p
, const const_iterator
& __i
,
1997 const const_iterator
& __j
) {
1998 replace(__p
, 1, __i
, __j
);
2001 void replace(size_t __p
, const iterator
& __i
,
2002 const iterator
& __j
) {
2003 replace(__p
, 1, __i
, __j
);
2006 // Erase, (position, size) variant.
2007 void erase(size_t __p
, size_t __n
) {
2008 _RopeRep
* __result
= replace(_M_tree_ptr
, __p
, __p
+ __n
, 0);
2009 _S_unref(_M_tree_ptr
);
2010 _M_tree_ptr
= __result
;
2013 // Erase, single character
2014 void erase(size_t __p
) {
2015 erase(__p
, __p
+ 1);
2018 // Insert, iterator variants.
2019 iterator
insert(const iterator
& __p
, const rope
& __r
)
2020 { insert(__p
.index(), __r
); return __p
; }
2021 iterator
insert(const iterator
& __p
, size_t __n
, _CharT __c
)
2022 { insert(__p
.index(), __n
, __c
); return __p
; }
2023 iterator
insert(const iterator
& __p
, _CharT __c
)
2024 { insert(__p
.index(), __c
); return __p
; }
2025 iterator
insert(const iterator
& __p
)
2026 { insert(__p
.index()); return __p
; }
2027 iterator
insert(const iterator
& __p
, const _CharT
* c_string
)
2028 { insert(__p
.index(), c_string
); return __p
; }
2029 iterator
insert(const iterator
& __p
, const _CharT
* __i
, size_t __n
)
2030 { insert(__p
.index(), __i
, __n
); return __p
; }
2031 iterator
insert(const iterator
& __p
, const _CharT
* __i
,
2033 { insert(__p
.index(), __i
, __j
); return __p
; }
2034 iterator
insert(const iterator
& __p
,
2035 const const_iterator
& __i
, const const_iterator
& __j
)
2036 { insert(__p
.index(), __i
, __j
); return __p
; }
2037 iterator
insert(const iterator
& __p
,
2038 const iterator
& __i
, const iterator
& __j
)
2039 { insert(__p
.index(), __i
, __j
); return __p
; }
2041 // Replace, range variants.
2042 void replace(const iterator
& __p
, const iterator
& __q
,
2044 { replace(__p
.index(), __q
.index() - __p
.index(), __r
); }
2045 void replace(const iterator
& __p
, const iterator
& __q
, _CharT __c
)
2046 { replace(__p
.index(), __q
.index() - __p
.index(), __c
); }
2047 void replace(const iterator
& __p
, const iterator
& __q
,
2048 const _CharT
* __c_string
)
2049 { replace(__p
.index(), __q
.index() - __p
.index(), __c_string
); }
2050 void replace(const iterator
& __p
, const iterator
& __q
,
2051 const _CharT
* __i
, size_t __n
)
2052 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __n
); }
2053 void replace(const iterator
& __p
, const iterator
& __q
,
2054 const _CharT
* __i
, const _CharT
* __j
)
2055 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __j
); }
2056 void replace(const iterator
& __p
, const iterator
& __q
,
2057 const const_iterator
& __i
, const const_iterator
& __j
)
2058 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __j
); }
2059 void replace(const iterator
& __p
, const iterator
& __q
,
2060 const iterator
& __i
, const iterator
& __j
)
2061 { replace(__p
.index(), __q
.index() - __p
.index(), __i
, __j
); }
2063 // Replace, iterator variants.
2064 void replace(const iterator
& __p
, const rope
& __r
)
2065 { replace(__p
.index(), __r
); }
2066 void replace(const iterator
& __p
, _CharT __c
)
2067 { replace(__p
.index(), __c
); }
2068 void replace(const iterator
& __p
, const _CharT
* __c_string
)
2069 { replace(__p
.index(), __c_string
); }
2070 void replace(const iterator
& __p
, const _CharT
* __i
, size_t __n
)
2071 { replace(__p
.index(), __i
, __n
); }
2072 void replace(const iterator
& __p
, const _CharT
* __i
, const _CharT
* __j
)
2073 { replace(__p
.index(), __i
, __j
); }
2074 void replace(const iterator
& __p
, const_iterator __i
,
2076 { replace(__p
.index(), __i
, __j
); }
2077 void replace(const iterator
& __p
, iterator __i
, iterator __j
)
2078 { replace(__p
.index(), __i
, __j
); }
2080 // Iterator and range variants of erase
2081 iterator
erase(const iterator
& __p
, const iterator
& __q
) {
2082 size_t __p_index
= __p
.index();
2083 erase(__p_index
, __q
.index() - __p_index
);
2084 return iterator(this, __p_index
);
2086 iterator
erase(const iterator
& __p
) {
2087 size_t __p_index
= __p
.index();
2088 erase(__p_index
, 1);
2089 return iterator(this, __p_index
);
2092 rope
substr(size_t __start
, size_t __len
= 1) const {
2093 return rope
<_CharT
,_Alloc
>(
2094 _S_substring(_M_tree_ptr
, __start
, __start
+ __len
));
2097 rope
substr(iterator __start
, iterator __end
) const {
2098 return rope
<_CharT
,_Alloc
>(
2099 _S_substring(_M_tree_ptr
, __start
.index(), __end
.index()));
2102 rope
substr(iterator __start
) const {
2103 size_t __pos
= __start
.index();
2104 return rope
<_CharT
,_Alloc
>(
2105 _S_substring(_M_tree_ptr
, __pos
, __pos
+ 1));
2108 rope
substr(const_iterator __start
, const_iterator __end
) const {
2109 // This might eventually take advantage of the cache in the
2111 return rope
<_CharT
,_Alloc
>(
2112 _S_substring(_M_tree_ptr
, __start
.index(), __end
.index()));
2115 rope
<_CharT
,_Alloc
> substr(const_iterator __start
) {
2116 size_t __pos
= __start
.index();
2117 return rope
<_CharT
,_Alloc
>(
2118 _S_substring(_M_tree_ptr
, __pos
, __pos
+ 1));
2121 static const size_type npos
;
2123 size_type
find(_CharT __c
, size_type __pos
= 0) const;
2124 size_type
find(const _CharT
* __s
, size_type __pos
= 0) const {
2125 size_type __result_pos
;
2126 const_iterator __result
=
2127 std::search(const_begin() + __pos
, const_end(),
2128 __s
, __s
+ _S_char_ptr_len(__s
));
2129 __result_pos
= __result
.index();
2130 # ifndef __STL_OLD_ROPE_SEMANTICS
2131 if (__result_pos
== size()) __result_pos
= npos
;
2133 return __result_pos
;
2136 iterator
mutable_begin() {
2137 return(iterator(this, 0));
2140 iterator
mutable_end() {
2141 return(iterator(this, size()));
2144 typedef reverse_iterator
<iterator
> reverse_iterator
;
2146 reverse_iterator
mutable_rbegin() {
2147 return reverse_iterator(mutable_end());
2150 reverse_iterator
mutable_rend() {
2151 return reverse_iterator(mutable_begin());
2154 reference
mutable_reference_at(size_type __pos
) {
2155 return reference(this, __pos
);
2159 reference
operator[] (size_type __pos
) {
2160 return _char_ref_proxy(this, __pos
);
2163 reference
at(size_type __pos
) {
2164 // if (__pos >= size()) throw out_of_range; // XXX
2165 return (*this)[__pos
];
2168 void resize(size_type __n
, _CharT __c
) {}
2169 void resize(size_type __n
) {}
2170 void reserve(size_type __res_arg
= 0) {}
2171 size_type
capacity() const {
2175 // Stuff below this line is dangerous because it's error prone.
2176 // I would really like to get rid of it.
2177 // copy function with funny arg ordering.
2178 size_type
copy(_CharT
* __buffer
, size_type __n
,
2179 size_type __pos
= 0) const {
2180 return copy(__pos
, __n
, __buffer
);
2183 iterator
end() { return mutable_end(); }
2185 iterator
begin() { return mutable_begin(); }
2187 reverse_iterator
rend() { return mutable_rend(); }
2189 reverse_iterator
rbegin() { return mutable_rbegin(); }
2193 const_iterator
end() { return const_end(); }
2195 const_iterator
begin() { return const_begin(); }
2197 const_reverse_iterator
rend() { return const_rend(); }
2199 const_reverse_iterator
rbegin() { return const_rbegin(); }
2205 template <class _CharT
, class _Alloc
>
2206 const typename rope
<_CharT
, _Alloc
>::size_type rope
<_CharT
, _Alloc
>::npos
=
2209 template <class _CharT
, class _Alloc
>
2210 inline bool operator== (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2211 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2212 return (__x
._M_current_pos
== __y
._M_current_pos
&&
2213 __x
._M_root
== __y
._M_root
);
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
._M_current_pos
< __y
._M_current_pos
);
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 bool operator> (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2230 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
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 !(__y
< __x
);
2240 template <class _CharT
, class _Alloc
>
2241 inline bool operator>= (const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2242 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2243 return !(__x
< __y
);
2246 template <class _CharT
, class _Alloc
>
2247 inline ptrdiff_t operator-(const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
,
2248 const _Rope_const_iterator
<_CharT
,_Alloc
>& __y
) {
2249 return (ptrdiff_t)__x
._M_current_pos
- (ptrdiff_t)__y
._M_current_pos
;
2252 template <class _CharT
, class _Alloc
>
2253 inline _Rope_const_iterator
<_CharT
,_Alloc
>
2254 operator-(const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
, ptrdiff_t __n
) {
2255 return _Rope_const_iterator
<_CharT
,_Alloc
>(
2256 __x
._M_root
, __x
._M_current_pos
- __n
);
2259 template <class _CharT
, class _Alloc
>
2260 inline _Rope_const_iterator
<_CharT
,_Alloc
>
2261 operator+(const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
, ptrdiff_t __n
) {
2262 return _Rope_const_iterator
<_CharT
,_Alloc
>(
2263 __x
._M_root
, __x
._M_current_pos
+ __n
);
2266 template <class _CharT
, class _Alloc
>
2267 inline _Rope_const_iterator
<_CharT
,_Alloc
>
2268 operator+(ptrdiff_t __n
, const _Rope_const_iterator
<_CharT
,_Alloc
>& __x
) {
2269 return _Rope_const_iterator
<_CharT
,_Alloc
>(
2270 __x
._M_root
, __x
._M_current_pos
+ __n
);
2273 template <class _CharT
, class _Alloc
>
2274 inline bool operator== (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2275 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2276 return (__x
._M_current_pos
== __y
._M_current_pos
&&
2277 __x
._M_root_rope
== __y
._M_root_rope
);
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
._M_current_pos
< __y
._M_current_pos
);
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 bool operator> (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2294 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
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 !(__y
< __x
);
2304 template <class _CharT
, class _Alloc
>
2305 inline bool operator>= (const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2306 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2307 return !(__x
< __y
);
2310 template <class _CharT
, class _Alloc
>
2311 inline ptrdiff_t operator-(const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2312 const _Rope_iterator
<_CharT
,_Alloc
>& __y
) {
2313 return (ptrdiff_t)__x
._M_current_pos
- (ptrdiff_t)__y
._M_current_pos
;
2316 template <class _CharT
, class _Alloc
>
2317 inline _Rope_iterator
<_CharT
,_Alloc
>
2318 operator-(const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2320 return _Rope_iterator
<_CharT
,_Alloc
>(
2321 __x
._M_root_rope
, __x
._M_current_pos
- __n
);
2324 template <class _CharT
, class _Alloc
>
2325 inline _Rope_iterator
<_CharT
,_Alloc
>
2326 operator+(const _Rope_iterator
<_CharT
,_Alloc
>& __x
,
2328 return _Rope_iterator
<_CharT
,_Alloc
>(
2329 __x
._M_root_rope
, __x
._M_current_pos
+ __n
);
2332 template <class _CharT
, class _Alloc
>
2333 inline _Rope_iterator
<_CharT
,_Alloc
>
2334 operator+(ptrdiff_t __n
, const _Rope_iterator
<_CharT
,_Alloc
>& __x
) {
2335 return _Rope_iterator
<_CharT
,_Alloc
>(
2336 __x
._M_root_rope
, __x
._M_current_pos
+ __n
);
2339 template <class _CharT
, class _Alloc
>
2342 operator+ (const rope
<_CharT
,_Alloc
>& __left
,
2343 const rope
<_CharT
,_Alloc
>& __right
)
2345 return rope
<_CharT
,_Alloc
>(
2346 rope
<_CharT
,_Alloc
>::_S_concat(__left
._M_tree_ptr
, __right
._M_tree_ptr
));
2347 // Inlining this should make it possible to keep __left and
2348 // __right in registers.
2351 template <class _CharT
, class _Alloc
>
2353 rope
<_CharT
,_Alloc
>&
2354 operator+= (rope
<_CharT
,_Alloc
>& __left
,
2355 const rope
<_CharT
,_Alloc
>& __right
)
2357 __left
.append(__right
);
2361 template <class _CharT
, class _Alloc
>
2364 operator+ (const rope
<_CharT
,_Alloc
>& __left
,
2365 const _CharT
* __right
) {
2366 size_t __rlen
= rope
<_CharT
,_Alloc
>::_S_char_ptr_len(__right
);
2367 return rope
<_CharT
,_Alloc
>(
2368 rope
<_CharT
,_Alloc
>::_S_concat_char_iter(
2369 __left
._M_tree_ptr
, __right
, __rlen
));
2372 template <class _CharT
, class _Alloc
>
2374 rope
<_CharT
,_Alloc
>&
2375 operator+= (rope
<_CharT
,_Alloc
>& __left
,
2376 const _CharT
* __right
) {
2377 __left
.append(__right
);
2381 template <class _CharT
, class _Alloc
>
2384 operator+ (const rope
<_CharT
,_Alloc
>& __left
, _CharT __right
) {
2385 return rope
<_CharT
,_Alloc
>(
2386 rope
<_CharT
,_Alloc
>::_S_concat_char_iter(
2387 __left
._M_tree_ptr
, &__right
, 1));
2390 template <class _CharT
, class _Alloc
>
2392 rope
<_CharT
,_Alloc
>&
2393 operator+= (rope
<_CharT
,_Alloc
>& __left
, _CharT __right
) {
2394 __left
.append(__right
);
2398 template <class _CharT
, class _Alloc
>
2400 operator< (const rope
<_CharT
,_Alloc
>& __left
,
2401 const rope
<_CharT
,_Alloc
>& __right
) {
2402 return __left
.compare(__right
) < 0;
2405 template <class _CharT
, class _Alloc
>
2407 operator== (const rope
<_CharT
,_Alloc
>& __left
,
2408 const rope
<_CharT
,_Alloc
>& __right
) {
2409 return __left
.compare(__right
) == 0;
2412 template <class _CharT
, class _Alloc
>
2413 inline bool operator== (const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __x
,
2414 const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __y
) {
2415 return (__x
._M_pos
== __y
._M_pos
&& __x
._M_root
== __y
._M_root
);
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
>
2426 operator> (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2430 template <class _CharT
, class _Alloc
>
2432 operator<= (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2433 return !(__y
< __x
);
2436 template <class _CharT
, class _Alloc
>
2438 operator>= (const rope
<_CharT
,_Alloc
>& __x
, const rope
<_CharT
,_Alloc
>& __y
) {
2439 return !(__x
< __y
);
2442 template <class _CharT
, class _Alloc
>
2443 inline bool operator!= (const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __x
,
2444 const _Rope_char_ptr_proxy
<_CharT
,_Alloc
>& __y
) {
2445 return !(__x
== __y
);
2448 template<class _CharT
, class _Traits
, class _Alloc
>
2449 std::basic_ostream
<_CharT
, _Traits
>& operator<<
2450 (std::basic_ostream
<_CharT
, _Traits
>& __o
,
2451 const rope
<_CharT
, _Alloc
>& __r
);
2453 typedef rope
<char> crope
;
2454 typedef rope
<wchar_t> wrope
;
2456 inline crope::reference
__mutable_reference_at(crope
& __c
, size_t __i
)
2458 return __c
.mutable_reference_at(__i
);
2461 inline wrope::reference
__mutable_reference_at(wrope
& __c
, size_t __i
)
2463 return __c
.mutable_reference_at(__i
);
2466 template <class _CharT
, class _Alloc
>
2467 inline void swap(rope
<_CharT
,_Alloc
>& __x
, rope
<_CharT
,_Alloc
>& __y
) {
2471 // Hash functions should probably be revisited later:
2472 template<> struct hash
<crope
>
2474 size_t operator()(const crope
& __str
) const
2476 size_t __size
= __str
.size();
2478 if (0 == __size
) return 0;
2479 return 13*__str
[0] + 5*__str
[__size
- 1] + __size
;
2484 template<> struct hash
<wrope
>
2486 size_t operator()(const wrope
& __str
) const
2488 size_t __size
= __str
.size();
2490 if (0 == __size
) return 0;
2491 return 13*__str
[0] + 5*__str
[__size
- 1] + __size
;
2495 } // namespace __gnu_cxx
2497 # include <ext/ropeimpl.h>
2499 # endif /* __SGI_STL_INTERNAL_ROPE_H */