File Coverage

/usr/include/c++/5/bits/list.tcc
Criterion Covered Total %
statement 8 8 100.0
branch 3 4 75.0
condition n/a
subroutine n/a
pod n/a
total 11 12 91.6


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