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