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