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 _Alloc& __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
171  forward_list<_Tp, _Alloc>::
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
208  forward_list<_Tp, _Alloc>::
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>
226  typename forward_list<_Tp, _Alloc>::iterator
227  forward_list<_Tp, _Alloc>::
228  _M_splice_after(const_iterator __pos, forward_list&& __list)
229  {
230  _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
231  iterator __before = __list.before_begin();
232  return iterator(__tmp->_M_transfer_after(__before._M_node));
233  }
234 
235  template<typename _Tp, typename _Alloc>
236  void
237  forward_list<_Tp, _Alloc>::
238  splice_after(const_iterator __pos, forward_list&&,
239  const_iterator __before, const_iterator __last)
240  {
241  _Node_base* __tmp = const_cast<_Node_base*>(__pos._M_node);
242  __tmp->_M_transfer_after(const_cast<_Node_base*>(__before._M_node),
243  const_cast<_Node_base*>(__last._M_node));
244  }
245 
246  template<typename _Tp, typename _Alloc>
247  typename forward_list<_Tp, _Alloc>::iterator
248  forward_list<_Tp, _Alloc>::
249  insert_after(const_iterator __pos, size_type __n, const _Tp& __val)
250  {
251  if (__n)
252  {
253  forward_list __tmp(__n, __val, this->_M_get_Node_allocator());
254  return _M_splice_after(__pos, std::move(__tmp));
255  }
256  else
257  return iterator(const_cast<_Node_base*>(__pos._M_node));
258  }
259 
260  template<typename _Tp, typename _Alloc>
261  template<typename _InputIterator>
262  typename forward_list<_Tp, _Alloc>::iterator
263  forward_list<_Tp, _Alloc>::
264  insert_after(const_iterator __pos,
265  _InputIterator __first, _InputIterator __last)
266  {
267  forward_list __tmp(__first, __last, this->_M_get_Node_allocator());
268  if (!__tmp.empty())
269  return _M_splice_after(__pos, std::move(__tmp));
270  else
271  return iterator(const_cast<_Node_base*>(__pos._M_node));
272  }
273 
274  template<typename _Tp, typename _Alloc>
275  typename forward_list<_Tp, _Alloc>::iterator
276  forward_list<_Tp, _Alloc>::
277  insert_after(const_iterator __pos, std::initializer_list<_Tp> __il)
278  {
279  if (__il.size())
280  {
281  forward_list __tmp(__il, this->_M_get_Node_allocator());
282  return _M_splice_after(__pos, std::move(__tmp));
283  }
284  else
285  return iterator(const_cast<_Node_base*>(__pos._M_node));
286  }
287 
288  template<typename _Tp, typename _Alloc>
289  void
290  forward_list<_Tp, _Alloc>::
291  remove(const _Tp& __val)
292  {
293  _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
294  _Node* __extra = 0;
295 
296  while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
297  {
298  if (__tmp->_M_value == __val)
299  {
300  if (std::__addressof(__tmp->_M_value)
301  != std::__addressof(__val))
302  {
303  this->_M_erase_after(__curr);
304  continue;
305  }
306  else
307  __extra = __curr;
308  }
309  __curr = static_cast<_Node*>(__curr->_M_next);
310  }
311 
312  if (__extra)
313  this->_M_erase_after(__extra);
314  }
315 
316  template<typename _Tp, typename _Alloc>
317  template<typename _Pred>
318  void
319  forward_list<_Tp, _Alloc>::
320  remove_if(_Pred __pred)
321  {
322  _Node* __curr = static_cast<_Node*>(&this->_M_impl._M_head);
323  while (_Node* __tmp = static_cast<_Node*>(__curr->_M_next))
324  {
325  if (__pred(__tmp->_M_value))
326  this->_M_erase_after(__curr);
327  else
328  __curr = static_cast<_Node*>(__curr->_M_next);
329  }
330  }
331 
332  template<typename _Tp, typename _Alloc>
333  template<typename _BinPred>
334  void
335  forward_list<_Tp, _Alloc>::
336  unique(_BinPred __binary_pred)
337  {
338  iterator __first = begin();
339  iterator __last = end();
340  if (__first == __last)
341  return;
342  iterator __next = __first;
343  while (++__next != __last)
344  {
345  if (__binary_pred(*__first, *__next))
346  erase_after(__first);
347  else
348  __first = __next;
349  __next = __first;
350  }
351  }
352 
353  template<typename _Tp, typename _Alloc>
354  template<typename _Comp>
355  void
356  forward_list<_Tp, _Alloc>::
357  merge(forward_list&& __list, _Comp __comp)
358  {
359  _Node_base* __node = &this->_M_impl._M_head;
360  while (__node->_M_next && __list._M_impl._M_head._M_next)
361  {
362  if (__comp(static_cast<_Node*>
363  (__list._M_impl._M_head._M_next)->_M_value,
364  static_cast<_Node*>
365  (__node->_M_next)->_M_value))
366  __node->_M_transfer_after(&__list._M_impl._M_head,
367  __list._M_impl._M_head._M_next);
368  __node = __node->_M_next;
369  }
370  if (__list._M_impl._M_head._M_next)
371  {
372  __node->_M_next = __list._M_impl._M_head._M_next;
373  __list._M_impl._M_head._M_next = 0;
374  }
375  }
376 
377  template<typename _Tp, typename _Alloc>
378  bool
379  operator==(const forward_list<_Tp, _Alloc>& __lx,
380  const forward_list<_Tp, _Alloc>& __ly)
381  {
382  // We don't have size() so we need to walk through both lists
383  // making sure both iterators are valid.
384  auto __ix = __lx.cbegin();
385  auto __iy = __ly.cbegin();
386  while (__ix != __lx.cend() && __iy != __ly.cend())
387  {
388  if (*__ix != *__iy)
389  return false;
390  ++__ix;
391  ++__iy;
392  }
393  if (__ix == __lx.cend() && __iy == __ly.cend())
394  return true;
395  else
396  return false;
397  }
398 
399  template<typename _Tp, class _Alloc>
400  template<typename _Comp>
401  void
402  forward_list<_Tp, _Alloc>::
403  sort(_Comp __comp)
404  {
405  // If `next' is 0, return immediately.
406  _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next);
407  if (!__list)
408  return;
409 
410  unsigned long __insize = 1;
411 
412  while (1)
413  {
414  _Node* __p = __list;
415  __list = 0;
416  _Node* __tail = 0;
417 
418  // Count number of merges we do in this pass.
419  unsigned long __nmerges = 0;
420 
421  while (__p)
422  {
423  ++__nmerges;
424  // There exists a merge to be done.
425  // Step `insize' places along from p.
426  _Node* __q = __p;
427  unsigned long __psize = 0;
428  for (unsigned long __i = 0; __i < __insize; ++__i)
429  {
430  ++__psize;
431  __q = static_cast<_Node*>(__q->_M_next);
432  if (!__q)
433  break;
434  }
435 
436  // If q hasn't fallen off end, we have two lists to merge.
437  unsigned long __qsize = __insize;
438 
439  // Now we have two lists; merge them.
440  while (__psize > 0 || (__qsize > 0 && __q))
441  {
442  // Decide whether next node of merge comes from p or q.
443  _Node* __e;
444  if (__psize == 0)
445  {
446  // p is empty; e must come from q.
447  __e = __q;
448  __q = static_cast<_Node*>(__q->_M_next);
449  --__qsize;
450  }
451  else if (__qsize == 0 || !__q)
452  {
453  // q is empty; e must come from p.
454  __e = __p;
455  __p = static_cast<_Node*>(__p->_M_next);
456  --__psize;
457  }
458  else if (__comp(__p->_M_value, __q->_M_value))
459  {
460  // First node of p is lower; e must come from p.
461  __e = __p;
462  __p = static_cast<_Node*>(__p->_M_next);
463  --__psize;
464  }
465  else
466  {
467  // First node of q is lower; e must come from q.
468  __e = __q;
469  __q = static_cast<_Node*>(__q->_M_next);
470  --__qsize;
471  }
472 
473  // Add the next node to the merged list.
474  if (__tail)
475  __tail->_M_next = __e;
476  else
477  __list = __e;
478  __tail = __e;
479  }
480 
481  // Now p has stepped `insize' places along, and q has too.
482  __p = __q;
483  }
484  __tail->_M_next = 0;
485 
486  // If we have done only one merge, we're finished.
487  // Allow for nmerges == 0, the empty list case.
488  if (__nmerges <= 1)
489  {
490  this->_M_impl._M_head._M_next = __list;
491  return;
492  }
493 
494  // Otherwise repeat, merging lists twice the size.
495  __insize *= 2;
496  }
497  }
498 
499 _GLIBCXX_END_NAMESPACE_CONTAINER
500 } // namespace std
501 
502 #endif /* _FORWARD_LIST_TCC */
503