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 | |
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 | _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 = __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 | |