1 // <forward_list.tcc> -*- C++ -*-
2 
3 // Copyright (C) 2008-2018 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 /** @file bits/forward_list.tcc
26  *  This is an internal header file, included by other library headers.
27  *  Do not attempt to use it directly. @headername{forward_list}
28  */
29 
30 #ifndef _FORWARD_LIST_TCC
31 #define _FORWARD_LIST_TCC 1
32 
33 namespace std _GLIBCXX_VISIBILITY(default)
34 {
35 _GLIBCXX_BEGIN_NAMESPACE_VERSION
36 _GLIBCXX_BEGIN_NAMESPACE_CONTAINER
37 
38   template<typename _Tp, typename _Alloc>
39     _Fwd_list_base<_Tp, _Alloc>::
40     _Fwd_list_base(_Fwd_list_base&& __lst, _Node_alloc_type&& __a)
41     : _M_impl(std::move(__a))
42     {
43       if (__lst._M_get_Node_allocator() == _M_get_Node_allocator())
44 	this->_M_impl._M_head = std::move(__lst._M_impl._M_head);
45     }
46 
47   template<typename _Tp, typename _Alloc>
48     template<typename... _Args>
49       _Fwd_list_node_base*
50       _Fwd_list_base<_Tp, _Alloc>::
51       _M_insert_after(const_iterator __pos, _Args&&... __args)
52       {
53 	_Fwd_list_node_base* __to
54 	  = const_cast<_Fwd_list_node_base*>(__pos._M_node);
55 	_Node* __thing = _M_create_node(std::forward<_Args>(__args)...);
56 	__thing->_M_next = __to->_M_next;
57 	__to->_M_next = __thing;
58 	return __to->_M_next;
59       }
60 
61   template<typename _Tp, typename _Alloc>
62     _Fwd_list_node_base*
63     _Fwd_list_base<_Tp, _Alloc>::
64     _M_erase_after(_Fwd_list_node_base* __pos)
65     {
66       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
67       __pos->_M_next = __curr->_M_next;
68       _Node_alloc_traits::destroy(_M_get_Node_allocator(),
69 				  __curr->_M_valptr());
70       __curr->~_Node();
71       _M_put_node(__curr);
72       return __pos->_M_next;
73     }
74 
75   template<typename _Tp, typename _Alloc>
76     _Fwd_list_node_base*
77     _Fwd_list_base<_Tp, _Alloc>::
78     _M_erase_after(_Fwd_list_node_base* __pos,
79 		   _Fwd_list_node_base* __last)
80     {
81       _Node* __curr = static_cast<_Node*>(__pos->_M_next);
82       while (__curr != __last)
83 	{
84 	  _Node* __temp = __curr;
85 	  __curr = static_cast<_Node*>(__curr->_M_next);
86 	  _Node_alloc_traits::destroy(_M_get_Node_allocator(),
87 				      __temp->_M_valptr());
88 	  __temp->~_Node();
89 	  _M_put_node(__temp);
90 	}
91       __pos->_M_next = __last;
92       return __last;
93     }
94 
95   // Called by the range constructor to implement [23.3.4.2]/9
96   template<typename _Tp, typename _Alloc>
97     template<typename _InputIterator>
98       void
99       forward_list<_Tp, _Alloc>::
100       _M_range_initialize(_InputIterator __first, _InputIterator __last)
101       {
102 	_Node_base* __to = &this->_M_impl._M_head;
103 	for (; __first != __last; ++__first)
104 	  {
105 	    __to->_M_next = this->_M_create_node(*__first);
106 	    __to = __to->_M_next;
107 	  }
108       }
109 
110   // Called by forward_list(n,v,a).
111   template<typename _Tp, typename _Alloc>
112     void
113     forward_list<_Tp, _Alloc>::
114     _M_fill_initialize(size_type __n, const value_type& __value)
115     {
116       _Node_base* __to = &this->_M_impl._M_head;
117       for (; __n; --__n)
118 	{
119 	  __to->_M_next = this->_M_create_node(__value);
120 	  __to = __to->_M_next;
121 	}
122     }
123 
124   template<typename _Tp, typename _Alloc>
125     void
126     forward_list<_Tp, _Alloc>::
127     _M_default_initialize(size_type __n)
128     {
129       _Node_base* __to = &this->_M_impl._M_head;
130       for (; __n; --__n)
131 	{
132 	  __to->_M_next = this->_M_create_node();
133 	  __to = __to->_M_next;
134 	}
135     }
136 
137   template<typename _Tp, typename _Alloc>
138     forward_list<_Tp, _Alloc>&
139     forward_list<_Tp, _Alloc>::
140     operator=(const forward_list& __list)
141     {
142       if (std::__addressof(__list) != this)
143 	{
144 	  if (_Node_alloc_traits::_S_propagate_on_copy_assign())
145 	    {
146 	      auto& __this_alloc = this->_M_get_Node_allocator();
147 	      auto& __that_alloc = __list._M_get_Node_allocator();
148 	      if (!_Node_alloc_traits::_S_always_equal()
149 		  && __this_alloc != __that_alloc)
150 		{
151 		  // replacement allocator cannot free existing storage
152 		  clear();
153 		}
154 	      std::__alloc_on_copy(__this_alloc, __that_alloc);
155 	    }
156 	  assign(__list.cbegin(), __list.cend());
157 	}
158       return *this;
159     }
160 
161   template<typename _Tp, typename _Alloc>
162     void
163     forward_list<_Tp, _Alloc>::
164     _M_default_insert_after(const_iterator __pos, size_type __n)
165     {
166       const_iterator __saved_pos = __pos;
167       __try
168 	{
169 	  for (; __n; --__n)
170 	    __pos = emplace_after(__pos);
171 	}
172       __catch(...)
173 	{
174 	  erase_after(__saved_pos, ++__pos);
175 	  __throw_exception_again;
176 	}
177     }
178 
179   template<typename _Tp, typename _Alloc>
180     void
181     forward_list<_Tp, _Alloc>::
182     resize(size_type __sz)
183     {
184       iterator __k = before_begin();
185 
186       size_type __len = 0;
187       while (__k._M_next() != end() && __len < __sz)
188 	{
189 	  ++__k;
190 	  ++__len;
191 	}
192       if (__len == __sz)
193 	erase_after(__k, end());
194       else
195 	_M_default_insert_after(__k, __sz - __len);
196     }
197 
198   template<typename _Tp, typename _Alloc>
199     void
200     forward_list<_Tp, _Alloc>::
201     resize(size_type __sz, const value_type& __val)
202     {
203       iterator __k = before_begin();
204 
205       size_type __len = 0;
206       while (__k._M_next() != end() && __len < __sz)
207 	{
208 	  ++__k;
209 	  ++__len;
210 	}
211       if (__len == __sz)
212 	erase_after(__k, end());
213       else
214 	insert_after(__k, __sz - __len, __val);
215     }
216 
217   template<typename _Tp, typename _Alloc>
218     typename forward_list<_Tp, _Alloc>::iterator
219     forward_list<_Tp, _Alloc>::
220     _M_splice_after(const_iterator __pos,
221 		    const_iterator __before, const_iterator __last)
222     {
223       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
224       _Node_base* __b = const_cast<_Node_base*>(__before._M_node);
225       _Node_base* __end = __b;
226 
227       while (__end && __end->_M_next != __last._M_node)
228 	__end = __end->_M_next;
229 
230       if (__b != __end)
231 	return iterator(__tmp->_M_transfer_after(__b, __end));
232       else
233 	return iterator(__tmp);
234     }
235 
236   template<typename _Tp, typename _Alloc>
237     void
238     forward_list<_Tp, _Alloc>::
239     splice_after(const_iterator __pos, forward_list&&,
240 		 const_iterator __i) noexcept
241     {
242       const_iterator __j = __i;
243       ++__j;
244 
245       if (__pos == __i || __pos == __j)
246 	return;
247 
248       _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
249       __tmp->_M_transfer_after(const_cast<_Node_base*>(__i._M_node),
250 			       const_cast<_Node_base*>(__j._M_node));
251     }
252 
253   template<typename _Tp, typename _Alloc>
254     typename forward_list<_Tp, _Alloc>::iterator
255     forward_list<_Tp, _Alloc>::
256     insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
257     {
258       if (__n)
259 	{
260 	  forward_list __tmp(__n, __val, get_allocator());
261 	  return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
262 	}
263       else
264 	return iterator(const_cast<_Node_base*>(__pos._M_node));
265     }
266 
267   template<typename _Tp, typename _Alloc>
268     template<typename _InputIterator, typename>
269       typename forward_list<_Tp, _Alloc>::iterator
270       forward_list<_Tp, _Alloc>::
271       insert_after(const_iterator __pos,
272 		   _InputIterator __first, _InputIterator __last)
273       {
274 	forward_list __tmp(__first, __last, get_allocator());
275 	if (!__tmp.empty())
276 	  return _M_splice_after(__pos, __tmp.before_begin(), __tmp.end());
277 	else
278 	  return iterator(const_cast<_Node_base*>(__pos._M_node));
279       }
280 
281   template<typename _Tp, typename _Alloc>
282     void
283     forward_list<_Tp, _Alloc>::
284     remove(const _Tp& __val)
285     {
286       _Node_base* __curr = &this->_M_impl._M_head;
287       _Node_base* __extra = nullptr;
288 
289       while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
290 	{
291 	  if (*__tmp->_M_valptr() == __val)
292 	    {
293 	      if (__tmp->_M_valptr() != std::__addressof(__val))
294 		{
295 		  this->_M_erase_after(__curr);
296 		  continue;
297 		}
298 	      else
299 		__extra = __curr;
300 	    }
301 	  __curr = __curr->_M_next;
302 	}
303 
304       if (__extra)
305 	this->_M_erase_after(__extra);
306     }
307 
308   template<typename _Tp, typename _Alloc>
309     template<typename _Pred>
310       void
311       forward_list<_Tp, _Alloc>::
312       remove_if(_Pred __pred)
313       {
314 	_Node_base* __curr = &this->_M_impl._M_head;
315 	while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
316 	  {
317 	    if (__pred(*__tmp->_M_valptr()))
318 	      this->_M_erase_after(__curr);
319 	    else
320 	      __curr = __curr->_M_next;
321 	  }
322       }
323 
324   template<typename _Tp, typename _Alloc>
325     template<typename _BinPred>
326       void
327       forward_list<_Tp, _Alloc>::
328       unique(_BinPred __binary_pred)
329       {
330 	iterator __first = begin();
331 	iterator __last = end();
332 	if (__first == __last)
333 	  return;
334 	iterator __next = __first;
335 	while (++__next != __last)
336 	{
337 	  if (__binary_pred(*__first, *__next))
338 	    erase_after(__first);
339 	  else
340 	    __first = __next;
341 	  __next = __first;
342 	}
343       }
344 
345   template<typename _Tp, typename _Alloc>
346     template<typename _Comp>
347       void
348       forward_list<_Tp, _Alloc>::
349       merge(forward_list&& __list, _Comp __comp)
350       {
351 	_Node_base* __node = &this->_M_impl._M_head;
352 	while (__node->_M_next && __list._M_impl._M_head._M_next)
353 	  {
354 	    if (__comp(*static_cast<_Node*>
355 		       (__list._M_impl._M_head._M_next)->_M_valptr(),
356 		       *static_cast<_Node*>
357 		       (__node->_M_next)->_M_valptr()))
358 	      __node->_M_transfer_after(&__list._M_impl._M_head,
359 					__list._M_impl._M_head._M_next);
360 	    __node = __node->_M_next;
361 	  }
362 
363 	if (__list._M_impl._M_head._M_next)
364 	  *__node = std::move(__list._M_impl._M_head);
365       }
366 
367   template<typename _Tp, typename _Alloc>
368     bool
369     operator==(const forward_list<_Tp, _Alloc>& __lx,
370 	       const forward_list<_Tp, _Alloc>& __ly)
371     {
372       //  We don't have size() so we need to walk through both lists
373       //  making sure both iterators are valid.
374       auto __ix = __lx.cbegin();
375       auto __iy = __ly.cbegin();
376       while (__ix != __lx.cend() && __iy != __ly.cend())
377 	{
378 	  if (*__ix != *__iy)
379 	    return false;
380 	  ++__ix;
381 	  ++__iy;
382 	}
383       if (__ix == __lx.cend() && __iy == __ly.cend())
384 	return true;
385       else
386 	return false;
387     }
388 
389   template<typename _Tp, class _Alloc>
390     template<typename _Comp>
391       void
392       forward_list<_Tp, _Alloc>::
393       sort(_Comp __comp)
394       {
395 	// If `next' is nullptr, return immediately.
396 	_Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
397 	if (!__list)
398 	  return;
399 
400 	unsigned long __insize = 1;
401 
402 	while (1)
403 	  {
404 	    _Node* __p = __list;
405 	    __list = nullptr;
406 	    _Node* __tail = nullptr;
407 
408 	    // Count number of merges we do in this pass.
409 	    unsigned long __nmerges = 0;
410 
411 	    while (__p)
412 	      {
413 		++__nmerges;
414 		// There exists a merge to be done.
415 		// Step `insize' places along from p.
416 		_Node* __q = __p;
417 		unsigned long __psize = 0;
418 		for (unsigned long __i = 0; __i < __insize; ++__i)
419 		  {
420 		    ++__psize;
421 		    __q = static_cast<_Node*>(__q->_M_next);
422 		    if (!__q)
423 		      break;
424 		  }
425 
426 		// If q hasn't fallen off end, we have two lists to merge.
427 		unsigned long __qsize = __insize;
428 
429 		// Now we have two lists; merge them.
430 		while (__psize > 0 || (__qsize > 0 && __q))
431 		  {
432 		    // Decide whether next node of merge comes from p or q.
433 		    _Node* __e;
434 		    if (__psize == 0)
435 		      {
436 			// p is empty; e must come from q.
437 			__e = __q;
438 			__q = static_cast<_Node*>(__q->_M_next);
439 			--__qsize;
440 		      }
441 		    else if (__qsize == 0 || !__q)
442 		      {
443 			// q is empty; e must come from p.
444 			__e = __p;
445 			__p = static_cast<_Node*>(__p->_M_next);
446 			--__psize;
447 		      }
448 		    else if (__comp(*__p->_M_valptr(), *__q->_M_valptr()))
449 		      {
450 			// First node of p is lower; e must come from p.
451 			__e = __p;
452 			__p = static_cast<_Node*>(__p->_M_next);
453 			--__psize;
454 		      }
455 		    else
456 		      {
457 			// First node of q is lower; e must come from q.
458 			__e = __q;
459 			__q = static_cast<_Node*>(__q->_M_next);
460 			--__qsize;
461 		      }
462 
463 		    // Add the next node to the merged list.
464 		    if (__tail)
465 		      __tail->_M_next = __e;
466 		    else
467 		      __list = __e;
468 		    __tail = __e;
469 		  }
470 
471 		// Now p has stepped `insize' places along, and q has too.
472 		__p = __q;
473 	      }
474 	    __tail->_M_next = nullptr;
475 
476 	    // If we have done only one merge, we're finished.
477 	    // Allow for nmerges == 0, the empty list case.
478 	    if (__nmerges <= 1)
479 	      {
480 		this->_M_impl._M_head._M_next = __list;
481 		return;
482 	      }
483 
484 	    // Otherwise repeat, merging lists twice the size.
485 	    __insize *= 2;
486 	  }
487       }
488 
489 _GLIBCXX_END_NAMESPACE_CONTAINER
490 _GLIBCXX_END_NAMESPACE_VERSION
491 } // namespace std
492 
493 #endif /* _FORWARD_LIST_TCC */
494