1 // List implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001-2015 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>:: 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 #if __cplusplus >= 201103L 75 _M_get_Node_allocator().destroy(__tmp); 76 #else 77 _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data)); 78 #endif 79 _M_put_node(__tmp); 80 } 81 } 82 83 #if __cplusplus >= 201103L 84 template<typename _Tp, typename _Alloc> 85 template<typename... _Args> 86 typename list<_Tp, _Alloc>::iterator 87 list<_Tp, _Alloc>:: 88 emplace(const_iterator __position, _Args&&... __args) 89 { 90 _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); 91 __tmp->_M_hook(__position._M_const_cast()._M_node); 92 this->_M_inc_size(1); 93 return iterator(__tmp); 94 } 95 #endif 96 97 template<typename _Tp, typename _Alloc> 98 typename list<_Tp, _Alloc>::iterator 99 list<_Tp, _Alloc>:: 100 #if __cplusplus >= 201103L 101 insert(const_iterator __position, const value_type& __x) 102 #else 103 insert(iterator __position, const value_type& __x) 104 #endif 105 { 106 _Node* __tmp = _M_create_node(__x); 107 __tmp->_M_hook(__position._M_const_cast()._M_node); 108 this->_M_inc_size(1); 109 return iterator(__tmp); 110 } 111 112 #if __cplusplus >= 201103L 113 template<typename _Tp, typename _Alloc> 114 typename list<_Tp, _Alloc>::iterator 115 list<_Tp, _Alloc>:: 116 insert(const_iterator __position, size_type __n, const value_type& __x) 117 { 118 if (__n) 119 { 120 list __tmp(__n, __x, get_allocator()); 121 iterator __it = __tmp.begin(); 122 splice(__position, __tmp); 123 return __it; 124 } 125 return __position._M_const_cast(); 126 } 127 128 template<typename _Tp, typename _Alloc> 129 template<typename _InputIterator, typename> 130 typename list<_Tp, _Alloc>::iterator 131 list<_Tp, _Alloc>:: 132 insert(const_iterator __position, _InputIterator __first, 133 _InputIterator __last) 134 { 135 list __tmp(__first, __last, get_allocator()); 136 if (!__tmp.empty()) 137 { 138 iterator __it = __tmp.begin(); 139 splice(__position, __tmp); 140 return __it; 141 } 142 return __position._M_const_cast(); 143 } 144 #endif 145 146 template<typename _Tp, typename _Alloc> 147 typename list<_Tp, _Alloc>::iterator 148 list<_Tp, _Alloc>:: 149 #if __cplusplus >= 201103L 150 erase(const_iterator __position) noexcept 151 #else 152 erase(iterator __position) 153 #endif 154 { 155 iterator __ret = iterator(__position._M_node->_M_next); 156 _M_erase(__position._M_const_cast()); 157 return __ret; 158 } 159 160 #if __cplusplus >= 201103L 161 template<typename _Tp, typename _Alloc> 162 void 163 list<_Tp, _Alloc>:: 164 _M_default_append(size_type __n) 165 { 166 size_type __i = 0; 167 __try 168 { 169 for (; __i < __n; ++__i) 170 emplace_back(); 171 } 172 __catch(...) 173 { 174 for (; __i; --__i) 175 pop_back(); 176 __throw_exception_again; 177 } 178 } 179 180 template<typename _Tp, typename _Alloc> 181 void 182 list<_Tp, _Alloc>:: 183 resize(size_type __new_size) 184 { 185 iterator __i = begin(); 186 size_type __len = 0; 187 for (; __i != end() && __len < __new_size; ++__i, ++__len) 188 ; 189 if (__len == __new_size) 190 erase(__i, end()); 191 else // __i == end() 192 _M_default_append(__new_size - __len); 193 } 194 195 template<typename _Tp, typename _Alloc> 196 void 197 list<_Tp, _Alloc>:: 198 resize(size_type __new_size, const value_type& __x) 199 { 200 iterator __i = begin(); 201 size_type __len = 0; 202 for (; __i != end() && __len < __new_size; ++__i, ++__len) 203 ; 204 if (__len == __new_size) 205 erase(__i, end()); 206 else // __i == end() 207 insert(end(), __new_size - __len, __x); 208 } 209 #else 210 template<typename _Tp, typename _Alloc> 211 void 212 list<_Tp, _Alloc>:: 213 resize(size_type __new_size, value_type __x) 214 { 215 iterator __i = begin(); 216 size_type __len = 0; 217 for (; __i != end() && __len < __new_size; ++__i, ++__len) 218 ; 219 if (__len == __new_size) 220 erase(__i, end()); 221 else // __i == end() 222 insert(end(), __new_size - __len, __x); 223 } 224 #endif 225 226 template<typename _Tp, typename _Alloc> 227 list<_Tp, _Alloc>& 228 list<_Tp, _Alloc>:: 229 operator=(const list& __x) 230 { 231 if (this != &__x) 232 { 233 iterator __first1 = begin(); 234 iterator __last1 = end(); 235 const_iterator __first2 = __x.begin(); 236 const_iterator __last2 = __x.end(); 237 for (; __first1 != __last1 && __first2 != __last2; 238 ++__first1, ++__first2) 239 *__first1 = *__first2; 240 if (__first2 == __last2) 241 erase(__first1, __last1); 242 else 243 insert(__last1, __first2, __last2); 244 } 245 return *this; 246 } 247 248 template<typename _Tp, typename _Alloc> 249 void 250 list<_Tp, _Alloc>:: 251 _M_fill_assign(size_type __n, const value_type& __val) 252 { 253 iterator __i = begin(); 254 for (; __i != end() && __n > 0; ++__i, --__n) 255 *__i = __val; 256 if (__n > 0) 257 insert(end(), __n, __val); 258 else 259 erase(__i, end()); 260 } 261 262 template<typename _Tp, typename _Alloc> 263 template <typename _InputIterator> 264 void 265 list<_Tp, _Alloc>:: 266 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 267 __false_type) 268 { 269 iterator __first1 = begin(); 270 iterator __last1 = end(); 271 for (; __first1 != __last1 && __first2 != __last2; 272 ++__first1, ++__first2) 273 *__first1 = *__first2; 274 if (__first2 == __last2) 275 erase(__first1, __last1); 276 else 277 insert(__last1, __first2, __last2); 278 } 279 280 template<typename _Tp, typename _Alloc> 281 void 282 list<_Tp, _Alloc>:: 283 remove(const value_type& __value) 284 { 285 iterator __first = begin(); 286 iterator __last = end(); 287 iterator __extra = __last; 288 while (__first != __last) 289 { 290 iterator __next = __first; 291 ++__next; 292 if (*__first == __value) 293 { 294 // _GLIBCXX_RESOLVE_LIB_DEFECTS 295 // 526. Is it undefined if a function in the standard changes 296 // in parameters? 297 if (std::__addressof(*__first) != std::__addressof(__value)) 298 _M_erase(__first); 299 else 300 __extra = __first; 301 } 302 __first = __next; 303 } 304 if (__extra != __last) 305 _M_erase(__extra); 306 } 307 308 template<typename _Tp, typename _Alloc> 309 void 310 list<_Tp, _Alloc>:: 311 unique() 312 { 313 iterator __first = begin(); 314 iterator __last = end(); 315 if (__first == __last) 316 return; 317 iterator __next = __first; 318 while (++__next != __last) 319 { 320 if (*__first == *__next) 321 _M_erase(__next); 322 else 323 __first = __next; 324 __next = __first; 325 } 326 } 327 328 template<typename _Tp, typename _Alloc> 329 void 330 list<_Tp, _Alloc>:: 331 #if __cplusplus >= 201103L 332 merge(list&& __x) 333 #else 334 merge(list& __x) 335 #endif 336 { 337 // _GLIBCXX_RESOLVE_LIB_DEFECTS 338 // 300. list::merge() specification incomplete 339 if (this != &__x) 340 { 341 _M_check_equal_allocators(__x); 342 343 iterator __first1 = begin(); 344 iterator __last1 = end(); 345 iterator __first2 = __x.begin(); 346 iterator __last2 = __x.end(); 347 const size_t __orig_size = __x.size(); 348 __try { 349 while (__first1 != __last1 && __first2 != __last2) 350 if (*__first2 < *__first1) 351 { 352 iterator __next = __first2; 353 _M_transfer(__first1, __first2, ++__next); 354 __first2 = __next; 355 } 356 else 357 ++__first1; 358 if (__first2 != __last2) 359 _M_transfer(__last1, __first2, __last2); 360 361 this->_M_inc_size(__x._M_get_size()); 362 __x._M_set_size(0); 363 } 364 __catch(...) 365 { 366 const size_t __dist = std::distance(__first2, __last2); 367 this->_M_inc_size(__orig_size - __dist); 368 __x._M_set_size(__dist); 369 __throw_exception_again; 370 } 371 } 372 } 373 374 template<typename _Tp, typename _Alloc> 375 template <typename _StrictWeakOrdering> 376 void 377 list<_Tp, _Alloc>:: 378 #if __cplusplus >= 201103L 379 merge(list&& __x, _StrictWeakOrdering __comp) 380 #else 381 merge(list& __x, _StrictWeakOrdering __comp) 382 #endif 383 { 384 // _GLIBCXX_RESOLVE_LIB_DEFECTS 385 // 300. list::merge() specification incomplete 386 if (this != &__x) 387 { 388 _M_check_equal_allocators(__x); 389 390 iterator __first1 = begin(); 391 iterator __last1 = end(); 392 iterator __first2 = __x.begin(); 393 iterator __last2 = __x.end(); 394 const size_t __orig_size = __x.size(); 395 __try 396 { 397 while (__first1 != __last1 && __first2 != __last2) 398 if (__comp(*__first2, *__first1)) 399 { 400 iterator __next = __first2; 401 _M_transfer(__first1, __first2, ++__next); 402 __first2 = __next; 403 } 404 else 405 ++__first1; 406 if (__first2 != __last2) 407 _M_transfer(__last1, __first2, __last2); 408 409 this->_M_inc_size(__x._M_get_size()); 410 __x._M_set_size(0); 411 } 412 __catch(...) 413 { 414 const size_t __dist = std::distance(__first2, __last2); 415 this->_M_inc_size(__orig_size - __dist); 416 __x._M_set_size(__dist); 417 __throw_exception_again; 418 } 419 } 420 } 421 422 template<typename _Tp, typename _Alloc> 423 void 424 list<_Tp, _Alloc>:: 425 sort() 426 { 427 // Do nothing if the list has length 0 or 1. 428 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 429 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 430 { 431 list __carry; 432 list __tmp[64]; 433 list * __fill = &__tmp[0]; 434 list * __counter; 435 436 do 437 { 438 __carry.splice(__carry.begin(), *this, begin()); 439 440 for(__counter = &__tmp[0]; 441 __counter != __fill && !__counter->empty(); 442 ++__counter) 443 { 444 __counter->merge(__carry); 445 __carry.swap(*__counter); 446 } 447 __carry.swap(*__counter); 448 if (__counter == __fill) 449 ++__fill; 450 } 451 while ( !empty() ); 452 453 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 454 __counter->merge(*(__counter - 1)); 455 swap( *(__fill - 1) ); 456 } 457 } 458 459 template<typename _Tp, typename _Alloc> 460 template <typename _Predicate> 461 void 462 list<_Tp, _Alloc>:: 463 remove_if(_Predicate __pred) 464 { 465 iterator __first = begin(); 466 iterator __last = end(); 467 while (__first != __last) 468 { 469 iterator __next = __first; 470 ++__next; 471 if (__pred(*__first)) 472 _M_erase(__first); 473 __first = __next; 474 } 475 } 476 477 template<typename _Tp, typename _Alloc> 478 template <typename _BinaryPredicate> 479 void 480 list<_Tp, _Alloc>:: 481 unique(_BinaryPredicate __binary_pred) 482 { 483 iterator __first = begin(); 484 iterator __last = end(); 485 if (__first == __last) 486 return; 487 iterator __next = __first; 488 while (++__next != __last) 489 { 490 if (__binary_pred(*__first, *__next)) 491 _M_erase(__next); 492 else 493 __first = __next; 494 __next = __first; 495 } 496 } 497 498 template<typename _Tp, typename _Alloc> 499 template <typename _StrictWeakOrdering> 500 void 501 list<_Tp, _Alloc>:: 502 sort(_StrictWeakOrdering __comp) 503 { 504 // Do nothing if the list has length 0 or 1. 505 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 506 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 507 { 508 list __carry; 509 list __tmp[64]; 510 list * __fill = &__tmp[0]; 511 list * __counter; 512 513 do 514 { 515 __carry.splice(__carry.begin(), *this, begin()); 516 517 for(__counter = &__tmp[0]; 518 __counter != __fill && !__counter->empty(); 519 ++__counter) 520 { 521 __counter->merge(__carry, __comp); 522 __carry.swap(*__counter); 523 } 524 __carry.swap(*__counter); 525 if (__counter == __fill) 526 ++__fill; 527 } 528 while ( !empty() ); 529 530 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 531 __counter->merge(*(__counter - 1), __comp); 532 swap(*(__fill - 1)); 533 } 534 } 535 536 _GLIBCXX_END_NAMESPACE_CONTAINER 537 } // namespace std 538 539 #endif /* _LIST_TCC */ 540 541