Line data Source code
1 : // List implementation (out of line) -*- C++ -*-
2 :
3 : // Copyright (C) 2001-2022 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_VERSION
62 : _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
63 :
64 : template<typename _Tp, typename _Alloc>
65 : void
66 2968 : _List_base<_Tp, _Alloc>::
67 : _M_clear() _GLIBCXX_NOEXCEPT
68 : {
69 : typedef _List_node<_Tp> _Node;
70 2968 : __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
71 2968 : while (__cur != &_M_impl._M_node)
72 : {
73 46809 : _Node* __tmp = static_cast<_Node*>(__cur);
74 46809 : __cur = __tmp->_M_next;
75 46809 : _Tp* __val = __tmp->_M_valptr();
76 : #if __cplusplus >= 201103L
77 47553 : _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
78 : #else
79 : _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
80 : #endif
81 49777 : _M_put_node(__tmp);
82 : }
83 2968 : }
84 :
85 : #if __cplusplus >= 201103L
86 : template<typename _Tp, typename _Alloc>
87 : template<typename... _Args>
88 : typename list<_Tp, _Alloc>::iterator
89 : list<_Tp, _Alloc>::
90 : emplace(const_iterator __position, _Args&&... __args)
91 : {
92 : _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
93 : __tmp->_M_hook(__position._M_const_cast()._M_node);
94 : this->_M_inc_size(1);
95 : return iterator(__tmp);
96 : }
97 : #endif
98 :
99 : template<typename _Tp, typename _Alloc>
100 : typename list<_Tp, _Alloc>::iterator
101 112819 : list<_Tp, _Alloc>::
102 : #if __cplusplus >= 201103L
103 : insert(const_iterator __position, const value_type& __x)
104 : #else
105 : insert(iterator __position, const value_type& __x)
106 : #endif
107 : {
108 112819 : _Node* __tmp = _M_create_node(__x);
109 112819 : __tmp->_M_hook(__position._M_const_cast()._M_node);
110 112819 : this->_M_inc_size(1);
111 112819 : return iterator(__tmp);
112 : }
113 :
114 : #if __cplusplus >= 201103L
115 : template<typename _Tp, typename _Alloc>
116 : typename list<_Tp, _Alloc>::iterator
117 : list<_Tp, _Alloc>::
118 : insert(const_iterator __position, size_type __n, const value_type& __x)
119 : {
120 : if (__n)
121 : {
122 : list __tmp(__n, __x, get_allocator());
123 : iterator __it = __tmp.begin();
124 : splice(__position, __tmp);
125 : return __it;
126 : }
127 : return __position._M_const_cast();
128 : }
129 :
130 : template<typename _Tp, typename _Alloc>
131 : template<typename _InputIterator, typename>
132 : typename list<_Tp, _Alloc>::iterator
133 : list<_Tp, _Alloc>::
134 : insert(const_iterator __position, _InputIterator __first,
135 : _InputIterator __last)
136 : {
137 : list __tmp(__first, __last, get_allocator());
138 : if (!__tmp.empty())
139 : {
140 : iterator __it = __tmp.begin();
141 : splice(__position, __tmp);
142 : return __it;
143 : }
144 : return __position._M_const_cast();
145 : }
146 : #endif
147 :
148 : template<typename _Tp, typename _Alloc>
149 : typename list<_Tp, _Alloc>::iterator
150 70588 : list<_Tp, _Alloc>::
151 : #if __cplusplus >= 201103L
152 : erase(const_iterator __position) noexcept
153 : #else
154 : erase(iterator __position)
155 : #endif
156 : {
157 70588 : iterator __ret = iterator(__position._M_node->_M_next);
158 70588 : _M_erase(__position._M_const_cast());
159 : return __ret;
160 : }
161 :
162 : // Return a const_iterator indicating the position to start inserting or
163 : // erasing elements (depending whether the list is growing or shrinking),
164 : // and set __new_size to the number of new elements that must be appended.
165 : // Equivalent to the following, but performed optimally:
166 : // if (__new_size < size()) {
167 : // __new_size = 0;
168 : // return std::next(begin(), __new_size);
169 : // } else {
170 : // __newsize -= size();
171 : // return end();
172 : // }
173 : template<typename _Tp, typename _Alloc>
174 : typename list<_Tp, _Alloc>::const_iterator
175 : list<_Tp, _Alloc>::
176 : _M_resize_pos(size_type& __new_size) const
177 : {
178 : const_iterator __i;
179 : #if _GLIBCXX_USE_CXX11_ABI
180 : const size_type __len = size();
181 : if (__new_size < __len)
182 : {
183 : if (__new_size <= __len / 2)
184 : {
185 : __i = begin();
186 : std::advance(__i, __new_size);
187 : }
188 : else
189 : {
190 : __i = end();
191 : ptrdiff_t __num_erase = __len - __new_size;
192 : std::advance(__i, -__num_erase);
193 : }
194 : __new_size = 0;
195 : return __i;
196 : }
197 : else
198 : __i = end();
199 : #else
200 : size_type __len = 0;
201 : for (__i = begin(); __i != end() && __len < __new_size; ++__i, ++__len)
202 : ;
203 : #endif
204 : __new_size -= __len;
205 : return __i;
206 : }
207 :
208 : #if __cplusplus >= 201103L
209 : template<typename _Tp, typename _Alloc>
210 : void
211 : list<_Tp, _Alloc>::
212 : _M_default_append(size_type __n)
213 : {
214 : size_type __i = 0;
215 : __try
216 : {
217 : for (; __i < __n; ++__i)
218 : emplace_back();
219 : }
220 : __catch(...)
221 : {
222 : for (; __i; --__i)
223 : pop_back();
224 : __throw_exception_again;
225 : }
226 : }
227 :
228 : template<typename _Tp, typename _Alloc>
229 : void
230 : list<_Tp, _Alloc>::
231 : resize(size_type __new_size)
232 : {
233 : const_iterator __i = _M_resize_pos(__new_size);
234 : if (__new_size)
235 : _M_default_append(__new_size);
236 : else
237 : erase(__i, end());
238 : }
239 :
240 : template<typename _Tp, typename _Alloc>
241 : void
242 : list<_Tp, _Alloc>::
243 : resize(size_type __new_size, const value_type& __x)
244 : {
245 : const_iterator __i = _M_resize_pos(__new_size);
246 : if (__new_size)
247 : insert(end(), __new_size, __x);
248 : else
249 : erase(__i, end());
250 : }
251 : #else
252 : template<typename _Tp, typename _Alloc>
253 : void
254 : list<_Tp, _Alloc>::
255 : resize(size_type __new_size, value_type __x)
256 : {
257 : const_iterator __i = _M_resize_pos(__new_size);
258 : if (__new_size)
259 : insert(end(), __new_size, __x);
260 : else
261 : erase(__i._M_const_cast(), end());
262 : }
263 : #endif
264 :
265 : template<typename _Tp, typename _Alloc>
266 : list<_Tp, _Alloc>&
267 : list<_Tp, _Alloc>::
268 : operator=(const list& __x)
269 : {
270 : if (this != std::__addressof(__x))
271 : {
272 : #if __cplusplus >= 201103L
273 : if (_Node_alloc_traits::_S_propagate_on_copy_assign())
274 : {
275 : auto& __this_alloc = this->_M_get_Node_allocator();
276 : auto& __that_alloc = __x._M_get_Node_allocator();
277 : if (!_Node_alloc_traits::_S_always_equal()
278 : && __this_alloc != __that_alloc)
279 : {
280 : // replacement allocator cannot free existing storage
281 : clear();
282 : }
283 : std::__alloc_on_copy(__this_alloc, __that_alloc);
284 : }
285 : #endif
286 : _M_assign_dispatch(__x.begin(), __x.end(), __false_type());
287 : }
288 : return *this;
289 : }
290 :
291 : template<typename _Tp, typename _Alloc>
292 : void
293 : list<_Tp, _Alloc>::
294 : _M_fill_assign(size_type __n, const value_type& __val)
295 : {
296 : iterator __i = begin();
297 : for (; __i != end() && __n > 0; ++__i, --__n)
298 : *__i = __val;
299 : if (__n > 0)
300 : insert(end(), __n, __val);
301 : else
302 : erase(__i, end());
303 : }
304 :
305 : template<typename _Tp, typename _Alloc>
306 : template <typename _InputIterator>
307 : void
308 : list<_Tp, _Alloc>::
309 : _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
310 : __false_type)
311 : {
312 : iterator __first1 = begin();
313 : iterator __last1 = end();
314 : for (; __first1 != __last1 && __first2 != __last2;
315 : ++__first1, (void)++__first2)
316 : *__first1 = *__first2;
317 : if (__first2 == __last2)
318 : erase(__first1, __last1);
319 : else
320 : insert(__last1, __first2, __last2);
321 : }
322 :
323 : #if __cplusplus > 201703L
324 : # define _GLIBCXX20_ONLY(__expr) __expr
325 : #else
326 : # define _GLIBCXX20_ONLY(__expr)
327 : #endif
328 :
329 : template<typename _Tp, typename _Alloc>
330 : typename list<_Tp, _Alloc>::__remove_return_type
331 : list<_Tp, _Alloc>::
332 : remove(const value_type& __value)
333 : {
334 : #if !_GLIBCXX_USE_CXX11_ABI
335 : size_type __removed __attribute__((__unused__)) = 0;
336 : #endif
337 : list __to_destroy(get_allocator());
338 : iterator __first = begin();
339 : iterator __last = end();
340 : while (__first != __last)
341 : {
342 : iterator __next = __first;
343 : ++__next;
344 : if (*__first == __value)
345 : {
346 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
347 : // 526. Is it undefined if a function in the standard changes
348 : // in parameters?
349 : __to_destroy.splice(__to_destroy.begin(), *this, __first);
350 : #if !_GLIBCXX_USE_CXX11_ABI
351 : _GLIBCXX20_ONLY( __removed++ );
352 : #endif
353 : }
354 :
355 : __first = __next;
356 : }
357 :
358 : #if !_GLIBCXX_USE_CXX11_ABI
359 : return _GLIBCXX20_ONLY( __removed );
360 : #else
361 : return _GLIBCXX20_ONLY( __to_destroy.size() );
362 : #endif
363 : }
364 :
365 : template<typename _Tp, typename _Alloc>
366 : typename list<_Tp, _Alloc>::__remove_return_type
367 : list<_Tp, _Alloc>::
368 : unique()
369 : {
370 : iterator __first = begin();
371 : iterator __last = end();
372 : if (__first == __last)
373 : return _GLIBCXX20_ONLY( 0 );
374 : #if !_GLIBCXX_USE_CXX11_ABI
375 : size_type __removed __attribute__((__unused__)) = 0;
376 : #endif
377 : list __to_destroy(get_allocator());
378 : iterator __next = __first;
379 : while (++__next != __last)
380 : {
381 : if (*__first == *__next)
382 : {
383 : __to_destroy.splice(__to_destroy.begin(), *this, __next);
384 : #if !_GLIBCXX_USE_CXX11_ABI
385 : _GLIBCXX20_ONLY( __removed++ );
386 : #endif
387 : }
388 : else
389 : __first = __next;
390 : __next = __first;
391 : }
392 :
393 : #if !_GLIBCXX_USE_CXX11_ABI
394 : return _GLIBCXX20_ONLY( __removed );
395 : #else
396 : return _GLIBCXX20_ONLY( __to_destroy.size() );
397 : #endif
398 : }
399 :
400 : template<typename _Tp, typename _Alloc>
401 : void
402 : list<_Tp, _Alloc>::
403 : #if __cplusplus >= 201103L
404 : merge(list&& __x)
405 : #else
406 : merge(list& __x)
407 : #endif
408 : {
409 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
410 : // 300. list::merge() specification incomplete
411 : if (this != std::__addressof(__x))
412 : {
413 : _M_check_equal_allocators(__x);
414 :
415 : iterator __first1 = begin();
416 : iterator __last1 = end();
417 : iterator __first2 = __x.begin();
418 : iterator __last2 = __x.end();
419 :
420 : const _Finalize_merge __fin(*this, __x, __first2);
421 :
422 : while (__first1 != __last1 && __first2 != __last2)
423 : if (*__first2 < *__first1)
424 : {
425 : iterator __next = __first2;
426 : _M_transfer(__first1, __first2, ++__next);
427 : __first2 = __next;
428 : }
429 : else
430 : ++__first1;
431 : if (__first2 != __last2)
432 : {
433 : _M_transfer(__last1, __first2, __last2);
434 : __first2 = __last2;
435 : }
436 : }
437 : }
438 :
439 : template<typename _Tp, typename _Alloc>
440 : template <typename _StrictWeakOrdering>
441 : void
442 : list<_Tp, _Alloc>::
443 : #if __cplusplus >= 201103L
444 : merge(list&& __x, _StrictWeakOrdering __comp)
445 : #else
446 : merge(list& __x, _StrictWeakOrdering __comp)
447 : #endif
448 : {
449 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
450 : // 300. list::merge() specification incomplete
451 : if (this != std::__addressof(__x))
452 : {
453 : _M_check_equal_allocators(__x);
454 :
455 : iterator __first1 = begin();
456 : iterator __last1 = end();
457 : iterator __first2 = __x.begin();
458 : iterator __last2 = __x.end();
459 :
460 : const _Finalize_merge __fin(*this, __x, __first2);
461 :
462 : while (__first1 != __last1 && __first2 != __last2)
463 : if (__comp(*__first2, *__first1))
464 : {
465 : iterator __next = __first2;
466 : _M_transfer(__first1, __first2, ++__next);
467 : __first2 = __next;
468 : }
469 : else
470 : ++__first1;
471 : if (__first2 != __last2)
472 : {
473 : _M_transfer(__last1, __first2, __last2);
474 : __first2 = __last2;
475 : }
476 : }
477 : }
478 :
479 : template<typename _Tp, typename _Alloc>
480 : void
481 : list<_Tp, _Alloc>::
482 : sort()
483 : {
484 : // Do nothing if the list has length 0 or 1.
485 : if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
486 : && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
487 : {
488 : using __detail::_Scratch_list;
489 : // The algorithm used here is largely unchanged from the SGI STL
490 : // and is described in The C++ Standard Template Library by Plauger,
491 : // Stepanov, Lee, Musser.
492 : // Each element of *this is spliced out and merged into one of the
493 : // sorted lists in __tmp, then all the lists in __tmp are merged
494 : // together and then swapped back into *this.
495 : // Because all nodes end up back in *this we do not need to update
496 : // this->size() while nodes are temporarily moved out.
497 : _Scratch_list __carry;
498 : _Scratch_list __tmp[64];
499 : _Scratch_list* __fill = __tmp;
500 : _Scratch_list* __counter;
501 :
502 : _Scratch_list::_Ptr_cmp<iterator, void> __ptr_comp;
503 :
504 : __try
505 : {
506 : do
507 : {
508 : __carry._M_take_one(begin()._M_node);
509 :
510 : for(__counter = __tmp;
511 : __counter != __fill && !__counter->empty();
512 : ++__counter)
513 : {
514 :
515 : __counter->merge(__carry, __ptr_comp);
516 : __carry.swap(*__counter);
517 : }
518 : __carry.swap(*__counter);
519 : if (__counter == __fill)
520 : ++__fill;
521 : }
522 : while ( !empty() );
523 :
524 : for (__counter = __tmp + 1; __counter != __fill; ++__counter)
525 : __counter->merge(__counter[-1], __ptr_comp);
526 : __fill[-1].swap(this->_M_impl._M_node);
527 : }
528 : __catch(...)
529 : {
530 : // Move all nodes back into *this.
531 : __carry._M_put_all(end()._M_node);
532 : for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
533 : __tmp[__i]._M_put_all(end()._M_node);
534 : __throw_exception_again;
535 : }
536 : }
537 : }
538 :
539 : template<typename _Tp, typename _Alloc>
540 : template <typename _Predicate>
541 : typename list<_Tp, _Alloc>::__remove_return_type
542 : list<_Tp, _Alloc>::
543 : remove_if(_Predicate __pred)
544 : {
545 : #if !_GLIBCXX_USE_CXX11_ABI
546 : size_type __removed __attribute__((__unused__)) = 0;
547 : #endif
548 : list __to_destroy(get_allocator());
549 : iterator __first = begin();
550 : iterator __last = end();
551 : while (__first != __last)
552 : {
553 : iterator __next = __first;
554 : ++__next;
555 : if (__pred(*__first))
556 : {
557 : __to_destroy.splice(__to_destroy.begin(), *this, __first);
558 : #if !_GLIBCXX_USE_CXX11_ABI
559 : _GLIBCXX20_ONLY( __removed++ );
560 : #endif
561 : }
562 : __first = __next;
563 : }
564 :
565 : #if !_GLIBCXX_USE_CXX11_ABI
566 : return _GLIBCXX20_ONLY( __removed );
567 : #else
568 : return _GLIBCXX20_ONLY( __to_destroy.size() );
569 : #endif
570 : }
571 :
572 : template<typename _Tp, typename _Alloc>
573 : template <typename _BinaryPredicate>
574 : typename list<_Tp, _Alloc>::__remove_return_type
575 : list<_Tp, _Alloc>::
576 : unique(_BinaryPredicate __binary_pred)
577 : {
578 : iterator __first = begin();
579 : iterator __last = end();
580 : if (__first == __last)
581 : return _GLIBCXX20_ONLY(0);
582 : #if !_GLIBCXX_USE_CXX11_ABI
583 : size_type __removed __attribute__((__unused__)) = 0;
584 : #endif
585 : list __to_destroy(get_allocator());
586 : iterator __next = __first;
587 : while (++__next != __last)
588 : {
589 : if (__binary_pred(*__first, *__next))
590 : {
591 : __to_destroy.splice(__to_destroy.begin(), *this, __next);
592 : #if !_GLIBCXX_USE_CXX11_ABI
593 : _GLIBCXX20_ONLY( __removed++ );
594 : #endif
595 : }
596 : else
597 : __first = __next;
598 : __next = __first;
599 : }
600 :
601 : #if !_GLIBCXX_USE_CXX11_ABI
602 : return _GLIBCXX20_ONLY( __removed );
603 : #else
604 : return _GLIBCXX20_ONLY( __to_destroy.size() );
605 : #endif
606 : }
607 :
608 : #undef _GLIBCXX20_ONLY
609 :
610 : template<typename _Tp, typename _Alloc>
611 : template <typename _StrictWeakOrdering>
612 : void
613 : list<_Tp, _Alloc>::
614 : sort(_StrictWeakOrdering __comp)
615 : {
616 : // Do nothing if the list has length 0 or 1.
617 : if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
618 : && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
619 : {
620 : using __detail::_Scratch_list;
621 : _Scratch_list __carry;
622 : _Scratch_list __tmp[64];
623 : _Scratch_list* __fill = __tmp;
624 : _Scratch_list* __counter;
625 :
626 : _Scratch_list::_Ptr_cmp<iterator, _StrictWeakOrdering> __ptr_comp
627 : = { __comp };
628 :
629 : __try
630 : {
631 : do
632 : {
633 : __carry._M_take_one(begin()._M_node);
634 :
635 : for(__counter = __tmp;
636 : __counter != __fill && !__counter->empty();
637 : ++__counter)
638 : {
639 :
640 : __counter->merge(__carry, __ptr_comp);
641 : __carry.swap(*__counter);
642 : }
643 : __carry.swap(*__counter);
644 : if (__counter == __fill)
645 : ++__fill;
646 : }
647 : while ( !empty() );
648 :
649 : for (__counter = __tmp + 1; __counter != __fill; ++__counter)
650 : __counter->merge(__counter[-1], __ptr_comp);
651 : __fill[-1].swap(this->_M_impl._M_node);
652 : }
653 : __catch(...)
654 : {
655 : // Move all nodes back into *this.
656 : __carry._M_put_all(end()._M_node);
657 : for (int __i = 0; __i < sizeof(__tmp)/sizeof(__tmp[0]); ++__i)
658 : __tmp[__i]._M_put_all(end()._M_node);
659 : __throw_exception_again;
660 : }
661 : }
662 : }
663 :
664 : _GLIBCXX_END_NAMESPACE_CONTAINER
665 : _GLIBCXX_END_NAMESPACE_VERSION
666 : } // namespace std
667 :
668 : #endif /* _LIST_TCC */
669 :
|
