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
59namespace 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 _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>::
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
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>::
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>::
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
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>::
175 _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>::
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>::
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>::
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>::
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>::
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>::
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>::
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>::
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>::
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
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
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>::
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>::
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>::
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>::
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