Line data Source code
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 198 : _List_base<_Tp, _Alloc>::
66 : _M_clear() _GLIBCXX_NOEXCEPT
67 : {
68 : typedef _List_node<_Tp> _Node;
69 198 : __detail::_List_node_base* __cur = _M_impl._M_node._M_next;
70 330 : while (__cur != &_M_impl._M_node)
71 : {
72 132 : _Node* __tmp = static_cast<_Node*>(__cur);
73 132 : __cur = __tmp->_M_next;
74 132 : _Tp* __val = __tmp->_M_valptr();
75 : #if __cplusplus >= 201103L
76 264 : _Node_alloc_traits::destroy(_M_get_Node_allocator(), __val);
77 : #else
78 : _Tp_alloc_type(_M_get_Node_allocator()).destroy(__val);
79 : #endif
80 132 : _M_put_node(__tmp);
81 : }
82 198 : }
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 :
|
