1f2ced752SOliver Tappe/*
2f2ced752SOliver Tappe * Copyright (c) 1997
3f2ced752SOliver Tappe * Silicon Graphics Computer Systems, Inc.
4f2ced752SOliver Tappe *
5f2ced752SOliver Tappe * Permission to use, copy, modify, distribute and sell this software
6f2ced752SOliver Tappe * and its documentation for any purpose is hereby granted without fee,
7f2ced752SOliver Tappe * provided that the above copyright notice appear in all copies and
8f2ced752SOliver Tappe * that both that copyright notice and this permission notice appear
9f2ced752SOliver Tappe * in supporting documentation.  Silicon Graphics makes no
10f2ced752SOliver Tappe * representations about the suitability of this software for any
11f2ced752SOliver Tappe * purpose.  It is provided "as is" without express or implied warranty.
12f2ced752SOliver Tappe */
13f2ced752SOliver Tappe
14f2ced752SOliver Tappe/* NOTE: This is an internal header file, included by other STL headers.
15f2ced752SOliver Tappe *   You should not attempt to use it directly.
16f2ced752SOliver Tappe */
17f2ced752SOliver Tappe
18f2ced752SOliver Tappe// rope<_CharT,_Alloc> is a sequence of _CharT.
19f2ced752SOliver Tappe// Ropes appear to be mutable, but update operations
20f2ced752SOliver Tappe// really copy enough of the data structure to leave the original
21f2ced752SOliver Tappe// valid.  Thus ropes can be logically copied by just copying
22f2ced752SOliver Tappe// a pointer value.
23f2ced752SOliver Tappe
24f2ced752SOliver Tappe#ifndef __SGI_STL_INTERNAL_ROPE_H
25f2ced752SOliver Tappe# define __SGI_STL_INTERNAL_ROPE_H
26f2ced752SOliver Tappe
27f2ced752SOliver Tappe# ifdef __GC
28f2ced752SOliver Tappe#   define __GC_CONST const
29f2ced752SOliver Tappe# else
30f2ced752SOliver Tappe#   define __GC_CONST   // constant except for deallocation
31f2ced752SOliver Tappe# endif
32f2ced752SOliver Tappe# ifdef __STL_SGI_THREADS
33f2ced752SOliver Tappe#    include <mutex.h>
34f2ced752SOliver Tappe# endif
35f2ced752SOliver Tappe
36f2ced752SOliver Tappe__STL_BEGIN_NAMESPACE
37f2ced752SOliver Tappe
38f2ced752SOliver Tappe#if defined(__sgi) && !defined(__GNUC__) && (_MIPS_SIM != _MIPS_SIM_ABI32)
39f2ced752SOliver Tappe#pragma set woff 1174
40f2ced752SOliver Tappe#endif
41f2ced752SOliver Tappe
42f2ced752SOliver Tappe// The _S_eos function is used for those functions that
43f2ced752SOliver Tappe// convert to/from C-like strings to detect the end of the string.
44f2ced752SOliver Tappe
45f2ced752SOliver Tappe// The end-of-C-string character.
46f2ced752SOliver Tappe// This is what the draft standard says it should be.
47f2ced752SOliver Tappetemplate <class _CharT>
48f2ced752SOliver Tappeinline _CharT _S_eos(_CharT*) { return _CharT(); }
49f2ced752SOliver Tappe
50f2ced752SOliver Tappe// Test for basic character types.
51f2ced752SOliver Tappe// For basic character types leaves having a trailing eos.
52f2ced752SOliver Tappetemplate <class _CharT>
53f2ced752SOliver Tappeinline bool _S_is_basic_char_type(_CharT*) { return false; }
54f2ced752SOliver Tappetemplate <class _CharT>
55f2ced752SOliver Tappeinline bool _S_is_one_byte_char_type(_CharT*) { return false; }
56f2ced752SOliver Tappe
57f2ced752SOliver Tappeinline bool _S_is_basic_char_type(char*) { return true; }
58f2ced752SOliver Tappeinline bool _S_is_one_byte_char_type(char*) { return true; }
59f2ced752SOliver Tappeinline bool _S_is_basic_char_type(wchar_t*) { return true; }
60f2ced752SOliver Tappe
61f2ced752SOliver Tappe// Store an eos iff _CharT is a basic character type.
62f2ced752SOliver Tappe// Do not reference _S_eos if it isn't.
63f2ced752SOliver Tappetemplate <class _CharT>
64f2ced752SOliver Tappeinline void _S_cond_store_eos(_CharT&) {}
65f2ced752SOliver Tappe
66f2ced752SOliver Tappeinline void _S_cond_store_eos(char& __c) { __c = 0; }
67f2ced752SOliver Tappeinline void _S_cond_store_eos(wchar_t& __c) { __c = 0; }
68f2ced752SOliver Tappe
69f2ced752SOliver Tappe// char_producers are logically functions that generate a section of
70f2ced752SOliver Tappe// a string.  These can be convereted to ropes.  The resulting rope
71f2ced752SOliver Tappe// invokes the char_producer on demand.  This allows, for example,
72f2ced752SOliver Tappe// files to be viewed as ropes without reading the entire file.
73f2ced752SOliver Tappetemplate <class _CharT>
74f2ced752SOliver Tappeclass char_producer {
75f2ced752SOliver Tappe    public:
76f2ced752SOliver Tappe        virtual ~char_producer() {};
77f2ced752SOliver Tappe        virtual void operator()(size_t __start_pos, size_t __len,
78f2ced752SOliver Tappe                                _CharT* __buffer) = 0;
79f2ced752SOliver Tappe        // Buffer should really be an arbitrary output iterator.
80f2ced752SOliver Tappe        // That way we could flatten directly into an ostream, etc.
81f2ced752SOliver Tappe        // This is thoroughly impossible, since iterator types don't
82f2ced752SOliver Tappe        // have runtime descriptions.
83f2ced752SOliver Tappe};
84f2ced752SOliver Tappe
85f2ced752SOliver Tappe// Sequence buffers:
86f2ced752SOliver Tappe//
87f2ced752SOliver Tappe// Sequence must provide an append operation that appends an
88f2ced752SOliver Tappe// array to the sequence.  Sequence buffers are useful only if
89f2ced752SOliver Tappe// appending an entire array is cheaper than appending element by element.
90f2ced752SOliver Tappe// This is true for many string representations.
91f2ced752SOliver Tappe// This should  perhaps inherit from ostream<sequence::value_type>
92f2ced752SOliver Tappe// and be implemented correspondingly, so that they can be used
93f2ced752SOliver Tappe// for formatted.  For the sake of portability, we don't do this yet.
94f2ced752SOliver Tappe//
95f2ced752SOliver Tappe// For now, sequence buffers behave as output iterators.  But they also
96f2ced752SOliver Tappe// behave a little like basic_ostringstream<sequence::value_type> and a
97f2ced752SOliver Tappe// little like containers.
98f2ced752SOliver Tappe
99f2ced752SOliver Tappetemplate<class _Sequence, size_t _Buf_sz = 100
100f2ced752SOliver Tappe#   if defined(__sgi) && !defined(__GNUC__)
101f2ced752SOliver Tappe#        define __TYPEDEF_WORKAROUND
102f2ced752SOliver Tappe         ,class _V = typename _Sequence::value_type
103f2ced752SOliver Tappe#   endif
104f2ced752SOliver Tappe        >
105f2ced752SOliver Tappe// The 3rd parameter works around a common compiler bug.
106f2ced752SOliver Tappeclass sequence_buffer : public output_iterator {
107f2ced752SOliver Tappe    public:
108f2ced752SOliver Tappe#       ifndef __TYPEDEF_WORKAROUND
109f2ced752SOliver Tappe            typedef typename _Sequence::value_type value_type;
110f2ced752SOliver Tappe#       else
111f2ced752SOliver Tappe            typedef _V value_type;
112f2ced752SOliver Tappe#       endif
113f2ced752SOliver Tappe    protected:
114f2ced752SOliver Tappe        _Sequence* _M_prefix;
115f2ced752SOliver Tappe        value_type _M_buffer[_Buf_sz];
116f2ced752SOliver Tappe        size_t     _M_buf_count;
117f2ced752SOliver Tappe    public:
118f2ced752SOliver Tappe        void flush() {
119f2ced752SOliver Tappe            _M_prefix->append(_M_buffer, _M_buffer + _M_buf_count);
120f2ced752SOliver Tappe            _M_buf_count = 0;
121f2ced752SOliver Tappe        }
122f2ced752SOliver Tappe        ~sequence_buffer() { flush(); }
123f2ced752SOliver Tappe        sequence_buffer() : _M_prefix(0), _M_buf_count(0) {}
124f2ced752SOliver Tappe        sequence_buffer(const sequence_buffer& __x) {
125f2ced752SOliver Tappe            _M_prefix = __x._M_prefix;
126f2ced752SOliver Tappe            _M_buf_count = __x._M_buf_count;
127f2ced752SOliver Tappe            copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
128f2ced752SOliver Tappe        }
129f2ced752SOliver Tappe        sequence_buffer(sequence_buffer& __x) {
130f2ced752SOliver Tappe            __x.flush();
131f2ced752SOliver Tappe            _M_prefix = __x._M_prefix;
132f2ced752SOliver Tappe            _M_buf_count = 0;
133f2ced752SOliver Tappe        }
134f2ced752SOliver Tappe        sequence_buffer(_Sequence& __s) : _M_prefix(&__s), _M_buf_count(0) {}
135f2ced752SOliver Tappe        sequence_buffer& operator= (sequence_buffer& __x) {
136f2ced752SOliver Tappe            __x.flush();
137f2ced752SOliver Tappe            _M_prefix = __x._M_prefix;
138f2ced752SOliver Tappe            _M_buf_count = 0;
139f2ced752SOliver Tappe            return *this;
140f2ced752SOliver Tappe        }
141f2ced752SOliver Tappe        sequence_buffer& operator= (const sequence_buffer& __x) {
142f2ced752SOliver Tappe            _M_prefix = __x._M_prefix;
143f2ced752SOliver Tappe            _M_buf_count = __x._M_buf_count;
144f2ced752SOliver Tappe            copy(__x._M_buffer, __x._M_buffer + __x._M_buf_count, _M_buffer);
145f2ced752SOliver Tappe            return *this;
146f2ced752SOliver Tappe        }
147f2ced752SOliver Tappe        void push_back(value_type __x)
148f2ced752SOliver Tappe        {
149f2ced752SOliver Tappe            if (_M_buf_count < _Buf_sz) {
150f2ced752SOliver Tappe                _M_buffer[_M_buf_count] = __x;
151f2ced752SOliver Tappe                ++_M_buf_count;
152f2ced752SOliver Tappe            } else {
153f2ced752SOliver Tappe                flush();
154f2ced752SOliver Tappe                _M_buffer[0] = __x;
155f2ced752SOliver Tappe                _M_buf_count = 1;
156f2ced752SOliver Tappe            }
157f2ced752SOliver Tappe        }
158f2ced752SOliver Tappe        void append(value_type* __s, size_t __len)
159f2ced752SOliver Tappe        {
160f2ced752SOliver Tappe            if (__len + _M_buf_count <= _Buf_sz) {
161f2ced752SOliver Tappe                size_t __i = _M_buf_count;
162f2ced752SOliver Tappe                size_t __j = 0;
163f2ced752SOliver Tappe                for (; __j < __len; __i++, __j++) {
164f2ced752SOliver Tappe                    _M_buffer[__i] = __s[__j];
165f2ced752SOliver Tappe                }
166f2ced752SOliver Tappe                _M_buf_count += __len;
167f2ced752SOliver Tappe            } else if (0 == _M_buf_count) {
168f2ced752SOliver Tappe                _M_prefix->append(__s, __s + __len);
169f2ced752SOliver Tappe            } else {
170f2ced752SOliver Tappe                flush();
171f2ced752SOliver Tappe                append(__s, __len);
172f2ced752SOliver Tappe            }
173f2ced752SOliver Tappe        }
174f2ced752SOliver Tappe        sequence_buffer& write(value_type* __s, size_t __len)
175f2ced752SOliver Tappe        {
176f2ced752SOliver Tappe            append(__s, __len);
177f2ced752SOliver Tappe            return *this;
178f2ced752SOliver Tappe        }
179f2ced752SOliver Tappe        sequence_buffer& put(value_type __x)
180f2ced752SOliver Tappe        {
181f2ced752SOliver Tappe            push_back(__x);
182f2ced752SOliver Tappe            return *this;
183f2ced752SOliver Tappe        }
184f2ced752SOliver Tappe        sequence_buffer& operator=(const value_type& __rhs)
185f2ced752SOliver Tappe        {
186f2ced752SOliver Tappe            push_back(__rhs);
187f2ced752SOliver Tappe            return *this;
188f2ced752SOliver Tappe        }
189f2ced752SOliver Tappe        sequence_buffer& operator*() { return *this; }
190f2ced752SOliver Tappe        sequence_buffer& operator++() { return *this; }
191f2ced752SOliver Tappe        sequence_buffer& operator++(int) { return *this; }
192f2ced752SOliver Tappe};
193f2ced752SOliver Tappe
194f2ced752SOliver Tappe// The following should be treated as private, at least for now.
195f2ced752SOliver Tappetemplate<class _CharT>
196f2ced752SOliver Tappeclass _Rope_char_consumer {
197f2ced752SOliver Tappe    public:
198f2ced752SOliver Tappe        // If we had member templates, these should not be virtual.
199f2ced752SOliver Tappe        // For now we need to use run-time parametrization where
200f2ced752SOliver Tappe        // compile-time would do.  _Hence this should all be private
201f2ced752SOliver Tappe        // for now.
202f2ced752SOliver Tappe        // The symmetry with char_producer is accidental and temporary.
203f2ced752SOliver Tappe        virtual ~_Rope_char_consumer() {};
204f2ced752SOliver Tappe        virtual bool operator()(const _CharT* __buffer, size_t __len) = 0;
205f2ced752SOliver Tappe};
206f2ced752SOliver Tappe
207f2ced752SOliver Tappe//
208f2ced752SOliver Tappe// What follows should really be local to rope.  Unfortunately,
209f2ced752SOliver Tappe// that doesn't work, since it makes it impossible to define generic
210f2ced752SOliver Tappe// equality on rope iterators.  According to the draft standard, the
211f2ced752SOliver Tappe// template parameters for such an equality operator cannot be inferred
212f2ced752SOliver Tappe// from the occurence of a member class as a parameter.
213f2ced752SOliver Tappe// (SGI compilers in fact allow this, but the __result wouldn't be
214f2ced752SOliver Tappe// portable.)
215f2ced752SOliver Tappe// Similarly, some of the static member functions are member functions
216f2ced752SOliver Tappe// only to avoid polluting the global namespace, and to circumvent
217f2ced752SOliver Tappe// restrictions on type inference for template functions.
218f2ced752SOliver Tappe//
219f2ced752SOliver Tappe
220f2ced752SOliver Tappetemplate<class _CharT, class _Alloc=__STL_DEFAULT_ALLOCATOR(_CharT)> class rope;
221f2ced752SOliver Tappetemplate<class _CharT, class _Alloc> struct _Rope_RopeConcatenation;
222f2ced752SOliver Tappetemplate<class _CharT, class _Alloc> struct _Rope_RopeLeaf;
223f2ced752SOliver Tappetemplate<class _CharT, class _Alloc> struct _Rope_RopeFunction;
224f2ced752SOliver Tappetemplate<class _CharT, class _Alloc> struct _Rope_RopeSubstring;
225f2ced752SOliver Tappetemplate<class _CharT, class _Alloc> class _Rope_iterator;
226f2ced752SOliver Tappetemplate<class _CharT, class _Alloc> class _Rope_const_iterator;
227f2ced752SOliver Tappetemplate<class _CharT, class _Alloc> class _Rope_char_ref_proxy;
228f2ced752SOliver Tappetemplate<class _CharT, class _Alloc> class _Rope_char_ptr_proxy;
229f2ced752SOliver Tappe
230f2ced752SOliver Tappe//
231f2ced752SOliver Tappe// The internal data structure for representing a rope.  This is
232f2ced752SOliver Tappe// private to the implementation.  A rope is really just a pointer
233f2ced752SOliver Tappe// to one of these.
234f2ced752SOliver Tappe//
235f2ced752SOliver Tappe// A few basic functions for manipulating this data structure
236f2ced752SOliver Tappe// are members of _RopeRep.  Most of the more complex algorithms
237f2ced752SOliver Tappe// are implemented as rope members.
238f2ced752SOliver Tappe//
239f2ced752SOliver Tappe// Some of the static member functions of _RopeRep have identically
240f2ced752SOliver Tappe// named functions in rope that simply invoke the _RopeRep versions.
241f2ced752SOliver Tappe//
242f2ced752SOliver Tappe// A macro to introduce various allocation and deallocation functions
243f2ced752SOliver Tappe// These need to be defined differently depending on whether or not
244f2ced752SOliver Tappe// we are using standard conforming allocators, and whether the allocator
245f2ced752SOliver Tappe// instances have real state.  Thus this macro is invoked repeatedly
246f2ced752SOliver Tappe// with different definitions of __ROPE_DEFINE_ALLOC.
247f2ced752SOliver Tappe// __ROPE_DEFINE_ALLOC(type,name) defines
248f2ced752SOliver Tappe//   type * name_allocate(size_t) and
249f2ced752SOliver Tappe//   void name_deallocate(tipe *, size_t)
250f2ced752SOliver Tappe// Both functions may or may not be static.
251f2ced752SOliver Tappe
252f2ced752SOliver Tappe#define __ROPE_DEFINE_ALLOCS(__a) \
253f2ced752SOliver Tappe        __ROPE_DEFINE_ALLOC(_CharT,_Data) /* character data */ \
254f2ced752SOliver Tappe        typedef _Rope_RopeConcatenation<_CharT,__a> __C; \
255f2ced752SOliver Tappe        __ROPE_DEFINE_ALLOC(__C,_C) \
256f2ced752SOliver Tappe        typedef _Rope_RopeLeaf<_CharT,__a> __L; \
257f2ced752SOliver Tappe        __ROPE_DEFINE_ALLOC(__L,_L) \
258f2ced752SOliver Tappe        typedef _Rope_RopeFunction<_CharT,__a> __F; \
259f2ced752SOliver Tappe        __ROPE_DEFINE_ALLOC(__F,_F) \
260f2ced752SOliver Tappe        typedef _Rope_RopeSubstring<_CharT,__a> __S; \
261f2ced752SOliver Tappe        __ROPE_DEFINE_ALLOC(__S,_S)
262f2ced752SOliver Tappe
263f2ced752SOliver Tappe//  Internal rope nodes potentially store a copy of the allocator
264f2ced752SOliver Tappe//  instance used to allocate them.  This is mostly redundant.
265f2ced752SOliver Tappe//  But the alternative would be to pass allocator instances around
266f2ced752SOliver Tappe//  in some form to nearly all internal functions, since any pointer
267f2ced752SOliver Tappe//  assignment may result in a zero reference count and thus require
268f2ced752SOliver Tappe//  deallocation.
269f2ced752SOliver Tappe//  The _Rope_rep_base class encapsulates
270f2ced752SOliver Tappe//  the differences between SGI-style allocators and standard-conforming
271f2ced752SOliver Tappe//  allocators.
272f2ced752SOliver Tappe
273f2ced752SOliver Tappe#ifdef __STL_USE_STD_ALLOCATORS
274f2ced752SOliver Tappe
275f2ced752SOliver Tappe#define __STATIC_IF_SGI_ALLOC  /* not static */
276f2ced752SOliver Tappe
277f2ced752SOliver Tappe// Base class for ordinary allocators.
278f2ced752SOliver Tappetemplate <class _CharT, class _Allocator, bool _IsStatic>
279f2ced752SOliver Tappeclass _Rope_rep_alloc_base {
280f2ced752SOliver Tappepublic:
281f2ced752SOliver Tappe  typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type
282f2ced752SOliver Tappe          allocator_type;
283f2ced752SOliver Tappe  allocator_type get_allocator() const { return _M_data_allocator; }
284f2ced752SOliver Tappe  _Rope_rep_alloc_base(size_t __size, const allocator_type& __a)
285f2ced752SOliver Tappe        : _M_size(__size), _M_data_allocator(__a) {}
286f2ced752SOliver Tappe  size_t _M_size;       // This is here only to avoid wasting space
287f2ced752SOliver Tappe                // for an otherwise empty base class.
288f2ced752SOliver Tappe
289f2ced752SOliver Tappe
290f2ced752SOliver Tappeprotected:
291f2ced752SOliver Tappe    allocator_type _M_data_allocator;
292f2ced752SOliver Tappe
293f2ced752SOliver Tappe# define __ROPE_DEFINE_ALLOC(_Tp, __name) \
294f2ced752SOliver Tappe        typedef typename \
295f2ced752SOliver Tappe          _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
296f2ced752SOliver Tappe        /*static*/ _Tp * __name##_allocate(size_t __n) \
297f2ced752SOliver Tappe          { return __name##Allocator(_M_data_allocator).allocate(__n); } \
298f2ced752SOliver Tappe        void __name##_deallocate(_Tp* __p, size_t __n) \
299f2ced752SOliver Tappe          { __name##Allocator(_M_data_allocator).deallocate(__p, __n); }
300f2ced752SOliver Tappe  __ROPE_DEFINE_ALLOCS(_Allocator);
301f2ced752SOliver Tappe# undef __ROPE_DEFINE_ALLOC
302f2ced752SOliver Tappe};
303f2ced752SOliver Tappe
304f2ced752SOliver Tappe// Specialization for allocators that have the property that we don't
305f2ced752SOliver Tappe//  actually have to store an allocator object.
306f2ced752SOliver Tappetemplate <class _CharT, class _Allocator>
307f2ced752SOliver Tappeclass _Rope_rep_alloc_base<_CharT,_Allocator,true> {
308f2ced752SOliver Tappepublic:
309f2ced752SOliver Tappe  typedef typename _Alloc_traits<_CharT,_Allocator>::allocator_type
310f2ced752SOliver Tappe          allocator_type;
311f2ced752SOliver Tappe  allocator_type get_allocator() const { return allocator_type(); }
312f2ced752SOliver Tappe  _Rope_rep_alloc_base(size_t __size, const allocator_type&)
313f2ced752SOliver Tappe                : _M_size(__size) {}
314f2ced752SOliver Tappe  size_t _M_size;
315f2ced752SOliver Tappe
316f2ced752SOliver Tappeprotected:
317f2ced752SOliver Tappe
318f2ced752SOliver Tappe# define __ROPE_DEFINE_ALLOC(_Tp, __name) \
319f2ced752SOliver Tappe        typedef typename \
320f2ced752SOliver Tappe          _Alloc_traits<_Tp,_Allocator>::_Alloc_type __name##Alloc; \
321f2ced752SOliver Tappe        typedef typename \
322f2ced752SOliver Tappe          _Alloc_traits<_Tp,_Allocator>::allocator_type __name##Allocator; \
323f2ced752SOliver Tappe        static _Tp* __name##_allocate(size_t __n) \
324f2ced752SOliver Tappe                { return __name##Alloc::allocate(__n); } \
325f2ced752SOliver Tappe        void __name##_deallocate(_Tp *__p, size_t __n) \
326f2ced752SOliver Tappe                { __name##Alloc::deallocate(__p, __n); }
327f2ced752SOliver Tappe  __ROPE_DEFINE_ALLOCS(_Allocator);
328f2ced752SOliver Tappe# undef __ROPE_DEFINE_ALLOC
329f2ced752SOliver Tappe};
330f2ced752SOliver Tappe
331f2ced752SOliver Tappetemplate <class _CharT, class _Alloc>
332f2ced752SOliver Tappestruct _Rope_rep_base
333f2ced752SOliver Tappe  : public _Rope_rep_alloc_base<_CharT,_Alloc,
334f2ced752SOliver Tappe                                _Alloc_traits<_CharT,_Alloc>::_S_instanceless>
335f2ced752SOliver Tappe{
336f2ced752SOliver Tappe  typedef _Rope_rep_alloc_base<_CharT,_Alloc,
337f2ced752SOliver Tappe                               _Alloc_traits<_CharT,_Alloc>::_S_instanceless>
338f2ced752SOliver Tappe          _Base;
339f2ced752SOliver Tappe  typedef typename _Base::allocator_type allocator_type;
340f2ced752SOliver Tappe  _Rope_rep_base(size_t __size, const allocator_type& __a)
341f2ced752SOliver Tappe    : _Base(__size, __a) {}
342f2ced752SOliver Tappe};
343f2ced752SOliver Tappe
344f2ced752SOliver Tappe#else /* !__STL_USE_STD_ALLOCATORS */
345f2ced752SOliver Tappe
346f2ced752SOliver Tappe#define __STATIC_IF_SGI_ALLOC static
347f2ced752SOliver Tappe
348f2ced752SOliver Tappetemplate <class _CharT, class _Alloc>
349f2ced752SOliver Tappeclass _Rope_rep_base {
350f2ced752SOliver Tappepublic:
351f2ced752SOliver Tappe  typedef _Alloc allocator_type;
352f2ced752SOliver Tappe  static allocator_type get_allocator() { return allocator_type(); }
353f2ced752SOliver Tappe  _Rope_rep_base(size_t __size, const allocator_type&) : _M_size(__size) {}
354f2ced752SOliver Tappe  size_t _M_size;
355f2ced752SOliver Tappe
356f2ced752SOliver Tappeprotected:
357f2ced752SOliver Tappe
358f2ced752SOliver Tappe# define __ROPE_DEFINE_ALLOC(_Tp, __name) \
359f2ced752SOliver Tappe        typedef simple_alloc<_Tp, _Alloc> __name##Alloc; \
360f2ced752SOliver Tappe        static _Tp* __name##_allocate(size_t __n) \
361f2ced752SOliver Tappe                { return __name##Alloc::allocate(__n); } \
362f2ced752SOliver Tappe        static void __name##_deallocate(_Tp* __p, size_t __n) \
363f2ced752SOliver Tappe                { __name##Alloc::deallocate(__p, __n); }
364f2ced752SOliver Tappe  __ROPE_DEFINE_ALLOCS(_Alloc);
365f2ced752SOliver Tappe# undef __ROPE_DEFINE_ALLOC
366f2ced752SOliver Tappe};
367f2ced752SOliver Tappe
368f2ced752SOliver Tappe#endif /* __STL_USE_STD_ALLOCATORS */
369f2ced752SOliver Tappe
370f2ced752SOliver Tappe
371f2ced752SOliver Tappetemplate<class _CharT, class _Alloc>
372f2ced752SOliver Tappestruct _Rope_RopeRep : public _Rope_rep_base<_CharT,_Alloc> {
373f2ced752SOliver Tappe    public:
374f2ced752SOliver Tappe    enum { _S_max_rope_depth = 45 };
375f2ced752SOliver Tappe    enum _Tag {_S_leaf, _S_concat, _S_substringfn, _S_function};
376f2ced752SOliver Tappe    _Tag _M_tag:8;
377f2ced752SOliver Tappe    bool _M_is_balanced:8;
378f2ced752SOliver Tappe    unsigned char _M_depth;
379f2ced752SOliver Tappe    __GC_CONST _CharT* _M_c_string;
380f2ced752SOliver Tappe                        /* Flattened version of string, if needed.  */
381f2ced752SOliver Tappe                        /* typically 0.                             */
382f2ced752SOliver Tappe                        /* If it's not 0, then the memory is owned  */
383f2ced752SOliver Tappe                        /* by this node.                            */
384f2ced752SOliver Tappe                        /* In the case of a leaf, this may point to */
385f2ced752SOliver Tappe                        /* the same memory as the data field.       */
386f2ced752SOliver Tappe    typedef _Rope_rep_base<_CharT,_Alloc>::allocator_type allocator_type;
387f2ced752SOliver Tappe    _Rope_RopeRep(_Tag __t, int __d, bool __b, size_t __size,
388f2ced752SOliver Tappe                  allocator_type __a)
389f2ced752SOliver Tappe        : _Rope_rep_base<_CharT,_Alloc>(__size, __a),
390f2ced752SOliver Tappe          _M_tag(__t), _M_depth(__d), _M_is_balanced(__b), _M_c_string(0)
391f2ced752SOliver Tappe    {
392f2ced752SOliver Tappe#       ifndef __GC
393f2ced752SOliver Tappe            _M_refcount = 1;
394f2ced752SOliver Tappe            _M_init_refcount_lock();
395f2ced752SOliver Tappe#       endif
396f2ced752SOliver Tappe    }
397f2ced752SOliver Tappe#   ifndef __GC
398f2ced752SOliver Tappe#       if defined(__STL_WIN32THREADS)
399f2ced752SOliver Tappe            long _M_refcount;   // InterlockedIncrement wants a long *
400f2ced752SOliver Tappe#       else
401f2ced752SOliver Tappe            size_t _M_refcount;
402f2ced752SOliver Tappe#       endif
403f2ced752SOliver Tappe        // We count references from rope instances
404f2ced752SOliver Tappe        // and references from other rope nodes.  We
405f2ced752SOliver Tappe        // do not count const_iterator references.
406f2ced752SOliver Tappe        // Iterator references are counted so that rope modifications
407f2ced752SOliver Tappe        // can be detected after the fact.
408f2ced752SOliver Tappe        // Generally function results are counted, i.__e.
409f2ced752SOliver Tappe        // a pointer returned by a function is included at the
410f2ced752SOliver Tappe        // point at which the pointer is returned.
411f2ced752SOliver Tappe        // The recipient should decrement the count if the
412f2ced752SOliver Tappe        // __result is not needed.
413f2ced752SOliver Tappe        // Generally function arguments are not reflected
414f2ced752SOliver Tappe        // in the reference count.  The callee should increment
415f2ced752SOliver Tappe        // the count before saving the argument someplace that
416f2ced752SOliver Tappe        // will outlive the call.
417f2ced752SOliver Tappe#   endif
418f2ced752SOliver Tappe#   ifndef __GC
419f2ced752SOliver Tappe#       ifdef __STL_SGI_THREADS
420f2ced752SOliver Tappe            // Reference counting with multiple threads and no
421f2ced752SOliver Tappe            // hardware or thread package support is pretty awful.
422f2ced752SOliver Tappe            // Mutexes are normally too expensive.
423f2ced752SOliver Tappe            // We'll assume a COMPARE_AND_SWAP(destp, __old, new)
424f2ced752SOliver Tappe            // operation, which might be cheaper.
425f2ced752SOliver Tappe#           if __mips < 3 || !(defined (_ABIN32) || defined(_ABI64))
426f2ced752SOliver Tappe#               define __add_and_fetch(l,v) add_then_test((unsigned long*)l,v)
427f2ced752SOliver Tappe#           endif
428f2ced752SOliver Tappe            void _M_init_refcount_lock() {}
429f2ced752SOliver Tappe            void _M_incr_refcount ()
430f2ced752SOliver Tappe            {
431f2ced752SOliver Tappe                __add_and_fetch(&_M_refcount, 1);
432f2ced752SOliver Tappe            }
433f2ced752SOliver Tappe            size_t _M_decr_refcount ()
434f2ced752SOliver Tappe            {
435f2ced752SOliver Tappe                return __add_and_fetch(&_M_refcount, (size_t)(-1));
436f2ced752SOliver Tappe            }
437f2ced752SOliver Tappe#       elif defined(__STL_WIN32THREADS)
438f2ced752SOliver Tappe            void _M_init_refcount_lock() {}
439f2ced752SOliver Tappe            void _M_incr_refcount ()
440f2ced752SOliver Tappe            {
441f2ced752SOliver Tappe                InterlockedIncrement(&_M_refcount);
442f2ced752SOliver Tappe            }
443f2ced752SOliver Tappe            size_t _M_decr_refcount ()
444f2ced752SOliver Tappe            {
445f2ced752SOliver Tappe                return InterlockedDecrement(&_M_refcount);
446f2ced752SOliver Tappe            }
447f2ced752SOliver Tappe#	elif defined(__STL_PTHREADS)
448f2ced752SOliver Tappe            // This should be portable, but performance is expected
449f2ced752SOliver Tappe            // to be quite awful.  This really needs platform specific
450f2ced752SOliver Tappe            // code.
451f2ced752SOliver Tappe            pthread_mutex_t _M_refcount_lock;
452f2ced752SOliver Tappe            void _M_init_refcount_lock() {
453f2ced752SOliver Tappe                pthread_mutex_init(&_M_refcount_lock, 0);
454f2ced752SOliver Tappe            }
455f2ced752SOliver Tappe            void _M_incr_refcount ()
456f2ced752SOliver Tappe            {
457f2ced752SOliver Tappe                pthread_mutex_lock(&_M_refcount_lock);
458f2ced752SOliver Tappe                ++_M_refcount;
459f2ced752SOliver Tappe                pthread_mutex_unlock(&_M_refcount_lock);
460f2ced752SOliver Tappe            }
461f2ced752SOliver Tappe            size_t _M_decr_refcount ()
462f2ced752SOliver Tappe            {
463f2ced752SOliver Tappe                size_t __result;
464f2ced752SOliver Tappe                pthread_mutex_lock(&_M_refcount_lock);
465f2ced752SOliver Tappe                __result = --_M_refcount;
466f2ced752SOliver Tappe                pthread_mutex_unlock(&_M_refcount_lock);
467f2ced752SOliver Tappe                return __result;
468f2ced752SOliver Tappe            }
469f2ced752SOliver Tappe#       else
470f2ced752SOliver Tappe            void _M_init_refcount_lock() {}
471f2ced752SOliver Tappe            void _M_incr_refcount ()
472f2ced752SOliver Tappe            {
473f2ced752SOliver Tappe                ++_M_refcount;
474f2ced752SOliver Tappe            }
475f2ced752SOliver Tappe            size_t _M_decr_refcount ()
476f2ced752SOliver Tappe            {
477f2ced752SOliver Tappe                --_M_refcount;
478f2ced752SOliver Tappe                return _M_refcount;
479f2ced752SOliver Tappe            }
480f2ced752SOliver Tappe#       endif
481f2ced752SOliver Tappe#   else
482f2ced752SOliver Tappe        void _M_incr_refcount () {}
483f2ced752SOliver Tappe#   endif
484f2ced752SOliver Tappe#   ifdef __STL_USE_STD_ALLOCATORS
485f2ced752SOliver Tappe        static void _S_free_string(__GC_CONST _CharT*, size_t __len,
486f2ced752SOliver Tappe                                   allocator_type __a);
487f2ced752SOliver Tappe#       define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l, __a);
488f2ced752SOliver Tappe#   else
489f2ced752SOliver Tappe        static void _S_free_string(__GC_CONST _CharT*, size_t __len);
490f2ced752SOliver Tappe#       define __STL_FREE_STRING(__s, __l, __a) _S_free_string(__s, __l);
491f2ced752SOliver Tappe#   endif
492f2ced752SOliver Tappe                        // Deallocate data section of a leaf.
493f2ced752SOliver Tappe                        // This shouldn't be a member function.
494f2ced752SOliver Tappe                        // But its hard to do anything else at the
495f2ced752SOliver Tappe                        // moment, because it's templatized w.r.t.
496f2ced752SOliver Tappe                        // an allocator.
497f2ced752SOliver Tappe                        // Does nothing if __GC is defined.
498f2ced752SOliver Tappe#   ifndef __GC
499f2ced752SOliver Tappe          void _M_free_c_string();
500f2ced752SOliver Tappe          void _M_free_tree();
501f2ced752SOliver Tappe                        // Deallocate t. Assumes t is not 0.
502f2ced752SOliver Tappe          void _M_unref_nonnil()
503f2ced752SOliver Tappe          {
504f2ced752SOliver Tappe              if (0 == _M_decr_refcount()) _M_free_tree();
505f2ced752SOliver Tappe          }
506f2ced752SOliver Tappe          void _M_ref_nonnil()
507f2ced752SOliver Tappe          {
508f2ced752SOliver Tappe              _M_incr_refcount();
509f2ced752SOliver Tappe          }
510f2ced752SOliver Tappe          static void _S_unref(_Rope_RopeRep* __t)
511f2ced752SOliver Tappe          {
512f2ced752SOliver Tappe              if (0 != __t) {
513f2ced752SOliver Tappe                  __t->_M_unref_nonnil();
514f2ced752SOliver Tappe              }
515f2ced752SOliver Tappe          }
516f2ced752SOliver Tappe          static void _S_ref(_Rope_RopeRep* __t)
517f2ced752SOliver Tappe          {
518f2ced752SOliver Tappe              if (0 != __t) __t->_M_incr_refcount();
519f2ced752SOliver Tappe          }
520f2ced752SOliver Tappe          static void _S_free_if_unref(_Rope_RopeRep* __t)
521f2ced752SOliver Tappe          {
522f2ced752SOliver Tappe              if (0 != __t && 0 == __t->_M_refcount) __t->_M_free_tree();
523f2ced752SOliver Tappe          }
524f2ced752SOliver Tappe#   else /* __GC */
525f2ced752SOliver Tappe          void _M_unref_nonnil() {}
526f2ced752SOliver Tappe          void _M_ref_nonnil() {}
527f2ced752SOliver Tappe          static void _S_unref(_Rope_RopeRep*) {}
528f2ced752SOliver Tappe          static void _S_ref(_Rope_RopeRep*) {}
529f2ced752SOliver Tappe          static void _S_free_if_unref(_Rope_RopeRep*) {}
530f2ced752SOliver Tappe#   endif
531f2ced752SOliver Tappe
532f2ced752SOliver Tappe};
533f2ced752SOliver Tappe
534f2ced752SOliver Tappetemplate<class _CharT, class _Alloc>
535f2ced752SOliver Tappestruct _Rope_RopeLeaf : public _Rope_RopeRep<_CharT,_Alloc> {
536f2ced752SOliver Tappe  public:
537f2ced752SOliver Tappe    // Apparently needed by VC++
538f2ced752SOliver Tappe    // The data fields of leaves are allocated with some
539f2ced752SOliver Tappe    // extra space, to accomodate future growth and for basic
540f2ced752SOliver Tappe    // character types, to hold a trailing eos character.
541f2ced752SOliver Tappe    enum { _S_alloc_granularity = 8 };
542f2ced752SOliver Tappe    static size_t _S_rounded_up_size(size_t __n) {
543f2ced752SOliver Tappe        size_t __size_with_eos;
544f2ced752SOliver Tappe
545f2ced752SOliver Tappe        if (_S_is_basic_char_type((_CharT*)0)) {
546f2ced752SOliver Tappe            __size_with_eos = __n + 1;
547f2ced752SOliver Tappe        } else {
548f2ced752SOliver Tappe            __size_with_eos = __n;
549f2ced752SOliver Tappe        }
550f2ced752SOliver Tappe#       ifdef __GC
551f2ced752SOliver Tappe           return __size_with_eos;
552f2ced752SOliver Tappe#       else
553f2ced752SOliver Tappe           // Allow slop for in-place expansion.
554f2ced752SOliver Tappe           return (__size_with_eos + _S_alloc_granularity-1)
555f2ced752SOliver Tappe                        &~ (_S_alloc_granularity-1);
556f2ced752SOliver Tappe#       endif
557f2ced752SOliver Tappe    }
558f2ced752SOliver Tappe    __GC_CONST _CharT* _M_data; /* Not necessarily 0 terminated. */
559f2ced752SOliver Tappe                                /* The allocated size is         */
560f2ced752SOliver Tappe                                /* _S_rounded_up_size(size), except */
561f2ced752SOliver Tappe                                /* in the GC case, in which it   */
562f2ced752SOliver Tappe                                /* doesn't matter.               */
563f2ced752SOliver Tappe    typedef _Rope_rep_base<_CharT,_Alloc>::allocator_type allocator_type;
564f2ced752SOliver Tappe    _Rope_RopeLeaf(__GC_CONST _CharT* __d, size_t __size, allocator_type __a)
565f2ced752SOliver Tappe        : _Rope_RopeRep<_CharT,_Alloc>(_S_leaf, 0, true, __size, __a),
566f2ced752SOliver Tappe	  _M_data(__d)
567f2ced752SOliver Tappe        {
568f2ced752SOliver Tappe        __stl_assert(__size > 0);
569f2ced752SOliver Tappe        if (_S_is_basic_char_type((_CharT *)0)) {
570f2ced752SOliver Tappe            // already eos terminated.
571f2ced752SOliver Tappe            _M_c_string = __d;
572f2ced752SOliver Tappe        }
573f2ced752SOliver Tappe    }
574f2ced752SOliver Tappe        // The constructor assumes that d has been allocated with
575f2ced752SOliver Tappe        // the proper allocator and the properly padded size.
576f2ced752SOliver Tappe        // In contrast, the destructor deallocates the data:
577f2ced752SOliver Tappe# ifndef __GC
578f2ced752SOliver Tappe    ~_Rope_RopeLeaf() {
579f2ced752SOliver Tappe        if (_M_data != _M_c_string) {
580f2ced752SOliver Tappe            _M_free_c_string();
581f2ced752SOliver Tappe        }
582f2ced752SOliver Tappe        __STL_FREE_STRING(_M_data, _M_size, get_allocator());
583f2ced752SOliver Tappe    }
584f2ced752SOliver Tappe# endif
585f2ced752SOliver Tappe};
586f2ced752SOliver Tappe
587f2ced752SOliver Tappetemplate<class _CharT, class _Alloc>
588f2ced752SOliver Tappestruct _Rope_RopeConcatenation : public _Rope_RopeRep<_CharT,_Alloc> {
589f2ced752SOliver Tappe  public:
590f2ced752SOliver Tappe    _Rope_RopeRep<_CharT,_Alloc>* _M_left;
591f2ced752SOliver Tappe    _Rope_RopeRep<_CharT,_Alloc>* _M_right;
592f2ced752SOliver Tappe    typedef _Rope_rep_base<_CharT,_Alloc>::allocator_type allocator_type;
593f2ced752SOliver Tappe    _Rope_RopeConcatenation(_Rope_RopeRep<_CharT,_Alloc>* __l,
594f2ced752SOliver Tappe                             _Rope_RopeRep<_CharT,_Alloc>* __r,
595f2ced752SOliver Tappe                             allocator_type __a)
596f2ced752SOliver Tappe      : _Rope_RopeRep<_CharT,_Alloc>(
597f2ced752SOliver Tappe          _S_concat, max(__l->_M_depth, __r->_M_depth) + 1, false,
598f2ced752SOliver Tappe          __l->_M_size + __r->_M_size, __a),
599f2ced752SOliver Tappe      _M_left(__l), _M_right(__r)
600f2ced752SOliver Tappe      {}
601f2ced752SOliver Tappe# ifndef __GC
602f2ced752SOliver Tappe    ~_Rope_RopeConcatenation() {
603f2ced752SOliver Tappe        _M_free_c_string();
604f2ced752SOliver Tappe        _M_left->_M_unref_nonnil();
605f2ced752SOliver Tappe        _M_right->_M_unref_nonnil();
606f2ced752SOliver Tappe    }
607f2ced752SOliver Tappe# endif
608f2ced752SOliver Tappe};
609f2ced752SOliver Tappe
610f2ced752SOliver Tappetemplate<class _CharT, class _Alloc>
611f2ced752SOliver Tappestruct _Rope_RopeFunction : public _Rope_RopeRep<_CharT,_Alloc> {
612f2ced752SOliver Tappe  public:
613f2ced752SOliver Tappe    char_producer<_CharT>* _M_fn;
614f2ced752SOliver Tappe#   ifndef __GC
615f2ced752SOliver Tappe      bool _M_delete_when_done; // Char_producer is owned by the
616f2ced752SOliver Tappe                                // rope and should be explicitly
617f2ced752SOliver Tappe                                // deleted when the rope becomes
618f2ced752SOliver Tappe                                // inaccessible.
619f2ced752SOliver Tappe#   else
620f2ced752SOliver Tappe      // In the GC case, we either register the rope for
621f2ced752SOliver Tappe      // finalization, or not.  Thus the field is unnecessary;
622f2ced752SOliver Tappe      // the information is stored in the collector data structures.
623f2ced752SOliver Tappe      // We do need a finalization procedure to be invoked by the
624f2ced752SOliver Tappe      // collector.
625f2ced752SOliver Tappe      static void _S_fn_finalization_proc(void * __tree, void *) {
626f2ced752SOliver Tappe        delete ((_Rope_RopeFunction *)__tree) -> _M_fn;
627f2ced752SOliver Tappe      }
628f2ced752SOliver Tappe#   endif
629f2ced752SOliver Tappe    typedef _Rope_rep_base<_CharT,_Alloc>::allocator_type allocator_type;
630f2ced752SOliver Tappe    _Rope_RopeFunction(char_producer<_CharT>* __f, size_t __size,
631f2ced752SOliver Tappe                        bool __d, allocator_type __a)
632f2ced752SOliver Tappe      :_Rope_RopeRep<_CharT,_Alloc>(_S_function, 0, true, __size, __a),
633f2ced752SOliver Tappe       _M_fn(__f)
634f2ced752SOliver Tappe#       ifndef __GC
635f2ced752SOliver Tappe      , _M_delete_when_done(__d)
636f2ced752SOliver Tappe#       endif
637f2ced752SOliver Tappe          {
638f2ced752SOliver Tappe        __stl_assert(__size > 0);
639f2ced752SOliver Tappe#       ifdef __GC
640f2ced752SOliver Tappe            if (__d) {
641f2ced752SOliver Tappe                GC_REGISTER_FINALIZER(
642f2ced752SOliver Tappe                  this, _Rope_RopeFunction::_S_fn_finalization_proc, 0, 0, 0);
643f2ced752SOliver Tappe            }
644f2ced752SOliver Tappe#       endif
645f2ced752SOliver Tappe    }
646f2ced752SOliver Tappe# ifndef __GC
647f2ced752SOliver Tappe    ~_Rope_RopeFunction() {
648f2ced752SOliver Tappe          _M_free_c_string();
649f2ced752SOliver Tappe          if (_M_delete_when_done) {
650f2ced752SOliver Tappe              delete _M_fn;
651f2ced752SOliver Tappe          }
652f2ced752SOliver Tappe    }
653f2ced752SOliver Tappe# endif
654f2ced752SOliver Tappe};
655f2ced752SOliver Tappe// Substring results are usually represented using just
656f2ced752SOliver Tappe// concatenation nodes.  But in the case of very long flat ropes
657f2ced752SOliver Tappe// or ropes with a functional representation that isn't practical.
658f2ced752SOliver Tappe// In that case, we represent the __result as a special case of
659f2ced752SOliver Tappe// RopeFunction, whose char_producer points back to the rope itself.
660f2ced752SOliver Tappe// In all cases except repeated substring operations and
661f2ced752SOliver Tappe// deallocation, we treat the __result as a RopeFunction.
662f2ced752SOliver Tappetemplate<class _CharT, class _Alloc>
663f2ced752SOliver Tappestruct _Rope_RopeSubstring : public _Rope_RopeFunction<_CharT,_Alloc>,
664f2ced752SOliver Tappe                             public char_producer<_CharT> {
665f2ced752SOliver Tappe  public:
666f2ced752SOliver Tappe    // XXX this whole class should be rewritten.
667f2ced752SOliver Tappe    _Rope_RopeRep<_CharT,_Alloc>* _M_base;      // not 0
668f2ced752SOliver Tappe    size_t _M_start;
669f2ced752SOliver Tappe    virtual void operator()(size_t __start_pos, size_t __req_len,
670f2ced752SOliver Tappe                            _CharT* __buffer) {
671f2ced752SOliver Tappe        switch(_M_base->_M_tag) {
672f2ced752SOliver Tappe            case _S_function:
673f2ced752SOliver Tappe            case _S_substringfn:
674f2ced752SOliver Tappe              {
675f2ced752SOliver Tappe                char_producer<_CharT>* __fn =
676f2ced752SOliver Tappe                        ((_Rope_RopeFunction<_CharT,_Alloc>*)_M_base)->_M_fn;
677f2ced752SOliver Tappe                __stl_assert(__start_pos + __req_len <= _M_size);
678f2ced752SOliver Tappe                __stl_assert(_M_start + _M_size <= _M_base->_M_size);
679f2ced752SOliver Tappe                (*__fn)(__start_pos + _M_start, __req_len, __buffer);
680f2ced752SOliver Tappe              }
681f2ced752SOliver Tappe              break;
682f2ced752SOliver Tappe            case _S_leaf:
683f2ced752SOliver Tappe              {
684f2ced752SOliver Tappe                __GC_CONST _CharT* __s =
685f2ced752SOliver Tappe                        ((_Rope_RopeLeaf<_CharT,_Alloc>*)_M_base)->_M_data;
686f2ced752SOliver Tappe                uninitialized_copy_n(__s + __start_pos + _M_start, __req_len,
687f2ced752SOliver Tappe                                     __buffer);
688f2ced752SOliver Tappe              }
689f2ced752SOliver Tappe              break;
690f2ced752SOliver Tappe            default:
691f2ced752SOliver Tappe              __stl_assert(false);
692f2ced752SOliver Tappe        }
693f2ced752SOliver Tappe    }
694f2ced752SOliver Tappe    typedef _Rope_rep_base<_CharT,_Alloc>::allocator_type allocator_type;
695f2ced752SOliver Tappe    _Rope_RopeSubstring(_Rope_RopeRep<_CharT,_Alloc>* __b, size_t __s,
696f2ced752SOliver Tappe                          size_t __l, allocator_type __a)
697f2ced752SOliver Tappe      : _Rope_RopeFunction<_CharT,_Alloc>(this, __l, false, __a), _M_base(__b)
698f2ced752SOliver Tappe      , _M_start(__s)
699f2ced752SOliver Tappe    {
700f2ced752SOliver Tappe        __stl_assert(__l > 0);
701f2ced752SOliver Tappe        __stl_assert(__s + __l <= __b->_M_size);
702f2ced752SOliver Tappe#       ifndef __GC
703f2ced752SOliver Tappe            _M_base->_M_ref_nonnil();
704f2ced752SOliver Tappe#       endif
705f2ced752SOliver Tappe        _M_tag = _S_substringfn;
706f2ced752SOliver Tappe    }
707f2ced752SOliver Tappe    virtual ~_Rope_RopeSubstring()
708f2ced752SOliver Tappe      {
709f2ced752SOliver Tappe#       ifndef __GC
710f2ced752SOliver Tappe          _M_base->_M_unref_nonnil();
711f2ced752SOliver Tappe          // _M_free_c_string();  -- done by parent class
712f2ced752SOliver Tappe#       endif
713f2ced752SOliver Tappe      }
714f2ced752SOliver Tappe};
715f2ced752SOliver Tappe
716f2ced752SOliver Tappe
717f2ced752SOliver Tappe// Self-destructing pointers to Rope_rep.
718f2ced752SOliver Tappe// These are not conventional smart pointers.  Their
719f2ced752SOliver Tappe// only purpose in life is to ensure that unref is called
720f2ced752SOliver Tappe// on the pointer either at normal exit or if an exception
721f2ced752SOliver Tappe// is raised.  It is the caller's responsibility to
722f2ced752SOliver Tappe// adjust reference counts when these pointers are initialized
723f2ced752SOliver Tappe// or assigned to.  (This convention significantly reduces
724f2ced752SOliver Tappe// the number of potentially expensive reference count
725f2ced752SOliver Tappe// updates.)
726f2ced752SOliver Tappe#ifndef __GC
727f2ced752SOliver Tappe  template<class _CharT, class _Alloc>
728f2ced752SOliver Tappe  struct _Rope_self_destruct_ptr {
729f2ced752SOliver Tappe    _Rope_RopeRep<_CharT,_Alloc>* _M_ptr;
730f2ced752SOliver Tappe    ~_Rope_self_destruct_ptr()
731f2ced752SOliver Tappe      { _Rope_RopeRep<_CharT,_Alloc>::_S_unref(_M_ptr); }
732f2ced752SOliver Tappe#   ifdef __STL_USE_EXCEPTIONS
733f2ced752SOliver Tappe        _Rope_self_destruct_ptr() : _M_ptr(0) {};
734f2ced752SOliver Tappe#   else
735f2ced752SOliver Tappe        _Rope_self_destruct_ptr() {};
736f2ced752SOliver Tappe#   endif
737f2ced752SOliver Tappe    _Rope_self_destruct_ptr(_Rope_RopeRep<_CharT,_Alloc>* __p) : _M_ptr(__p) {}
738f2ced752SOliver Tappe    _Rope_RopeRep<_CharT,_Alloc>& operator*() { return *_M_ptr; }