1 | // <forward_list.tcc> -*- C++ -*- |
2 | |
3 | // Copyright (C) 2008-2021 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 | #if __cplusplus > 201703L |
282 | # define _GLIBCXX20_ONLY(__expr) __expr |
283 | #else |
284 | # define _GLIBCXX20_ONLY(__expr) |
285 | #endif |
286 | |
287 | template<typename _Tp, typename _Alloc> |
288 | auto |
289 | forward_list<_Tp, _Alloc>:: |
290 | remove(const _Tp& __val) -> __remove_return_type |
291 | { |
292 | size_type __removed __attribute__((__unused__)) = 0; |
293 | forward_list __to_destroy(get_allocator()); |
294 | |
295 | auto __prev_it = cbefore_begin(); |
296 | while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next)) |
297 | if (*__tmp->_M_valptr() == __val) |
298 | { |
299 | __to_destroy.splice_after(__to_destroy.cbefore_begin(), |
300 | *this, __prev_it); |
301 | _GLIBCXX20_ONLY( __removed++ ); |
302 | } |
303 | else |
304 | ++__prev_it; |
305 | |
306 | return _GLIBCXX20_ONLY( __removed ); |
307 | } |
308 | |
309 | template<typename _Tp, typename _Alloc> |
310 | template<typename _Pred> |
311 | auto |
312 | forward_list<_Tp, _Alloc>:: |
313 | remove_if(_Pred __pred) -> __remove_return_type |
314 | { |
315 | size_type __removed __attribute__((__unused__)) = 0; |
316 | forward_list __to_destroy(get_allocator()); |
317 | |
318 | auto __prev_it = cbefore_begin(); |
319 | while (_Node* __tmp = static_cast<_Node*>(__prev_it._M_node->_M_next)) |
320 | if (__pred(*__tmp->_M_valptr())) |
321 | { |
322 | __to_destroy.splice_after(__to_destroy.cbefore_begin(), |
323 | *this, __prev_it); |
324 | _GLIBCXX20_ONLY( __removed++ ); |
325 | } |
326 | else |
327 | ++__prev_it; |
328 | |
329 | return _GLIBCXX20_ONLY( __removed ); |
330 | } |
331 | |
332 | template<typename _Tp, typename _Alloc> |
333 | template<typename _BinPred> |
334 | auto |
335 | forward_list<_Tp, _Alloc>:: |
336 | unique(_BinPred __binary_pred) -> __remove_return_type |
337 | { |
338 | iterator __first = begin(); |
339 | iterator __last = end(); |
340 | if (__first == __last) |
341 | return _GLIBCXX20_ONLY(0); |
342 | |
343 | forward_list __to_destroy(get_allocator()); |
344 | size_type __removed __attribute__((__unused__)) = 0; |
345 | iterator __next = __first; |
346 | while (++__next != __last) |
347 | { |
348 | if (__binary_pred(*__first, *__next)) |
349 | { |
350 | __to_destroy.splice_after(__to_destroy.cbefore_begin(), |
351 | *this, __first); |
352 | _GLIBCXX20_ONLY( __removed++ ); |
353 | } |
354 | else |
355 | __first = __next; |
356 | __next = __first; |
357 | } |
358 | |
359 | return _GLIBCXX20_ONLY( __removed ); |
360 | } |
361 | |
362 | #undef _GLIBCXX20_ONLY |
363 | |
364 | template<typename _Tp, typename _Alloc> |
365 | template<typename _Comp> |
366 | void |
367 | forward_list<_Tp, _Alloc>:: |
368 | merge(forward_list&& __list, _Comp __comp) |
369 | { |
370 | _Node_base* __node = &this->_M_impl._M_head; |
371 | while (__node->_M_next && __list._M_impl._M_head._M_next) |
372 | { |
373 | if (__comp(*static_cast<_Node*> |
374 | (__list._M_impl._M_head._M_next)->_M_valptr(), |
375 | *static_cast<_Node*> |
376 | (__node->_M_next)->_M_valptr())) |
377 | __node->_M_transfer_after(&__list._M_impl._M_head, |
378 | __list._M_impl._M_head._M_next); |
379 | __node = __node->_M_next; |
380 | } |
381 | |
382 | if (__list._M_impl._M_head._M_next) |
383 | *__node = std::move(__list._M_impl._M_head); |
384 | } |
385 | |
386 | template<typename _Tp, typename _Alloc> |
387 | bool |
388 | operator==(const forward_list<_Tp, _Alloc>& __lx, |
389 | const forward_list<_Tp, _Alloc>& __ly) |
390 | { |
391 | // We don't have size() so we need to walk through both lists |
392 | // making sure both iterators are valid. |
393 | auto __ix = __lx.cbegin(); |
394 | auto __iy = __ly.cbegin(); |
395 | while (__ix != __lx.cend() && __iy != __ly.cend()) |
396 | { |
397 | if (!(*__ix == *__iy)) |
398 | return false; |
399 | ++__ix; |
400 | ++__iy; |
401 | } |
402 | if (__ix == __lx.cend() && __iy == __ly.cend()) |
403 | return true; |
404 | else |
405 | return false; |
406 | } |
407 | |
408 | template<typename _Tp, class _Alloc> |
409 | template<typename _Comp> |
410 | void |
411 | forward_list<_Tp, _Alloc>:: |
412 | sort(_Comp __comp) |
413 | { |
414 | // If `next' is nullptr, return immediately. |
415 | _Node* __list = static_cast<_Node*>(this->_M_impl._M_head._M_next); |
416 | if (!__list) |
417 | return; |
418 | |
419 | unsigned long __insize = 1; |
420 | |
421 | while (1) |
422 | { |
423 | _Node* __p = __list; |
424 | __list = nullptr; |
425 | _Node* __tail = nullptr; |
426 | |
427 | // Count number of merges we do in this pass. |
428 | unsigned long __nmerges = 0; |
429 | |
430 | while (__p) |
431 | { |
432 | ++__nmerges; |
433 | // There exists a merge to be done. |
434 | // Step `insize' places along from p. |
435 | _Node* __q = __p; |
436 | unsigned long __psize = 0; |
437 | for (unsigned long __i = 0; __i < __insize; ++__i) |
438 | { |
439 | ++__psize; |
440 | __q = static_cast<_Node*>(__q->_M_next); |
441 | if (!__q) |
442 | break; |
443 | } |
444 | |
445 | // If q hasn't fallen off end, we have two lists to merge. |
446 | unsigned long __qsize = __insize; |
447 | |
448 | // Now we have two lists; merge them. |
449 | while (__psize > 0 || (__qsize > 0 && __q)) |
450 | { |
451 | // Decide whether next node of merge comes from p or q. |
452 | _Node* __e; |
453 | if (__psize == 0) |
454 | { |
455 | // p is empty; e must come from q. |
456 | __e = __q; |
457 | __q = static_cast<_Node*>(__q->_M_next); |
458 | --__qsize; |
459 | } |
460 | else if (__qsize == 0 || !__q) |
461 | { |
462 | // q is empty; e must come from p. |
463 | __e = __p; |
464 | __p = static_cast<_Node*>(__p->_M_next); |
465 | --__psize; |
466 | } |
467 | else if (!__comp(*__q->_M_valptr(), *__p->_M_valptr())) |
468 | { |
469 | // First node of q is not lower; e must come from p. |
470 | __e = __p; |
471 | __p = static_cast<_Node*>(__p->_M_next); |
472 | --__psize; |
473 | } |
474 | else |
475 | { |
476 | // First node of q is lower; e must come from q. |
477 | __e = __q; |
478 | __q = static_cast<_Node*>(__q->_M_next); |
479 | --__qsize; |
480 | } |
481 | |
482 | // Add the next node to the merged list. |
483 | if (__tail) |
484 | __tail->_M_next = __e; |
485 | else |
486 | __list = __e; |
487 | __tail = __e; |
488 | } |
489 | |
490 | // Now p has stepped `insize' places along, and q has too. |
491 | __p = __q; |
492 | } |
493 | __tail->_M_next = nullptr; |
494 | |
495 | // If we have done only one merge, we're finished. |
496 | // Allow for nmerges == 0, the empty list case. |
497 | if (__nmerges <= 1) |
498 | { |
499 | this->_M_impl._M_head._M_next = __list; |
500 | return; |
501 | } |
502 | |
503 | // Otherwise repeat, merging lists twice the size. |
504 | __insize *= 2; |
505 | } |
506 | } |
507 | |
508 | _GLIBCXX_END_NAMESPACE_CONTAINER |
509 | _GLIBCXX_END_NAMESPACE_VERSION |
510 | } // namespace std |
511 | |
512 | #endif /* _FORWARD_LIST_TCC */ |
513 | |