1 // List implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001-2017 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 3, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // Under Section 7 of GPL version 3, you are granted additional 17 // permissions described in the GCC Runtime Library Exception, version 18 // 3.1, as published by the Free Software Foundation. 19 20 // You should have received a copy of the GNU General Public License and 21 // a copy of the GCC Runtime Library Exception along with this program; 22 // see the files COPYING3 and COPYING.RUNTIME respectively. If not, see 23 // <http://www.gnu.org/licenses/>. 24 25 /* 26 * 27 * Copyright (c) 1994 28 * Hewlett-Packard Company 29 * 30 * Permission to use, copy, modify, distribute and sell this software 31 * and its documentation for any purpose is hereby granted without fee, 32 * provided that the above copyright notice appear in all copies and 33 * that both that copyright notice and this permission notice appear 34 * in supporting documentation. Hewlett-Packard Company makes no 35 * representations about the suitability of this software for any 36 * purpose. It is provided "as is" without express or implied warranty. 37 * 38 * 39 * Copyright (c) 1996,1997 40 * Silicon Graphics Computer Systems, Inc. 41 * 42 * Permission to use, copy, modify, distribute and sell this software 43 * and its documentation for any purpose is hereby granted without fee, 44 * provided that the above copyright notice appear in all copies and 45 * that both that copyright notice and this permission notice appear 46 * in supporting documentation. Silicon Graphics makes no 47 * representations about the suitability of this software for any 48 * purpose. It is provided "as is" without express or implied warranty. 49 */ 50 51 /** @file bits/list.tcc 52 * This is an internal header file, included by other library headers. 53 * Do not attempt to use it directly. @headername{list} 54 */ 55 56 #ifndef _LIST_TCC 57 #define _LIST_TCC 1 58 59 namespace std _GLIBCXX_VISIBILITY(default) 60 { 61 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER 62 63 template<typename _Tp, typename _Alloc> 64 void 65 _List_base<_Tp, _Alloc>:: _M_clear()66 _M_clear() _GLIBCXX_NOEXCEPT 67 { 68 typedef _List_node<_Tp> _Node; 69 __detail::_List_node_base* __cur = _M_impl._M_node._M_next; 70 while (__cur != &_M_impl._M_node) 71 { 72 _Node* __tmp = static_cast<_Node*>(__cur); 73 __cur = __tmp->_M_next; 74 _Tp* __val = __tmp->_M_valptr(); 75 #if __cplusplus >= 201103L 76 _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val); 77 #else 78 _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val); 79 #endif 80 _M_put_node(__tmp); 81 } 82 } 83 84 #if __cplusplus >= 201103L 85 template<typename _Tp, typename _Alloc> 86 template<typename... _Args> 87 typename list<_Tp, _Alloc>::iterator 88 list<_Tp, _Alloc>:: emplace(const_iterator __position,_Args &&...__args)89 emplace(const_iterator __position, _Args&&... __args) 90 { 91 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); 92 __tmp->_M_hook(__position._M_const_cast()._M_node); 93 this->_M_inc_size(1); 94 return iterator(__tmp); 95 } 96 #endif 97 98 template<typename _Tp, typename _Alloc> 99 typename list<_Tp, _Alloc>::iterator 100 list<_Tp, _Alloc>:: 101 #if __cplusplus >= 201103L insert(const_iterator __position,const value_type & __x)102 insert(const_iterator __position, const value_type& __x) 103 #else 104 insert(iterator __position, const value_type& __x) 105 #endif 106 { 107 _Node* __tmp = _M_create_node(__x); 108 __tmp->_M_hook(__position._M_const_cast()._M_node); 109 this->_M_inc_size(1); 110 return iterator(__tmp); 111 } 112 113 #if __cplusplus >= 201103L 114 template<typename _Tp, typename _Alloc> 115 typename list<_Tp, _Alloc>::iterator 116 list<_Tp, _Alloc>:: insert(const_iterator __position,size_type __n,const value_type & __x)117 insert(const_iterator __position, size_type __n, const value_type& __x) 118 { 119 if (__n) 120 { 121 list __tmp(__n, __x, get_allocator()); 122 iterator __it = __tmp.begin(); 123 splice(__position, __tmp); 124 return __it; 125 } 126 return __position._M_const_cast(); 127 } 128 129 template<typename _Tp, typename _Alloc> 130 template<typename _InputIterator, typename> 131 typename list<_Tp, _Alloc>::iterator 132 list<_Tp, _Alloc>:: insert(const_iterator __position,_InputIterator __first,_InputIterator __last)133 insert(const_iterator __position, _InputIterator __first, 134 _InputIterator __last) 135 { 136 list __tmp(__first, __last, get_allocator()); 137 if (!__tmp.empty()) 138 { 139 iterator __it = __tmp.begin(); 140 splice(__position, __tmp); 141 return __it; 142 } 143 return __position._M_const_cast(); 144 } 145 #endif 146 147 template<typename _Tp, typename _Alloc> 148 typename list<_Tp, _Alloc>::iterator 149 list<_Tp, _Alloc>:: 150 #if __cplusplus >= 201103L erase(const_iterator __position)151 erase(const_iterator __position) noexcept 152 #else 153 erase(iterator __position) 154 #endif 155 { 156 iterator __ret = iterator(__position._M_node->_M_next); 157 _M_erase(__position._M_const_cast()); 158 return __ret; 159 } 160 161 // Return a const_iterator indicating the position to start inserting or 162 // erasing elements (depending whether the list is growing or shrinking), 163 // and set __new_size to the number of new elements that must be appended. 164 // Equivalent to the following, but performed optimally: 165 // if (__new_size < size()) { 166 // __new_size = 0; 167 // return std::next(begin(), __new_size); 168 // } else { 169 // __newsize -= size(); 170 // return end(); 171 // } 172 template<typename _Tp, typename _Alloc> 173 typename list<_Tp, _Alloc>::const_iterator 174 list<_Tp, _Alloc>:: _M_resize_pos(size_type & __new_size) const175 _M_resize_pos(size_type& __new_size) const 176 { 177 const_iterator __i; 178 #if _GLIBCXX_USE_CXX11_ABI 179 const size_type __len = size(); 180 if (__new_size < __len) 181 { 182 if (__new_size <= __len / 2) 183 { 184 __i = begin(); 185 std::advance(__i, __new_size); 186 } 187 else 188 { 189 __i = end(); 190 ptrdiff_t __num_erase = __len - __new_size; 191 std::advance(__i, -__num_erase); 192 } 193 __new_size = 0; 194 return __i; 195 } 196 else 197 __i = end(); 198 #else 199 size_type __len = 0; 200 for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len) 201 ; 202 #endif 203 __new_size -= __len; 204 return __i; 205 } 206 207 #if __cplusplus >= 201103L 208 template<typename _Tp, typename _Alloc> 209 void 210 list<_Tp, _Alloc>:: _M_default_append(size_type __n)211 _M_default_append(size_type __n) 212 { 213 size_type __i = 0; 214 __try 215 { 216 for (; __i < __n; ++__i) 217 emplace_back(); 218 } 219 __catch(...) 220 { 221 for (; __i; --__i) 222 pop_back(); 223 __throw_exception_again; 224 } 225 } 226 227 template<typename _Tp, typename _Alloc> 228 void 229 list<_Tp, _Alloc>:: resize(size_type __new_size)230 resize(size_type __new_size) 231 { 232 const_iterator __i = _M_resize_pos(__new_size); 233 if (__new_size) 234 _M_default_append(__new_size); 235 else 236 erase(__i, end()); 237 } 238 239 template<typename _Tp, typename _Alloc> 240 void 241 list<_Tp, _Alloc>:: resize(size_type __new_size,const value_type & __x)242 resize(size_type __new_size, const value_type& __x) 243 { 244 const_iterator __i = _M_resize_pos(__new_size); 245 if (__new_size) 246 insert(end(), __new_size, __x); 247 else 248 erase(__i, end()); 249 } 250 #else 251 template<typename _Tp, typename _Alloc> 252 void 253 list<_Tp, _Alloc>:: resize(size_type __new_size,value_type __x)254 resize(size_type __new_size, value_type __x) 255 { 256 const_iterator __i = _M_resize_pos(__new_size); 257 if (__new_size) 258 insert(end(), __new_size, __x); 259 else 260 erase(__i._M_const_cast(), end()); 261 } 262 #endif 263 264 template<typename _Tp, typename _Alloc> 265 list<_Tp, _Alloc>& 266 list<_Tp, _Alloc>:: operator =(const list & __x)267 operator=(const list& __x) 268 { 269 if (this != std::__addressof(__x)) 270 { 271 #if __cplusplus >= 201103L 272 if (_Node_alloc_traits::_S_propagate_on_copy_assign()) 273 { 274 auto& __this_alloc = this->_M_get_Node_allocator(); 275 auto& __that_alloc = __x._M_get_Node_allocator(); 276 if (!_Node_alloc_traits::_S_always_equal() 277 && __this_alloc != __that_alloc) 278 { 279 // replacement allocator cannot free existing storage 280 clear(); 281 } 282 std::__alloc_on_copy(__this_alloc, __that_alloc); 283 } 284 #endif 285 _M_assign_dispatch(__x.begin(), __x.end(), __false_type()); 286 } 287 return *this; 288 } 289 290 template<typename _Tp, typename _Alloc> 291 void 292 list<_Tp, _Alloc>:: _M_fill_assign(size_type __n,const value_type & __val)293 _M_fill_assign(size_type __n, const value_type& __val) 294 { 295 iterator __i = begin(); 296 for (; __i != end() && __n > 0; ++__i, --__n) 297 *__i = __val; 298 if (__n > 0) 299 insert(end(), __n, __val); 300 else 301 erase(__i, end()); 302 } 303 304 template<typename _Tp, typename _Alloc> 305 template <typename _InputIterator> 306 void 307 list<_Tp, _Alloc>:: _M_assign_dispatch(_InputIterator __first2,_InputIterator __last2,__false_type)308 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 309 __false_type) 310 { 311 iterator __first1 = begin(); 312 iterator __last1 = end(); 313 for (; __first1 != __last1 && __first2 != __last2; 314 ++__first1, ++__first2) 315 *__first1 = *__first2; 316 if (__first2 == __last2) 317 erase(__first1, __last1); 318 else 319 insert(__last1, __first2, __last2); 320 } 321 322 template<typename _Tp, typename _Alloc> 323 void 324 list<_Tp, _Alloc>:: remove(const value_type & __value)325 remove(const value_type& __value) 326 { 327 iterator __first = begin(); 328 iterator __last = end(); 329 iterator __extra = __last; 330 while (__first != __last) 331 { 332 iterator __next = __first; 333 ++__next; 334 if (*__first == __value) 335 { 336 // _GLIBCXX_RESOLVE_LIB_DEFECTS 337 // 526. Is it undefined if a function in the standard changes 338 // in parameters? 339 if (std::__addressof(*__first) != std::__addressof(__value)) 340 _M_erase(__first); 341 else 342 __extra = __first; 343 } 344 __first = __next; 345 } 346 if (__extra != __last) 347 _M_erase(__extra); 348 } 349 350 template<typename _Tp, typename _Alloc> 351 void 352 list<_Tp, _Alloc>:: unique()353 unique() 354 { 355 iterator __first = begin(); 356 iterator __last = end(); 357 if (__first == __last) 358 return; 359 iterator __next = __first; 360 while (++__next != __last) 361 { 362 if (*__first == *__next) 363 _M_erase(__next); 364 else 365 __first = __next; 366 __next = __first; 367 } 368 } 369 370 template<typename _Tp, typename _Alloc> 371 void 372 list<_Tp, _Alloc>:: 373 #if __cplusplus >= 201103L merge(list && __x)374 merge(list&& __x) 375 #else 376 merge(list& __x) 377 #endif 378 { 379 // _GLIBCXX_RESOLVE_LIB_DEFECTS 380 // 300. list::merge() specification incomplete 381 if (this != std::__addressof(__x)) 382 { 383 _M_check_equal_allocators(__x); 384 385 iterator __first1 = begin(); 386 iterator __last1 = end(); 387 iterator __first2 = __x.begin(); 388 iterator __last2 = __x.end(); 389 const size_t __orig_size = __x.size(); 390 __try { 391 while (__first1 != __last1 && __first2 != __last2) 392 if (*__first2 < *__first1) 393 { 394 iterator __next = __first2; 395 _M_transfer(__first1, __first2, ++__next); 396 __first2 = __next; 397 } 398 else 399 ++__first1; 400 if (__first2 != __last2) 401 _M_transfer(__last1, __first2, __last2); 402 403 this->_M_inc_size(__x._M_get_size()); 404 __x._M_set_size(0); 405 } 406 __catch(...) 407 { 408 const size_t __dist = std::distance(__first2, __last2); 409 this->_M_inc_size(__orig_size - __dist); 410 __x._M_set_size(__dist); 411 __throw_exception_again; 412 } 413 } 414 } 415 416 template<typename _Tp, typename _Alloc> 417 template <typename _StrictWeakOrdering> 418 void 419 list<_Tp, _Alloc>:: 420 #if __cplusplus >= 201103L merge(list && __x,_StrictWeakOrdering __comp)421 merge(list&& __x, _StrictWeakOrdering __comp) 422 #else 423 merge(list& __x, _StrictWeakOrdering __comp) 424 #endif 425 { 426 // _GLIBCXX_RESOLVE_LIB_DEFECTS 427 // 300. list::merge() specification incomplete 428 if (this != std::__addressof(__x)) 429 { 430 _M_check_equal_allocators(__x); 431 432 iterator __first1 = begin(); 433 iterator __last1 = end(); 434 iterator __first2 = __x.begin(); 435 iterator __last2 = __x.end(); 436 const size_t __orig_size = __x.size(); 437 __try 438 { 439 while (__first1 != __last1 && __first2 != __last2) 440 if (__comp(*__first2, *__first1)) 441 { 442 iterator __next = __first2; 443 _M_transfer(__first1, __first2, ++__next); 444 __first2 = __next; 445 } 446 else 447 ++__first1; 448 if (__first2 != __last2) 449 _M_transfer(__last1, __first2, __last2); 450 451 this->_M_inc_size(__x._M_get_size()); 452 __x._M_set_size(0); 453 } 454 __catch(...) 455 { 456 const size_t __dist = std::distance(__first2, __last2); 457 this->_M_inc_size(__orig_size - __dist); 458 __x._M_set_size(__dist); 459 __throw_exception_again; 460 } 461 } 462 } 463 464 template<typename _Tp, typename _Alloc> 465 void 466 list<_Tp, _Alloc>:: sort()467 sort() 468 { 469 // Do nothing if the list has length 0 or 1. 470 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 471 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 472 { 473 list __carry; 474 list __tmp[64]; 475 list * __fill = __tmp; 476 list * __counter; 477 __try 478 { 479 do 480 { 481 __carry.splice(__carry.begin(), *this, begin()); 482 483 for(__counter = __tmp; 484 __counter != __fill && !__counter->empty(); 485 ++__counter) 486 { 487 __counter->merge(__carry); 488 __carry.swap(*__counter); 489 } 490 __carry.swap(*__counter); 491 if (__counter == __fill) 492 ++__fill; 493 } 494 while ( !empty() ); 495 496 for (__counter = __tmp + 1; __counter != __fill; ++__counter) 497 __counter->merge(*(__counter - 1)); 498 swap( *(__fill - 1) ); 499 } 500 __catch(...) 501 { 502 this->splice(this->end(), __carry); 503 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) 504 this->splice(this->end(), __tmp[__i]); 505 __throw_exception_again; 506 } 507 } 508 } 509 510 template<typename _Tp, typename _Alloc> 511 template <typename _Predicate> 512 void 513 list<_Tp, _Alloc>:: remove_if(_Predicate __pred)514 remove_if(_Predicate __pred) 515 { 516 iterator __first = begin(); 517 iterator __last = end(); 518 while (__first != __last) 519 { 520 iterator __next = __first; 521 ++__next; 522 if (__pred(*__first)) 523 _M_erase(__first); 524 __first = __next; 525 } 526 } 527 528 template<typename _Tp, typename _Alloc> 529 template <typename _BinaryPredicate> 530 void 531 list<_Tp, _Alloc>:: unique(_BinaryPredicate __binary_pred)532 unique(_BinaryPredicate __binary_pred) 533 { 534 iterator __first = begin(); 535 iterator __last = end(); 536 if (__first == __last) 537 return; 538 iterator __next = __first; 539 while (++__next != __last) 540 { 541 if (__binary_pred(*__first, *__next)) 542 _M_erase(__next); 543 else 544 __first = __next; 545 __next = __first; 546 } 547 } 548 549 template<typename _Tp, typename _Alloc> 550 template <typename _StrictWeakOrdering> 551 void 552 list<_Tp, _Alloc>:: sort(_StrictWeakOrdering __comp)553 sort(_StrictWeakOrdering __comp) 554 { 555 // Do nothing if the list has length 0 or 1. 556 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 557 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 558 { 559 list __carry; 560 list __tmp[64]; 561 list * __fill = __tmp; 562 list * __counter; 563 __try 564 { 565 do 566 { 567 __carry.splice(__carry.begin(), *this, begin()); 568 569 for(__counter = __tmp; 570 __counter != __fill && !__counter->empty(); 571 ++__counter) 572 { 573 __counter->merge(__carry, __comp); 574 __carry.swap(*__counter); 575 } 576 __carry.swap(*__counter); 577 if (__counter == __fill) 578 ++__fill; 579 } 580 while ( !empty() ); 581 582 for (__counter = __tmp + 1; __counter != __fill; ++__counter) 583 __counter->merge(*(__counter - 1), __comp); 584 swap(*(__fill - 1)); 585 } 586 __catch(...) 587 { 588 this->splice(this->end(), __carry); 589 for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i) 590 this->splice(this->end(), __tmp[__i]); 591 __throw_exception_again; 592 } 593 } 594 } 595 596 _GLIBCXX_END_NAMESPACE_CONTAINER 597 } // namespace std 598 599 #endif /* _LIST_TCC */ 600 601