| 4680 |
right-hear |
1 |
/* |
|
|
2 |
* Copyright (c) 1997 |
|
|
3 |
* Silicon Graphics Computer Systems, Inc. |
|
|
4 |
* |
|
|
5 |
* Permission to use, copy, modify, distribute and sell this software |
|
|
6 |
* and its documentation for any purpose is hereby granted without fee, |
|
|
7 |
* provided that the above copyright notice appear in all copies and |
|
|
8 |
* that both that copyright notice and this permission notice appear |
|
|
9 |
* in supporting documentation. Silicon Graphics makes no |
|
|
10 |
* representations about the suitability of this software for any |
|
|
11 |
* purpose. It is provided "as is" without express or implied warranty. |
|
|
12 |
*/ |
|
|
13 |
|
|
|
14 |
/* NOTE: This is an internal header file, included by other STL headers. |
|
|
15 |
* You should not attempt to use it directly. |
|
|
16 |
*/ |
|
|
17 |
|
|
|
18 |
#include |
|
|
19 |
#include |
|
|
20 |
|
|
|
21 |
#ifdef __STL_USE_EXCEPTIONS |
|
|
22 |
# include |
|
|
23 |
#endif |
|
|
24 |
|
|
|
25 |
namespace std |
|
|
26 |
{ |
|
|
27 |
|
|
|
28 |
// Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf |
|
|
29 |
// if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct. |
|
|
30 |
// Results in a valid buf_ptr if the iterator can be legitimately |
|
|
31 |
// dereferenced. |
|
|
32 |
template |
|
|
33 |
void _Rope_iterator_base<_CharT,_Alloc>::_S_setbuf( |
|
|
34 |
_Rope_iterator_base<_CharT,_Alloc>& __x) |
|
|
35 |
{ |
|
|
36 |
const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index]; |
|
|
37 |
size_t __leaf_pos = __x._M_leaf_pos; |
|
|
38 |
size_t __pos = __x._M_current_pos; |
|
|
39 |
|
|
|
40 |
switch(__leaf->_M_tag) { |
|
|
41 |
case _RopeRep::_S_leaf: |
|
|
42 |
__x._M_buf_start = |
|
|
43 |
((_Rope_RopeLeaf<_CharT,_Alloc>*)__leaf)->_M_data; |
|
|
44 |
__x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos); |
|
|
45 |
__x._M_buf_end = __x._M_buf_start + __leaf->_M_size; |
|
|
46 |
break; |
|
|
47 |
case _RopeRep::_S_function: |
|
|
48 |
case _RopeRep::_S_substringfn: |
|
|
49 |
{ |
|
|
50 |
size_t __len = _S_iterator_buf_len; |
|
|
51 |
size_t __buf_start_pos = __leaf_pos; |
|
|
52 |
size_t __leaf_end = __leaf_pos + __leaf->_M_size; |
|
|
53 |
char_producer<_CharT>* __fn = |
|
|
54 |
((_Rope_RopeFunction<_CharT,_Alloc>*)__leaf)->_M_fn; |
|
|
55 |
|
|
|
56 |
if (__buf_start_pos + __len <= __pos) { |
|
|
57 |
__buf_start_pos = __pos - __len/4; |
|
|
58 |
if (__buf_start_pos + __len > __leaf_end) { |
|
|
59 |
__buf_start_pos = __leaf_end - __len; |
|
|
60 |
} |
|
|
61 |
} |
|
|
62 |
if (__buf_start_pos + __len > __leaf_end) { |
|
|
63 |
__len = __leaf_end - __buf_start_pos; |
|
|
64 |
} |
|
|
65 |
(*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf); |
|
|
66 |
__x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos); |
|
|
67 |
__x._M_buf_start = __x._M_tmp_buf; |
|
|
68 |
__x._M_buf_end = __x._M_tmp_buf + __len; |
|
|
69 |
} |
|
|
70 |
break; |
|
|
71 |
default: |
|
|
72 |
__stl_assert(0); |
|
|
73 |
} |
|
|
74 |
} |
|
|
75 |
|
|
|
76 |
// Set path and buffer inside a rope iterator. We assume that |
|
|
77 |
// pos and root are already set. |
|
|
78 |
template |
|
|
79 |
void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache |
|
|
80 |
(_Rope_iterator_base<_CharT,_Alloc>& __x) |
|
|
81 |
{ |
|
|
82 |
const _RopeRep* __path[_RopeRep::_S_max_rope_depth+1]; |
|
|
83 |
const _RopeRep* __curr_rope; |
|
|
84 |
int __curr_depth = -1; /* index into path */ |
|
|
85 |
size_t __curr_start_pos = 0; |
|
|
86 |
size_t __pos = __x._M_current_pos; |
|
|
87 |
unsigned char __dirns = 0; // Bit vector marking right turns in the path |
|
|
88 |
|
|
|
89 |
__stl_assert(__pos <= __x._M_root->_M_size); |
|
|
90 |
if (__pos >= __x._M_root->_M_size) { |
|
|
91 |
__x._M_buf_ptr = 0; |
|
|
92 |
return; |
|
|
93 |
} |
|
|
94 |
__curr_rope = __x._M_root; |
|
|
95 |
if (0 != __curr_rope->_M_c_string) { |
|
|
96 |
/* Treat the root as a leaf. */ |
|
|
97 |
__x._M_buf_start = __curr_rope->_M_c_string; |
|
|
98 |
__x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size; |
|
|
99 |
__x._M_buf_ptr = __curr_rope->_M_c_string + __pos; |
|
|
100 |
__x._M_path_end[0] = __curr_rope; |
|
|
101 |
__x._M_leaf_index = 0; |
|
|
102 |
__x._M_leaf_pos = 0; |
|
|
103 |
return; |
|
|
104 |
} |
|
|
105 |
for(;;) { |
|
|
106 |
++__curr_depth; |
|
|
107 |
__stl_assert(__curr_depth <= _RopeRep::_S_max_rope_depth); |
|
|
108 |
__path[__curr_depth] = __curr_rope; |
|
|
109 |
switch(__curr_rope->_M_tag) { |
|
|
110 |
case _RopeRep::_S_leaf: |
|
|
111 |
case _RopeRep::_S_function: |
|
|
112 |
case _RopeRep::_S_substringfn: |
|
|
113 |
__x._M_leaf_pos = __curr_start_pos; |
|
|
114 |
goto done; |
|
|
115 |
case _RopeRep::_S_concat: |
|
|
116 |
{ |
|
|
117 |
_Rope_RopeConcatenation<_CharT,_Alloc>* __c = |
|
|
118 |
(_Rope_RopeConcatenation<_CharT,_Alloc>*)__curr_rope; |
|
|
119 |
_RopeRep* __left = __c->_M_left; |
|
|
120 |
size_t __left_len = __left->_M_size; |
|
|
121 |
|
|
|
122 |
__dirns <<= 1; |
|
|
123 |
if (__pos >= __curr_start_pos + __left_len) { |
|
|
124 |
__dirns |= 1; |
|
|
125 |
__curr_rope = __c->_M_right; |
|
|
126 |
__curr_start_pos += __left_len; |
|
|
127 |
} else { |
|
|
128 |
__curr_rope = __left; |
|
|
129 |
} |
|
|
130 |
} |
|
|
131 |
break; |
|
|
132 |
} |
|
|
133 |
} |
|
|
134 |
done: |
|
|
135 |
// Copy last section of path into _M_path_end. |
|
|
136 |
{ |
|
|
137 |
int __i = -1; |
|
|
138 |
int __j = __curr_depth + 1 - _S_path_cache_len; |
|
|
139 |
|
|
|
140 |
if (__j < 0) __j = 0; |
|
|
141 |
while (__j <= __curr_depth) { |
|
|
142 |
__x._M_path_end[++__i] = __path[__j++]; |
|
|
143 |
} |
|
|
144 |
__x._M_leaf_index = __i; |
|
|
145 |
} |
|
|
146 |
__x._M_path_directions = __dirns; |
|
|
147 |
_S_setbuf(__x); |
|
|
148 |
} |
|
|
149 |
|
|
|
150 |
// Specialized version of the above. Assumes that |
|
|
151 |
// the path cache is valid for the previous position. |
|
|
152 |
template |
|
|
153 |
void _Rope_iterator_base<_CharT,_Alloc>::_S_setcache_for_incr |
|
|
154 |
(_Rope_iterator_base<_CharT,_Alloc>& __x) |
|
|
155 |
{ |
|
|
156 |
int __current_index = __x._M_leaf_index; |
|
|
157 |
const _RopeRep* __current_node = __x._M_path_end[__current_index]; |
|
|
158 |
size_t __len = __current_node->_M_size; |
|
|
159 |
size_t __node_start_pos = __x._M_leaf_pos; |
|
|
160 |
unsigned char __dirns = __x._M_path_directions; |
|
|
161 |
_Rope_RopeConcatenation<_CharT,_Alloc>* __c; |
|
|
162 |
|
|
|
163 |
__stl_assert(__x._M_current_pos <= __x._M_root->_M_size); |
|
|
164 |
if (__x._M_current_pos - __node_start_pos < __len) { |
|
|
165 |
/* More stuff in this leaf, we just didn't cache it. */ |
|
|
166 |
_S_setbuf(__x); |
|
|
167 |
return; |
|
|
168 |
} |
|
|
169 |
__stl_assert(__node_start_pos + __len == __x._M_current_pos); |
|
|
170 |
// node_start_pos is starting position of last_node. |
|
|
171 |
while (--__current_index >= 0) { |
|
|
172 |
if (!(__dirns & 1) /* Path turned left */) |
|
|
173 |
break; |
|
|
174 |
__current_node = __x._M_path_end[__current_index]; |
|
|
175 |
__c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node; |
|
|
176 |
// Otherwise we were in the right child. Thus we should pop |
|
|
177 |
// the concatenation node. |
|
|
178 |
__node_start_pos -= __c->_M_left->_M_size; |
|
|
179 |
__dirns >>= 1; |
|
|
180 |
} |
|
|
181 |
if (__current_index < 0) { |
|
|
182 |
// We underflowed the cache. Punt. |
|
|
183 |
_S_setcache(__x); |
|
|
184 |
return; |
|
|
185 |
} |
|
|
186 |
__current_node = __x._M_path_end[__current_index]; |
|
|
187 |
__c = (_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node; |
|
|
188 |
// current_node is a concatenation node. We are positioned on the first |
|
|
189 |
// character in its right child. |
|
|
190 |
// node_start_pos is starting position of current_node. |
|
|
191 |
__node_start_pos += __c->_M_left->_M_size; |
|
|
192 |
__current_node = __c->_M_right; |
|
|
193 |
__x._M_path_end[++__current_index] = __current_node; |
|
|
194 |
__dirns |= 1; |
|
|
195 |
while (_RopeRep::_S_concat == __current_node->_M_tag) { |
|
|
196 |
++__current_index; |
|
|
197 |
if (_S_path_cache_len == __current_index) { |
|
|
198 |
int __i; |
|
|
199 |
for (__i = 0; __i < _S_path_cache_len-1; __i++) { |
|
|
200 |
__x._M_path_end[__i] = __x._M_path_end[__i+1]; |
|
|
201 |
} |
|
|
202 |
--__current_index; |
|
|
203 |
} |
|
|
204 |
__current_node = |
|
|
205 |
((_Rope_RopeConcatenation<_CharT,_Alloc>*)__current_node)->_M_left; |
|
|
206 |
__x._M_path_end[__current_index] = __current_node; |
|
|
207 |
__dirns <<= 1; |
|
|
208 |
// node_start_pos is unchanged. |
|
|
209 |
} |
|
|
210 |
__x._M_leaf_index = __current_index; |
|
|
211 |
__x._M_leaf_pos = __node_start_pos; |
|
|
212 |
__x._M_path_directions = __dirns; |
|
|
213 |
_S_setbuf(__x); |
|
|
214 |
} |
|
|
215 |
|
|
|
216 |
template |
|
|
217 |
void _Rope_iterator_base<_CharT,_Alloc>::_M_incr(size_t __n) { |
|
|
218 |
_M_current_pos += __n; |
|
|
219 |
if (0 != _M_buf_ptr) { |
|
|
220 |
size_t __chars_left = _M_buf_end - _M_buf_ptr; |
|
|
221 |
if (__chars_left > __n) { |
|
|
222 |
_M_buf_ptr += __n; |
|
|
223 |
} else if (__chars_left == __n) { |
|
|
224 |
_M_buf_ptr += __n; |
|
|
225 |
_S_setcache_for_incr(*this); |
|
|
226 |
} else { |
|
|
227 |
_M_buf_ptr = 0; |
|
|
228 |
} |
|
|
229 |
} |
|
|
230 |
} |
|
|
231 |
|
|
|
232 |
template |
|
|
233 |
void _Rope_iterator_base<_CharT,_Alloc>::_M_decr(size_t __n) { |
|
|
234 |
if (0 != _M_buf_ptr) { |
|
|
235 |
size_t __chars_left = _M_buf_ptr - _M_buf_start; |
|
|
236 |
if (__chars_left >= __n) { |
|
|
237 |
_M_buf_ptr -= __n; |
|
|
238 |
} else { |
|
|
239 |
_M_buf_ptr = 0; |
|
|
240 |
} |
|
|
241 |
} |
|
|
242 |
_M_current_pos -= __n; |
|
|
243 |
} |
|
|
244 |
|
|
|
245 |
template |
|
|
246 |
void _Rope_iterator<_CharT,_Alloc>::_M_check() { |
|
|
247 |
if (_M_root_rope->_M_tree_ptr != _M_root) { |
|
|
248 |
// _Rope was modified. Get things fixed up. |
|
|
249 |
_RopeRep::_S_unref(_M_root); |
|
|
250 |
_M_root = _M_root_rope->_M_tree_ptr; |
|
|
251 |
_RopeRep::_S_ref(_M_root); |
|
|
252 |
_M_buf_ptr = 0; |
|
|
253 |
} |
|
|
254 |
} |
|
|
255 |
|
|
|
256 |
template |
|
|
257 |
inline |
|
|
258 |
_Rope_const_iterator<_CharT, _Alloc>::_Rope_const_iterator( |
|
|
259 |
const _Rope_iterator<_CharT,_Alloc>& __x) |
|
|
260 |
: _Rope_iterator_base<_CharT,_Alloc>(__x) |
|
|
261 |
{ } |
|
|
262 |
|
|
|
263 |
template |
|
|
264 |
inline _Rope_iterator<_CharT,_Alloc>::_Rope_iterator( |
|
|
265 |
rope<_CharT,_Alloc>& __r, size_t __pos) |
|
|
266 |
: _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos), |
|
|
267 |
_M_root_rope(&__r) |
|
|
268 |
{ |
|
|
269 |
_RopeRep::_S_ref(_M_root); |
|
|
270 |
} |
|
|
271 |
|
|
|
272 |
template |
|
|
273 |
inline size_t |
|
|
274 |
rope<_CharT,_Alloc>::_S_char_ptr_len(const _CharT* __s) |
|
|
275 |
{ |
|
|
276 |
const _CharT* __p = __s; |
|
|
277 |
|
|
|
278 |
while (!_S_is0(*__p)) { ++__p; } |
|
|
279 |
return (__p - __s); |
|
|
280 |
} |
|
|
281 |
|
|
|
282 |
|
|
|
283 |
#ifndef __GC |
|
|
284 |
|
|
|
285 |
template |
|
|
286 |
inline void _Rope_RopeRep<_CharT,_Alloc>::_M_free_c_string() |
|
|
287 |
{ |
|
|
288 |
_CharT* __cstr = _M_c_string; |
|
|
289 |
if (0 != __cstr) { |
|
|
290 |
size_t __size = _M_size + 1; |
|
|
291 |
destroy(__cstr, __cstr + __size); |
|
|
292 |
_Data_deallocate(__cstr, __size); |
|
|
293 |
} |
|
|
294 |
} |
|
|
295 |
|
|
|
296 |
|
|
|
297 |
template |
|
|
298 |
inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string(_CharT* __s, |
|
|
299 |
size_t __n, |
|
|
300 |
allocator_type __a) |
|
|
301 |
{ |
|
|
302 |
if (!_S_is_basic_char_type((_CharT*)0)) { |
|
|
303 |
destroy(__s, __s + __n); |
|
|
304 |
} |
|
|
305 |
// This has to be a static member, so this gets a bit messy |
|
|
306 |
__a.deallocate( |
|
|
307 |
__s, _Rope_RopeLeaf<_CharT,_Alloc>::_S_rounded_up_size(__n)); |
|
|
308 |
} |
|
|
309 |
|
|
|
310 |
|
|
|
311 |
// There are several reasons for not doing this with virtual destructors |
|
|
312 |
// and a class specific delete operator: |
|
|
313 |
// - A class specific delete operator can't easily get access to |
|
|
314 |
// allocator instances if we need them. |
|
|
315 |
// - Any virtual function would need a 4 or byte vtable pointer; |
|
|
316 |
// this only requires a one byte tag per object. |
|
|
317 |
template |
|
|
318 |
void _Rope_RopeRep<_CharT,_Alloc>::_M_free_tree() |
|
|
319 |
{ |
|
|
320 |
switch(_M_tag) { |
|
|
321 |
case _S_leaf: |
|
|
322 |
{ |
|
|
323 |
_Rope_RopeLeaf<_CharT,_Alloc>* __l |
|
|
324 |
= (_Rope_RopeLeaf<_CharT,_Alloc>*)this; |
|
|
325 |
__l->_Rope_RopeLeaf<_CharT,_Alloc>::~_Rope_RopeLeaf(); |
|
|
326 |
_L_deallocate(__l, 1); |
|
|
327 |
break; |
|
|
328 |
} |
|
|
329 |
case _S_concat: |
|
|
330 |
{ |
|
|
331 |
_Rope_RopeConcatenation<_CharT,_Alloc>* __c |
|
|
332 |
= (_Rope_RopeConcatenation<_CharT,_Alloc>*)this; |
|
|
333 |
__c->_Rope_RopeConcatenation<_CharT,_Alloc>:: |
|
|
334 |
~_Rope_RopeConcatenation(); |
|
|
335 |
_C_deallocate(__c, 1); |
|
|
336 |
break; |
|
|
337 |
} |
|
|
338 |
case _S_function: |
|
|
339 |
{ |
|
|
340 |
_Rope_RopeFunction<_CharT,_Alloc>* __f |
|
|
341 |
= (_Rope_RopeFunction<_CharT,_Alloc>*)this; |
|
|
342 |
__f->_Rope_RopeFunction<_CharT,_Alloc>::~_Rope_RopeFunction(); |
|
|
343 |
_F_deallocate(__f, 1); |
|
|
344 |
break; |
|
|
345 |
} |
|
|
346 |
case _S_substringfn: |
|
|
347 |
{ |
|
|
348 |
_Rope_RopeSubstring<_CharT,_Alloc>* __ss = |
|
|
349 |
(_Rope_RopeSubstring<_CharT,_Alloc>*)this; |
|
|
350 |
__ss->_Rope_RopeSubstring<_CharT,_Alloc>:: |
|
|
351 |
~_Rope_RopeSubstring(); |
|
|
352 |
_S_deallocate(__ss, 1); |
|
|
353 |
break; |
|
|
354 |
} |
|
|
355 |
} |
|
|
356 |
} |
|
|
357 |
#else |
|
|
358 |
|
|
|
359 |
template |
|
|
360 |
inline void _Rope_RopeRep<_CharT,_Alloc>::_S_free_string |
|
|
361 |
(const _CharT*, size_t, allocator_type) |
|
|
362 |
{} |
|
|
363 |
|
|
|
364 |
#endif |
|
|
365 |
|
|
|
366 |
|
|
|
367 |
// Concatenate a C string onto a leaf rope by copying the rope data. |
|
|
368 |
// Used for short ropes. |
|
|
369 |
template |
|
|
370 |
rope<_CharT,_Alloc>::_RopeLeaf* |
|
|
371 |
rope<_CharT,_Alloc>::_S_leaf_concat_char_iter |
|
|
372 |
(_RopeLeaf* __r, const _CharT* __iter, size_t __len) |
|
|
373 |
{ |
|
|
374 |
size_t __old_len = __r->_M_size; |
|
|
375 |
_CharT* __new_data = (_CharT*) |
|
|
376 |
_Data_allocate(_S_rounded_up_size(__old_len + __len)); |
|
|
377 |
_RopeLeaf* __result; |
|
|
378 |
|
|
|
379 |
uninitialized_copy_n(__r->_M_data, __old_len, __new_data); |
|
|
380 |
uninitialized_copy_n(__iter, __len, __new_data + __old_len); |
|
|
381 |
_S_cond_store_eos(__new_data[__old_len + __len]); |
|
|
382 |
__STL_TRY { |
|
|
383 |
__result = _S_new_RopeLeaf(__new_data, __old_len + __len, |
|
|
384 |
__r->get_allocator()); |
|
|
385 |
} |
|
|
386 |
__STL_UNWIND(_RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len, |
|
|
387 |
__r->get_allocator())); |
|
|
388 |
return __result; |
|
|
389 |
} |
|
|
390 |
|
|
|
391 |
#ifndef __GC |
|
|
392 |
// As above, but it's OK to clobber original if refcount is 1 |
|
|
393 |
template |
|
|
394 |
rope<_CharT,_Alloc>::_RopeLeaf* |
|
|
395 |
rope<_CharT,_Alloc>::_S_destr_leaf_concat_char_iter |
|
|
396 |
(_RopeLeaf* __r, const _CharT* __iter, size_t __len) |
|
|
397 |
{ |
|
|
398 |
__stl_assert(__r->_M_ref_count >= 1); |
|
|
399 |
if (__r->_M_ref_count > 1) |
|
|
400 |
return _S_leaf_concat_char_iter(__r, __iter, __len); |
|
|
401 |
size_t __old_len = __r->_M_size; |
|
|
402 |
if (_S_allocated_capacity(__old_len) >= __old_len + __len) { |
|
|
403 |
// The space has been partially initialized for the standard |
|
|
404 |
// character types. But that doesn't matter for those types. |
|
|
405 |
uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len); |
|
|
406 |
if (_S_is_basic_char_type((_CharT*)0)) { |
|
|
407 |
_S_cond_store_eos(__r->_M_data[__old_len + __len]); |
|
|
408 |
__stl_assert(__r->_M_c_string == __r->_M_data); |
|
|
409 |
} else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) { |
|
|
410 |
__r->_M_free_c_string(); |
|
|
411 |
__r->_M_c_string = 0; |
|
|
412 |
} |
|
|
413 |
__r->_M_size = __old_len + __len; |
|
|
414 |
__stl_assert(__r->_M_ref_count == 1); |
|
|
415 |
__r->_M_ref_count = 2; |
|
|
416 |
return __r; |
|
|
417 |
} else { |
|
|
418 |
_RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len); |
|
|
419 |
__stl_assert(__result->_M_ref_count == 1); |
|
|
420 |
return __result; |
|
|
421 |
} |
|
|
422 |
} |
|
|
423 |
#endif |
|
|
424 |
|
|
|
425 |
// Assumes left and right are not 0. |
|
|
426 |
// Does not increment (nor decrement on exception) child reference counts. |
|
|
427 |
// Result has ref count 1. |
|
|
428 |
template |
|
|
429 |
rope<_CharT,_Alloc>::_RopeRep* |
|
|
430 |
rope<_CharT,_Alloc>::_S_tree_concat (_RopeRep* __left, _RopeRep* __right) |
|
|
431 |
{ |
|
|
432 |
_RopeConcatenation* __result = |
|
|
433 |
_S_new_RopeConcatenation(__left, __right, __left->get_allocator()); |
|
|
434 |
size_t __depth = __result->_M_depth; |
|
|
435 |
|
|
|
436 |
__stl_assert(__left->get_allocator() == __right->get_allocator()); |
|
|
437 |
if (__depth > 20 && (__result->_M_size < 1000 || |
|
|
438 |
__depth > _RopeRep::_S_max_rope_depth)) { |
|
|
439 |
_RopeRep* __balanced; |
|
|
440 |
|
|
|
441 |
__STL_TRY { |
|
|
442 |
__balanced = _S_balance(__result); |
|
|
443 |
# ifndef __GC |
|
|
444 |
if (__result != __balanced) { |
|
|
445 |
__stl_assert(1 == __result->_M_ref_count |
|
|
446 |
&& 1 == __balanced->_M_ref_count); |
|
|
447 |
} |
|
|
448 |
# endif |
|
|
449 |
__result->_M_unref_nonnil(); |
|
|
450 |
} |
|
|
451 |
__STL_UNWIND((_C_deallocate(__result,1))); |
|
|
452 |
// In case of exception, we need to deallocate |
|
|
453 |
// otherwise dangling result node. But caller |
|
|
454 |
// still owns its children. Thus unref is |
|
|
455 |
// inappropriate. |
|
|
456 |
return __balanced; |
|
|
457 |
} else { |
|
|
458 |
return __result; |
|
|
459 |
} |
|
|
460 |
} |
|
|
461 |
|
|
|
462 |
template |
|
|
463 |
rope<_CharT,_Alloc>::_RopeRep* rope<_CharT,_Alloc>::_S_concat_char_iter |
|
|
464 |
(_RopeRep* __r, const _CharT*__s, size_t __slen) |
|
|
465 |
{ |
|
|
466 |
_RopeRep* __result; |
|
|
467 |
if (0 == __slen) { |
|
|
468 |
_S_ref(__r); |
|
|
469 |
return __r; |
|
|
470 |
} |
|
|
471 |
if (0 == __r) |
|
|
472 |
return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, |
|
|
473 |
__r->get_allocator()); |
|
|
474 |
if (_RopeRep::_S_leaf == __r->_M_tag && |
|
|
475 |
__r->_M_size + __slen <= _S_copy_max) { |
|
|
476 |
__result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); |
|
|
477 |
# ifndef __GC |
|
|
478 |
__stl_assert(1 == __result->_M_ref_count); |
|
|
479 |
# endif |
|
|
480 |
return __result; |
|
|
481 |
} |
|
|
482 |
if (_RopeRep::_S_concat == __r->_M_tag |
|
|
483 |
&& _RopeRep::_S_leaf == ((_RopeConcatenation*)__r)->_M_right->_M_tag) { |
|
|
484 |
_RopeLeaf* __right = |
|
|
485 |
(_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right); |
|
|
486 |
if (__right->_M_size + __slen <= _S_copy_max) { |
|
|
487 |
_RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left; |
|
|
488 |
_RopeRep* __nright = |
|
|
489 |
_S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen); |
|
|
490 |
__left->_M_ref_nonnil(); |
|
|
491 |
__STL_TRY { |
|
|
492 |
__result = _S_tree_concat(__left, __nright); |
|
|
493 |
} |
|
|
494 |
__STL_UNWIND(_S_unref(__left); _S_unref(__nright)); |
|
|
495 |
# ifndef __GC |
|
|
496 |
__stl_assert(1 == __result->_M_ref_count); |
|
|
497 |
# endif |
|
|
498 |
return __result; |
|
|
499 |
} |
|
|
500 |
} |
|
|
501 |
_RopeRep* __nright = |
|
|
502 |
__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); |
|
|
503 |
__STL_TRY { |
|
|
504 |
__r->_M_ref_nonnil(); |
|
|
505 |
__result = _S_tree_concat(__r, __nright); |
|
|
506 |
} |
|
|
507 |
__STL_UNWIND(_S_unref(__r); _S_unref(__nright)); |
|
|
508 |
# ifndef __GC |
|
|
509 |
__stl_assert(1 == __result->_M_ref_count); |
|
|
510 |
# endif |
|
|
511 |
return __result; |
|
|
512 |
} |
|
|
513 |
|
|
|
514 |
#ifndef __GC |
|
|
515 |
template |
|
|
516 |
rope<_CharT,_Alloc>::_RopeRep* |
|
|
517 |
rope<_CharT,_Alloc>::_S_destr_concat_char_iter( |
|
|
518 |
_RopeRep* __r, const _CharT* __s, size_t __slen) |
|
|
519 |
{ |
|
|
520 |
_RopeRep* __result; |
|
|
521 |
if (0 == __r) |
|
|
522 |
return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, |
|
|
523 |
__r->get_allocator()); |
|
|
524 |
size_t __count = __r->_M_ref_count; |
|
|
525 |
size_t __orig_size = __r->_M_size; |
|
|
526 |
__stl_assert(__count >= 1); |
|
|
527 |
if (__count > 1) return _S_concat_char_iter(__r, __s, __slen); |
|
|
528 |
if (0 == __slen) { |
|
|
529 |
__r->_M_ref_count = 2; // One more than before |
|
|
530 |
return __r; |
|
|
531 |
} |
|
|
532 |
if (__orig_size + __slen <= _S_copy_max && |
|
|
533 |
_RopeRep::_S_leaf == __r->_M_tag) { |
|
|
534 |
__result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); |
|
|
535 |
return __result; |
|
|
536 |
} |
|
|
537 |
if (_RopeRep::_S_concat == __r->_M_tag) { |
|
|
538 |
_RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*)__r)->_M_right); |
|
|
539 |
if (_RopeRep::_S_leaf == __right->_M_tag |
|
|
540 |
&& __right->_M_size + __slen <= _S_copy_max) { |
|
|
541 |
_RopeRep* __new_right = |
|
|
542 |
_S_destr_leaf_concat_char_iter(__right, __s, __slen); |
|
|
543 |
if (__right == __new_right) { |
|
|
544 |
__stl_assert(__new_right->_M_ref_count == 2); |
|
|
545 |
__new_right->_M_ref_count = 1; |
|
|
546 |
} else { |
|
|
547 |
__stl_assert(__new_right->_M_ref_count >= 1); |
|
|
548 |
__right->_M_unref_nonnil(); |
|
|
549 |
} |
|
|
550 |
__stl_assert(__r->_M_ref_count == 1); |
|
|
551 |
__r->_M_ref_count = 2; // One more than before. |
|
|
552 |
((_RopeConcatenation*)__r)->_M_right = __new_right; |
|
|
553 |
__r->_M_size = __orig_size + __slen; |
|
|
554 |
if (0 != __r->_M_c_string) { |
|
|
555 |
__r->_M_free_c_string(); |
|
|
556 |
__r->_M_c_string = 0; |
|
|
557 |
} |
|
|
558 |
return __r; |
|
|
559 |
} |
|
|
560 |
} |
|
|
561 |
_RopeRep* __right = |
|
|
562 |
__STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); |
|
|
563 |
__r->_M_ref_nonnil(); |
|
|
564 |
__STL_TRY { |
|
|
565 |
__result = _S_tree_concat(__r, __right); |
|
|
566 |
} |
|
|
567 |
__STL_UNWIND(_S_unref(__r); _S_unref(__right)) |
|
|
568 |
__stl_assert(1 == __result->_M_ref_count); |
|
|
569 |
return __result; |
|
|
570 |
} |
|
|
571 |
#endif /* !__GC */ |
|
|
572 |
|
|
|
573 |
template |
|
|
574 |
rope<_CharT,_Alloc>::_RopeRep* |
|
|
575 |
rope<_CharT,_Alloc>::_S_concat(_RopeRep* __left, _RopeRep* __right) |
|
|
576 |
{ |
|
|
577 |
if (0 == __left) { |
|
|
578 |
_S_ref(__right); |
|
|
579 |
return __right; |
|
|
580 |
} |
|
|
581 |
if (0 == __right) { |
|
|
582 |
__left->_M_ref_nonnil(); |
|
|
583 |
return __left; |
|
|
584 |
} |
|
|
585 |
if (_RopeRep::_S_leaf == __right->_M_tag) { |
|
|
586 |
if (_RopeRep::_S_leaf == __left->_M_tag) { |
|
|
587 |
if (__right->_M_size + __left->_M_size <= _S_copy_max) { |
|
|
588 |
return _S_leaf_concat_char_iter((_RopeLeaf*)__left, |
|
|
589 |
((_RopeLeaf*)__right)->_M_data, |
|
|
590 |
__right->_M_size); |
|
|
591 |
} |
|
|
592 |
} else if (_RopeRep::_S_concat == __left->_M_tag |
|
|
593 |
&& _RopeRep::_S_leaf == |
|
|
594 |
((_RopeConcatenation*)__left)->_M_right->_M_tag) { |
|
|
595 |
_RopeLeaf* __leftright = |
|
|
596 |
(_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); |
|
|
597 |
if (__leftright->_M_size + __right->_M_size <= _S_copy_max) { |
|
|
598 |
_RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left; |
|
|
599 |
_RopeRep* __rest = _S_leaf_concat_char_iter(__leftright, |
|
|
600 |
((_RopeLeaf*)__right)->_M_data, |
|
|
601 |
__right->_M_size); |
|
|
602 |
__leftleft->_M_ref_nonnil(); |
|
|
603 |
__STL_TRY { |
|
|
604 |
return(_S_tree_concat(__leftleft, __rest)); |
|
|
605 |
} |
|
|
606 |
__STL_UNWIND(_S_unref(__leftleft); _S_unref(__rest)) |
|
|
607 |
} |
|
|
608 |
} |
|
|
609 |
} |
|
|
610 |
__left->_M_ref_nonnil(); |
|
|
611 |
__right->_M_ref_nonnil(); |
|
|
612 |
__STL_TRY { |
|
|
613 |
return(_S_tree_concat(__left, __right)); |
|
|
614 |
} |
|
|
615 |
__STL_UNWIND(_S_unref(__left); _S_unref(__right)); |
|
|
616 |
} |
|
|
617 |
|
|
|
618 |
template |
|
|
619 |
rope<_CharT,_Alloc>::_RopeRep* |
|
|
620 |
rope<_CharT,_Alloc>::_S_substring(_RopeRep* __base, |
|
|
621 |
size_t __start, size_t __endp1) |
|
|
622 |
{ |
|
|
623 |
if (0 == __base) return 0; |
|
|
624 |
size_t __len = __base->_M_size; |
|
|
625 |
size_t __adj_endp1; |
|
|
626 |
const size_t __lazy_threshold = 128; |
|
|
627 |
|
|
|
628 |
if (__endp1 >= __len) { |
|
|
629 |
if (0 == __start) { |
|
|
630 |
__base->_M_ref_nonnil(); |
|
|
631 |
return __base; |
|
|
632 |
} else { |
|
|
633 |
__adj_endp1 = __len; |
|
|
634 |
} |
|
|
635 |
} else { |
|
|
636 |
__adj_endp1 = __endp1; |
|
|
637 |
} |
|
|
638 |
switch(__base->_M_tag) { |
|
|
639 |
case _RopeRep::_S_concat: |
|
|
640 |
{ |
|
|
641 |
_RopeConcatenation* __c = (_RopeConcatenation*)__base; |
|
|
642 |
_RopeRep* __left = __c->_M_left; |
|
|
643 |
_RopeRep* __right = __c->_M_right; |
|
|
644 |
size_t __left_len = __left->_M_size; |
|
|
645 |
_RopeRep* __result; |
|
|
646 |
|
|
|
647 |
if (__adj_endp1 <= __left_len) { |
|
|
648 |
return _S_substring(__left, __start, __endp1); |
|
|
649 |
} else if (__start >= __left_len) { |
|
|
650 |
return _S_substring(__right, __start - __left_len, |
|
|
651 |
__adj_endp1 - __left_len); |
|
|
652 |
} |
|
|
653 |
_Self_destruct_ptr __left_result( |
|
|
654 |
_S_substring(__left, __start, __left_len)); |
|
|
655 |
_Self_destruct_ptr __right_result( |
|
|
656 |
_S_substring(__right, 0, __endp1 - __left_len)); |
|
|
657 |
__result = _S_concat(__left_result, __right_result); |
|
|
658 |
# ifndef __GC |
|
|
659 |
__stl_assert(1 == __result->_M_ref_count); |
|
|
660 |
# endif |
|
|
661 |
return __result; |
|
|
662 |
} |
|
|
663 |
case _RopeRep::_S_leaf: |
|
|
664 |
{ |
|
|
665 |
_RopeLeaf* __l = (_RopeLeaf*)__base; |
|
|
666 |
_RopeLeaf* __result; |
|
|
667 |
size_t __result_len; |
|
|
668 |
if (__start >= __adj_endp1) return 0; |
|
|
669 |
__result_len = __adj_endp1 - __start; |
|
|
670 |
if (__result_len > __lazy_threshold) goto lazy; |
|
|
671 |
# ifdef __GC |
|
|
672 |
const _CharT* __section = __l->_M_data + __start; |
|
|
673 |
__result = _S_new_RopeLeaf(__section, __result_len, |
|
|
674 |
__base->get_allocator()); |
|
|
675 |
__result->_M_c_string = 0; // Not eos terminated. |
|
|
676 |
# else |
|
|
677 |
// We should sometimes create substring node instead. |
|
|
678 |
__result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR( |
|
|
679 |
__l->_M_data + __start, __result_len, |
|
|
680 |
__base->get_allocator()); |
|
|
681 |
# endif |
|
|
682 |
return __result; |
|
|
683 |
} |
|
|
684 |
case _RopeRep::_S_substringfn: |
|
|
685 |
// Avoid introducing multiple layers of substring nodes. |
|
|
686 |
{ |
|
|
687 |
_RopeSubstring* __old = (_RopeSubstring*)__base; |
|
|
688 |
size_t __result_len; |
|
|
689 |
if (__start >= __adj_endp1) return 0; |
|
|
690 |
__result_len = __adj_endp1 - __start; |
|
|
691 |
if (__result_len > __lazy_threshold) { |
|
|
692 |
_RopeSubstring* __result = |
|
|
693 |
_S_new_RopeSubstring(__old->_M_base, |
|
|
694 |
__start + __old->_M_start, |
|
|
695 |
__adj_endp1 - __start, |
|
|
696 |
__base->get_allocator()); |
|
|
697 |
return __result; |
|
|
698 |
|
|
|
699 |
} // *** else fall through: *** |
|
|
700 |
} |
|
|
701 |
case _RopeRep::_S_function: |
|
|
702 |
{ |
|
|
703 |
_RopeFunction* __f = (_RopeFunction*)__base; |
|
|
704 |
_CharT* __section; |
|
|
705 |
size_t __result_len; |
|
|
706 |
if (__start >= __adj_endp1) return 0; |
|
|
707 |
__result_len = __adj_endp1 - __start; |
|
|
708 |
|
|
|
709 |
if (__result_len > __lazy_threshold) goto lazy; |
|
|
710 |
__section = (_CharT*) |
|
|
711 |
_Data_allocate(_S_rounded_up_size(__result_len)); |
|
|
712 |
__STL_TRY { |
|
|
713 |
(*(__f->_M_fn))(__start, __result_len, __section); |
|
|
714 |
} |
|
|
715 |
__STL_UNWIND(_RopeRep::__STL_FREE_STRING( |
|
|
716 |
__section, __result_len, __base->get_allocator())); |
|
|
717 |
_S_cond_store_eos(__section[__result_len]); |
|
|
718 |
return _S_new_RopeLeaf(__section, __result_len, |
|
|
719 |
__base->get_allocator()); |
|
|
720 |
} |
|
|
721 |
} |
|
|
722 |
/*NOTREACHED*/ |
|
|
723 |
__stl_assert(false); |
|
|
724 |
lazy: |
|
|
725 |
{ |
|
|
726 |
// Create substring node. |
|
|
727 |
return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start, |
|
|
728 |
__base->get_allocator()); |
|
|
729 |
} |
|
|
730 |
} |
|
|
731 |
|
|
|
732 |
template |
|
|
733 |
class _Rope_flatten_char_consumer : public _Rope_char_consumer<_CharT> { |
|
|
734 |
private: |
|
|
735 |
_CharT* _M_buf_ptr; |
|
|
736 |
public: |
|
|
737 |
|
|
|
738 |
_Rope_flatten_char_consumer(_CharT* __buffer) { |
|
|
739 |
_M_buf_ptr = __buffer; |
|
|
740 |
}; |
|
|
741 |
~_Rope_flatten_char_consumer() {} |
|
|
742 |
bool operator() (const _CharT* __leaf, size_t __n) { |
|
|
743 |
uninitialized_copy_n(__leaf, __n, _M_buf_ptr); |
|
|
744 |
_M_buf_ptr += __n; |
|
|
745 |
return true; |
|
|
746 |
} |
|
|
747 |
}; |
|
|
748 |
|
|
|
749 |
template |
|
|
750 |
class _Rope_find_char_char_consumer : public _Rope_char_consumer<_CharT> { |
|
|
751 |
private: |
|
|
752 |
_CharT _M_pattern; |
|
|
753 |
public: |
|
|
754 |
size_t _M_count; // Number of nonmatching characters |
|
|
755 |
_Rope_find_char_char_consumer(_CharT __p) |
|
|
756 |
: _M_pattern(__p), _M_count(0) {} |
|
|
757 |
~_Rope_find_char_char_consumer() {} |
|
|
758 |
bool operator() (const _CharT* __leaf, size_t __n) { |
|
|
759 |
size_t __i; |
|
|
760 |
for (__i = 0; __i < __n; __i++) { |
|
|
761 |
if (__leaf[__i] == _M_pattern) { |
|
|
762 |
_M_count += __i; return false; |
|
|
763 |
} |
|
|
764 |
} |
|
|
765 |
_M_count += __n; return true; |
|
|
766 |
} |
|
|
767 |
}; |
|
|
768 |
|
|
|
769 |
template |
|
|
770 |
// Here _CharT is both the stream and rope character type. |
|
|
771 |
class _Rope_insert_char_consumer : public _Rope_char_consumer<_CharT> { |
|
|
772 |
private: |
|
|
773 |
typedef basic_ostream<_CharT,_Traits> _Insert_ostream; |
|
|
774 |
_Insert_ostream& _M_o; |
|
|
775 |
public: |
|
|
776 |
_Rope_insert_char_consumer(_Insert_ostream& __writer) |
|
|
777 |
: _M_o(__writer) {}; |
|
|
778 |
~_Rope_insert_char_consumer() { }; |
|
|
779 |
// Caller is presumed to own the ostream |
|
|
780 |
bool operator() (const _CharT* __leaf, size_t __n); |
|
|
781 |
// Returns true to continue traversal. |
|
|
782 |
}; |
|
|
783 |
|
|
|
784 |
template |
|
|
785 |
bool _Rope_insert_char_consumer<_CharT, _Traits>::operator() |
|
|
786 |
(const _CharT* __leaf, size_t __n) |
|
|
787 |
{ |
|
|
788 |
size_t __i; |
|
|
789 |
// We assume that formatting is set up correctly for each element. |
|
|
790 |
for (__i = 0; __i < __n; __i++) _M_o.put(__leaf[__i]); |
|
|
791 |
return true; |
|
|
792 |
} |
|
|
793 |
|
|
|
794 |
template |
|
|
795 |
bool rope<_CharT, _Alloc>::_S_apply_to_pieces( |
|
|
796 |
_Rope_char_consumer<_CharT>& __c, |
|
|
797 |
const _RopeRep* __r, |
|
|
798 |
size_t __begin, size_t __end) |
|
|
799 |
{ |
|
|
800 |
if (0 == __r) return true; |
|
|
801 |
switch(__r->_M_tag) { |
|
|
802 |
case _RopeRep::_S_concat: |
|
|
803 |
{ |
|
|
804 |
_RopeConcatenation* __conc = (_RopeConcatenation*)__r; |
|
|
805 |
_RopeRep* __left = __conc->_M_left; |
|
|
806 |
size_t __left_len = __left->_M_size; |
|
|
807 |
if (__begin < __left_len) { |
|
|
808 |
size_t __left_end = min(__left_len, __end); |
|
|
809 |
if (!_S_apply_to_pieces(__c, __left, __begin, __left_end)) |
|
|
810 |
return false; |
|
|
811 |
} |
|
|
812 |
if (__end > __left_len) { |
|
|
813 |
_RopeRep* __right = __conc->_M_right; |
|
|
814 |
size_t __right_start = max(__left_len, __begin); |
|
|
815 |
if (!_S_apply_to_pieces(__c, __right, |
|
|
816 |
__right_start - __left_len, |
|
|
817 |
__end - __left_len)) { |
|
|
818 |
return false; |
|
|
819 |
} |
|
|
820 |
} |
|
|
821 |
} |
|
|
822 |
return true; |
|
|
823 |
case _RopeRep::_S_leaf: |
|
|
824 |
{ |
|
|
825 |
_RopeLeaf* __l = (_RopeLeaf*)__r; |
|
|
826 |
return __c(__l->_M_data + __begin, __end - __begin); |
|
|
827 |
} |
|
|
828 |
case _RopeRep::_S_function: |
|
|
829 |
case _RopeRep::_S_substringfn: |
|
|
830 |
{ |
|
|
831 |
_RopeFunction* __f = (_RopeFunction*)__r; |
|
|
832 |
size_t __len = __end - __begin; |
|
|
833 |
bool __result; |
|
|
834 |
_CharT* __buffer = |
|
|
835 |
(_CharT*)alloc::allocate(__len * sizeof(_CharT)); |
|
|
836 |
__STL_TRY { |
|
|
837 |
(*(__f->_M_fn))(__begin, __len, __buffer); |
|
|
838 |
__result = __c(__buffer, __len); |
|
|
839 |
alloc::deallocate(__buffer, __len * sizeof(_CharT)); |
|
|
840 |
} |
|
|
841 |
__STL_UNWIND((alloc::deallocate(__buffer, |
|
|
842 |
__len * sizeof(_CharT)))) |
|
|
843 |
return __result; |
|
|
844 |
} |
|
|
845 |
default: |
|
|
846 |
__stl_assert(false); |
|
|
847 |
/*NOTREACHED*/ |
|
|
848 |
return false; |
|
|
849 |
} |
|
|
850 |
} |
|
|
851 |
|
|
|
852 |
template |
|
|
853 |
inline void _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n) |
|
|
854 |
{ |
|
|
855 |
char __f = __o.fill(); |
|
|
856 |
size_t __i; |
|
|
857 |
|
|
|
858 |
for (__i = 0; __i < __n; __i++) __o.put(__f); |
|
|
859 |
} |
|
|
860 |
|
|
|
861 |
|
|
|
862 |
template inline bool _Rope_is_simple(_CharT*) { return false; } |
|
|
863 |
inline bool _Rope_is_simple(char*) { return true; } |
|
|
864 |
inline bool _Rope_is_simple(wchar_t*) { return true; } |
|
|
865 |
|
|
|
866 |
template |
|
|
867 |
basic_ostream<_CharT, _Traits>& operator<< (basic_ostream<_CharT, _Traits>& __o, |
|
|
868 |
const rope<_CharT, _Alloc>& __r) |
|
|
869 |
{ |
|
|
870 |
size_t __w = __o.width(); |
|
|
871 |
bool __left = bool(__o.flags() & ios::left); |
|
|
872 |
size_t __pad_len; |
|
|
873 |
size_t __rope_len = __r.size(); |
|
|
874 |
_Rope_insert_char_consumer<_CharT, _Traits> __c(__o); |
|
|
875 |
bool __is_simple = _Rope_is_simple((_CharT*)0); |
|
|
876 |
|
|
|
877 |
if (__rope_len < __w) { |
|
|
878 |
__pad_len = __w - __rope_len; |
|
|
879 |
} else { |
|
|
880 |
__pad_len = 0; |
|
|
881 |
} |
|
|
882 |
if (!__is_simple) __o.width(__w/__rope_len); |
|
|
883 |
__STL_TRY { |
|
|
884 |
if (__is_simple && !__left && __pad_len > 0) { |
|
|
885 |
_Rope_fill(__o, __pad_len); |
|
|
886 |
} |
|
|
887 |
__r.apply_to_pieces(0, __r.size(), __c); |
|
|
888 |
if (__is_simple && __left && __pad_len > 0) { |
|
|
889 |
_Rope_fill(__o, __pad_len); |
|
|
890 |
} |
|
|
891 |
if (!__is_simple) |
|
|
892 |
__o.width(__w); |
|
|
893 |
} |
|
|
894 |
__STL_UNWIND(if (!__is_simple) __o.width(__w)) |
|
|
895 |
return __o; |
|
|
896 |
} |
|
|
897 |
|
|
|
898 |
template |
|
|
899 |
_CharT* |
|
|
900 |
rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, |
|
|
901 |
size_t __start, size_t __len, |
|
|
902 |
_CharT* __buffer) |
|
|
903 |
{ |
|
|
904 |
_Rope_flatten_char_consumer<_CharT> __c(__buffer); |
|
|
905 |
_S_apply_to_pieces(__c, __r, __start, __start + __len); |
|
|
906 |
return(__buffer + __len); |
|
|
907 |
} |
|
|
908 |
|
|
|
909 |
template |
|
|
910 |
size_t |
|
|
911 |
rope<_CharT,_Alloc>::find(_CharT __pattern, size_t __start) const |
|
|
912 |
{ |
|
|
913 |
_Rope_find_char_char_consumer<_CharT> __c(__pattern); |
|
|
914 |
_S_apply_to_pieces(__c, _M_tree_ptr, __start, size()); |
|
|
915 |
size_type __result_pos = __start + __c._M_count; |
|
|
916 |
# ifndef __STL_OLD_ROPE_SEMANTICS |
|
|
917 |
if (__result_pos == size()) __result_pos = npos; |
|
|
918 |
# endif |
|
|
919 |
return __result_pos; |
|
|
920 |
} |
|
|
921 |
|
|
|
922 |
template |
|
|
923 |
_CharT* |
|
|
924 |
rope<_CharT,_Alloc>::_S_flatten(_RopeRep* __r, _CharT* __buffer) |
|
|
925 |
{ |
|
|
926 |
if (0 == __r) return __buffer; |
|
|
927 |
switch(__r->_M_tag) { |
|
|
928 |
case _RopeRep::_S_concat: |
|
|
929 |
{ |
|
|
930 |
_RopeConcatenation* __c = (_RopeConcatenation*)__r; |
|
|
931 |
_RopeRep* __left = __c->_M_left; |
|
|
932 |
_RopeRep* __right = __c->_M_right; |
|
|
933 |
_CharT* __rest = _S_flatten(__left, __buffer); |
|
|
934 |
return _S_flatten(__right, __rest); |
|
|
935 |
} |
|
|
936 |
case _RopeRep::_S_leaf: |
|
|
937 |
{ |
|
|
938 |
_RopeLeaf* __l = (_RopeLeaf*)__r; |
|
|
939 |
return copy_n(__l->_M_data, __l->_M_size, __buffer).second; |
|
|
940 |
} |
|
|
941 |
case _RopeRep::_S_function: |
|
|
942 |
case _RopeRep::_S_substringfn: |
|
|
943 |
// We dont yet do anything with substring nodes. |
|
|
944 |
// This needs to be fixed before ropefiles will work well. |
|
|
945 |
{ |
|
|
946 |
_RopeFunction* __f = (_RopeFunction*)__r; |
|
|
947 |
(*(__f->_M_fn))(0, __f->_M_size, __buffer); |
|
|
948 |
return __buffer + __f->_M_size; |
|
|
949 |
} |
|
|
950 |
default: |
|
|
951 |
__stl_assert(false); |
|
|
952 |
/*NOTREACHED*/ |
|
|
953 |
return 0; |
|
|
954 |
} |
|
|
955 |
} |
|
|
956 |
|
|
|
957 |
|
|
|
958 |
// This needs work for _CharT != char |
|
|
959 |
template |
|
|
960 |
void |
|
|
961 |
rope<_CharT,_Alloc>::_S_dump(_RopeRep* __r, int __indent) |
|
|
962 |
{ |
|
|
963 |
for (int __i = 0; __i < __indent; __i++) putchar(' '); |
|
|
964 |
if (0 == __r) { |
|
|
965 |
printf("NULL\n"); return; |
|
|
966 |
} |
|
|
967 |
if (_RopeRep::_S_concat == __r->_M_tag) { |
|
|
968 |
_RopeConcatenation* __c = (_RopeConcatenation*)__r; |
|
|
969 |
_RopeRep* __left = __c->_M_left; |
|
|
970 |
_RopeRep* __right = __c->_M_right; |
|
|
971 |
|
|
|
972 |
# ifdef __GC |
|
|
973 |
printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n", |
|
|
974 |
__r, __r->_M_depth, __r->_M_size, __r->_M_is_balanced? "" : "not"); |
|
|
975 |
# else |
|
|
976 |
printf("Concatenation %p (rc = %ld, depth = %d, " |
|
|
977 |
"len = %ld, %s balanced)\n", |
|
|
978 |
__r, __r->_M_ref_count, __r->_M_depth, __r->_M_size, |
|
|
979 |
__r->_M_is_balanced? "" : "not"); |
|
|
980 |
# endif |
|
|
981 |
_S_dump(__left, __indent + 2); |
|
|
982 |
_S_dump(__right, __indent + 2); |
|
|
983 |
return; |
|
|
984 |
} else { |
|
|
985 |
char* __kind; |
|
|
986 |
|
|
|
987 |
switch (__r->_M_tag) { |
|
|
988 |
case _RopeRep::_S_leaf: |
|
|
989 |
__kind = "Leaf"; |
|
|
990 |
break; |
|
|
991 |
case _RopeRep::_S_function: |
|
|
992 |
__kind = "Function"; |
|
|
993 |
break; |
|
|
994 |
case _RopeRep::_S_substringfn: |
|
|
995 |
__kind = "Function representing substring"; |
|
|
996 |
break; |
|
|
997 |
default: |
|
|
998 |
__kind = "(corrupted kind field!)"; |
|
|
999 |
} |
|
|
1000 |
# ifdef __GC |
|
|
1001 |
printf("%s %p (depth = %d, len = %ld) ", |
|
|
1002 |
__kind, __r, __r->_M_depth, __r->_M_size); |
|
|
1003 |
# else |
|
|
1004 |
printf("%s %p (rc = %ld, depth = %d, len = %ld) ", |
|
|
1005 |
__kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size); |
|
|
1006 |
# endif |
|
|
1007 |
if (_S_is_one_byte_char_type((_CharT*)0)) { |
|
|
1008 |
const int __max_len = 40; |
|
|
1009 |
_Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len)); |
|
|
1010 |
_CharT __buffer[__max_len + 1]; |
|
|
1011 |
bool __too_big = __r->_M_size > __prefix->_M_size; |
|
|
1012 |
|
|
|
1013 |
_S_flatten(__prefix, __buffer); |
|
|
1014 |
__buffer[__prefix->_M_size] = _S_eos((_CharT*)0); |
|
|
1015 |
printf("%s%s\n", |
|
|
1016 |
(char*)__buffer, __too_big? "...\n" : "\n"); |
|
|
1017 |
} else { |
|
|
1018 |
printf("\n"); |
|
|
1019 |
} |
|
|
1020 |
} |
|
|
1021 |
} |
|
|
1022 |
|
|
|
1023 |
template |
|
|
1024 |
const unsigned long |
|
|
1025 |
rope<_CharT,_Alloc>::_S_min_len[ |
|
|
1026 |
_Rope_RopeRep<_CharT,_Alloc>::_S_max_rope_depth + 1] = { |
|
|
1027 |
/* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, |
|
|
1028 |
/* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, |
|
|
1029 |
/* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, |
|
|
1030 |
/* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368, |
|
|
1031 |
/* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811, |
|
|
1032 |
/* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309, |
|
|
1033 |
/* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352, |
|
|
1034 |
/* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155, |
|
|
1035 |
/* 39 */165580141, /* 40 */267914296, /* 41 */433494437, |
|
|
1036 |
/* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903, |
|
|
1037 |
/* 45 */2971215073u }; |
|
|
1038 |
// These are Fibonacci numbers < 2**32. |
|
|
1039 |
|
|
|
1040 |
template |
|
|
1041 |
rope<_CharT,_Alloc>::_RopeRep* |
|
|
1042 |
rope<_CharT,_Alloc>::_S_balance(_RopeRep* __r) |
|
|
1043 |
{ |
|
|
1044 |
_RopeRep* __forest[_RopeRep::_S_max_rope_depth + 1]; |
|
|
1045 |
_RopeRep* __result = 0; |
|
|
1046 |
int __i; |
|
|
1047 |
// Invariant: |
|
|
1048 |
// The concatenation of forest in descending order is equal to __r. |
|
|
1049 |
// __forest[__i]._M_size >= _S_min_len[__i] |
|
|
1050 |
// __forest[__i]._M_depth = __i |
|
|
1051 |
// References from forest are included in refcount. |
|
|
1052 |
|
|
|
1053 |
for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i) |
|
|
1054 |
__forest[__i] = 0; |
|
|
1055 |
__STL_TRY { |
|
|
1056 |
_S_add_to_forest(__r, __forest); |
|
|
1057 |
for (__i = 0; __i <= _RopeRep::_S_max_rope_depth; ++__i) |
|
|
1058 |
if (0 != __forest[__i]) { |
|
|
1059 |
# ifndef __GC |
|
|
1060 |
_Self_destruct_ptr __old(__result); |
|
|
1061 |
# endif |
|
|
1062 |
__result = _S_concat(__forest[__i], __result); |
|
|
1063 |
__forest[__i]->_M_unref_nonnil(); |
|
|
1064 |
# if !defined(__GC) && defined(__STL_USE_EXCEPTIONS) |
|
|
1065 |
__forest[__i] = 0; |
|
|
1066 |
# endif |
|
|
1067 |
} |
|
|
1068 |
} |
|
|
1069 |
__STL_UNWIND(for(__i = 0; __i <= _RopeRep::_S_max_rope_depth; __i++) |
|
|
1070 |
_S_unref(__forest[__i])) |
|
|
1071 |
if (__result->_M_depth > _RopeRep::_S_max_rope_depth) { |
|
|
1072 |
# ifdef __STL_USE_EXCEPTIONS |
|
|
1073 |
__STL_THROW(length_error("rope too long")); |
|
|
1074 |
# else |
|
|
1075 |
abort(); |
|
|
1076 |
# endif |
|
|
1077 |
} |
|
|
1078 |
return(__result); |
|
|
1079 |
} |
|
|
1080 |
|
|
|
1081 |
|
|
|
1082 |
template |
|
|
1083 |
void |
|
|
1084 |
rope<_CharT,_Alloc>::_S_add_to_forest(_RopeRep* __r, _RopeRep** __forest) |
|
|
1085 |
{ |
|
|
1086 |
if (__r->_M_is_balanced) { |
|
|
1087 |
_S_add_leaf_to_forest(__r, __forest); |
|
|
1088 |
return; |
|
|
1089 |
} |
|
|
1090 |
__stl_assert(__r->_M_tag == _RopeRep::_S_concat); |
|
|
1091 |
{ |
|
|
1092 |
_RopeConcatenation* __c = (_RopeConcatenation*)__r; |
|
|
1093 |
|
|
|
1094 |
_S_add_to_forest(__c->_M_left, __forest); |
|
|
1095 |
_S_add_to_forest(__c->_M_right, __forest); |
|
|
1096 |
} |
|
|
1097 |
} |
|
|
1098 |
|
|
|
1099 |
|
|
|
1100 |
template |
|
|
1101 |
void |
|
|
1102 |
rope<_CharT,_Alloc>::_S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest) |
|
|
1103 |
{ |
|
|
1104 |
_RopeRep* __insertee; // included in refcount |
|
|
1105 |
_RopeRep* __too_tiny = 0; // included in refcount |
|
|
1106 |
int __i; // forest[0..__i-1] is empty |
|
|
1107 |
size_t __s = __r->_M_size; |
|
|
1108 |
|
|
|
1109 |
for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) { |
|
|
1110 |
if (0 != __forest[__i]) { |
|
|
1111 |
# ifndef __GC |
|
|
1112 |
_Self_destruct_ptr __old(__too_tiny); |
|
|
1113 |
# endif |
|
|
1114 |
__too_tiny = _S_concat_and_set_balanced(__forest[__i], __too_tiny); |
|
|
1115 |
__forest[__i]->_M_unref_nonnil(); |
|
|
1116 |
__forest[__i] = 0; |
|
|
1117 |
} |
|
|
1118 |
} |
|
|
1119 |
{ |
|
|
1120 |
# ifndef __GC |
|
|
1121 |
_Self_destruct_ptr __old(__too_tiny); |
|
|
1122 |
# endif |
|
|
1123 |
__insertee = _S_concat_and_set_balanced(__too_tiny, __r); |
|
|
1124 |
} |
|
|
1125 |
// Too_tiny dead, and no longer included in refcount. |
|
|
1126 |
// Insertee is live and included. |
|
|
1127 |
__stl_assert(_S_is_almost_balanced(__insertee)); |
|
|
1128 |
__stl_assert(__insertee->_M_depth <= __r->_M_depth + 1); |
|
|
1129 |
for (;; ++__i) { |
|
|
1130 |
if (0 != __forest[__i]) { |
|
|
1131 |
# ifndef __GC |
|
|
1132 |
_Self_destruct_ptr __old(__insertee); |
|
|
1133 |
# endif |
|
|
1134 |
__insertee = _S_concat_and_set_balanced(__forest[__i], __insertee); |
|
|
1135 |
__forest[__i]->_M_unref_nonnil(); |
|
|
1136 |
__forest[__i] = 0; |
|
|
1137 |
__stl_assert(_S_is_almost_balanced(__insertee)); |
|
|
1138 |
} |
|
|
1139 |
__stl_assert(_S_min_len[__i] <= __insertee->_M_size); |
|
|
1140 |
__stl_assert(__forest[__i] == 0); |
|
|
1141 |
if (__i == _RopeRep::_S_max_rope_depth || |
|
|
1142 |
__insertee->_M_size < _S_min_len[__i+1]) { |
|
|
1143 |
__forest[__i] = __insertee; |
|
|
1144 |
// refcount is OK since __insertee is now dead. |
|
|
1145 |
return; |
|
|
1146 |
} |
|
|
1147 |
} |
|
|
1148 |
} |
|
|
1149 |
|
|
|
1150 |
template |
|
|
1151 |
_CharT |
|
|
1152 |
rope<_CharT,_Alloc>::_S_fetch(_RopeRep* __r, size_type __i) |
|
|
1153 |
{ |
|
|
1154 |
__GC_CONST _CharT* __cstr = __r->_M_c_string; |
|
|
1155 |
|
|
|
1156 |
__stl_assert(__i < __r->_M_size); |
|
|
1157 |
if (0 != __cstr) return __cstr[__i]; |
|
|
1158 |
for(;;) { |
|
|
1159 |
switch(__r->_M_tag) { |
|
|
1160 |
case _RopeRep::_S_concat: |
|
|
1161 |
{ |
|
|
1162 |
_RopeConcatenation* __c = (_RopeConcatenation*)__r; |
|
|
1163 |
_RopeRep* __left = __c->_M_left; |
|
|
1164 |
size_t __left_len = __left->_M_size; |
|
|
1165 |
|
|
|
1166 |
if (__i >= __left_len) { |
|
|
1167 |
__i -= __left_len; |
|
|
1168 |
__r = __c->_M_right; |
|
|
1169 |
} else { |
|
|
1170 |
__r = __left; |
|
|
1171 |
} |
|
|
1172 |
} |
|
|
1173 |
break; |
|
|
1174 |
case _RopeRep::_S_leaf: |
|
|
1175 |
{ |
|
|
1176 |
_RopeLeaf* __l = (_RopeLeaf*)__r; |
|
|
1177 |
return __l->_M_data[__i]; |
|
|
1178 |
} |
|
|
1179 |
case _RopeRep::_S_function: |
|
|
1180 |
case _RopeRep::_S_substringfn: |
|
|
1181 |
{ |
|
|
1182 |
_RopeFunction* __f = (_RopeFunction*)__r; |
|
|
1183 |
_CharT __result; |
|
|
1184 |
|
|
|
1185 |
(*(__f->_M_fn))(__i, 1, &__result); |
|
|
1186 |
return __result; |
|
|
1187 |
} |
|
|
1188 |
} |
|
|
1189 |
} |
|
|
1190 |
} |
|
|
1191 |
|
|
|
1192 |
# ifndef __GC |
|
|
1193 |
// Return a uniquely referenced character slot for the given |
|
|
1194 |
// position, or 0 if that's not possible. |
|
|
1195 |
template |
|
|
1196 |
_CharT* |
|
|
1197 |
rope<_CharT,_Alloc>::_S_fetch_ptr(_RopeRep* __r, size_type __i) |
|
|
1198 |
{ |
|
|
1199 |
_RopeRep* __clrstack[_RopeRep::_S_max_rope_depth]; |
|
|
1200 |
size_t __csptr = 0; |
|
|
1201 |
|
|
|
1202 |
for(;;) { |
|
|
1203 |
if (__r->_M_ref_count > 1) return 0; |
|
|
1204 |
switch(__r->_M_tag) { |
|
|
1205 |
case _RopeRep::_S_concat: |
|
|
1206 |
{ |
|
|
1207 |
_RopeConcatenation* __c = (_RopeConcatenation*)__r; |
|
|
1208 |
_RopeRep* __left = __c->_M_left; |
|
|
1209 |
size_t __left_len = __left->_M_size; |
|
|
1210 |
|
|
|
1211 |
if (__c->_M_c_string != 0) __clrstack[__csptr++] = __c; |
|
|
1212 |
if (__i >= __left_len) { |
|
|
1213 |
__i -= __left_len; |
|
|
1214 |
__r = __c->_M_right; |
|
|
1215 |
} else { |
|
|
1216 |
__r = __left; |
|
|
1217 |
} |
|
|
1218 |
} |
|
|
1219 |
break; |
|
|
1220 |
case _RopeRep::_S_leaf: |
|
|
1221 |
{ |
|
|
1222 |
_RopeLeaf* __l = (_RopeLeaf*)__r; |
|
|
1223 |
if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0) |
|
|
1224 |
__clrstack[__csptr++] = __l; |
|
|
1225 |
while (__csptr > 0) { |
|
|
1226 |
-- __csptr; |
|
|
1227 |
_RopeRep* __d = __clrstack[__csptr]; |
|
|
1228 |
__d->_M_free_c_string(); |
|
|
1229 |
__d->_M_c_string = 0; |
|
|
1230 |
} |
|
|
1231 |
return __l->_M_data + __i; |
|
|
1232 |
} |
|
|
1233 |
case _RopeRep::_S_function: |
|
|
1234 |
case _RopeRep::_S_substringfn: |
|
|
1235 |
return 0; |
|
|
1236 |
} |
|
|
1237 |
} |
|
|
1238 |
} |
|
|
1239 |
# endif /* __GC */ |
|
|
1240 |
|
|
|
1241 |
// The following could be implemented trivially using |
|
|
1242 |
// lexicographical_compare_3way. |
|
|
1243 |
// We do a little more work to avoid dealing with rope iterators for |
|
|
1244 |
// flat strings. |
|
|
1245 |
template |
|
|
1246 |
int |
|
|
1247 |
rope<_CharT,_Alloc>::_S_compare (const _RopeRep* __left, |
|
|
1248 |
const _RopeRep* __right) |
|
|
1249 |
{ |
|
|
1250 |
size_t __left_len; |
|
|
1251 |
size_t __right_len; |
|
|
1252 |
|
|
|
1253 |
if (0 == __right) return 0 != __left; |
|
|
1254 |
if (0 == __left) return -1; |
|
|
1255 |
__left_len = __left->_M_size; |
|
|
1256 |
__right_len = __right->_M_size; |
|
|
1257 |
if (_RopeRep::_S_leaf == __left->_M_tag) { |
|
|
1258 |
_RopeLeaf* __l = (_RopeLeaf*) __left; |
|
|
1259 |
if (_RopeRep::_S_leaf == __right->_M_tag) { |
|
|
1260 |
_RopeLeaf* __r = (_RopeLeaf*) __right; |
|
|
1261 |
return lexicographical_compare_3way( |
|
|
1262 |
__l->_M_data, __l->_M_data + __left_len, |
|
|
1263 |
__r->_M_data, __r->_M_data + __right_len); |
|
|
1264 |
} else { |
|
|
1265 |
const_iterator __rstart(__right, 0); |
|
|
1266 |
const_iterator __rend(__right, __right_len); |
|
|
1267 |
return lexicographical_compare_3way( |
|
|
1268 |
__l->_M_data, __l->_M_data + __left_len, |
|
|
1269 |
__rstart, __rend); |
|
|
1270 |
} |
|
|
1271 |
} else { |
|
|
1272 |
const_iterator __lstart(__left, 0); |
|
|
1273 |
const_iterator __lend(__left, __left_len); |
|
|
1274 |
if (_RopeRep::_S_leaf == __right->_M_tag) { |
|
|
1275 |
_RopeLeaf* __r = (_RopeLeaf*) __right; |
|
|
1276 |
return lexicographical_compare_3way( |
|
|
1277 |
__lstart, __lend, |
|
|
1278 |
__r->_M_data, __r->_M_data + __right_len); |
|
|
1279 |
} else { |
|
|
1280 |
const_iterator __rstart(__right, 0); |
|
|
1281 |
const_iterator __rend(__right, __right_len); |
|
|
1282 |
return lexicographical_compare_3way( |
|
|
1283 |
__lstart, __lend, |
|
|
1284 |
__rstart, __rend); |
|
|
1285 |
} |
|
|
1286 |
} |
|
|
1287 |
} |
|
|
1288 |
|
|
|
1289 |
// Assignment to reference proxies. |
|
|
1290 |
template |
|
|
1291 |
_Rope_char_ref_proxy<_CharT, _Alloc>& |
|
|
1292 |
_Rope_char_ref_proxy<_CharT, _Alloc>::operator= (_CharT __c) { |
|
|
1293 |
_RopeRep* __old = _M_root->_M_tree_ptr; |
|
|
1294 |
# ifndef __GC |
|
|
1295 |
// First check for the case in which everything is uniquely |
|
|
1296 |
// referenced. In that case we can do this destructively. |
|
|
1297 |
_CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos); |
|
|
1298 |
if (0 != __ptr) { |
|
|
1299 |
*__ptr = __c; |
|
|
1300 |
return *this; |
|
|
1301 |
} |
|
|
1302 |
# endif |
|
|
1303 |
_Self_destruct_ptr __left( |
|
|
1304 |
_My_rope::_S_substring(__old, 0, _M_pos)); |
|
|
1305 |
_Self_destruct_ptr __right( |
|
|
1306 |
_My_rope::_S_substring(__old, _M_pos+1, __old->_M_size)); |
|
|
1307 |
_Self_destruct_ptr __result_left( |
|
|
1308 |
_My_rope::_S_destr_concat_char_iter(__left, &__c, 1)); |
|
|
1309 |
|
|
|
1310 |
# ifndef __GC |
|
|
1311 |
__stl_assert(__left == __result_left || 1 == __result_left->_M_ref_count); |
|
|
1312 |
# endif |
|
|
1313 |
_RopeRep* __result = |
|
|
1314 |
_My_rope::_S_concat(__result_left, __right); |
|
|
1315 |
# ifndef __GC |
|
|
1316 |
__stl_assert(1 <= __result->_M_ref_count); |
|
|
1317 |
_RopeRep::_S_unref(__old); |
|
|
1318 |
# endif |
|
|
1319 |
_M_root->_M_tree_ptr = __result; |
|
|
1320 |
return *this; |
|
|
1321 |
} |
|
|
1322 |
|
|
|
1323 |
template |
|
|
1324 |
inline _Rope_char_ref_proxy<_CharT, _Alloc>::operator _CharT () const |
|
|
1325 |
{ |
|
|
1326 |
if (_M_current_valid) { |
|
|
1327 |
return _M_current; |
|
|
1328 |
} else { |
|
|
1329 |
return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos); |
|
|
1330 |
} |
|
|
1331 |
} |
|
|
1332 |
template |
|
|
1333 |
_Rope_char_ptr_proxy<_CharT, _Alloc> |
|
|
1334 |
_Rope_char_ref_proxy<_CharT, _Alloc>::operator& () const { |
|
|
1335 |
return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); |
|
|
1336 |
} |
|
|
1337 |
|
|
|
1338 |
template |
|
|
1339 |
rope<_CharT, _Alloc>::rope(size_t __n, _CharT __c, |
|
|
1340 |
const allocator_type& __a) |
|
|
1341 |
: _Base(__a) |
|
|
1342 |
{ |
|
|
1343 |
rope<_CharT,_Alloc> __result; |
|
|
1344 |
const size_t __exponentiate_threshold = 32; |
|
|
1345 |
size_t __exponent; |
|
|
1346 |
size_t __rest; |
|
|
1347 |
_CharT* __rest_buffer; |
|
|
1348 |
_RopeRep* __remainder; |
|
|
1349 |
rope<_CharT,_Alloc> __remainder_rope; |
|
|
1350 |
|
|
|
1351 |
if (0 == __n) |
|
|
1352 |
return; |
|
|
1353 |
|
|
|
1354 |
__exponent = __n / __exponentiate_threshold; |
|
|
1355 |
__rest = __n % __exponentiate_threshold; |
|
|
1356 |
if (0 == __rest) { |
|
|
1357 |
__remainder = 0; |
|
|
1358 |
} else { |
|
|
1359 |
__rest_buffer = _Data_allocate(_S_rounded_up_size(__rest)); |
|
|
1360 |
uninitialized_fill_n(__rest_buffer, __rest, __c); |
|
|
1361 |
_S_cond_store_eos(__rest_buffer[__rest]); |
|
|
1362 |
__STL_TRY { |
|
|
1363 |
__remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a); |
|
|
1364 |
} |
|
|
1365 |
__STL_UNWIND(_RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a)) |
|
|
1366 |
} |
|
|
1367 |
__remainder_rope._M_tree_ptr = __remainder; |
|
|
1368 |
if (__exponent != 0) { |
|
|
1369 |
_CharT* __base_buffer = |
|
|
1370 |
_Data_allocate(_S_rounded_up_size(__exponentiate_threshold)); |
|
|
1371 |
_RopeLeaf* __base_leaf; |
|
|
1372 |
rope __base_rope; |
|
|
1373 |
uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c); |
|
|
1374 |
_S_cond_store_eos(__base_buffer[__exponentiate_threshold]); |
|
|
1375 |
__STL_TRY { |
|
|
1376 |
__base_leaf = _S_new_RopeLeaf(__base_buffer, |
|
|
1377 |
__exponentiate_threshold, __a); |
|
|
1378 |
} |
|
|
1379 |
__STL_UNWIND(_RopeRep::__STL_FREE_STRING(__base_buffer, |
|
|
1380 |
__exponentiate_threshold, __a)) |
|
|
1381 |
__base_rope._M_tree_ptr = __base_leaf; |
|
|
1382 |
if (1 == __exponent) { |
|
|
1383 |
__result = __base_rope; |
|
|
1384 |
# ifndef __GC |
|
|
1385 |
__stl_assert(2 == __result._M_tree_ptr->_M_ref_count); |
|
|
1386 |
// One each for base_rope and __result |
|
|
1387 |
# endif |
|
|
1388 |
} else { |
|
|
1389 |
__result = power(__base_rope, __exponent, |
|
|
1390 |
_Rope_Concat_fn<_CharT,_Alloc>()); |
|
|
1391 |
} |
|
|
1392 |
if (0 != __remainder) { |
|
|
1393 |
__result += __remainder_rope; |
|
|
1394 |
} |
|
|
1395 |
} else { |
|
|
1396 |
__result = __remainder_rope; |
|
|
1397 |
} |
|
|
1398 |
_M_tree_ptr = __result._M_tree_ptr; |
|
|
1399 |
_M_tree_ptr->_M_ref_nonnil(); |
|
|
1400 |
} |
|
|
1401 |
|
|
|
1402 |
template |
|
|
1403 |
_CharT rope<_CharT,_Alloc>::_S_empty_c_str[1]; |
|
|
1404 |
|
|
|
1405 |
template |
|
|
1406 |
const _CharT* rope<_CharT,_Alloc>::c_str() const { |
|
|
1407 |
if (0 == _M_tree_ptr) { |
|
|
1408 |
_S_empty_c_str[0] = _S_eos((_CharT*)0); // Possibly redundant, |
|
|
1409 |
// but probably fast. |
|
|
1410 |
return _S_empty_c_str; |
|
|
1411 |
} |
|
|
1412 |
__GC_CONST _CharT* __old_c_string = _M_tree_ptr->_M_c_string; |
|
|
1413 |
if (0 != __old_c_string) return(__old_c_string); |
|
|
1414 |
size_t __s = size(); |
|
|
1415 |
_CharT* __result = _Data_allocate(__s + 1); |
|
|
1416 |
_S_flatten(_M_tree_ptr, __result); |
|
|
1417 |
__result[__s] = _S_eos((_CharT*)0); |
|
|
1418 |
# ifdef __GC |
|
|
1419 |
_M_tree_ptr->_M_c_string = __result; |
|
|
1420 |
# else |
|
|
1421 |
if ((__old_c_string = (__GC_CONST _CharT*) |
|
|
1422 |
_Atomic_swap((unsigned long *)(&(_M_tree_ptr->_M_c_string)), |
|
|
1423 |
(unsigned long)__result)) != 0) { |
|
|
1424 |
// It must have been added in the interim. Hence it had to have been |
|
|
1425 |
// separately allocated. Deallocate the old copy, since we just |
|
|
1426 |
// replaced it. |
|
|
1427 |
destroy(__old_c_string, __old_c_string + __s + 1); |
|
|
1428 |
_Data_deallocate(__old_c_string, __s + 1); |
|
|
1429 |
} |
|
|
1430 |
# endif |
|
|
1431 |
return(__result); |
|
|
1432 |
} |
|
|
1433 |
|
|
|
1434 |
template |
|
|
1435 |
const _CharT* rope<_CharT,_Alloc>::replace_with_c_str() { |
|
|
1436 |
if (0 == _M_tree_ptr) { |
|
|
1437 |
_S_empty_c_str[0] = _S_eos((_CharT*)0); |
|
|
1438 |
return _S_empty_c_str; |
|
|
1439 |
} |
|
|
1440 |
__GC_CONST _CharT* __old_c_string = _M_tree_ptr->_M_c_string; |
|
|
1441 |
if (_RopeRep::_S_leaf == _M_tree_ptr->_M_tag && 0 != __old_c_string) { |
|
|
1442 |
return(__old_c_string); |
|
|
1443 |
} |
|
|
1444 |
size_t __s = size(); |
|
|
1445 |
_CharT* __result = _Data_allocate(_S_rounded_up_size(__s)); |
|
|
1446 |
_S_flatten(_M_tree_ptr, __result); |
|
|
1447 |
__result[__s] = _S_eos((_CharT*)0); |
|
|
1448 |
_M_tree_ptr->_M_unref_nonnil(); |
|
|
1449 |
_M_tree_ptr = _S_new_RopeLeaf(__result, __s, get_allocator()); |
|
|
1450 |
return(__result); |
|
|
1451 |
} |
|
|
1452 |
|
|
|
1453 |
// Algorithm specializations. More should be added. |
|
|
1454 |
|
|
|
1455 |
template // was templated on CharT and Alloc |
|
|
1456 |
void // VC++ workaround |
|
|
1457 |
_Rope_rotate(_Rope_iterator __first, |
|
|
1458 |
_Rope_iterator __middle, |
|
|
1459 |
_Rope_iterator __last) |
|
|
1460 |
{ |
|
|
1461 |
typedef typename _Rope_iterator::value_type _CharT; |
|
|
1462 |
typedef typename _Rope_iterator::_allocator_type _Alloc; |
|
|
1463 |
|
|
|
1464 |
__stl_assert(__first.container() == __middle.container() |
|
|
1465 |
&& __middle.container() == __last.container()); |
|
|
1466 |
rope<_CharT,_Alloc>& __r(__first.container()); |
|
|
1467 |
rope<_CharT,_Alloc> __prefix = __r.substr(0, __first.index()); |
|
|
1468 |
rope<_CharT,_Alloc> __suffix = |
|
|
1469 |
__r.substr(__last.index(), __r.size() - __last.index()); |
|
|
1470 |
rope<_CharT,_Alloc> __part1 = |
|
|
1471 |
__r.substr(__middle.index(), __last.index() - __middle.index()); |
|
|
1472 |
rope<_CharT,_Alloc> __part2 = |
|
|
1473 |
__r.substr(__first.index(), __middle.index() - __first.index()); |
|
|
1474 |
__r = __prefix; |
|
|
1475 |
__r += __part1; |
|
|
1476 |
__r += __part2; |
|
|
1477 |
__r += __suffix; |
|
|
1478 |
} |
|
|
1479 |
|
|
|
1480 |
#if !defined(__GNUC__) |
|
|
1481 |
// Appears to confuse g++ |
|
|
1482 |
inline void rotate(_Rope_iterator __first, |
|
|
1483 |
_Rope_iterator __middle, |
|
|
1484 |
_Rope_iterator __last) { |
|
|
1485 |
_Rope_rotate(__first, __middle, __last); |
|
|
1486 |
} |
|
|
1487 |
#endif |
|
|
1488 |
|
|
|
1489 |
# if 0 |
|
|
1490 |
// Probably not useful for several reasons: |
|
|
1491 |
// - for SGIs 7.1 compiler and probably some others, |
|
|
1492 |
// this forces lots of rope instantiations, creating a |
|
|
1493 |
// code bloat and compile time problem. (Fixed in 7.2.) |
|
|
1494 |
// - wchar_t is 4 bytes wide on most UNIX platforms, making it unattractive |
|
|
1495 |
// for unicode strings. Unsigned short may be a better character |
|
|
1496 |
// type. |
|
|
1497 |
inline void rotate( |
|
|
1498 |
_Rope_iterator __first, |
|
|
1499 |
_Rope_iterator __middle, |
|
|
1500 |
_Rope_iterator __last) { |
|
|
1501 |
_Rope_rotate(__first, __middle, __last); |
|
|
1502 |
} |
|
|
1503 |
# endif |
|
|
1504 |
|
|
|
1505 |
} // namespace std |
|
|
1506 |
|
|
|
1507 |
// Local Variables: |
|
|
1508 |
// mode:C++ |
|
|
1509 |
// End: |