1 /* 2 * 3 * 4 * Copyright (c) 1994 5 * Hewlett-Packard Company 6 * 7 * Copyright (c) 1996,1997 8 * Silicon Graphics Computer Systems, Inc. 9 * 10 * Copyright (c) 1997 11 * Moscow Center for SPARC Technology 12 * 13 * Copyright (c) 1999 14 * Boris Fomitchev 15 * 16 * This material is provided "as is", with absolutely no warranty expressed 17 * or implied. Any use is at your own risk. 18 * 19 * Permission to use or copy this software for any purpose is hereby granted 20 * without fee, provided the above notices are retained on all copies. 21 * Permission to modify the code and to distribute modified code is granted, 22 * provided the above notices are retained, and a notice that the code was 23 * modified is included with the above copyright notice. 24 * 25 */ 26 #ifndef _STLP_DEQUE_C 27 #define _STLP_DEQUE_C 28 29 #ifndef _STLP_INTERNAL_DEQUE_H 30 # include <stl/_deque.h> 31 #endif 32 33 _STLP_BEGIN_NAMESPACE 34 35 _STLP_MOVE_TO_PRIV_NAMESPACE 36 37 // Non-inline member functions from _Deque_base. 38 39 template <class _Tp, class _Alloc > 40 _Deque_base<_Tp,_Alloc >::~_Deque_base() { 41 if (_M_map._M_data) { 42 _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1); 43 _M_map.deallocate(_M_map._M_data, _M_map_size._M_data); 44 } 45 } 46 47 template <class _Tp, class _Alloc > 48 void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) { 49 size_t __num_nodes = __num_elements / this->buffer_size() + 1 ; 50 51 _M_map_size._M_data = (max)((size_t) _S_initial_map_size, __num_nodes + 2); 52 _M_map._M_data = _M_map.allocate(_M_map_size._M_data); 53 54 _Tp** __nstart = _M_map._M_data + (_M_map_size._M_data - __num_nodes) / 2; 55 _Tp** __nfinish = __nstart + __num_nodes; 56 57 _STLP_TRY { 58 _M_create_nodes(__nstart, __nfinish); 59 } 60 _STLP_UNWIND((_M_map.deallocate(_M_map._M_data, _M_map_size._M_data), 61 _M_map._M_data = 0, _M_map_size._M_data = 0)) 62 _M_start._M_set_node(__nstart); 63 this->_M_finish._M_set_node(__nfinish - 1); 64 _M_start._M_cur = _M_start._M_first; 65 this->_M_finish._M_cur = this->_M_finish._M_first + __num_elements % this->buffer_size(); 66 } 67 68 template <class _Tp, class _Alloc > 69 void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, 70 _Tp** __nfinish) { 71 _Tp** __cur = __nstart; 72 _STLP_TRY { 73 for (; __cur < __nfinish; ++__cur) 74 *__cur = _M_map_size.allocate(this->buffer_size()); 75 } 76 _STLP_UNWIND(_M_destroy_nodes(__nstart, __cur)) 77 } 78 79 template <class _Tp, class _Alloc > 80 void _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart, 81 _Tp** __nfinish) { 82 for (_Tp** __n = __nstart; __n < __nfinish; ++__n) 83 _M_map_size.deallocate(*__n, this->buffer_size()); 84 } 85 86 #if defined (_STLP_USE_PTR_SPECIALIZATIONS) 87 # define deque _STLP_PTR_IMPL_NAME(deque) 88 #elif defined (_STLP_DEBUG) 89 # define deque _STLP_NON_DBG_NAME(deque) 90 #else 91 _STLP_MOVE_TO_STD_NAMESPACE 92 #endif 93 94 #if defined (_STLP_NESTED_TYPE_PARAM_BUG) 95 // qualified references 96 # define __iterator__ _Deque_iterator<_Tp, _Nonconst_traits<_Tp> > 97 # define const_iterator _Deque_iterator<_Tp, _Const_traits<_Tp> > 98 # define iterator __iterator__ 99 # define size_type size_t 100 # define value_type _Tp 101 #else 102 # define __iterator__ _STLP_TYPENAME_ON_RETURN_TYPE deque<_Tp, _Alloc>::iterator 103 #endif 104 105 template <class _Tp, class _Alloc > 106 deque<_Tp, _Alloc >& 107 deque<_Tp, _Alloc >::operator= (const deque<_Tp, _Alloc >& __x) { 108 const size_type __len = size(); 109 if (&__x != this) { 110 if (__len >= __x.size()) 111 erase(_STLP_STD::copy(__x.begin(), __x.end(), this->_M_start), this->_M_finish); 112 else { 113 const_iterator __mid = __x.begin() + difference_type(__len); 114 _STLP_STD::copy(__x.begin(), __mid, this->_M_start); 115 insert(this->_M_finish, __mid, __x.end()); 116 } 117 } 118 return *this; 119 } 120 121 template <class _Tp, class _Alloc > 122 void deque<_Tp, _Alloc >::_M_fill_insert(iterator __pos, 123 size_type __n, const value_type& __x) { 124 #if !defined (_STLP_NO_MOVE_SEMANTIC) 125 typedef typename __move_traits<_Tp>::implemented _Movable; 126 #endif 127 if (__pos._M_cur == this->_M_start._M_cur) { 128 iterator __new_start = _M_reserve_elements_at_front(__n); 129 _STLP_TRY { 130 uninitialized_fill(__new_start, this->_M_start, __x); 131 } 132 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) 133 this->_M_start = __new_start; 134 } 135 else if (__pos._M_cur == this->_M_finish._M_cur) { 136 iterator __new_finish = _M_reserve_elements_at_back(__n); 137 _STLP_TRY { 138 uninitialized_fill(this->_M_finish, __new_finish, __x); 139 } 140 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1)) 141 this->_M_finish = __new_finish; 142 } 143 else 144 _M_fill_insert_aux(__pos, __n, __x, _Movable()); 145 } 146 147 #if !defined (_STLP_MEMBER_TEMPLATES) 148 149 template <class _Tp, class _Alloc > 150 void deque<_Tp, _Alloc>::insert(iterator __pos, 151 const value_type* __first, const value_type* __last) { 152 #if !defined (_STLP_NO_MOVE_SEMANTIC) 153 typedef typename __move_traits<_Tp>::implemented _Movable; 154 #endif 155 size_type __n = __last - __first; 156 if (__pos._M_cur == this->_M_start._M_cur) { 157 iterator __new_start = _M_reserve_elements_at_front(__n); 158 _STLP_TRY { 159 _STLP_PRIV __ucopy(__first, __last, __new_start); 160 } 161 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) 162 this->_M_start = __new_start; 163 } 164 else if (__pos._M_cur == this->_M_finish._M_cur) { 165 iterator __new_finish = _M_reserve_elements_at_back(__n); 166 _STLP_TRY { 167 _STLP_PRIV __ucopy(__first, __last, this->_M_finish); 168 } 169 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, 170 __new_finish._M_node + 1)) 171 this->_M_finish = __new_finish; 172 } 173 else 174 _M_insert_range_aux(__pos, __first, __last, __n, _Movable()); 175 } 176 177 template <class _Tp, class _Alloc > 178 void deque<_Tp,_Alloc>::insert(iterator __pos, 179 const_iterator __first, const_iterator __last) { 180 #if !defined (_STLP_NO_MOVE_SEMANTIC) 181 typedef typename __move_traits<_Tp>::implemented _Movable; 182 #endif 183 size_type __n = __last - __first; 184 if (__pos._M_cur == this->_M_start._M_cur) { 185 iterator __new_start = _M_reserve_elements_at_front(__n); 186 _STLP_TRY { 187 _STLP_PRIV __ucopy(__first, __last, __new_start); 188 } 189 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) 190 this->_M_start = __new_start; 191 } 192 else if (__pos._M_cur == this->_M_finish._M_cur) { 193 iterator __new_finish = _M_reserve_elements_at_back(__n); 194 _STLP_TRY { 195 _STLP_PRIV __ucopy(__first, __last, this->_M_finish); 196 } 197 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, 198 __new_finish._M_node + 1)) 199 this->_M_finish = __new_finish; 200 } 201 else 202 _M_insert_range_aux(__pos, __first, __last, __n, _Movable()); 203 } 204 205 #endif /* _STLP_MEMBER_TEMPLATES */ 206 207 template <class _Tp, class _Alloc > 208 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos, 209 const __true_type& /*_Movable*/) { 210 difference_type __index = __pos - this->_M_start; 211 if (size_type(__index) < this->size() >> 1) { 212 //We move the start of the deque one position to the right 213 //starting from the rightmost element to move. 214 iterator __src = __pos, __dst = __pos; 215 _STLP_STD::_Destroy(&(*__dst)); 216 if (__src != this->_M_start) { 217 for (--__src; __dst != this->_M_start; --__src, --__dst) { 218 _STLP_STD::_Move_Construct(&(*__dst), *__src); 219 _STLP_STD::_Destroy_Moved(&(*__src)); 220 } 221 } 222 _M_pop_front_aux(); 223 } 224 else { 225 iterator __src = __pos, __dst = __pos; 226 _STLP_STD::_Destroy(&(*__dst)); 227 for (++__src; __src != this->_M_finish; ++__src, ++__dst) { 228 _STLP_STD::_Move_Construct(&(*__dst), *__src); 229 _STLP_STD::_Destroy_Moved(&(*__src)); 230 } 231 //Duplication of the pop_back code without the destroy which has already been done: 232 if (this->_M_finish._M_cur != this->_M_finish._M_first) { 233 --this->_M_finish._M_cur; 234 } 235 else { 236 _M_pop_back_aux(); 237 } 238 } 239 return this->_M_start + __index; 240 } 241 242 template <class _Tp, class _Alloc > 243 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos, 244 const __false_type& /*_Movable*/) { 245 iterator __next = __pos; 246 ++__next; 247 difference_type __index = __pos - this->_M_start; 248 if (size_type(__index) < this->size() >> 1) { 249 copy_backward(this->_M_start, __pos, __next); 250 pop_front(); 251 } 252 else { 253 _STLP_STD::copy(__next, this->_M_finish, __pos); 254 pop_back(); 255 } 256 return this->_M_start + __index; 257 } 258 259 template <class _Tp, class _Alloc > 260 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last, 261 const __true_type& /*_Movable*/) { 262 difference_type __n = __last - __first; 263 difference_type __elems_before = __first - this->_M_start; 264 if (__elems_before <= difference_type(this->size() - __n) / 2) { 265 iterator __src = __first, __dst = __last; 266 if (__src != this->_M_start) { 267 for (--__src, --__dst; (__src >= this->_M_start) && (__dst >= __first); --__src, --__dst) { 268 _STLP_STD::_Destroy(&(*__dst)); 269 _STLP_STD::_Move_Construct(&(*__dst), *__src); 270 } 271 if (__dst >= __first) { 272 //There are more elements to erase than elements to move 273 _STLP_STD::_Destroy_Range(__first, ++__dst); 274 _STLP_STD::_Destroy_Moved_Range(this->_M_start, __first); 275 } 276 else { 277 //There are more elements to move than elements to erase 278 for (; __src >= this->_M_start; --__src, --__dst) { 279 _STLP_STD::_Destroy_Moved(&(*__dst)); 280 _STLP_STD::_Move_Construct(&(*__dst), *__src); 281 } 282 _STLP_STD::_Destroy_Moved_Range(this->_M_start, ++__dst); 283 } 284 } 285 else { 286 _STLP_STD::_Destroy_Range(this->_M_start, __last); 287 } 288 iterator __new_start = this->_M_start + __n; 289 this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node); 290 this->_M_start = __new_start; 291 } 292 else { 293 if (__last != this->_M_finish) { 294 iterator __src = __last, __dst = __first; 295 for (; (__src != this->_M_finish) && (__dst != __last); ++__src, ++__dst) { 296 _STLP_STD::_Destroy(&(*__dst)); 297 _STLP_STD::_Move_Construct(&(*__dst), *__src); 298 } 299 if (__dst != __last) { 300 //There are more elements to erase than elements to move 301 _STLP_STD::_Destroy_Range(__dst, __last); 302 _STLP_STD::_Destroy_Moved_Range(__last, this->_M_finish); 303 } 304 else { 305 //There are more elements to move than elements to erase 306 for (; __src != this->_M_finish; ++__src, ++__dst) { 307 _STLP_STD::_Destroy_Moved(&(*__dst)); 308 _STLP_STD::_Move_Construct(&(*__dst), *__src); 309 } 310 _STLP_STD::_Destroy_Moved_Range(__dst, this->_M_finish); 311 } 312 } 313 else { 314 _STLP_STD::_Destroy_Range(__first, this->_M_finish); 315 } 316 iterator __new_finish = this->_M_finish - __n; 317 this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1); 318 this->_M_finish = __new_finish; 319 } 320 return this->_M_start + __elems_before; 321 } 322 323 template <class _Tp, class _Alloc > 324 __iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last, 325 const __false_type& /*_Movable*/) { 326 difference_type __n = __last - __first; 327 difference_type __elems_before = __first - this->_M_start; 328 if (__elems_before <= difference_type(this->size() - __n) / 2) { 329 copy_backward(this->_M_start, __first, __last); 330 iterator __new_start = this->_M_start + __n; 331 _STLP_STD::_Destroy_Range(this->_M_start, __new_start); 332 this->_M_destroy_nodes(this->_M_start._M_node, __new_start._M_node); 333 this->_M_start = __new_start; 334 } 335 else { 336 _STLP_STD::copy(__last, this->_M_finish, __first); 337 iterator __new_finish = this->_M_finish - __n; 338 _STLP_STD::_Destroy_Range(__new_finish, this->_M_finish); 339 this->_M_destroy_nodes(__new_finish._M_node + 1, this->_M_finish._M_node + 1); 340 this->_M_finish = __new_finish; 341 } 342 return this->_M_start + __elems_before; 343 } 344 345 template <class _Tp, class _Alloc > 346 void deque<_Tp,_Alloc>::clear() { 347 for (_Map_pointer __node = this->_M_start._M_node + 1; 348 __node < this->_M_finish._M_node; 349 ++__node) { 350 _STLP_STD::_Destroy_Range(*__node, *__node + this->buffer_size()); 351 this->_M_map_size.deallocate(*__node, this->buffer_size()); 352 } 353 354 if (this->_M_start._M_node != this->_M_finish._M_node) { 355 _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_start._M_last); 356 _STLP_STD::_Destroy_Range(this->_M_finish._M_first, this->_M_finish._M_cur); 357 this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size()); 358 } 359 else 360 _STLP_STD::_Destroy_Range(this->_M_start._M_cur, this->_M_finish._M_cur); 361 362 this->_M_finish = this->_M_start; 363 } 364 365 // Precondition: this->_M_start and this->_M_finish have already been initialized, 366 // but none of the deque's elements have yet been constructed. 367 template <class _Tp, class _Alloc > 368 void deque<_Tp,_Alloc>::_M_fill_initialize(const value_type& __val, 369 const __false_type& /*_TrivialInit*/) { 370 _Map_pointer __cur = this->_M_start._M_node; 371 _STLP_TRY { 372 for (; __cur < this->_M_finish._M_node; ++__cur) 373 uninitialized_fill(*__cur, *__cur + this->buffer_size(), __val); 374 uninitialized_fill(this->_M_finish._M_first, this->_M_finish._M_cur, __val); 375 } 376 _STLP_UNWIND(_STLP_STD::_Destroy_Range(this->_M_start, iterator(*__cur, __cur))) 377 } 378 379 380 // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1. 381 template <class _Tp, class _Alloc > 382 void deque<_Tp,_Alloc>::_M_push_back_aux_v(const value_type& __t) { 383 _M_reserve_map_at_back(); 384 *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size()); 385 _STLP_TRY { 386 _Copy_Construct(this->_M_finish._M_cur, __t); 387 this->_M_finish._M_set_node(this->_M_finish._M_node + 1); 388 this->_M_finish._M_cur = this->_M_finish._M_first; 389 } 390 _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1), 391 this->buffer_size())) 392 } 393 394 #if defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS) 395 // Called only if this->_M_finish._M_cur == this->_M_finish._M_last - 1. 396 template <class _Tp, class _Alloc > 397 void deque<_Tp,_Alloc>::_M_push_back_aux() { 398 _M_reserve_map_at_back(); 399 *(this->_M_finish._M_node + 1) = this->_M_map_size.allocate(this->buffer_size()); 400 _STLP_TRY { 401 _STLP_STD::_Construct(this->_M_finish._M_cur); 402 this->_M_finish._M_set_node(this->_M_finish._M_node + 1); 403 this->_M_finish._M_cur = this->_M_finish._M_first; 404 } 405 _STLP_UNWIND(this->_M_map_size.deallocate(*(this->_M_finish._M_node + 1), 406 this->buffer_size())) 407 } 408 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 409 410 // Called only if this->_M_start._M_cur == this->_M_start._M_first. 411 template <class _Tp, class _Alloc > 412 void deque<_Tp,_Alloc>::_M_push_front_aux_v(const value_type& __t) { 413 _M_reserve_map_at_front(); 414 *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size()); 415 _STLP_TRY { 416 this->_M_start._M_set_node(this->_M_start._M_node - 1); 417 this->_M_start._M_cur = this->_M_start._M_last - 1; 418 _Copy_Construct(this->_M_start._M_cur, __t); 419 } 420 _STLP_UNWIND((++this->_M_start, 421 this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), this->buffer_size()))) 422 } 423 424 425 #if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS) 426 // Called only if this->_M_start._M_cur == this->_M_start._M_first. 427 template <class _Tp, class _Alloc > 428 void deque<_Tp,_Alloc>::_M_push_front_aux() { 429 _M_reserve_map_at_front(); 430 *(this->_M_start._M_node - 1) = this->_M_map_size.allocate(this->buffer_size()); 431 _STLP_TRY { 432 this->_M_start._M_set_node(this->_M_start._M_node - 1); 433 this->_M_start._M_cur = this->_M_start._M_last - 1; 434 _STLP_STD::_Construct(this->_M_start._M_cur); 435 } 436 _STLP_UNWIND((++this->_M_start, this->_M_map_size.deallocate(*(this->_M_start._M_node - 1), 437 this->buffer_size()))) 438 } 439 #endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/ 440 441 // Called only if this->_M_finish._M_cur == this->_M_finish._M_first. 442 template <class _Tp, class _Alloc > 443 void deque<_Tp,_Alloc>::_M_pop_back_aux() { 444 this->_M_map_size.deallocate(this->_M_finish._M_first, this->buffer_size()); 445 this->_M_finish._M_set_node(this->_M_finish._M_node - 1); 446 this->_M_finish._M_cur = this->_M_finish._M_last - 1; 447 } 448 449 // Note that if the deque has at least one element (a precondition for this member 450 // function), and if this->_M_start._M_cur == this->_M_start._M_last, then the deque 451 // must have at least two nodes. 452 template <class _Tp, class _Alloc > 453 void deque<_Tp,_Alloc>::_M_pop_front_aux() { 454 if (this->_M_start._M_cur != this->_M_start._M_last - 1) 455 ++this->_M_start._M_cur; 456 else { 457 this->_M_map_size.deallocate(this->_M_start._M_first, this->buffer_size()); 458 this->_M_start._M_set_node(this->_M_start._M_node + 1); 459 this->_M_start._M_cur = this->_M_start._M_first; 460 } 461 } 462 463 template <class _Tp, class _Alloc > 464 __iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n, 465 const value_type& __x, 466 const __true_type& /*_Movable*/) { 467 const difference_type __elems_before = __pos - this->_M_start; 468 size_type __length = this->size(); 469 value_type __x_copy = __x; 470 if (__elems_before <= difference_type(__length / 2)) { 471 iterator __new_start = _M_reserve_elements_at_front(__n); 472 __pos = this->_M_start + __elems_before; 473 _STLP_TRY { 474 iterator __dst = __new_start; 475 iterator __src = this->_M_start; 476 for (; __src != __pos; ++__dst, ++__src) { 477 _STLP_STD::_Move_Construct(&(*__dst), *__src); 478 _STLP_STD::_Destroy_Moved(&(*__src)); 479 } 480 this->_M_start = __new_start; 481 uninitialized_fill(__dst, __src, __x_copy); 482 __pos = __dst; 483 } 484 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) 485 } 486 else { 487 iterator __new_finish = _M_reserve_elements_at_back(__n); 488 const difference_type __elems_after = difference_type(__length) - __elems_before; 489 __pos = this->_M_finish - __elems_after; 490 _STLP_TRY { 491 iterator __dst = __new_finish; 492 iterator __src = this->_M_finish; 493 for (--__src, --__dst; __src >= __pos; --__src, --__dst) { 494 _STLP_STD::_Move_Construct(&(*__dst), *__src); 495 _STLP_STD::_Destroy_Moved(&(*__src)); 496 } 497 this->_M_finish = __new_finish; 498 uninitialized_fill(__pos, __pos + __n, __x_copy); 499 } 500 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) 501 } 502 return __pos; 503 } 504 505 template <class _Tp, class _Alloc > 506 __iterator__ deque<_Tp,_Alloc>::_M_fill_insert_aux(iterator __pos, size_type __n, 507 const value_type& __x, 508 const __false_type& /*_Movable*/) { 509 const difference_type __elems_before = __pos - this->_M_start; 510 size_type __length = this->size(); 511 value_type __x_copy = __x; 512 if (__elems_before <= difference_type(__length / 2)) { 513 iterator __new_start = _M_reserve_elements_at_front(__n); 514 iterator __old_start = this->_M_start; 515 __pos = this->_M_start + __elems_before; 516 _STLP_TRY { 517 if (__elems_before >= difference_type(__n)) { 518 iterator __start_n = this->_M_start + difference_type(__n); 519 _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start); 520 this->_M_start = __new_start; 521 _STLP_STD::copy(__start_n, __pos, __old_start); 522 _STLP_STD::fill(__pos - difference_type(__n), __pos, __x_copy); 523 __pos -= difference_type(__n); 524 } 525 else { 526 _STLP_PRIV __uninitialized_copy_fill(this->_M_start, __pos, __new_start, 527 this->_M_start, __x_copy); 528 this->_M_start = __new_start; 529 fill(__old_start, __pos, __x_copy); 530 } 531 } 532 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) 533 } 534 else { 535 iterator __new_finish = _M_reserve_elements_at_back(__n); 536 iterator __old_finish = this->_M_finish; 537 const difference_type __elems_after = 538 difference_type(__length) - __elems_before; 539 __pos = this->_M_finish - __elems_after; 540 _STLP_TRY { 541 if (__elems_after > difference_type(__n)) { 542 iterator __finish_n = this->_M_finish - difference_type(__n); 543 _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish); 544 this->_M_finish = __new_finish; 545 copy_backward(__pos, __finish_n, __old_finish); 546 fill(__pos, __pos + difference_type(__n), __x_copy); 547 } 548 else { 549 _STLP_PRIV __uninitialized_fill_copy(this->_M_finish, __pos + difference_type(__n), 550 __x_copy, __pos, this->_M_finish); 551 this->_M_finish = __new_finish; 552 fill(__pos, __old_finish, __x_copy); 553 } 554 } 555 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) 556 } 557 return __pos; 558 } 559 560 #if !defined (_STLP_MEMBER_TEMPLATES) 561 template <class _Tp, class _Alloc > 562 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos, 563 const value_type* __first, const value_type* __last, 564 size_type __n, const __true_type& /*_Movable*/) { 565 const difference_type __elems_before = __pos - this->_M_start; 566 size_type __length = size(); 567 if (__elems_before <= difference_type(__length / 2)) { 568 iterator __new_start = _M_reserve_elements_at_front(__n); 569 __pos = this->_M_start + __elems_before; 570 _STLP_TRY { 571 iterator __dst = __new_start; 572 iterator __src = this->_M_start; 573 for (; __src != __pos; ++__dst, ++__src) { 574 _STLP_STD::_Move_Construct(&(*__dst), *__src); 575 _STLP_STD::_Destroy_Moved(&(*__src)); 576 } 577 this->_M_start = __new_start; 578 _STLP_PRIV __ucopy(__first, __last, __dst); 579 } 580 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) 581 } 582 else { 583 iterator __new_finish = _M_reserve_elements_at_back(__n); 584 const difference_type __elems_after = difference_type(__length) - __elems_before; 585 __pos = this->_M_finish - __elems_after; 586 _STLP_TRY { 587 iterator __dst = __new_finish; 588 iterator __src = this->_M_finish; 589 for (--__src, --__dst; __src >= __pos; --__src, --__dst) { 590 _STLP_STD::_Move_Construct(&(*__dst), *__src); 591 _STLP_STD::_Destroy_Moved(&(*__src)); 592 } 593 this->_M_finish = __new_finish; 594 _STLP_PRIV __ucopy(__first, __last, __pos); 595 } 596 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) 597 } 598 } 599 600 template <class _Tp, class _Alloc > 601 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos, 602 const value_type* __first, const value_type* __last, 603 size_type __n, const __false_type& /*_Movable*/) { 604 const difference_type __elems_before = __pos - this->_M_start; 605 size_type __length = size(); 606 if (__elems_before <= difference_type(__length / 2)) { 607 iterator __new_start = _M_reserve_elements_at_front(__n); 608 iterator __old_start = this->_M_start; 609 __pos = this->_M_start + __elems_before; 610 _STLP_TRY { 611 if (__elems_before >= difference_type(__n)) { 612 iterator __start_n = this->_M_start + difference_type(__n); 613 _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start); 614 this->_M_start = __new_start; 615 _STLP_STD::copy(__start_n, __pos, __old_start); 616 _STLP_STD::copy(__first, __last, __pos - difference_type(__n)); 617 } 618 else { 619 const value_type* __mid = __first + (difference_type(__n) - __elems_before); 620 _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start); 621 this->_M_start = __new_start; 622 _STLP_STD::copy(__mid, __last, __old_start); 623 } 624 } 625 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) 626 } 627 else { 628 iterator __new_finish = _M_reserve_elements_at_back(__n); 629 iterator __old_finish = this->_M_finish; 630 const difference_type __elems_after = 631 difference_type(__length) - __elems_before; 632 __pos = this->_M_finish - __elems_after; 633 _STLP_TRY { 634 635 if (__elems_after > difference_type(__n)) { 636 iterator __finish_n = this->_M_finish - difference_type(__n); 637 _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish); 638 this->_M_finish = __new_finish; 639 _STLP_STD::copy_backward(__pos, __finish_n, __old_finish); 640 _STLP_STD::copy(__first, __last, __pos); 641 } 642 else { 643 const value_type* __mid = __first + __elems_after; 644 _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish); 645 this->_M_finish = __new_finish; 646 _STLP_STD::copy(__first, __mid, __pos); 647 } 648 } 649 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) 650 } 651 } 652 653 template <class _Tp, class _Alloc > 654 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos, 655 const_iterator __first, const_iterator __last, 656 size_type __n, const __true_type& /*_Movable*/) { 657 const difference_type __elems_before = __pos - this->_M_start; 658 size_type __length = size(); 659 if (__elems_before <= difference_type(__length / 2)) { 660 iterator __new_start = _M_reserve_elements_at_front(__n); 661 __pos = this->_M_start + __elems_before; 662 _STLP_TRY { 663 iterator __dst = __new_start; 664 iterator __src = this->_M_start; 665 for (; __src != __pos; ++__dst, ++__src) { 666 _STLP_STD::_Move_Construct(&(*__dst), *__src); 667 _STLP_STD::_Destroy_Moved(&(*__src)); 668 } 669 this->_M_start = __new_start; 670 _STLP_PRIV __ucopy(__first, __last, __dst); 671 } 672 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) 673 } 674 else { 675 iterator __new_finish = _M_reserve_elements_at_back(__n); 676 const difference_type __elems_after = difference_type(__length) - __elems_before; 677 __pos = this->_M_finish - __elems_after; 678 _STLP_TRY { 679 iterator __dst = __new_finish; 680 iterator __src = this->_M_finish; 681 for (--__src, --__dst; __src >= __pos; --__src, --__dst) { 682 _STLP_STD::_Move_Construct(&(*__dst), *__src); 683 _STLP_STD::_Destroy_Moved(&(*__src)); 684 } 685 this->_M_finish = __new_finish; 686 _STLP_PRIV __ucopy(__first, __last, __pos); 687 } 688 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) 689 } 690 } 691 692 template <class _Tp, class _Alloc > 693 void deque<_Tp,_Alloc>::_M_insert_range_aux(iterator __pos, 694 const_iterator __first, const_iterator __last, 695 size_type __n, const __false_type& /*_Movable*/) { 696 const difference_type __elems_before = __pos - this->_M_start; 697 size_type __length = size(); 698 if (__elems_before < difference_type(__length / 2)) { 699 iterator __new_start = _M_reserve_elements_at_front(__n); 700 iterator __old_start = this->_M_start; 701 __pos = this->_M_start + __elems_before; 702 _STLP_TRY { 703 if (__elems_before >= difference_type(__n)) { 704 iterator __start_n = this->_M_start + __n; 705 _STLP_PRIV __ucopy(this->_M_start, __start_n, __new_start); 706 this->_M_start = __new_start; 707 _STLP_STD::copy(__start_n, __pos, __old_start); 708 _STLP_STD::copy(__first, __last, __pos - difference_type(__n)); 709 } 710 else { 711 const_iterator __mid = __first + (__n - __elems_before); 712 _STLP_PRIV __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid, __new_start); 713 this->_M_start = __new_start; 714 _STLP_STD::copy(__mid, __last, __old_start); 715 } 716 } 717 _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node)) 718 } 719 else { 720 iterator __new_finish = _M_reserve_elements_at_back(__n); 721 iterator __old_finish = this->_M_finish; 722 const difference_type __elems_after = __length - __elems_before; 723 __pos = this->_M_finish - __elems_after; 724 _STLP_TRY { 725 if (__elems_after > difference_type(__n)) { 726 iterator __finish_n = this->_M_finish - difference_type(__n); 727 _STLP_PRIV __ucopy(__finish_n, this->_M_finish, this->_M_finish); 728 this->_M_finish = __new_finish; 729 _STLP_STD::copy_backward(__pos, __finish_n, __old_finish); 730 _STLP_STD::copy(__first, __last, __pos); 731 } 732 else { 733 const_iterator __mid = __first + __elems_after; 734 _STLP_PRIV __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish); 735 this->_M_finish = __new_finish; 736 _STLP_STD::copy(__first, __mid, __pos); 737 } 738 } 739 _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1)) 740 } 741 } 742 #endif /* _STLP_MEMBER_TEMPLATES */ 743 744 template <class _Tp, class _Alloc > 745 void deque<_Tp,_Alloc>::_M_new_elements_at_front(size_type __new_elems) { 746 size_type __new_nodes 747 = (__new_elems + this->buffer_size() - 1) / this->buffer_size(); 748 _M_reserve_map_at_front(__new_nodes); 749 size_type __i = 1; 750 _STLP_TRY { 751 for (; __i <= __new_nodes; ++__i) 752 *(this->_M_start._M_node - __i) = this->_M_map_size.allocate(this->buffer_size()); 753 } 754 _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j) 755 this->_M_map_size.deallocate(*(this->_M_start._M_node - __j), this->buffer_size())) 756 } 757 758 template <class _Tp, class _Alloc > 759 void deque<_Tp,_Alloc>::_M_new_elements_at_back(size_type __new_elems) { 760 size_type __new_nodes 761 = (__new_elems + this->buffer_size() - 1) / this->buffer_size(); 762 _M_reserve_map_at_back(__new_nodes); 763 size_type __i = 1; 764 _STLP_TRY { 765 for (; __i <= __new_nodes; ++__i) 766 *(this->_M_finish._M_node + __i) = this->_M_map_size.allocate(this->buffer_size()); 767 } 768 _STLP_UNWIND(for (size_type __j = 1; __j < __i; ++__j) 769 this->_M_map_size.deallocate(*(this->_M_finish._M_node + __j), this->buffer_size())) 770 } 771 772 template <class _Tp, class _Alloc > 773 void deque<_Tp,_Alloc>::_M_reallocate_map(size_type __nodes_to_add, 774 bool __add_at_front) { 775 size_type __old_num_nodes = this->_M_finish._M_node - this->_M_start._M_node + 1; 776 size_type __new_num_nodes = __old_num_nodes + __nodes_to_add; 777 778 _Map_pointer __new_nstart; 779 if (this->_M_map_size._M_data > 2 * __new_num_nodes) { 780 __new_nstart = this->_M_map._M_data + (this->_M_map_size._M_data - __new_num_nodes) / 2 781 + (__add_at_front ? __nodes_to_add : 0); 782 if (__new_nstart < this->_M_start._M_node) 783 _STLP_STD::copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart); 784 else 785 _STLP_STD::copy_backward(this->_M_start._M_node, this->_M_finish._M_node + 1, 786 __new_nstart + __old_num_nodes); 787 } 788 else { 789 size_type __new_map_size = 790 this->_M_map_size._M_data + (max)((size_t)this->_M_map_size._M_data, __nodes_to_add) + 2; 791 792 _Map_pointer __new_map = this->_M_map.allocate(__new_map_size); 793 __new_nstart = __new_map + (__new_map_size - __new_num_nodes) / 2 794 + (__add_at_front ? __nodes_to_add : 0); 795 _STLP_STD::copy(this->_M_start._M_node, this->_M_finish._M_node + 1, __new_nstart); 796 this->_M_map.deallocate(this->_M_map._M_data, this->_M_map_size._M_data); 797 798 this->_M_map._M_data = __new_map; 799 this->_M_map_size._M_data = __new_map_size; 800 } 801 802 this->_M_start._M_set_node(__new_nstart); 803 this->_M_finish._M_set_node(__new_nstart + __old_num_nodes - 1); 804 } 805 806 #if defined (deque) 807 # undef deque 808 _STLP_MOVE_TO_STD_NAMESPACE 809 #endif 810 811 _STLP_END_NAMESPACE 812 813 #undef __iterator__ 814 #undef iterator 815 #undef const_iterator 816 #undef size_type 817 #undef value_type 818 819 #endif /* _STLP_DEQUE_C */ 820 821 // Local Variables: 822 // mode:C++ 823 // End: 824
