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