1 // List implementation (out of line) -*- C++ -*-
2 
3 // Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006, 2007, 2008, 2009, 2010,
4 // 2011, 2012 Free Software Foundation, Inc.
5 //
6 // This file is part of the GNU ISO C++ Library.  This library is free
7 // software; you can redistribute it and/or modify it under the
8 // terms of the GNU General Public License as published by the
9 // Free Software Foundation; either version 3, or (at your option)
10 // any later version.
11 
12 // This library is distributed in the hope that it will be useful,
13 // but WITHOUT ANY WARRANTY; without even the implied warranty of
14 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
15 // GNU General Public License for more details.
16 
17 // Under Section 7 of GPL version 3, you are granted additional
18 // permissions described in the GCC Runtime Library Exception, version
19 // 3.1, as published by the Free Software Foundation.
20 
21 // You should have received a copy of the GNU General Public License and
22 // a copy of the GCC Runtime Library Exception along with this program;
23 // see the files COPYING3 and COPYING.RUNTIME respectively.  If not, see
24 // <http://www.gnu.org/licenses/>.
25 
26 /*
27  *
28  * Copyright (c) 1994
29  * Hewlett-Packard Company
30  *
31  * Permission to use, copy, modify, distribute and sell this software
32  * and its documentation for any purpose is hereby granted without fee,
33  * provided that the above copyright notice appear in all copies and
34  * that both that copyright notice and this permission notice appear
35  * in supporting documentation.  Hewlett-Packard Company makes no
36  * representations about the suitability of this software for any
37  * purpose.  It is provided "as is" without express or implied warranty.
38  *
39  *
40  * Copyright (c) 1996,1997
41  * Silicon Graphics Computer Systems, Inc.
42  *
43  * Permission to use, copy, modify, distribute and sell this software
44  * and its documentation for any purpose is hereby granted without fee,
45  * provided that the above copyright notice appear in all copies and
46  * that both that copyright notice and this permission notice appear
47  * in supporting documentation.  Silicon Graphics makes no
48  * representations about the suitability of this software for any
49  * purpose.  It is provided "as is" without express or implied warranty.
50  */
51 
52 /** @file bits/list.tcc
53  *  This is an internal header file, included by other library headers.
54  *  Do not attempt to use it directly. @headername{list}
55  */
56 
57 #ifndef _LIST_TCC
58 #define _LIST_TCC 1
59 
60 namespace std _GLIBCXX_VISIBILITY(default)
61 {
62 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
63 
64   template<typename _Tp, typename _Alloc>
65     void
66     _List_base<_Tp, _Alloc>::
67     _M_clear()
68     {
69       typedef _List_node<_Tp>  _Node;
70       _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
71       while (__cur != &_M_impl._M_node)
72 	{
73 	  _Node* __tmp = __cur;
74 	  __cur = static_cast<_Node*>(__cur->_M_next);
75 #ifdef __GXX_EXPERIMENTAL_CXX0X__
76 	  _M_get_Node_allocator().destroy(__tmp);
77 #else
78 	  _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
79 #endif
80 	  _M_put_node(__tmp);
81 	}
82     }
83 
84 #ifdef __GXX_EXPERIMENTAL_CXX0X__
85   template<typename _Tp, typename _Alloc>
86     template<typename... _Args>
87       typename list<_Tp, _Alloc>::iterator
88       list<_Tp, _Alloc>::
89       emplace(iterator __position, _Args&&... __args)
90       {
91 	_Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
92 	__tmp->_M_hook(__position._M_node);
93 	return iterator(__tmp);
94       }
95 #endif
96 
97   template<typename _Tp, typename _Alloc>
98     typename list<_Tp, _Alloc>::iterator
99     list<_Tp, _Alloc>::
100     insert(iterator __position, const value_type& __x)
101     {
102       _Node* __tmp = _M_create_node(__x);
103       __tmp->_M_hook(__position._M_node);
104       return iterator(__tmp);
105     }
106 
107   template<typename _Tp, typename _Alloc>
108     typename list<_Tp, _Alloc>::iterator
109     list<_Tp, _Alloc>::
110     erase(iterator __position)
111     {
112       iterator __ret = iterator(__position._M_node->_M_next);
113       _M_erase(__position);
114       return __ret;
115     }
116 
117 #ifdef __GXX_EXPERIMENTAL_CXX0X__
118   template<typename _Tp, typename _Alloc>
119     void
120     list<_Tp, _Alloc>::
121     _M_default_append(size_type __n)
122     {
123       size_type __i = 0;
124       __try
125 	{
126 	  for (; __i < __n; ++__i)
127 	    emplace_back();
128 	}
129       __catch(...)
130 	{
131 	  for (; __i; --__i)
132 	    pop_back();
133 	  __throw_exception_again;
134 	}
135     }
136 
137   template<typename _Tp, typename _Alloc>
138     void
139     list<_Tp, _Alloc>::
140     resize(size_type __new_size)
141     {
142       iterator __i = begin();
143       size_type __len = 0;
144       for (; __i != end() && __len < __new_size; ++__i, ++__len)
145         ;
146       if (__len == __new_size)
147         erase(__i, end());
148       else                          // __i == end()
149 	_M_default_append(__new_size - __len);
150     }
151 
152   template<typename _Tp, typename _Alloc>
153     void
154     list<_Tp, _Alloc>::
155     resize(size_type __new_size, const value_type& __x)
156     {
157       iterator __i = begin();
158       size_type __len = 0;
159       for (; __i != end() && __len < __new_size; ++__i, ++__len)
160         ;
161       if (__len == __new_size)
162         erase(__i, end());
163       else                          // __i == end()
164         insert(end(), __new_size - __len, __x);
165     }
166 #else
167   template<typename _Tp, typename _Alloc>
168     void
169     list<_Tp, _Alloc>::
170     resize(size_type __new_size, value_type __x)
171     {
172       iterator __i = begin();
173       size_type __len = 0;
174       for (; __i != end() && __len < __new_size; ++__i, ++__len)
175         ;
176       if (__len == __new_size)
177         erase(__i, end());
178       else                          // __i == end()
179         insert(end(), __new_size - __len, __x);
180     }
181 #endif
182 
183   template<typename _Tp, typename _Alloc>
184     list<_Tp, _Alloc>&
185     list<_Tp, _Alloc>::
186     operator=(const list& __x)
187     {
188       if (this != &__x)
189 	{
190 	  iterator __first1 = begin();
191 	  iterator __last1 = end();
192 	  const_iterator __first2 = __x.begin();
193 	  const_iterator __last2 = __x.end();
194 	  for (; __first1 != __last1 && __first2 != __last2;
195 	       ++__first1, ++__first2)
196 	    *__first1 = *__first2;
197 	  if (__first2 == __last2)
198 	    erase(__first1, __last1);
199 	  else
200 	    insert(__last1, __first2, __last2);
201 	}
202       return *this;
203     }
204 
205   template<typename _Tp, typename _Alloc>
206     void
207     list<_Tp, _Alloc>::
208     _M_fill_assign(size_type __n, const value_type& __val)
209     {
210       iterator __i = begin();
211       for (; __i != end() && __n > 0; ++__i, --__n)
212         *__i = __val;
213       if (__n > 0)
214         insert(end(), __n, __val);
215       else
216         erase(__i, end());
217     }
218 
219   template<typename _Tp, typename _Alloc>
220     template <typename _InputIterator>
221       void
222       list<_Tp, _Alloc>::
223       _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
224 			 __false_type)
225       {
226         iterator __first1 = begin();
227         iterator __last1 = end();
228         for (; __first1 != __last1 && __first2 != __last2;
229 	     ++__first1, ++__first2)
230           *__first1 = *__first2;
231         if (__first2 == __last2)
232           erase(__first1, __last1);
233         else
234           insert(__last1, __first2, __last2);
235       }
236 
237   template<typename _Tp, typename _Alloc>
238     void
239     list<_Tp, _Alloc>::
240     remove(const value_type& __value)
241     {
242       iterator __first = begin();
243       iterator __last = end();
244       iterator __extra = __last;
245       while (__first != __last)
246 	{
247 	  iterator __next = __first;
248 	  ++__next;
249 	  if (*__first == __value)
250 	    {
251 	      // _GLIBCXX_RESOLVE_LIB_DEFECTS
252 	      // 526. Is it undefined if a function in the standard changes
253 	      // in parameters?
254 	      if (std::__addressof(*__first) != std::__addressof(__value))
255 		_M_erase(__first);
256 	      else
257 		__extra = __first;
258 	    }
259 	  __first = __next;
260 	}
261       if (__extra != __last)
262 	_M_erase(__extra);
263     }
264 
265   template<typename _Tp, typename _Alloc>
266     void
267     list<_Tp, _Alloc>::
268     unique()
269     {
270       iterator __first = begin();
271       iterator __last = end();
272       if (__first == __last)
273 	return;
274       iterator __next = __first;
275       while (++__next != __last)
276 	{
277 	  if (*__first == *__next)
278 	    _M_erase(__next);
279 	  else
280 	    __first = __next;
281 	  __next = __first;
282 	}
283     }
284 
285   template<typename _Tp, typename _Alloc>
286     void
287     list<_Tp, _Alloc>::
288 #ifdef __GXX_EXPERIMENTAL_CXX0X__
289     merge(list&& __x)
290 #else
291     merge(list& __x)
292 #endif
293     {
294       // _GLIBCXX_RESOLVE_LIB_DEFECTS
295       // 300. list::merge() specification incomplete
296       if (this != &__x)
297 	{
298 	  _M_check_equal_allocators(__x);
299 
300 	  iterator __first1 = begin();
301 	  iterator __last1 = end();
302 	  iterator __first2 = __x.begin();
303 	  iterator __last2 = __x.end();
304 	  while (__first1 != __last1 && __first2 != __last2)
305 	    if (*__first2 < *__first1)
306 	      {
307 		iterator __next = __first2;
308 		_M_transfer(__first1, __first2, ++__next);
309 		__first2 = __next;
310 	      }
311 	    else
312 	      ++__first1;
313 	  if (__first2 != __last2)
314 	    _M_transfer(__last1, __first2, __last2);
315 	}
316     }
317 
318   template<typename _Tp, typename _Alloc>
319     template <typename _StrictWeakOrdering>
320       void
321       list<_Tp, _Alloc>::
322 #ifdef __GXX_EXPERIMENTAL_CXX0X__
323       merge(list&& __x, _StrictWeakOrdering __comp)
324 #else
325       merge(list& __x, _StrictWeakOrdering __comp)
326 #endif
327       {
328 	// _GLIBCXX_RESOLVE_LIB_DEFECTS
329 	// 300. list::merge() specification incomplete
330 	if (this != &__x)
331 	  {
332 	    _M_check_equal_allocators(__x);
333 
334 	    iterator __first1 = begin();
335 	    iterator __last1 = end();
336 	    iterator __first2 = __x.begin();
337 	    iterator __last2 = __x.end();
338 	    while (__first1 != __last1 && __first2 != __last2)
339 	      if (__comp(*__first2, *__first1))
340 		{
341 		  iterator __next = __first2;
342 		  _M_transfer(__first1, __first2, ++__next);
343 		  __first2 = __next;
344 		}
345 	      else
346 		++__first1;
347 	    if (__first2 != __last2)
348 	      _M_transfer(__last1, __first2, __last2);
349 	  }
350       }
351 
352   template<typename _Tp, typename _Alloc>
353     void
354     list<_Tp, _Alloc>::
355     sort()
356     {
357       // Do nothing if the list has length 0 or 1.
358       if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
359 	  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
360       {
361         list __carry;
362         list __tmp[64];
363         list * __fill = &__tmp[0];
364         list * __counter;
365 
366         do
367 	  {
368 	    __carry.splice(__carry.begin(), *this, begin());
369 
370 	    for(__counter = &__tmp[0];
371 		__counter != __fill && !__counter->empty();
372 		++__counter)
373 	      {
374 		__counter->merge(__carry);
375 		__carry.swap(*__counter);
376 	      }
377 	    __carry.swap(*__counter);
378 	    if (__counter == __fill)
379 	      ++__fill;
380 	  }
381 	while ( !empty() );
382 
383         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
384           __counter->merge(*(__counter - 1));
385         swap( *(__fill - 1) );
386       }
387     }
388 
389   template<typename _Tp, typename _Alloc>
390     template <typename _Predicate>
391       void
392       list<_Tp, _Alloc>::
393       remove_if(_Predicate __pred)
394       {
395         iterator __first = begin();
396         iterator __last = end();
397         while (__first != __last)
398 	  {
399 	    iterator __next = __first;
400 	    ++__next;
401 	    if (__pred(*__first))
402 	      _M_erase(__first);
403 	    __first = __next;
404 	  }
405       }
406 
407   template<typename _Tp, typename _Alloc>
408     template <typename _BinaryPredicate>
409       void
410       list<_Tp, _Alloc>::
411       unique(_BinaryPredicate __binary_pred)
412       {
413         iterator __first = begin();
414         iterator __last = end();
415         if (__first == __last)
416 	  return;
417         iterator __next = __first;
418         while (++__next != __last)
419 	  {
420 	    if (__binary_pred(*__first, *__next))
421 	      _M_erase(__next);
422 	    else
423 	      __first = __next;
424 	    __next = __first;
425 	  }
426       }
427 
428   template<typename _Tp, typename _Alloc>
429     template <typename _StrictWeakOrdering>
430       void
431       list<_Tp, _Alloc>::
432       sort(_StrictWeakOrdering __comp)
433       {
434 	// Do nothing if the list has length 0 or 1.
435 	if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
436 	    && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
437 	  {
438 	    list __carry;
439 	    list __tmp[64];
440 	    list * __fill = &__tmp[0];
441 	    list * __counter;
442 
443 	    do
444 	      {
445 		__carry.splice(__carry.begin(), *this, begin());
446 
447 		for(__counter = &__tmp[0];
448 		    __counter != __fill && !__counter->empty();
449 		    ++__counter)
450 		  {
451 		    __counter->merge(__carry, __comp);
452 		    __carry.swap(*__counter);
453 		  }
454 		__carry.swap(*__counter);
455 		if (__counter == __fill)
456 		  ++__fill;
457 	      }
458 	    while ( !empty() );
459 
460 	    for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
461 	      __counter->merge(*(__counter - 1), __comp);
462 	    swap(*(__fill - 1));
463 	  }
464       }
465 
466 _GLIBCXX_END_NAMESPACE_CONTAINER
467 } // namespace std
468 
469 #endif /* _LIST_TCC */
470 
471