ropeimpl.h

Go to the documentation of this file.
00001 // SGI's rope class implementation -*- C++ -*- 00002 00003 // Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 00004 // 00005 // This file is part of the GNU ISO C++ Library. This library is free 00006 // software; you can redistribute it and/or modify it under the 00007 // terms of the GNU General Public License as published by the 00008 // Free Software Foundation; either version 2, or (at your option) 00009 // any later version. 00010 00011 // This library is distributed in the hope that it will be useful, 00012 // but WITHOUT ANY WARRANTY; without even the implied warranty of 00013 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 00014 // GNU General Public License for more details. 00015 00016 // You should have received a copy of the GNU General Public License along 00017 // with this library; see the file COPYING. If not, write to the Free 00018 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 00019 // USA. 00020 00021 // As a special exception, you may use this file as part of a free software 00022 // library without restriction. Specifically, if other files instantiate 00023 // templates or use macros or inline functions from this file, or you compile 00024 // this file and link it with other files to produce an executable, this 00025 // file does not by itself cause the resulting executable to be covered by 00026 // the GNU General Public License. This exception does not however 00027 // invalidate any other reasons why the executable file might be covered by 00028 // the GNU General Public License. 00029 00030 /* 00031 * Copyright (c) 1997 00032 * Silicon Graphics Computer Systems, Inc. 00033 * 00034 * Permission to use, copy, modify, distribute and sell this software 00035 * and its documentation for any purpose is hereby granted without fee, 00036 * provided that the above copyright notice appear in all copies and 00037 * that both that copyright notice and this permission notice appear 00038 * in supporting documentation. Silicon Graphics makes no 00039 * representations about the suitability of this software for any 00040 * purpose. It is provided "as is" without express or implied warranty. 00041 */ 00042 00043 /** @file ropeimpl.h 00044 * This is an internal header file, included by other library headers. 00045 * You should not attempt to use it directly. 00046 */ 00047 00048 #include <cstdio> 00049 #include <ostream> 00050 #include <bits/functexcept.h> 00051 00052 #include <ext/algorithm> // For copy_n and lexicographical_compare_3way 00053 #include <ext/memory> // For uninitialized_copy_n 00054 #include <ext/numeric> // For power 00055 00056 namespace __gnu_cxx 00057 { 00058 using std::size_t; 00059 using std::printf; 00060 using std::basic_ostream; 00061 using std::__throw_length_error; 00062 using std::_Destroy; 00063 using std::uninitialized_fill_n; 00064 00065 // Set buf_start, buf_end, and buf_ptr appropriately, filling tmp_buf 00066 // if necessary. Assumes _M_path_end[leaf_index] and leaf_pos are correct. 00067 // Results in a valid buf_ptr if the iterator can be legitimately 00068 // dereferenced. 00069 template <class _CharT, class _Alloc> 00070 void 00071 _Rope_iterator_base<_CharT, _Alloc>:: 00072 _S_setbuf(_Rope_iterator_base<_CharT, _Alloc>& __x) 00073 { 00074 const _RopeRep* __leaf = __x._M_path_end[__x._M_leaf_index]; 00075 size_t __leaf_pos = __x._M_leaf_pos; 00076 size_t __pos = __x._M_current_pos; 00077 00078 switch(__leaf->_M_tag) 00079 { 00080 case _Rope_constants::_S_leaf: 00081 __x._M_buf_start = ((_Rope_RopeLeaf<_CharT, _Alloc>*)__leaf)->_M_data; 00082 __x._M_buf_ptr = __x._M_buf_start + (__pos - __leaf_pos); 00083 __x._M_buf_end = __x._M_buf_start + __leaf->_M_size; 00084 break; 00085 case _Rope_constants::_S_function: 00086 case _Rope_constants::_S_substringfn: 00087 { 00088 size_t __len = _S_iterator_buf_len; 00089 size_t __buf_start_pos = __leaf_pos; 00090 size_t __leaf_end = __leaf_pos + __leaf->_M_size; 00091 char_producer<_CharT>* __fn = ((_Rope_RopeFunction<_CharT, 00092 _Alloc>*)__leaf)->_M_fn; 00093 if (__buf_start_pos + __len <= __pos) 00094 { 00095 __buf_start_pos = __pos - __len / 4; 00096 if (__buf_start_pos + __len > __leaf_end) 00097 __buf_start_pos = __leaf_end - __len; 00098 } 00099 if (__buf_start_pos + __len > __leaf_end) 00100 __len = __leaf_end - __buf_start_pos; 00101 (*__fn)(__buf_start_pos - __leaf_pos, __len, __x._M_tmp_buf); 00102 __x._M_buf_ptr = __x._M_tmp_buf + (__pos - __buf_start_pos); 00103 __x._M_buf_start = __x._M_tmp_buf; 00104 __x._M_buf_end = __x._M_tmp_buf + __len; 00105 } 00106 break; 00107 default: 00108 break; 00109 } 00110 } 00111 00112 // Set path and buffer inside a rope iterator. We assume that 00113 // pos and root are already set. 00114 template <class _CharT, class _Alloc> 00115 void 00116 _Rope_iterator_base<_CharT, _Alloc>:: 00117 _S_setcache(_Rope_iterator_base<_CharT, _Alloc>& __x) 00118 { 00119 const _RopeRep* __path[_Rope_constants::_S_max_rope_depth + 1]; 00120 const _RopeRep* __curr_rope; 00121 int __curr_depth = -1; /* index into path */ 00122 size_t __curr_start_pos = 0; 00123 size_t __pos = __x._M_current_pos; 00124 unsigned char __dirns = 0; // Bit vector marking right turns in the path 00125 00126 if (__pos >= __x._M_root->_M_size) 00127 { 00128 __x._M_buf_ptr = 0; 00129 return; 00130 } 00131 __curr_rope = __x._M_root; 00132 if (0 != __curr_rope->_M_c_string) 00133 { 00134 /* Treat the root as a leaf. */ 00135 __x._M_buf_start = __curr_rope->_M_c_string; 00136 __x._M_buf_end = __curr_rope->_M_c_string + __curr_rope->_M_size; 00137 __x._M_buf_ptr = __curr_rope->_M_c_string + __pos; 00138 __x._M_path_end[0] = __curr_rope; 00139 __x._M_leaf_index = 0; 00140 __x._M_leaf_pos = 0; 00141 return; 00142 } 00143 for(;;) 00144 { 00145 ++__curr_depth; 00146 __path[__curr_depth] = __curr_rope; 00147 switch(__curr_rope->_M_tag) 00148 { 00149 case _Rope_constants::_S_leaf: 00150 case _Rope_constants::_S_function: 00151 case _Rope_constants::_S_substringfn: 00152 __x._M_leaf_pos = __curr_start_pos; 00153 goto done; 00154 case _Rope_constants::_S_concat: 00155 { 00156 _Rope_RopeConcatenation<_CharT, _Alloc>* __c = 00157 (_Rope_RopeConcatenation<_CharT, _Alloc>*)__curr_rope; 00158 _RopeRep* __left = __c->_M_left; 00159 size_t __left_len = __left->_M_size; 00160 00161 __dirns <<= 1; 00162 if (__pos >= __curr_start_pos + __left_len) 00163 { 00164 __dirns |= 1; 00165 __curr_rope = __c->_M_right; 00166 __curr_start_pos += __left_len; 00167 } 00168 else 00169 __curr_rope = __left; 00170 } 00171 break; 00172 } 00173 } 00174 done: 00175 // Copy last section of path into _M_path_end. 00176 { 00177 int __i = -1; 00178 int __j = __curr_depth + 1 - _S_path_cache_len; 00179 00180 if (__j < 0) __j = 0; 00181 while (__j <= __curr_depth) 00182 __x._M_path_end[++__i] = __path[__j++]; 00183 __x._M_leaf_index = __i; 00184 } 00185 __x._M_path_directions = __dirns; 00186 _S_setbuf(__x); 00187 } 00188 00189 // Specialized version of the above. Assumes that 00190 // the path cache is valid for the previous position. 00191 template <class _CharT, class _Alloc> 00192 void 00193 _Rope_iterator_base<_CharT, _Alloc>:: 00194 _S_setcache_for_incr(_Rope_iterator_base<_CharT, _Alloc>& __x) 00195 { 00196 int __current_index = __x._M_leaf_index; 00197 const _RopeRep* __current_node = __x._M_path_end[__current_index]; 00198 size_t __len = __current_node->_M_size; 00199 size_t __node_start_pos = __x._M_leaf_pos; 00200 unsigned char __dirns = __x._M_path_directions; 00201 _Rope_RopeConcatenation<_CharT, _Alloc>* __c; 00202 00203 if (__x._M_current_pos - __node_start_pos < __len) 00204 { 00205 /* More stuff in this leaf, we just didn't cache it. */ 00206 _S_setbuf(__x); 00207 return; 00208 } 00209 // node_start_pos is starting position of last_node. 00210 while (--__current_index >= 0) 00211 { 00212 if (!(__dirns & 1) /* Path turned left */) 00213 break; 00214 __current_node = __x._M_path_end[__current_index]; 00215 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node; 00216 // Otherwise we were in the right child. Thus we should pop 00217 // the concatenation node. 00218 __node_start_pos -= __c->_M_left->_M_size; 00219 __dirns >>= 1; 00220 } 00221 if (__current_index < 0) 00222 { 00223 // We underflowed the cache. Punt. 00224 _S_setcache(__x); 00225 return; 00226 } 00227 __current_node = __x._M_path_end[__current_index]; 00228 __c = (_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node; 00229 // current_node is a concatenation node. We are positioned on the first 00230 // character in its right child. 00231 // node_start_pos is starting position of current_node. 00232 __node_start_pos += __c->_M_left->_M_size; 00233 __current_node = __c->_M_right; 00234 __x._M_path_end[++__current_index] = __current_node; 00235 __dirns |= 1; 00236 while (_Rope_constants::_S_concat == __current_node->_M_tag) 00237 { 00238 ++__current_index; 00239 if (_S_path_cache_len == __current_index) 00240 { 00241 int __i; 00242 for (__i = 0; __i < _S_path_cache_len-1; __i++) 00243 __x._M_path_end[__i] = __x._M_path_end[__i+1]; 00244 --__current_index; 00245 } 00246 __current_node = 00247 ((_Rope_RopeConcatenation<_CharT, _Alloc>*)__current_node)->_M_left; 00248 __x._M_path_end[__current_index] = __current_node; 00249 __dirns <<= 1; 00250 // node_start_pos is unchanged. 00251 } 00252 __x._M_leaf_index = __current_index; 00253 __x._M_leaf_pos = __node_start_pos; 00254 __x._M_path_directions = __dirns; 00255 _S_setbuf(__x); 00256 } 00257 00258 template <class _CharT, class _Alloc> 00259 void 00260 _Rope_iterator_base<_CharT, _Alloc>:: 00261 _M_incr(size_t __n) 00262 { 00263 _M_current_pos += __n; 00264 if (0 != _M_buf_ptr) 00265 { 00266 size_t __chars_left = _M_buf_end - _M_buf_ptr; 00267 if (__chars_left > __n) 00268 _M_buf_ptr += __n; 00269 else if (__chars_left == __n) 00270 { 00271 _M_buf_ptr += __n; 00272 _S_setcache_for_incr(*this); 00273 } 00274 else 00275 _M_buf_ptr = 0; 00276 } 00277 } 00278 00279 template <class _CharT, class _Alloc> 00280 void 00281 _Rope_iterator_base<_CharT, _Alloc>:: 00282 _M_decr(size_t __n) 00283 { 00284 if (0 != _M_buf_ptr) 00285 { 00286 size_t __chars_left = _M_buf_ptr - _M_buf_start; 00287 if (__chars_left >= __n) 00288 _M_buf_ptr -= __n; 00289 else 00290 _M_buf_ptr = 0; 00291 } 00292 _M_current_pos -= __n; 00293 } 00294 00295 template <class _CharT, class _Alloc> 00296 void 00297 _Rope_iterator<_CharT, _Alloc>:: 00298 _M_check() 00299 { 00300 if (_M_root_rope->_M_tree_ptr != this->_M_root) 00301 { 00302 // _Rope was modified. Get things fixed up. 00303 _RopeRep::_S_unref(this->_M_root); 00304 this->_M_root = _M_root_rope->_M_tree_ptr; 00305 _RopeRep::_S_ref(this->_M_root); 00306 this->_M_buf_ptr = 0; 00307 } 00308 } 00309 00310 template <class _CharT, class _Alloc> 00311 inline 00312 _Rope_const_iterator<_CharT, _Alloc>:: 00313 _Rope_const_iterator(const _Rope_iterator<_CharT, _Alloc>& __x) 00314 : _Rope_iterator_base<_CharT, _Alloc>(__x) 00315 { } 00316 00317 template <class _CharT, class _Alloc> 00318 inline 00319 _Rope_iterator<_CharT, _Alloc>:: 00320 _Rope_iterator(rope<_CharT, _Alloc>& __r, size_t __pos) 00321 : _Rope_iterator_base<_CharT,_Alloc>(__r._M_tree_ptr, __pos), 00322 _M_root_rope(&__r) 00323 { _RopeRep::_S_ref(this->_M_root); } 00324 00325 template <class _CharT, class _Alloc> 00326 inline size_t 00327 rope<_CharT, _Alloc>:: 00328 _S_char_ptr_len(const _CharT* __s) 00329 { 00330 const _CharT* __p = __s; 00331 00332 while (!_S_is0(*__p)) 00333 ++__p; 00334 return (__p - __s); 00335 } 00336 00337 00338 #ifndef __GC 00339 00340 template <class _CharT, class _Alloc> 00341 inline void 00342 _Rope_RopeRep<_CharT, _Alloc>:: 00343 _M_free_c_string() 00344 { 00345 _CharT* __cstr = _M_c_string; 00346 if (0 != __cstr) 00347 { 00348 size_t __size = this->_M_size + 1; 00349 _Destroy(__cstr, __cstr + __size); 00350 this->_Data_deallocate(__cstr, __size); 00351 } 00352 } 00353 00354 template <class _CharT, class _Alloc> 00355 inline void 00356 _Rope_RopeRep<_CharT, _Alloc>:: 00357 _S_free_string(_CharT* __s, size_t __n, allocator_type __a) 00358 { 00359 if (!_S_is_basic_char_type((_CharT*)0)) 00360 _Destroy(__s, __s + __n); 00361 00362 // This has to be a static member, so this gets a bit messy 00363 __a.deallocate(__s, 00364 _Rope_RopeLeaf<_CharT, _Alloc>::_S_rounded_up_size(__n)); 00365 } 00366 00367 // There are several reasons for not doing this with virtual destructors 00368 // and a class specific delete operator: 00369 // - A class specific delete operator can't easily get access to 00370 // allocator instances if we need them. 00371 // - Any virtual function would need a 4 or byte vtable pointer; 00372 // this only requires a one byte tag per object. 00373 template <class _CharT, class _Alloc> 00374 void 00375 _Rope_RopeRep<_CharT, _Alloc>:: 00376 _M_free_tree() 00377 { 00378 switch(_M_tag) 00379 { 00380 case _Rope_constants::_S_leaf: 00381 { 00382 _Rope_RopeLeaf<_CharT, _Alloc>* __l 00383 = (_Rope_RopeLeaf<_CharT, _Alloc>*)this; 00384 __l->_Rope_RopeLeaf<_CharT, _Alloc>::~_Rope_RopeLeaf(); 00385 _L_deallocate(__l, 1); 00386 break; 00387 } 00388 case _Rope_constants::_S_concat: 00389 { 00390 _Rope_RopeConcatenation<_CharT,_Alloc>* __c 00391 = (_Rope_RopeConcatenation<_CharT, _Alloc>*)this; 00392 __c->_Rope_RopeConcatenation<_CharT, _Alloc>:: ~_Rope_RopeConcatenation(); 00393 _C_deallocate(__c, 1); 00394 break; 00395 } 00396 case _Rope_constants::_S_function: 00397 { 00398 _Rope_RopeFunction<_CharT, _Alloc>* __f 00399 = (_Rope_RopeFunction<_CharT, _Alloc>*)this; 00400 __f->_Rope_RopeFunction<_CharT, _Alloc>::~_Rope_RopeFunction(); 00401 _F_deallocate(__f, 1); 00402 break; 00403 } 00404 case _Rope_constants::_S_substringfn: 00405 { 00406 _Rope_RopeSubstring<_CharT, _Alloc>* __ss = 00407 (_Rope_RopeSubstring<_CharT, _Alloc>*)this; 00408 __ss->_Rope_RopeSubstring<_CharT, _Alloc>:: ~_Rope_RopeSubstring(); 00409 _S_deallocate(__ss, 1); 00410 break; 00411 } 00412 } 00413 } 00414 #else 00415 00416 template <class _CharT, class _Alloc> 00417 inline void 00418 _Rope_RopeRep<_CharT, _Alloc>:: 00419 _S_free_string(const _CharT*, size_t, allocator_type) 00420 { } 00421 00422 #endif 00423 00424 // Concatenate a C string onto a leaf rope by copying the rope data. 00425 // Used for short ropes. 00426 template <class _CharT, class _Alloc> 00427 typename rope<_CharT, _Alloc>::_RopeLeaf* 00428 rope<_CharT, _Alloc>:: 00429 _S_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, size_t __len) 00430 { 00431 size_t __old_len = __r->_M_size; 00432 _CharT* __new_data = (_CharT*) 00433 _Data_allocate(_S_rounded_up_size(__old_len + __len)); 00434 _RopeLeaf* __result; 00435 00436 uninitialized_copy_n(__r->_M_data, __old_len, __new_data); 00437 uninitialized_copy_n(__iter, __len, __new_data + __old_len); 00438 _S_cond_store_eos(__new_data[__old_len + __len]); 00439 try 00440 { 00441 __result = _S_new_RopeLeaf(__new_data, __old_len + __len, 00442 __r->get_allocator()); 00443 } 00444 catch(...) 00445 { 00446 _RopeRep::__STL_FREE_STRING(__new_data, __old_len + __len, 00447 __r->get_allocator()); 00448 __throw_exception_again; 00449 } 00450 return __result; 00451 } 00452 00453 #ifndef __GC 00454 // As above, but it's OK to clobber original if refcount is 1 00455 template <class _CharT, class _Alloc> 00456 typename rope<_CharT,_Alloc>::_RopeLeaf* 00457 rope<_CharT, _Alloc>:: 00458 _S_destr_leaf_concat_char_iter(_RopeLeaf* __r, const _CharT* __iter, 00459 size_t __len) 00460 { 00461 if (__r->_M_ref_count > 1) 00462 return _S_leaf_concat_char_iter(__r, __iter, __len); 00463 size_t __old_len = __r->_M_size; 00464 if (_S_allocated_capacity(__old_len) >= __old_len + __len) 00465 { 00466 // The space has been partially initialized for the standard 00467 // character types. But that doesn't matter for those types. 00468 uninitialized_copy_n(__iter, __len, __r->_M_data + __old_len); 00469 if (_S_is_basic_char_type((_CharT*)0)) 00470 _S_cond_store_eos(__r->_M_data[__old_len + __len]); 00471 else if (__r->_M_c_string != __r->_M_data && 0 != __r->_M_c_string) 00472 { 00473 __r->_M_free_c_string(); 00474 __r->_M_c_string = 0; 00475 } 00476 __r->_M_size = __old_len + __len; 00477 __r->_M_ref_count = 2; 00478 return __r; 00479 } 00480 else 00481 { 00482 _RopeLeaf* __result = _S_leaf_concat_char_iter(__r, __iter, __len); 00483 return __result; 00484 } 00485 } 00486 #endif 00487 00488 // Assumes left and right are not 0. 00489 // Does not increment (nor decrement on exception) child reference counts. 00490 // Result has ref count 1. 00491 template <class _CharT, class _Alloc> 00492 typename rope<_CharT, _Alloc>::_RopeRep* 00493 rope<_CharT, _Alloc>:: 00494 _S_tree_concat(_RopeRep* __left, _RopeRep* __right) 00495 { 00496 _RopeConcatenation* __result = _S_new_RopeConcatenation(__left, __right, 00497 __left-> 00498 get_allocator()); 00499 size_t __depth = __result->_M_depth; 00500 00501 if (__depth > 20 && (__result->_M_size < 1000 00502 || __depth > _Rope_constants::_S_max_rope_depth)) 00503 { 00504 _RopeRep* __balanced; 00505 00506 try 00507 { 00508 __balanced = _S_balance(__result); 00509 __result->_M_unref_nonnil(); 00510 } 00511 catch(...) 00512 { 00513 _C_deallocate(__result,1); 00514 __throw_exception_again; 00515 } 00516 // In case of exception, we need to deallocate 00517 // otherwise dangling result node. But caller 00518 // still owns its children. Thus unref is 00519 // inappropriate. 00520 return __balanced; 00521 } 00522 else 00523 return __result; 00524 } 00525 00526 template <class _CharT, class _Alloc> 00527 typename rope<_CharT, _Alloc>::_RopeRep* 00528 rope<_CharT, _Alloc>:: 00529 _S_concat_char_iter(_RopeRep* __r, const _CharT*__s, size_t __slen) 00530 { 00531 _RopeRep* __result; 00532 if (0 == __slen) 00533 { 00534 _S_ref(__r); 00535 return __r; 00536 } 00537 if (0 == __r) 00538 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, 00539 __r->get_allocator()); 00540 if (_Rope_constants::_S_leaf == __r->_M_tag 00541 && __r->_M_size + __slen <= _S_copy_max) 00542 { 00543 __result = _S_leaf_concat_char_iter((_RopeLeaf*)__r, __s, __slen); 00544 return __result; 00545 } 00546 if (_Rope_constants::_S_concat == __r->_M_tag 00547 && _Rope_constants::_S_leaf == ((_RopeConcatenation*) 00548 __r)->_M_right->_M_tag) 00549 { 00550 _RopeLeaf* __right = 00551 (_RopeLeaf* )(((_RopeConcatenation* )__r)->_M_right); 00552 if (__right->_M_size + __slen <= _S_copy_max) 00553 { 00554 _RopeRep* __left = ((_RopeConcatenation*)__r)->_M_left; 00555 _RopeRep* __nright = 00556 _S_leaf_concat_char_iter((_RopeLeaf*)__right, __s, __slen); 00557 __left->_M_ref_nonnil(); 00558 try 00559 { __result = _S_tree_concat(__left, __nright); } 00560 catch(...) 00561 { 00562 _S_unref(__left); 00563 _S_unref(__nright); 00564 __throw_exception_again; 00565 } 00566 return __result; 00567 } 00568 } 00569 _RopeRep* __nright = 00570 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); 00571 try 00572 { 00573 __r->_M_ref_nonnil(); 00574 __result = _S_tree_concat(__r, __nright); 00575 } 00576 catch(...) 00577 { 00578 _S_unref(__r); 00579 _S_unref(__nright); 00580 __throw_exception_again; 00581 } 00582 return __result; 00583 } 00584 00585 #ifndef __GC 00586 template <class _CharT, class _Alloc> 00587 typename rope<_CharT,_Alloc>::_RopeRep* 00588 rope<_CharT,_Alloc>:: 00589 _S_destr_concat_char_iter(_RopeRep* __r, const _CharT* __s, size_t __slen) 00590 { 00591 _RopeRep* __result; 00592 if (0 == __r) 00593 return __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, 00594 __r->get_allocator()); 00595 size_t __count = __r->_M_ref_count; 00596 size_t __orig_size = __r->_M_size; 00597 if (__count > 1) 00598 return _S_concat_char_iter(__r, __s, __slen); 00599 if (0 == __slen) 00600 { 00601 __r->_M_ref_count = 2; // One more than before 00602 return __r; 00603 } 00604 if (__orig_size + __slen <= _S_copy_max 00605 && _Rope_constants::_S_leaf == __r->_M_tag) 00606 { 00607 __result = _S_destr_leaf_concat_char_iter((_RopeLeaf*)__r, __s, 00608 __slen); 00609 return __result; 00610 } 00611 if (_Rope_constants::_S_concat == __r->_M_tag) 00612 { 00613 _RopeLeaf* __right = (_RopeLeaf*)(((_RopeConcatenation*) 00614 __r)->_M_right); 00615 if (_Rope_constants::_S_leaf == __right->_M_tag 00616 && __right->_M_size + __slen <= _S_copy_max) 00617 { 00618 _RopeRep* __new_right = 00619 _S_destr_leaf_concat_char_iter(__right, __s, __slen); 00620 if (__right == __new_right) 00621 __new_right->_M_ref_count = 1; 00622 else 00623 __right->_M_unref_nonnil(); 00624 __r->_M_ref_count = 2; // One more than before. 00625 ((_RopeConcatenation*)__r)->_M_right = __new_right; 00626 __r->_M_size = __orig_size + __slen; 00627 if (0 != __r->_M_c_string) 00628 { 00629 __r->_M_free_c_string(); 00630 __r->_M_c_string = 0; 00631 } 00632 return __r; 00633 } 00634 } 00635 _RopeRep* __right = 00636 __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__s, __slen, __r->get_allocator()); 00637 __r->_M_ref_nonnil(); 00638 try 00639 { __result = _S_tree_concat(__r, __right); } 00640 catch(...) 00641 { 00642 _S_unref(__r); 00643 _S_unref(__right); 00644 __throw_exception_again; 00645 } 00646 return __result; 00647 } 00648 #endif /* !__GC */ 00649 00650 template <class _CharT, class _Alloc> 00651 typename rope<_CharT, _Alloc>::_RopeRep* 00652 rope<_CharT, _Alloc>:: 00653 _S_concat(_RopeRep* __left, _RopeRep* __right) 00654 { 00655 if (0 == __left) 00656 { 00657 _S_ref(__right); 00658 return __right; 00659 } 00660 if (0 == __right) 00661 { 00662 __left->_M_ref_nonnil(); 00663 return __left; 00664 } 00665 if (_Rope_constants::_S_leaf == __right->_M_tag) 00666 { 00667 if (_Rope_constants::_S_leaf == __left->_M_tag) 00668 { 00669 if (__right->_M_size + __left->_M_size <= _S_copy_max) 00670 return _S_leaf_concat_char_iter((_RopeLeaf*)__left, 00671 ((_RopeLeaf*)__right)->_M_data, 00672 __right->_M_size); 00673 } 00674 else if (_Rope_constants::_S_concat == __left->_M_tag 00675 && _Rope_constants::_S_leaf == ((_RopeConcatenation*) 00676 __left)->_M_right->_M_tag) 00677 { 00678 _RopeLeaf* __leftright = 00679 (_RopeLeaf*)(((_RopeConcatenation*)__left)->_M_right); 00680 if (__leftright->_M_size + __right->_M_size <= _S_copy_max) 00681 { 00682 _RopeRep* __leftleft = ((_RopeConcatenation*)__left)->_M_left; 00683 _RopeRep* __rest = _S_leaf_concat_char_iter(__leftright, 00684 ((_RopeLeaf*) 00685 __right)-> 00686 _M_data, 00687 __right->_M_size); 00688 __leftleft->_M_ref_nonnil(); 00689 try 00690 { return(_S_tree_concat(__leftleft, __rest)); } 00691 catch(...) 00692 { 00693 _S_unref(__leftleft); 00694 _S_unref(__rest); 00695 __throw_exception_again; 00696 } 00697 } 00698 } 00699 } 00700 __left->_M_ref_nonnil(); 00701 __right->_M_ref_nonnil(); 00702 try 00703 { return(_S_tree_concat(__left, __right)); } 00704 catch(...) 00705 { 00706 _S_unref(__left); 00707 _S_unref(__right); 00708 __throw_exception_again; 00709 } 00710 } 00711 00712 template <class _CharT, class _Alloc> 00713 typename rope<_CharT, _Alloc>::_RopeRep* 00714 rope<_CharT, _Alloc>:: 00715 _S_substring(_RopeRep* __base, size_t __start, size_t __endp1) 00716 { 00717 if (0 == __base) 00718 return 0; 00719 size_t __len = __base->_M_size; 00720 size_t __adj_endp1; 00721 const size_t __lazy_threshold = 128; 00722 00723 if (__endp1 >= __len) 00724 { 00725 if (0 == __start) 00726 { 00727 __base->_M_ref_nonnil(); 00728 return __base; 00729 } 00730 else 00731 __adj_endp1 = __len; 00732 00733 } 00734 else 00735 __adj_endp1 = __endp1; 00736 00737 switch(__base->_M_tag) 00738 { 00739 case _Rope_constants::_S_concat: 00740 { 00741 _RopeConcatenation* __c = (_RopeConcatenation*)__base; 00742 _RopeRep* __left = __c->_M_left; 00743 _RopeRep* __right = __c->_M_right; 00744 size_t __left_len = __left->_M_size; 00745 _RopeRep* __result; 00746 00747 if (__adj_endp1 <= __left_len) 00748 return _S_substring(__left, __start, __endp1); 00749 else if (__start >= __left_len) 00750 return _S_substring(__right, __start - __left_len, 00751 __adj_endp1 - __left_len); 00752 _Self_destruct_ptr __left_result(_S_substring(__left, 00753 __start, 00754 __left_len)); 00755 _Self_destruct_ptr __right_result(_S_substring(__right, 0, 00756 __endp1 00757 - __left_len)); 00758 __result = _S_concat(__left_result, __right_result); 00759 return __result; 00760 } 00761 case _Rope_constants::_S_leaf: 00762 { 00763 _RopeLeaf* __l = (_RopeLeaf*)__base; 00764 _RopeLeaf* __result; 00765 size_t __result_len; 00766 if (__start >= __adj_endp1) 00767 return 0; 00768 __result_len = __adj_endp1 - __start; 00769 if (__result_len > __lazy_threshold) 00770 goto lazy; 00771 #ifdef __GC 00772 const _CharT* __section = __l->_M_data + __start; 00773 __result = _S_new_RopeLeaf(__section, __result_len, 00774 __base->get_allocator()); 00775 __result->_M_c_string = 0; // Not eos terminated. 00776 #else 00777 // We should sometimes create substring node instead. 00778 __result = __STL_ROPE_FROM_UNOWNED_CHAR_PTR(__l->_M_data + __start, 00779 __result_len, 00780 __base-> 00781 get_allocator()); 00782 #endif 00783 return __result; 00784 } 00785 case _Rope_constants::_S_substringfn: 00786 // Avoid introducing multiple layers of substring nodes. 00787 { 00788 _RopeSubstring* __old = (_RopeSubstring*)__base; 00789 size_t __result_len; 00790 if (__start >= __adj_endp1) 00791 return 0; 00792 __result_len = __adj_endp1 - __start; 00793 if (__result_len > __lazy_threshold) 00794 { 00795 _RopeSubstring* __result = 00796 _S_new_RopeSubstring(__old->_M_base, 00797 __start + __old->_M_start, 00798 __adj_endp1 - __start, 00799 __base->get_allocator()); 00800 return __result; 00801 00802 } // *** else fall through: *** 00803 } 00804 case _Rope_constants::_S_function: 00805 { 00806 _RopeFunction* __f = (_RopeFunction*)__base; 00807 _CharT* __section; 00808 size_t __result_len; 00809 if (__start >= __adj_endp1) 00810 return 0; 00811 __result_len = __adj_endp1 - __start; 00812 00813 if (__result_len > __lazy_threshold) 00814 goto lazy; 00815 __section = (_CharT*) 00816 _Data_allocate(_S_rounded_up_size(__result_len)); 00817 try 00818 { (*(__f->_M_fn))(__start, __result_len, __section); } 00819 catch(...) 00820 { 00821 _RopeRep::__STL_FREE_STRING(__section, __result_len, 00822 __base->get_allocator()); 00823 __throw_exception_again; 00824 } 00825 _S_cond_store_eos(__section[__result_len]); 00826 return _S_new_RopeLeaf(__section, __result_len, 00827 __base->get_allocator()); 00828 } 00829 } 00830 lazy: 00831 { 00832 // Create substring node. 00833 return _S_new_RopeSubstring(__base, __start, __adj_endp1 - __start, 00834 __base->get_allocator()); 00835 } 00836 } 00837 00838 template<class _CharT> 00839 class _Rope_flatten_char_consumer 00840 : public _Rope_char_consumer<_CharT> 00841 { 00842 private: 00843 _CharT* _M_buf_ptr; 00844 public: 00845 00846 _Rope_flatten_char_consumer(_CharT* __buffer) 00847 { _M_buf_ptr = __buffer; }; 00848 00849 ~_Rope_flatten_char_consumer() {} 00850 00851 bool 00852 operator()(const _CharT* __leaf, size_t __n) 00853 { 00854 uninitialized_copy_n(__leaf, __n, _M_buf_ptr); 00855 _M_buf_ptr += __n; 00856 return true; 00857 } 00858 }; 00859 00860 template<class _CharT> 00861 class _Rope_find_char_char_consumer 00862 : public _Rope_char_consumer<_CharT> 00863 { 00864 private: 00865 _CharT _M_pattern; 00866 public: 00867 size_t _M_count; // Number of nonmatching characters 00868 00869 _Rope_find_char_char_consumer(_CharT __p) 00870 : _M_pattern(__p), _M_count(0) {} 00871 00872 ~_Rope_find_char_char_consumer() {} 00873 00874 bool 00875 operator()(const _CharT* __leaf, size_t __n) 00876 { 00877 size_t __i; 00878 for (__i = 0; __i < __n; __i++) 00879 { 00880 if (__leaf[__i] == _M_pattern) 00881 { 00882 _M_count += __i; 00883 return false; 00884 } 00885 } 00886 _M_count += __n; return true; 00887 } 00888 }; 00889 00890 template<class _CharT, class _Traits> 00891 // Here _CharT is both the stream and rope character type. 00892 class _Rope_insert_char_consumer 00893 : public _Rope_char_consumer<_CharT> 00894 { 00895 private: 00896 typedef basic_ostream<_CharT,_Traits> _Insert_ostream; 00897 _Insert_ostream& _M_o; 00898 public: 00899 _Rope_insert_char_consumer(_Insert_ostream& __writer) 00900 : _M_o(__writer) {}; 00901 ~_Rope_insert_char_consumer() { }; 00902 // Caller is presumed to own the ostream 00903 bool operator() (const _CharT* __leaf, size_t __n); 00904 // Returns true to continue traversal. 00905 }; 00906 00907 template<class _CharT, class _Traits> 00908 bool 00909 _Rope_insert_char_consumer<_CharT, _Traits>:: 00910 operator()(const _CharT* __leaf, size_t __n) 00911 { 00912 size_t __i; 00913 // We assume that formatting is set up correctly for each element. 00914 for (__i = 0; __i < __n; __i++) 00915 _M_o.put(__leaf[__i]); 00916 return true; 00917 } 00918 00919 template <class _CharT, class _Alloc> 00920 bool 00921 rope<_CharT, _Alloc>:: 00922 _S_apply_to_pieces(_Rope_char_consumer<_CharT>& __c, 00923 const _RopeRep* __r, size_t __begin, size_t __end) 00924 { 00925 if (0 == __r) 00926 return true; 00927 switch(__r->_M_tag) 00928 { 00929 case _Rope_constants::_S_concat: 00930 { 00931 _RopeConcatenation* __conc = (_RopeConcatenation*)__r; 00932 _RopeRep* __left = __conc->_M_left; 00933 size_t __left_len = __left->_M_size; 00934 if (__begin < __left_len) 00935 { 00936 size_t __left_end = std::min(__left_len, __end); 00937 if (!_S_apply_to_pieces(__c, __left, __begin, __left_end)) 00938 return false; 00939 } 00940 if (__end > __left_len) 00941 { 00942 _RopeRep* __right = __conc->_M_right; 00943 size_t __right_start = std::max(__left_len, __begin); 00944 if (!_S_apply_to_pieces(__c, __right, 00945 __right_start - __left_len, 00946 __end - __left_len)) 00947 return false; 00948 } 00949 } 00950 return true; 00951 case _Rope_constants::_S_leaf: 00952 { 00953 _RopeLeaf* __l = (_RopeLeaf*)__r; 00954 return __c(__l->_M_data + __begin, __end - __begin); 00955 } 00956 case _Rope_constants::_S_function: 00957 case _Rope_constants::_S_substringfn: 00958 { 00959 _RopeFunction* __f = (_RopeFunction*)__r; 00960 size_t __len = __end - __begin; 00961 bool __result; 00962 _CharT* __buffer = 00963 (_CharT*)_Alloc().allocate(__len * sizeof(_CharT)); 00964 try 00965 { 00966 (*(__f->_M_fn))(__begin, __len, __buffer); 00967 __result = __c(__buffer, __len); 00968 _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); 00969 } 00970 catch(...) 00971 { 00972 _Alloc().deallocate(__buffer, __len * sizeof(_CharT)); 00973 __throw_exception_again; 00974 } 00975 return __result; 00976 } 00977 default: 00978 return false; 00979 } 00980 } 00981 00982 template<class _CharT, class _Traits> 00983 inline void 00984 _Rope_fill(basic_ostream<_CharT, _Traits>& __o, size_t __n) 00985 { 00986 char __f = __o.fill(); 00987 size_t __i; 00988 00989 for (__i = 0; __i < __n; __i++) 00990 __o.put(__f); 00991 } 00992 00993 00994 template <class _CharT> 00995 inline bool 00996 _Rope_is_simple(_CharT*) 00997 { return false; } 00998 00999 inline bool 01000 _Rope_is_simple(char*) 01001 { return true; } 01002 01003 inline bool 01004 _Rope_is_simple(wchar_t*) 01005 { return true; } 01006 01007 template<class _CharT, class _Traits, class _Alloc> 01008 basic_ostream<_CharT, _Traits>& 01009 operator<<(basic_ostream<_CharT, _Traits>& __o, 01010 const rope<_CharT, _Alloc>& __r) 01011 { 01012 size_t __w = __o.width(); 01013 bool __left = bool(__o.flags() & std::ios::left); 01014 size_t __pad_len; 01015 size_t __rope_len = __r.size(); 01016 _Rope_insert_char_consumer<_CharT, _Traits> __c(__o); 01017 bool __is_simple = _Rope_is_simple((_CharT*)0); 01018 01019 if (__rope_len < __w) 01020 __pad_len = __w - __rope_len; 01021 else 01022 __pad_len = 0; 01023 01024 if (!__is_simple) 01025 __o.width(__w / __rope_len); 01026 try 01027 { 01028 if (__is_simple && !__left && __pad_len > 0) 01029 _Rope_fill(__o, __pad_len); 01030 __r.apply_to_pieces(0, __r.size(), __c); 01031 if (__is_simple && __left && __pad_len > 0) 01032 _Rope_fill(__o, __pad_len); 01033 if (!__is_simple) 01034 __o.width(__w); 01035 } 01036 catch(...) 01037 { 01038 if (!__is_simple) 01039 __o.width(__w); 01040 __throw_exception_again; 01041 } 01042 return __o; 01043 } 01044 01045 template <class _CharT, class _Alloc> 01046 _CharT* 01047 rope<_CharT, _Alloc>:: 01048 _S_flatten(_RopeRep* __r, size_t __start, size_t __len, 01049 _CharT* __buffer) 01050 { 01051 _Rope_flatten_char_consumer<_CharT> __c(__buffer); 01052 _S_apply_to_pieces(__c, __r, __start, __start + __len); 01053 return(__buffer + __len); 01054 } 01055 01056 template <class _CharT, class _Alloc> 01057 size_t 01058 rope<_CharT, _Alloc>:: 01059 find(_CharT __pattern, size_t __start) const 01060 { 01061 _Rope_find_char_char_consumer<_CharT> __c(__pattern); 01062 _S_apply_to_pieces(__c, this->_M_tree_ptr, __start, size()); 01063 size_type __result_pos = __start + __c._M_count; 01064 #ifndef __STL_OLD_ROPE_SEMANTICS 01065 if (__result_pos == size()) 01066 __result_pos = npos; 01067 #endif 01068 return __result_pos; 01069 } 01070 01071 template <class _CharT, class _Alloc> 01072 _CharT* 01073 rope<_CharT, _Alloc>:: 01074 _S_flatten(_RopeRep* __r, _CharT* __buffer) 01075 { 01076 if (0 == __r) 01077 return __buffer; 01078 switch(__r->_M_tag) 01079 { 01080 case _Rope_constants::_S_concat: 01081 { 01082 _RopeConcatenation* __c = (_RopeConcatenation*)__r; 01083 _RopeRep* __left = __c->_M_left; 01084 _RopeRep* __right = __c->_M_right; 01085 _CharT* __rest = _S_flatten(__left, __buffer); 01086 return _S_flatten(__right, __rest); 01087 } 01088 case _Rope_constants::_S_leaf: 01089 { 01090 _RopeLeaf* __l = (_RopeLeaf*)__r; 01091 return copy_n(__l->_M_data, __l->_M_size, __buffer).second; 01092 } 01093 case _Rope_constants::_S_function: 01094 case _Rope_constants::_S_substringfn: 01095 // We don't yet do anything with substring nodes. 01096 // This needs to be fixed before ropefiles will work well. 01097 { 01098 _RopeFunction* __f = (_RopeFunction*)__r; 01099 (*(__f->_M_fn))(0, __f->_M_size, __buffer); 01100 return __buffer + __f->_M_size; 01101 } 01102 default: 01103 return 0; 01104 } 01105 } 01106 01107 // This needs work for _CharT != char 01108 template <class _CharT, class _Alloc> 01109 void 01110 rope<_CharT, _Alloc>:: 01111 _S_dump(_RopeRep* __r, int __indent) 01112 { 01113 for (int __i = 0; __i < __indent; __i++) 01114 putchar(' '); 01115 if (0 == __r) 01116 { 01117 printf("NULL\n"); 01118 return; 01119 } 01120 if (_Rope_constants::_S_concat == __r->_M_tag) 01121 { 01122 _RopeConcatenation* __c = (_RopeConcatenation*)__r; 01123 _RopeRep* __left = __c->_M_left; 01124 _RopeRep* __right = __c->_M_right; 01125 01126 #ifdef __GC 01127 printf("Concatenation %p (depth = %d, len = %ld, %s balanced)\n", 01128 __r, __r->_M_depth, __r->_M_size, 01129 __r->_M_is_balanced? "" : "not"); 01130 #else 01131 printf("Concatenation %p (rc = %ld, depth = %d, " 01132 "len = %ld, %s balanced)\n", 01133 __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size, 01134 __r->_M_is_balanced? "" : "not"); 01135 #endif 01136 _S_dump(__left, __indent + 2); 01137 _S_dump(__right, __indent + 2); 01138 return; 01139 } 01140 else 01141 { 01142 char* __kind; 01143 01144 switch (__r->_M_tag) 01145 { 01146 case _Rope_constants::_S_leaf: 01147 __kind = "Leaf"; 01148 break; 01149 case _Rope_constants::_S_function: 01150 __kind = "Function"; 01151 break; 01152 case _Rope_constants::_S_substringfn: 01153 __kind = "Function representing substring"; 01154 break; 01155 default: 01156 __kind = "(corrupted kind field!)"; 01157 } 01158 #ifdef __GC 01159 printf("%s %p (depth = %d, len = %ld) ", 01160 __kind, __r, __r->_M_depth, __r->_M_size); 01161 #else 01162 printf("%s %p (rc = %ld, depth = %d, len = %ld) ", 01163 __kind, __r, __r->_M_ref_count, __r->_M_depth, __r->_M_size); 01164 #endif 01165 if (_S_is_one_byte_char_type((_CharT*)0)) 01166 { 01167 const int __max_len = 40; 01168 _Self_destruct_ptr __prefix(_S_substring(__r, 0, __max_len)); 01169 _CharT __buffer[__max_len + 1]; 01170 bool __too_big = __r->_M_size > __prefix->_M_size; 01171 01172 _S_flatten(__prefix, __buffer); 01173 __buffer[__prefix->_M_size] = _S_eos((_CharT*)0); 01174 printf("%s%s\n", (char*)__buffer, 01175 __too_big? "...\n" : "\n"); 01176 } 01177 else 01178 printf("\n"); 01179 } 01180 } 01181 01182 template <class _CharT, class _Alloc> 01183 const unsigned long 01184 rope<_CharT, _Alloc>:: 01185 _S_min_len[_Rope_constants::_S_max_rope_depth + 1] = { 01186 /* 0 */1, /* 1 */2, /* 2 */3, /* 3 */5, /* 4 */8, /* 5 */13, /* 6 */21, 01187 /* 7 */34, /* 8 */55, /* 9 */89, /* 10 */144, /* 11 */233, /* 12 */377, 01188 /* 13 */610, /* 14 */987, /* 15 */1597, /* 16 */2584, /* 17 */4181, 01189 /* 18 */6765, /* 19 */10946, /* 20 */17711, /* 21 */28657, /* 22 */46368, 01190 /* 23 */75025, /* 24 */121393, /* 25 */196418, /* 26 */317811, 01191 /* 27 */514229, /* 28 */832040, /* 29 */1346269, /* 30 */2178309, 01192 /* 31 */3524578, /* 32 */5702887, /* 33 */9227465, /* 34 */14930352, 01193 /* 35 */24157817, /* 36 */39088169, /* 37 */63245986, /* 38 */102334155, 01194 /* 39 */165580141, /* 40 */267914296, /* 41 */433494437, 01195 /* 42 */701408733, /* 43 */1134903170, /* 44 */1836311903, 01196 /* 45 */2971215073u }; 01197 // These are Fibonacci numbers < 2**32. 01198 01199 template <class _CharT, class _Alloc> 01200 typename rope<_CharT, _Alloc>::_RopeRep* 01201 rope<_CharT, _Alloc>:: 01202 _S_balance(_RopeRep* __r) 01203 { 01204 _RopeRep* __forest[_Rope_constants::_S_max_rope_depth + 1]; 01205 _RopeRep* __result = 0; 01206 int __i; 01207 // Invariant: 01208 // The concatenation of forest in descending order is equal to __r. 01209 // __forest[__i]._M_size >= _S_min_len[__i] 01210 // __forest[__i]._M_depth = __i 01211 // References from forest are included in refcount. 01212 01213 for (__i = 0; __i <= _Rope_constants::_S_max_rope_depth; ++__i) 01214 __forest[__i] = 0; 01215 try 01216 { 01217 _S_add_to_forest(__r, __forest); 01218 for (__i = 0; __i <= _Rope_constants::_S_max_rope_depth; ++__i) 01219 if (0 != __forest[__i]) 01220 { 01221 #ifndef __GC 01222 _Self_destruct_ptr __old(__result); 01223 #endif 01224 __result = _S_concat(__forest[__i], __result); 01225 __forest[__i]->_M_unref_nonnil(); 01226 #if !defined(__GC) && defined(__EXCEPTIONS) 01227 __forest[__i] = 0; 01228 #endif 01229 } 01230 } 01231 catch(...) 01232 { 01233 for(__i = 0; __i <= _Rope_constants::_S_max_rope_depth; __i++) 01234 _S_unref(__forest[__i]); 01235 __throw_exception_again; 01236 } 01237 01238 if (__result->_M_depth > _Rope_constants::_S_max_rope_depth) 01239 __throw_length_error(__N("rope::_S_balance")); 01240 return(__result); 01241 } 01242 01243 template <class _CharT, class _Alloc> 01244 void 01245 rope<_CharT, _Alloc>:: 01246 _S_add_to_forest(_RopeRep* __r, _RopeRep** __forest) 01247 { 01248 if (__r->_M_is_balanced) 01249 { 01250 _S_add_leaf_to_forest(__r, __forest); 01251 return; 01252 } 01253 01254 { 01255 _RopeConcatenation* __c = (_RopeConcatenation*)__r; 01256 01257 _S_add_to_forest(__c->_M_left, __forest); 01258 _S_add_to_forest(__c->_M_right, __forest); 01259 } 01260 } 01261 01262 01263 template <class _CharT, class _Alloc> 01264 void 01265 rope<_CharT, _Alloc>:: 01266 _S_add_leaf_to_forest(_RopeRep* __r, _RopeRep** __forest) 01267 { 01268 _RopeRep* __insertee; // included in refcount 01269 _RopeRep* __too_tiny = 0; // included in refcount 01270 int __i; // forest[0..__i-1] is empty 01271 size_t __s = __r->_M_size; 01272 01273 for (__i = 0; __s >= _S_min_len[__i+1]/* not this bucket */; ++__i) 01274 { 01275 if (0 != __forest[__i]) 01276 { 01277 #ifndef __GC 01278 _Self_destruct_ptr __old(__too_tiny); 01279 #endif 01280 __too_tiny = _S_concat_and_set_balanced(__forest[__i], 01281 __too_tiny); 01282 __forest[__i]->_M_unref_nonnil(); 01283 __forest[__i] = 0; 01284 } 01285 } 01286 { 01287 #ifndef __GC 01288 _Self_destruct_ptr __old(__too_tiny); 01289 #endif 01290 __insertee = _S_concat_and_set_balanced(__too_tiny, __r); 01291 } 01292 // Too_tiny dead, and no longer included in refcount. 01293 // Insertee is live and included. 01294 for (;; ++__i) 01295 { 01296 if (0 != __forest[__i]) 01297 { 01298 #ifndef __GC 01299 _Self_destruct_ptr __old(__insertee); 01300 #endif 01301 __insertee = _S_concat_and_set_balanced(__forest[__i], 01302 __insertee); 01303 __forest[__i]->_M_unref_nonnil(); 01304 __forest[__i] = 0; 01305 } 01306 if (__i == _Rope_constants::_S_max_rope_depth 01307 || __insertee->_M_size < _S_min_len[__i+1]) 01308 { 01309 __forest[__i] = __insertee; 01310 // refcount is OK since __insertee is now dead. 01311 return; 01312 } 01313 } 01314 } 01315 01316 template <class _CharT, class _Alloc> 01317 _CharT 01318 rope<_CharT, _Alloc>:: 01319 _S_fetch(_RopeRep* __r, size_type __i) 01320 { 01321 __GC_CONST _CharT* __cstr = __r->_M_c_string; 01322 01323 if (0 != __cstr) 01324 return __cstr[__i]; 01325 for(;;) 01326 { 01327 switch(__r->_M_tag) 01328 { 01329 case _Rope_constants::_S_concat: 01330 { 01331 _RopeConcatenation* __c = (_RopeConcatenation*)__r; 01332 _RopeRep* __left = __c->_M_left; 01333 size_t __left_len = __left->_M_size; 01334 01335 if (__i >= __left_len) 01336 { 01337 __i -= __left_len; 01338 __r = __c->_M_right; 01339 } 01340 else 01341 __r = __left; 01342 } 01343 break; 01344 case _Rope_constants::_S_leaf: 01345 { 01346 _RopeLeaf* __l = (_RopeLeaf*)__r; 01347 return __l->_M_data[__i]; 01348 } 01349 case _Rope_constants::_S_function: 01350 case _Rope_constants::_S_substringfn: 01351 { 01352 _RopeFunction* __f = (_RopeFunction*)__r; 01353 _CharT __result; 01354 01355 (*(__f->_M_fn))(__i, 1, &__result); 01356 return __result; 01357 } 01358 } 01359 } 01360 } 01361 01362 #ifndef __GC 01363 // Return a uniquely referenced character slot for the given 01364 // position, or 0 if that's not possible. 01365 template <class _CharT, class _Alloc> 01366 _CharT* 01367 rope<_CharT, _Alloc>:: 01368 _S_fetch_ptr(_RopeRep* __r, size_type __i) 01369 { 01370 _RopeRep* __clrstack[_Rope_constants::_S_max_rope_depth]; 01371 size_t __csptr = 0; 01372 01373 for(;;) 01374 { 01375 if (__r->_M_ref_count > 1) 01376 return 0; 01377 switch(__r->_M_tag) 01378 { 01379 case _Rope_constants::_S_concat: 01380 { 01381 _RopeConcatenation* __c = (_RopeConcatenation*)__r; 01382 _RopeRep* __left = __c->_M_left; 01383 size_t __left_len = __left->_M_size; 01384 01385 if (__c->_M_c_string != 0) 01386 __clrstack[__csptr++] = __c; 01387 if (__i >= __left_len) 01388 { 01389 __i -= __left_len; 01390 __r = __c->_M_right; 01391 } 01392 else 01393 __r = __left; 01394 } 01395 break; 01396 case _Rope_constants::_S_leaf: 01397 { 01398 _RopeLeaf* __l = (_RopeLeaf*)__r; 01399 if (__l->_M_c_string != __l->_M_data && __l->_M_c_string != 0) 01400 __clrstack[__csptr++] = __l; 01401 while (__csptr > 0) 01402 { 01403 -- __csptr; 01404 _RopeRep* __d = __clrstack[__csptr]; 01405 __d->_M_free_c_string(); 01406 __d->_M_c_string = 0; 01407 } 01408 return __l->_M_data + __i; 01409 } 01410 case _Rope_constants::_S_function: 01411 case _Rope_constants::_S_substringfn: 01412 return 0; 01413 } 01414 } 01415 } 01416 #endif /* __GC */ 01417 01418 // The following could be implemented trivially using 01419 // lexicographical_compare_3way. 01420 // We do a little more work to avoid dealing with rope iterators for 01421 // flat strings. 01422 template <class _CharT, class _Alloc> 01423 int 01424 rope<_CharT, _Alloc>:: 01425 _S_compare (const _RopeRep* __left, const _RopeRep* __right) 01426 { 01427 size_t __left_len; 01428 size_t __right_len; 01429 01430 if (0 == __right) 01431 return 0 != __left; 01432 if (0 == __left) 01433 return -1; 01434 __left_len = __left->_M_size; 01435 __right_len = __right->_M_size; 01436 if (_Rope_constants::_S_leaf == __left->_M_tag) 01437 { 01438 _RopeLeaf* __l = (_RopeLeaf*) __left; 01439 if (_RopeRep::_S_leaf == __right->_M_tag) 01440 { 01441 _RopeLeaf* __r = (_RopeLeaf*) __right; 01442 return lexicographical_compare_3way(__l->_M_data, 01443 __l->_M_data + __left_len, 01444 __r->_M_data, __r->_M_data 01445 + __right_len); 01446 } 01447 else 01448 { 01449 const_iterator __rstart(__right, 0); 01450 const_iterator __rend(__right, __right_len); 01451 return lexicographical_compare_3way(__l->_M_data, __l->_M_data 01452 + __left_len, 01453 __rstart, __rend); 01454 } 01455 } 01456 else 01457 { 01458 const_iterator __lstart(__left, 0); 01459 const_iterator __lend(__left, __left_len); 01460 if (_Rope_constants::_S_leaf == __right->_M_tag) 01461 { 01462 _RopeLeaf* __r = (_RopeLeaf*) __right; 01463 return lexicographical_compare_3way(__lstart, __lend, 01464 __r->_M_data, __r->_M_data 01465 + __right_len); 01466 } 01467 else 01468 { 01469 const_iterator __rstart(__right, 0); 01470 const_iterator __rend(__right, __right_len); 01471 return lexicographical_compare_3way(__lstart, __lend, 01472 __rstart, __rend); 01473 } 01474 } 01475 } 01476 01477 // Assignment to reference proxies. 01478 template <class _CharT, class _Alloc> 01479 _Rope_char_ref_proxy<_CharT, _Alloc>& 01480 _Rope_char_ref_proxy<_CharT, _Alloc>:: 01481 operator=(_CharT __c) 01482 { 01483 _RopeRep* __old = _M_root->_M_tree_ptr; 01484 #ifndef __GC 01485 // First check for the case in which everything is uniquely 01486 // referenced. In that case we can do this destructively. 01487 _CharT* __ptr = _My_rope::_S_fetch_ptr(__old, _M_pos); 01488 if (0 != __ptr) 01489 { 01490 *__ptr = __c; 01491 return *this; 01492 } 01493 #endif 01494 _Self_destruct_ptr __left(_My_rope::_S_substring(__old, 0, _M_pos)); 01495 _Self_destruct_ptr __right(_My_rope::_S_substring(__old, _M_pos + 1, 01496 __old->_M_size)); 01497 _Self_destruct_ptr __result_left(_My_rope:: 01498 _S_destr_concat_char_iter(__left, 01499 &__c, 1)); 01500 01501 _RopeRep* __result = _My_rope::_S_concat(__result_left, __right); 01502 #ifndef __GC 01503 _RopeRep::_S_unref(__old); 01504 #endif 01505 _M_root->_M_tree_ptr = __result; 01506 return *this; 01507 } 01508 01509 template <class _CharT, class _Alloc> 01510 inline _Rope_char_ref_proxy<_CharT, _Alloc>:: 01511 operator _CharT() const 01512 { 01513 if (_M_current_valid) 01514 return _M_current; 01515 else 01516 return _My_rope::_S_fetch(_M_root->_M_tree_ptr, _M_pos); 01517 } 01518 01519 template <class _CharT, class _Alloc> 01520 _Rope_char_ptr_proxy<_CharT, _Alloc> 01521 _Rope_char_ref_proxy<_CharT, _Alloc>:: 01522 operator&() const 01523 { return _Rope_char_ptr_proxy<_CharT, _Alloc>(*this); } 01524 01525 template <class _CharT, class _Alloc> 01526 rope<_CharT, _Alloc>:: 01527 rope(size_t __n, _CharT __c, const allocator_type& __a) 01528 : _Base(__a) 01529 { 01530 rope<_CharT,_Alloc> __result; 01531 const size_t __exponentiate_threshold = 32; 01532 size_t __exponent; 01533 size_t __rest; 01534 _CharT* __rest_buffer; 01535 _RopeRep* __remainder; 01536 rope<_CharT, _Alloc> __remainder_rope; 01537 01538 if (0 == __n) 01539 return; 01540 01541 __exponent = __n / __exponentiate_threshold; 01542 __rest = __n % __exponentiate_threshold; 01543 if (0 == __rest) 01544 __remainder = 0; 01545 else 01546 { 01547 __rest_buffer = this->_Data_allocate(_S_rounded_up_size(__rest)); 01548 uninitialized_fill_n(__rest_buffer, __rest, __c); 01549 _S_cond_store_eos(__rest_buffer[__rest]); 01550 try 01551 { __remainder = _S_new_RopeLeaf(__rest_buffer, __rest, __a); } 01552 catch(...) 01553 { 01554 _RopeRep::__STL_FREE_STRING(__rest_buffer, __rest, __a); 01555 __throw_exception_again; 01556 } 01557 } 01558 __remainder_rope._M_tree_ptr = __remainder; 01559 if (__exponent != 0) 01560 { 01561 _CharT* __base_buffer = 01562 this->_Data_allocate(_S_rounded_up_size(__exponentiate_threshold)); 01563 _RopeLeaf* __base_leaf; 01564 rope __base_rope; 01565 uninitialized_fill_n(__base_buffer, __exponentiate_threshold, __c); 01566 _S_cond_store_eos(__base_buffer[__exponentiate_threshold]); 01567 try 01568 { 01569 __base_leaf = _S_new_RopeLeaf(__base_buffer, 01570 __exponentiate_threshold, __a); 01571 } 01572 catch(...) 01573 { 01574 _RopeRep::__STL_FREE_STRING(__base_buffer, 01575 __exponentiate_threshold, __a); 01576 __throw_exception_again; 01577 } 01578 __base_rope._M_tree_ptr = __base_leaf; 01579 if (1 == __exponent) 01580 __result = __base_rope; 01581 else 01582 __result = power(__base_rope, __exponent, 01583 _Rope_Concat_fn<_CharT, _Alloc>()); 01584 01585 if (0 != __remainder) 01586 __result += __remainder_rope; 01587 } 01588 else 01589 __result = __remainder_rope; 01590 01591 this->_M_tree_ptr = __result._M_tree_ptr; 01592 this->_M_tree_ptr->_M_ref_nonnil(); 01593 } 01594 01595 template<class _CharT, class _Alloc> 01596 _CharT 01597 rope<_CharT, _Alloc>::_S_empty_c_str[1]; 01598 01599 template<class _CharT, class _Alloc> 01600 const _CharT* 01601 rope<_CharT, _Alloc>:: 01602 c_str() const 01603 { 01604 if (0 == this->_M_tree_ptr) 01605 { 01606 _S_empty_c_str[0] = _S_eos((_CharT*)0); // Possibly redundant, 01607 // but probably fast. 01608 return _S_empty_c_str; 01609 } 01610 __gthread_mutex_lock (&this->_M_tree_ptr->_M_c_string_lock); 01611 __GC_CONST _CharT* __result = this->_M_tree_ptr->_M_c_string; 01612 if (0 == __result) 01613 { 01614 size_t __s = size(); 01615 __result = this->_Data_allocate(__s + 1); 01616 _S_flatten(this->_M_tree_ptr, __result); 01617 __result[__s] = _S_eos((_CharT*)0); 01618 this->_M_tree_ptr->_M_c_string = __result; 01619 } 01620 __gthread_mutex_unlock (&this->_M_tree_ptr->_M_c_string_lock); 01621 return(__result); 01622 } 01623 01624 template<class _CharT, class _Alloc> 01625 const _CharT* rope<_CharT, _Alloc>:: 01626 replace_with_c_str() 01627 { 01628 if (0 == this->_M_tree_ptr) 01629 { 01630 _S_empty_c_str[0] = _S_eos((_CharT*)0); 01631 return _S_empty_c_str; 01632 } 01633 __GC_CONST _CharT* __old_c_string = this->_M_tree_ptr->_M_c_string; 01634 if (_Rope_constants::_S_leaf == this->_M_tree_ptr->_M_tag 01635 && 0 != __old_c_string) 01636 return(__old_c_string); 01637 size_t __s = size(); 01638 _CharT* __result = this->_Data_allocate(_S_rounded_up_size(__s)); 01639 _S_flatten(this->_M_tree_ptr, __result); 01640 __result[__s] = _S_eos((_CharT*)0); 01641 this->_M_tree_ptr->_M_unref_nonnil(); 01642 this->_M_tree_ptr = _S_new_RopeLeaf(__result, __s, 01643 this->get_allocator()); 01644 return(__result); 01645 } 01646 01647 // Algorithm specializations. More should be added. 01648 01649 template<class _Rope_iterator> // was templated on CharT and Alloc 01650 void // VC++ workaround 01651 _Rope_rotate(_Rope_iterator __first, 01652 _Rope_iterator __middle, 01653 _Rope_iterator __last) 01654 { 01655 typedef typename _Rope_iterator::value_type _CharT; 01656 typedef typename _Rope_iterator::_allocator_type _Alloc; 01657 01658 rope<_CharT, _Alloc>& __r(__first.container()); 01659 rope<_CharT, _Alloc> __prefix = __r.substr(0, __first.index()); 01660 rope<_CharT, _Alloc> __suffix = 01661 __r.substr(__last.index(), __r.size() - __last.index()); 01662 rope<_CharT, _Alloc> __part1 = 01663 __r.substr(__middle.index(), __last.index() - __middle.index()); 01664 rope<_CharT, _Alloc> __part2 = 01665 __r.substr(__first.index(), __middle.index() - __first.index()); 01666 __r = __prefix; 01667 __r += __part1; 01668 __r += __part2; 01669 __r += __suffix; 01670 } 01671 01672 #if !defined(__GNUC__) 01673 // Appears to confuse g++ 01674 inline void 01675 rotate(_Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __first, 01676 _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __middle, 01677 _Rope_iterator<char, __STL_DEFAULT_ALLOCATOR(char)> __last) 01678 { _Rope_rotate(__first, __middle, __last); } 01679 #endif 01680 01681 # if 0 01682 // Probably not useful for several reasons: 01683 // - for SGIs 7.1 compiler and probably some others, 01684 // this forces lots of rope<wchar_t, ...> instantiations, creating a 01685 // code bloat and compile time problem. (Fixed in 7.2.) 01686 // - wchar_t is 4 bytes wide on most UNIX platforms, making it 01687 // unattractive for unicode strings. Unsigned short may be a better 01688 // character type. 01689 inline void 01690 rotate(_Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __first, 01691 _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __middle, 01692 _Rope_iterator<wchar_t, __STL_DEFAULT_ALLOCATOR(char)> __last) 01693 { _Rope_rotate(__first, __middle, __last); } 01694 # endif 01695 01696 } // namespace __gnu_cxx 01697 01698 // Local Variables: 01699 // mode:C++ 01700 // End: 01701

Generated on Sun Jul 25 00:12:33 2004 for libstdc++ source by doxygen 1.3.7