Go to most recent revision | Details | Last modification | View Log | RSS feed
Rev | Author | Line No. | Line |
---|---|---|---|
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 |
||
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 |
||
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 |
||
1483 | _Rope_iterator |
||
1484 | _Rope_iterator |
||
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 |
||
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 |
||
1499 | _Rope_iterator |
||
1500 | _Rope_iterator |
||
1501 | _Rope_rotate(__first, __middle, __last); |
||
1502 | } |
||
1503 | # endif |
||
1504 | |||
1505 | } // namespace std |
||
1506 | |||
1507 | // Local Variables: |
||
1508 | // mode:C++ |
||
1509 | // End:=>>>=>=>=>=>=>>>>><>>>>>=>=>=>=>=>=>=>>=><=>>>>=>=>>=><=>=>=>=> |