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 while (__first1 != __last1 && __first2 != __last2) 348 if (*__first2 < *__first1) 349 { 350 iterator __next = __first2; 351 _M_transfer(__first1, __first2, ++__next); 352 __first2 = __next; 353 } 354 else 355 ++__first1; 356 if (__first2 != __last2) 357 _M_transfer(__last1, __first2, __last2); 358 359 this->_M_inc_size(__x._M_get_size()); 360 __x._M_set_size(0); 361 } 362 } 363 364 template<typename _Tp, typename _Alloc> 365 template <typename _StrictWeakOrdering> 366 void 367 list<_Tp, _Alloc>:: 368 #if __cplusplus >= 201103L 369 merge(list&& __x, _StrictWeakOrdering __comp) 370 #else 371 merge(list& __x, _StrictWeakOrdering __comp) 372 #endif 373 { 374 // _GLIBCXX_RESOLVE_LIB_DEFECTS 375 // 300. list::merge() specification incomplete 376 if (this != &__x) 377 { 378 _M_check_equal_allocators(__x); 379 380 iterator __first1 = begin(); 381 iterator __last1 = end(); 382 iterator __first2 = __x.begin(); 383 iterator __last2 = __x.end(); 384 while (__first1 != __last1 && __first2 != __last2) 385 if (__comp(*__first2, *__first1)) 386 { 387 iterator __next = __first2; 388 _M_transfer(__first1, __first2, ++__next); 389 __first2 = __next; 390 } 391 else 392 ++__first1; 393 if (__first2 != __last2) 394 _M_transfer(__last1, __first2, __last2); 395 396 this->_M_inc_size(__x._M_get_size()); 397 __x._M_set_size(0); 398 } 399 } 400 401 template<typename _Tp, typename _Alloc> 402 void 403 list<_Tp, _Alloc>:: 404 sort() 405 { 406 // Do nothing if the list has length 0 or 1. 407 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 408 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 409 { 410 list __carry; 411 list __tmp[64]; 412 list * __fill = &__tmp[0]; 413 list * __counter; 414 415 do 416 { 417 __carry.splice(__carry.begin(), *this, begin()); 418 419 for(__counter = &__tmp[0]; 420 __counter != __fill && !__counter->empty(); 421 ++__counter) 422 { 423 __counter->merge(__carry); 424 __carry.swap(*__counter); 425 } 426 __carry.swap(*__counter); 427 if (__counter == __fill) 428 ++__fill; 429 } 430 while ( !empty() ); 431 432 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 433 __counter->merge(*(__counter - 1)); 434 swap( *(__fill - 1) ); 435 } 436 } 437 438 template<typename _Tp, typename _Alloc> 439 template <typename _Predicate> 440 void 441 list<_Tp, _Alloc>:: 442 remove_if(_Predicate __pred) 443 { 444 iterator __first = begin(); 445 iterator __last = end(); 446 while (__first != __last) 447 { 448 iterator __next = __first; 449 ++__next; 450 if (__pred(*__first)) 451 _M_erase(__first); 452 __first = __next; 453 } 454 } 455 456 template<typename _Tp, typename _Alloc> 457 template <typename _BinaryPredicate> 458 void 459 list<_Tp, _Alloc>:: 460 unique(_BinaryPredicate __binary_pred) 461 { 462 iterator __first = begin(); 463 iterator __last = end(); 464 if (__first == __last) 465 return; 466 iterator __next = __first; 467 while (++__next != __last) 468 { 469 if (__binary_pred(*__first, *__next)) 470 _M_erase(__next); 471 else 472 __first = __next; 473 __next = __first; 474 } 475 } 476 477 template<typename _Tp, typename _Alloc> 478 template <typename _StrictWeakOrdering> 479 void 480 list<_Tp, _Alloc>:: 481 sort(_StrictWeakOrdering __comp) 482 { 483 // Do nothing if the list has length 0 or 1. 484 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 485 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 486 { 487 list __carry; 488 list __tmp[64]; 489 list * __fill = &__tmp[0]; 490 list * __counter; 491 492 do 493 { 494 __carry.splice(__carry.begin(), *this, begin()); 495 496 for(__counter = &__tmp[0]; 497 __counter != __fill && !__counter->empty(); 498 ++__counter) 499 { 500 __counter->merge(__carry, __comp); 501 __carry.swap(*__counter); 502 } 503 __carry.swap(*__counter); 504 if (__counter == __fill) 505 ++__fill; 506 } 507 while ( !empty() ); 508 509 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 510 __counter->merge(*(__counter - 1), __comp); 511 swap(*(__fill - 1)); 512 } 513 } 514 515 _GLIBCXX_END_NAMESPACE_CONTAINER 516 } // namespace std 517 518 #endif /* _LIST_TCC */ 519 520