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>::
_M_clear()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>::
emplace(const_iterator __position,_Args &&...__args)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
insert(const_iterator __position,const value_type & __x)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>::
insert(const_iterator __position,size_type __n,const value_type & __x)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>::
insert(const_iterator __position,_InputIterator __first,_InputIterator __last)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
erase(const_iterator __position)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>::
_M_resize_pos(size_type & __new_size) const175     _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>::
_M_default_append(size_type __n)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>::
resize(size_type __new_size)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>::
resize(size_type __new_size,const value_type & __x)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>::
resize(size_type __new_size,value_type __x)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>::
operator =(const list & __x)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>::
_M_fill_assign(size_type __n,const value_type & __val)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>::
_M_assign_dispatch(_InputIterator __first2,_InputIterator __last2,__false_type)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>::
remove(const value_type & __value)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>::
unique()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
merge(list && __x)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
merge(list && __x,_StrictWeakOrdering __comp)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>::
sort()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>::
remove_if(_Predicate __pred)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>::
unique(_BinaryPredicate __binary_pred)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>::
sort(_StrictWeakOrdering __comp)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