]>
Commit | Line | Data |
---|---|---|
b8b4301e PC |
1 | // <forward_list> -*- C++ -*- |
2 | ||
2203cb90 | 3 | // Copyright (C) 2010, 2011, 2012 Free Software Foundation, Inc. |
b8b4301e PC |
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 debug/forward_list | |
26 | * This file is a GNU debug extension to the Standard C++ Library. | |
27 | */ | |
28 | ||
29 | #ifndef _GLIBCXX_DEBUG_FORWARD_LIST | |
30 | #define _GLIBCXX_DEBUG_FORWARD_LIST 1 | |
31 | ||
32 | #pragma GCC system_header | |
33 | ||
34 | #include <forward_list> | |
35 | #include <debug/safe_sequence.h> | |
36 | #include <debug/safe_iterator.h> | |
37 | ||
12ffa228 | 38 | namespace std _GLIBCXX_VISIBILITY(default) |
b8b4301e PC |
39 | { |
40 | namespace __debug | |
41 | { | |
42 | /// Class std::forward_list with safety/checking/debug instrumentation. | |
43 | template<typename _Tp, typename _Alloc = std::allocator<_Tp> > | |
44 | class forward_list | |
12ffa228 | 45 | : public _GLIBCXX_STD_C::forward_list<_Tp, _Alloc>, |
b8b4301e PC |
46 | public __gnu_debug::_Safe_sequence<forward_list<_Tp, _Alloc> > |
47 | { | |
12ffa228 | 48 | typedef _GLIBCXX_STD_C::forward_list<_Tp, _Alloc> _Base; |
b8b4301e | 49 | |
afe96d41 FD |
50 | typedef typename _Base::iterator _Base_iterator; |
51 | typedef typename _Base::const_iterator _Base_const_iterator; | |
b8b4301e PC |
52 | public: |
53 | typedef typename _Base::reference reference; | |
54 | typedef typename _Base::const_reference const_reference; | |
55 | ||
afe96d41 | 56 | typedef __gnu_debug::_Safe_iterator<_Base_iterator, |
b8b4301e | 57 | forward_list> iterator; |
afe96d41 | 58 | typedef __gnu_debug::_Safe_iterator<_Base_const_iterator, |
b8b4301e PC |
59 | forward_list> const_iterator; |
60 | ||
61 | typedef typename _Base::size_type size_type; | |
62 | typedef typename _Base::difference_type difference_type; | |
63 | ||
64 | typedef _Tp value_type; | |
65 | typedef _Alloc allocator_type; | |
66 | typedef typename _Base::pointer pointer; | |
67 | typedef typename _Base::const_pointer const_pointer; | |
68 | ||
69 | // 23.2.3.1 construct/copy/destroy: | |
70 | explicit | |
71 | forward_list(const _Alloc& __al = _Alloc()) | |
72 | : _Base(__al) { } | |
73 | ||
74 | forward_list(const forward_list& __list, const _Alloc& __al) | |
75 | : _Base(__list, __al) | |
76 | { } | |
77 | ||
78 | forward_list(forward_list&& __list, const _Alloc& __al) | |
afe96d41 | 79 | : _Base(std::move(__list._M_base()), __al) |
b8b4301e PC |
80 | { |
81 | this->_M_swap(__list); | |
82 | } | |
83 | ||
84 | explicit | |
85 | forward_list(size_type __n) | |
86 | : _Base(__n) | |
87 | { } | |
88 | ||
89 | forward_list(size_type __n, const _Tp& __value, | |
90 | const _Alloc& __al = _Alloc()) | |
91 | : _Base(__n, __value, __al) | |
92 | { } | |
93 | ||
2203cb90 PC |
94 | template<typename _InputIterator, |
95 | typename = std::_RequireInputIter<_InputIterator>> | |
96 | forward_list(_InputIterator __first, _InputIterator __last, | |
b8b4301e PC |
97 | const _Alloc& __al = _Alloc()) |
98 | : _Base(__gnu_debug::__base(__gnu_debug::__check_valid_range(__first, | |
99 | __last)), | |
100 | __gnu_debug::__base(__last), __al) | |
101 | { } | |
102 | ||
103 | forward_list(const forward_list& __list) | |
104 | : _Base(__list) | |
105 | { } | |
106 | ||
6f59ea25 | 107 | forward_list(forward_list&& __list) noexcept |
afe96d41 FD |
108 | : _Base(std::move(__list._M_base())) |
109 | { | |
110 | this->_M_swap(__list); | |
111 | } | |
b8b4301e PC |
112 | |
113 | forward_list(std::initializer_list<_Tp> __il, | |
114 | const _Alloc& __al = _Alloc()) | |
115 | : _Base(__il, __al) | |
116 | { } | |
117 | ||
6f59ea25 | 118 | ~forward_list() noexcept |
b8b4301e PC |
119 | { } |
120 | ||
121 | forward_list& | |
122 | operator=(const forward_list& __list) | |
123 | { | |
124 | static_cast<_Base&>(*this) = __list; | |
125 | this->_M_invalidate_all(); | |
126 | return *this; | |
127 | } | |
128 | ||
129 | forward_list& | |
130 | operator=(forward_list&& __list) | |
131 | { | |
132 | // NB: DR 1204. | |
133 | // NB: DR 675. | |
739fd6a6 | 134 | __glibcxx_check_self_move_assign(__list); |
b8b4301e PC |
135 | clear(); |
136 | swap(__list); | |
137 | return *this; | |
138 | } | |
139 | ||
140 | forward_list& | |
141 | operator=(std::initializer_list<_Tp> __il) | |
142 | { | |
143 | static_cast<_Base&>(*this) = __il; | |
144 | this->_M_invalidate_all(); | |
145 | return *this; | |
146 | } | |
147 | ||
2203cb90 PC |
148 | template<typename _InputIterator, |
149 | typename = std::_RequireInputIter<_InputIterator>> | |
150 | void | |
b8b4301e PC |
151 | assign(_InputIterator __first, _InputIterator __last) |
152 | { | |
153 | __glibcxx_check_valid_range(__first, __last); | |
154 | _Base::assign(__gnu_debug::__base(__first), | |
155 | __gnu_debug::__base(__last)); | |
156 | this->_M_invalidate_all(); | |
157 | } | |
158 | ||
159 | void | |
160 | assign(size_type __n, const _Tp& __val) | |
161 | { | |
162 | _Base::assign(__n, __val); | |
163 | this->_M_invalidate_all(); | |
164 | } | |
165 | ||
166 | void | |
167 | assign(std::initializer_list<_Tp> __il) | |
168 | { | |
169 | _Base::assign(__il); | |
170 | this->_M_invalidate_all(); | |
171 | } | |
172 | ||
173 | using _Base::get_allocator; | |
174 | ||
175 | // iterators: | |
176 | ||
177 | iterator | |
d3677132 | 178 | before_begin() noexcept |
b8b4301e PC |
179 | { return iterator(_Base::before_begin(), this); } |
180 | ||
181 | const_iterator | |
d3677132 | 182 | before_begin() const noexcept |
b8b4301e PC |
183 | { return const_iterator(_Base::before_begin(), this); } |
184 | ||
185 | iterator | |
d3677132 | 186 | begin() noexcept |
b8b4301e PC |
187 | { return iterator(_Base::begin(), this); } |
188 | ||
189 | const_iterator | |
d3677132 | 190 | begin() const noexcept |
b8b4301e PC |
191 | { return const_iterator(_Base::begin(), this); } |
192 | ||
193 | iterator | |
d3677132 | 194 | end() noexcept |
b8b4301e PC |
195 | { return iterator(_Base::end(), this); } |
196 | ||
197 | const_iterator | |
d3677132 | 198 | end() const noexcept |
b8b4301e PC |
199 | { return const_iterator(_Base::end(), this); } |
200 | ||
201 | const_iterator | |
d3677132 | 202 | cbegin() const noexcept |
b8b4301e PC |
203 | { return const_iterator(_Base::cbegin(), this); } |
204 | ||
205 | const_iterator | |
d3677132 | 206 | cbefore_begin() const noexcept |
b8b4301e PC |
207 | { return const_iterator(_Base::cbefore_begin(), this); } |
208 | ||
209 | const_iterator | |
d3677132 | 210 | cend() const noexcept |
b8b4301e PC |
211 | { return const_iterator(_Base::cend(), this); } |
212 | ||
213 | using _Base::empty; | |
214 | using _Base::max_size; | |
215 | ||
216 | // element access: | |
217 | ||
218 | reference | |
219 | front() | |
220 | { | |
221 | __glibcxx_check_nonempty(); | |
222 | return _Base::front(); | |
223 | } | |
224 | ||
225 | const_reference | |
226 | front() const | |
227 | { | |
228 | __glibcxx_check_nonempty(); | |
229 | return _Base::front(); | |
230 | } | |
231 | ||
232 | // modifiers: | |
233 | ||
234 | using _Base::emplace_front; | |
235 | using _Base::push_front; | |
236 | ||
237 | void | |
238 | pop_front() | |
239 | { | |
240 | __glibcxx_check_nonempty(); | |
afe96d41 FD |
241 | this->_M_invalidate_if([this](_Base_const_iterator __it) |
242 | { return __it == this->_M_base().cbegin(); }); | |
b8b4301e PC |
243 | _Base::pop_front(); |
244 | } | |
245 | ||
246 | template<typename... _Args> | |
247 | iterator | |
248 | emplace_after(const_iterator __pos, _Args&&... __args) | |
249 | { | |
250 | __glibcxx_check_insert_after(__pos); | |
251 | return iterator(_Base::emplace_after(__pos.base(), | |
252 | std::forward<_Args>(__args)...), | |
253 | this); | |
254 | } | |
255 | ||
256 | iterator | |
257 | insert_after(const_iterator __pos, const _Tp& __val) | |
258 | { | |
259 | __glibcxx_check_insert_after(__pos); | |
260 | return iterator(_Base::insert_after(__pos.base(), __val), this); | |
261 | } | |
262 | ||
263 | iterator | |
264 | insert_after(const_iterator __pos, _Tp&& __val) | |
265 | { | |
266 | __glibcxx_check_insert_after(__pos); | |
267 | return iterator(_Base::insert_after(__pos.base(), std::move(__val)), | |
268 | this); | |
269 | } | |
270 | ||
271 | iterator | |
272 | insert_after(const_iterator __pos, size_type __n, const _Tp& __val) | |
273 | { | |
274 | __glibcxx_check_insert_after(__pos); | |
275 | return iterator(_Base::insert_after(__pos.base(), __n, __val), | |
276 | this); | |
277 | } | |
278 | ||
2203cb90 PC |
279 | template<typename _InputIterator, |
280 | typename = std::_RequireInputIter<_InputIterator>> | |
b8b4301e PC |
281 | iterator |
282 | insert_after(const_iterator __pos, | |
283 | _InputIterator __first, _InputIterator __last) | |
284 | { | |
285 | __glibcxx_check_insert_range_after(__pos, __first, __last); | |
286 | return iterator(_Base::insert_after(__pos.base(), | |
287 | __gnu_debug::__base(__first), | |
288 | __gnu_debug::__base(__last)), | |
289 | this); | |
290 | } | |
291 | ||
292 | iterator | |
293 | insert_after(const_iterator __pos, std::initializer_list<_Tp> __il) | |
294 | { | |
295 | __glibcxx_check_insert_after(__pos); | |
296 | return iterator(_Base::insert_after(__pos.base(), __il), this); | |
297 | } | |
298 | ||
afe96d41 FD |
299 | private: |
300 | _Base_iterator | |
301 | _M_erase_after(_Base_const_iterator __pos) | |
302 | { | |
303 | _Base_const_iterator __next = std::next(__pos); | |
304 | this->_M_invalidate_if([__next](_Base_const_iterator __it) | |
305 | { return __it == __next; }); | |
306 | return _Base::erase_after(__pos); | |
307 | } | |
308 | public: | |
efb7b456 | 309 | iterator |
b8b4301e PC |
310 | erase_after(const_iterator __pos) |
311 | { | |
312 | __glibcxx_check_erase_after(__pos); | |
afe96d41 | 313 | return iterator(_M_erase_after(__pos.base()), this); |
b8b4301e PC |
314 | } |
315 | ||
efb7b456 | 316 | iterator |
b8b4301e PC |
317 | erase_after(const_iterator __pos, const_iterator __last) |
318 | { | |
319 | __glibcxx_check_erase_range_after(__pos, __last); | |
afe96d41 FD |
320 | for (_Base_const_iterator __victim = std::next(__pos.base()); |
321 | __victim != __last.base(); ++__victim) | |
b8b4301e | 322 | { |
afe96d41 FD |
323 | _GLIBCXX_DEBUG_VERIFY(__victim != _Base::end(), |
324 | _M_message(__gnu_debug::__msg_valid_range2) | |
325 | ._M_sequence(*this, "this") | |
326 | ._M_iterator(__pos, "pos") | |
327 | ._M_iterator(__last, "last")); | |
328 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) | |
329 | { return __it == __victim; }); | |
b8b4301e | 330 | } |
efb7b456 | 331 | return iterator(_Base::erase_after(__pos.base(), __last.base()), this); |
b8b4301e PC |
332 | } |
333 | ||
334 | void | |
335 | swap(forward_list& __list) | |
336 | { | |
337 | _Base::swap(__list); | |
338 | this->_M_swap(__list); | |
339 | } | |
340 | ||
341 | void | |
342 | resize(size_type __sz) | |
343 | { | |
344 | this->_M_detach_singular(); | |
345 | ||
346 | // if __sz < size(), invalidate all iterators in [begin+__sz, end() | |
afe96d41 FD |
347 | _Base_iterator __victim = _Base::begin(); |
348 | _Base_iterator __end = _Base::end(); | |
b8b4301e PC |
349 | for (size_type __i = __sz; __victim != __end && __i > 0; --__i) |
350 | ++__victim; | |
351 | ||
afe96d41 | 352 | for (; __victim != __end; ++__victim) |
b8b4301e | 353 | { |
afe96d41 FD |
354 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
355 | { return __it == __victim; }); | |
b8b4301e PC |
356 | } |
357 | ||
358 | __try | |
359 | { | |
360 | _Base::resize(__sz); | |
361 | } | |
362 | __catch(...) | |
363 | { | |
364 | this->_M_revalidate_singular(); | |
365 | __throw_exception_again; | |
366 | } | |
367 | } | |
368 | ||
369 | void | |
370 | resize(size_type __sz, const value_type& __val) | |
371 | { | |
372 | this->_M_detach_singular(); | |
373 | ||
374 | // if __sz < size(), invalidate all iterators in [begin+__sz, end()) | |
afe96d41 FD |
375 | _Base_iterator __victim = _Base::begin(); |
376 | _Base_iterator __end = _Base::end(); | |
b8b4301e PC |
377 | for (size_type __i = __sz; __victim != __end && __i > 0; --__i) |
378 | ++__victim; | |
379 | ||
afe96d41 | 380 | for (; __victim != __end; ++__victim) |
b8b4301e | 381 | { |
afe96d41 FD |
382 | this->_M_invalidate_if([__victim](_Base_const_iterator __it) |
383 | { return __it == __victim; }); | |
b8b4301e PC |
384 | } |
385 | ||
386 | __try | |
387 | { | |
388 | _Base::resize(__sz, __val); | |
389 | } | |
390 | __catch(...) | |
391 | { | |
392 | this->_M_revalidate_singular(); | |
393 | __throw_exception_again; | |
394 | } | |
395 | } | |
396 | ||
397 | void | |
d3677132 | 398 | clear() noexcept |
b8b4301e PC |
399 | { |
400 | _Base::clear(); | |
401 | this->_M_invalidate_all(); | |
402 | } | |
403 | ||
404 | // 23.2.3.5 forward_list operations: | |
b8b4301e PC |
405 | void |
406 | splice_after(const_iterator __pos, forward_list&& __list) | |
407 | { | |
408 | __glibcxx_check_insert_after(__pos); | |
409 | _GLIBCXX_DEBUG_VERIFY(&__list != this, | |
410 | _M_message(__gnu_debug::__msg_self_splice) | |
411 | ._M_sequence(*this, "this")); | |
afe96d41 FD |
412 | this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it) |
413 | { | |
414 | return __it != __list._M_base().cbefore_begin() | |
415 | && __it != __list._M_base().end(); | |
416 | }); | |
417 | _Base::splice_after(__pos.base(), std::move(__list._M_base())); | |
b8b4301e PC |
418 | } |
419 | ||
78263296 PC |
420 | void |
421 | splice_after(const_iterator __pos, forward_list& __list) | |
422 | { splice_after(__pos, std::move(__list)); } | |
423 | ||
b8b4301e PC |
424 | void |
425 | splice_after(const_iterator __pos, forward_list&& __list, | |
426 | const_iterator __i) | |
427 | { | |
428 | __glibcxx_check_insert_after(__pos); | |
429 | _GLIBCXX_DEBUG_VERIFY(__i._M_before_dereferenceable(), | |
430 | _M_message(__gnu_debug::__msg_splice_bad) | |
431 | ._M_iterator(__i, "__i")); | |
432 | _GLIBCXX_DEBUG_VERIFY(__i._M_attached_to(&__list), | |
433 | _M_message(__gnu_debug::__msg_splice_other) | |
434 | ._M_iterator(__i, "__i") | |
435 | ._M_sequence(__list, "__list")); | |
436 | ||
437 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
438 | // 250. splicing invalidates iterators | |
afe96d41 FD |
439 | _Base_const_iterator __next = std::next(__i.base()); |
440 | this->_M_transfer_from_if(__list, [__next](_Base_const_iterator __it) | |
441 | { return __it == __next; }); | |
b8b4301e PC |
442 | _Base::splice_after(__pos.base(), std::move(__list._M_base()), |
443 | __i.base()); | |
444 | } | |
445 | ||
78263296 PC |
446 | void |
447 | splice_after(const_iterator __pos, forward_list& __list, | |
448 | const_iterator __i) | |
449 | { splice_after(__pos, std::move(__list), __i); } | |
450 | ||
b8b4301e PC |
451 | void |
452 | splice_after(const_iterator __pos, forward_list&& __list, | |
453 | const_iterator __before, const_iterator __last) | |
454 | { | |
455 | __glibcxx_check_insert_after(__pos); | |
456 | __glibcxx_check_valid_range(__before, __last); | |
457 | _GLIBCXX_DEBUG_VERIFY(__before._M_attached_to(&__list), | |
458 | _M_message(__gnu_debug::__msg_splice_other) | |
459 | ._M_sequence(__list, "list") | |
460 | ._M_iterator(__before, "before")); | |
461 | _GLIBCXX_DEBUG_VERIFY(__before._M_dereferenceable() | |
462 | || __before._M_is_before_begin(), | |
463 | _M_message(__gnu_debug::__msg_valid_range2) | |
464 | ._M_sequence(__list, "list") | |
465 | ._M_iterator(__before, "before") | |
466 | ._M_iterator(__last, "last")); | |
467 | _GLIBCXX_DEBUG_VERIFY(__before != __last, | |
468 | _M_message(__gnu_debug::__msg_valid_range2) | |
469 | ._M_sequence(__list, "list") | |
470 | ._M_iterator(__before, "before") | |
471 | ._M_iterator(__last, "last")); | |
afe96d41 FD |
472 | |
473 | for (_Base_const_iterator __tmp = std::next(__before.base()); | |
474 | __tmp != __last.base(); ++__tmp) | |
475 | { | |
476 | _GLIBCXX_DEBUG_VERIFY(__tmp != __list._M_base().end(), | |
477 | _M_message(__gnu_debug::__msg_valid_range2) | |
478 | ._M_sequence(__list, "list") | |
479 | ._M_iterator(__before, "before") | |
480 | ._M_iterator(__last, "last")); | |
481 | _GLIBCXX_DEBUG_VERIFY(&__list != this || __tmp != __pos.base(), | |
482 | _M_message(__gnu_debug::__msg_splice_overlap) | |
483 | ._M_iterator(__tmp, "position") | |
484 | ._M_iterator(__before, "before") | |
485 | ._M_iterator(__last, "last")); | |
486 | // _GLIBCXX_RESOLVE_LIB_DEFECTS | |
487 | // 250. splicing invalidates iterators | |
488 | this->_M_transfer_from_if(__list, [__tmp](_Base_const_iterator __it) | |
489 | { return __it == __tmp; }); | |
490 | } | |
491 | ||
492 | _Base::splice_after(__pos.base(), std::move(__list._M_base()), | |
493 | __before.base(), __last.base()); | |
b8b4301e PC |
494 | } |
495 | ||
78263296 PC |
496 | void |
497 | splice_after(const_iterator __pos, forward_list& __list, | |
498 | const_iterator __before, const_iterator __last) | |
499 | { splice_after(__pos, std::move(__list), __before, __last); } | |
500 | ||
b8b4301e PC |
501 | void |
502 | remove(const _Tp& __val) | |
503 | { | |
afe96d41 FD |
504 | _Base_iterator __x = _Base::before_begin(); |
505 | _Base_iterator __old = __x++; | |
506 | while (__x != _Base::end()) | |
b8b4301e PC |
507 | { |
508 | if (*__x == __val) | |
afe96d41 | 509 | __x = _M_erase_after(__old); |
b8b4301e PC |
510 | else |
511 | __old = __x++; | |
512 | } | |
513 | } | |
514 | ||
515 | template<typename _Pred> | |
516 | void | |
517 | remove_if(_Pred __pred) | |
518 | { | |
afe96d41 FD |
519 | _Base_iterator __x = _Base::before_begin(); |
520 | _Base_iterator __old = __x++; | |
521 | while (__x != _Base::end()) | |
b8b4301e PC |
522 | { |
523 | if (__pred(*__x)) | |
afe96d41 | 524 | __x = _M_erase_after(__old); |
b8b4301e PC |
525 | else |
526 | __old = __x++; | |
527 | } | |
528 | } | |
529 | ||
530 | void | |
531 | unique() | |
532 | { | |
afe96d41 FD |
533 | _Base_iterator __first = _Base::begin(); |
534 | _Base_iterator __last = _Base::end(); | |
b8b4301e PC |
535 | if (__first == __last) |
536 | return; | |
afe96d41 FD |
537 | _Base_iterator __next = std::next(__first); |
538 | while (__next != __last) | |
b8b4301e PC |
539 | { |
540 | if (*__first == *__next) | |
afe96d41 | 541 | __next = _M_erase_after(__first); |
b8b4301e | 542 | else |
afe96d41 | 543 | __first = __next++; |
b8b4301e PC |
544 | } |
545 | } | |
546 | ||
547 | template<typename _BinPred> | |
548 | void | |
549 | unique(_BinPred __binary_pred) | |
550 | { | |
afe96d41 FD |
551 | _Base_iterator __first = _Base::begin(); |
552 | _Base_iterator __last = _Base::end(); | |
b8b4301e PC |
553 | if (__first == __last) |
554 | return; | |
afe96d41 FD |
555 | _Base_iterator __next = std::next(__first); |
556 | while (__next != __last) | |
b8b4301e PC |
557 | { |
558 | if (__binary_pred(*__first, *__next)) | |
afe96d41 | 559 | __next = _M_erase_after(__first); |
b8b4301e | 560 | else |
afe96d41 | 561 | __first = __next++; |
b8b4301e PC |
562 | } |
563 | } | |
564 | ||
565 | void | |
566 | merge(forward_list&& __list) | |
567 | { | |
568 | if (this != &__list) | |
569 | { | |
570 | __glibcxx_check_sorted(_Base::begin(), _Base::end()); | |
571 | __glibcxx_check_sorted(__list._M_base().begin(), | |
572 | __list._M_base().end()); | |
afe96d41 | 573 | this->_M_transfer_from_if(__list, [&__list](_Base_const_iterator __it) |
b8b4301e | 574 | { |
afe96d41 FD |
575 | return __it != __list._M_base().cbefore_begin() |
576 | && __it != __list._M_base().cend(); | |
577 | }); | |
b8b4301e PC |
578 | _Base::merge(std::move(__list._M_base())); |
579 | } | |
580 | } | |
581 | ||
78263296 PC |
582 | void |
583 | merge(forward_list& __list) | |
584 | { merge(std::move(__list)); } | |
585 | ||
b8b4301e PC |
586 | template<typename _Comp> |
587 | void | |
588 | merge(forward_list&& __list, _Comp __comp) | |
589 | { | |
590 | if (this != &__list) | |
591 | { | |
592 | __glibcxx_check_sorted_pred(_Base::begin(), _Base::end(), __comp); | |
593 | __glibcxx_check_sorted_pred(__list._M_base().begin(), | |
594 | __list._M_base().end(), __comp); | |
afe96d41 FD |
595 | this->_M_transfer_from_if(__list, |
596 | [&__list](_Base_const_iterator __it) | |
b8b4301e | 597 | { |
afe96d41 FD |
598 | return __it != __list._M_base().cbefore_begin() |
599 | && __it != __list._M_base().cend(); | |
600 | }); | |
b8b4301e PC |
601 | _Base::merge(std::move(__list._M_base()), __comp); |
602 | } | |
603 | } | |
604 | ||
78263296 PC |
605 | template<typename _Comp> |
606 | void | |
607 | merge(forward_list& __list, _Comp __comp) | |
608 | { merge(std::move(__list), __comp); } | |
609 | ||
b8b4301e PC |
610 | using _Base::sort; |
611 | using _Base::reverse; | |
612 | ||
613 | _Base& | |
d3677132 | 614 | _M_base() noexcept { return *this; } |
b8b4301e PC |
615 | |
616 | const _Base& | |
d3677132 | 617 | _M_base() const noexcept { return *this; } |
b8b4301e PC |
618 | |
619 | private: | |
620 | void | |
621 | _M_invalidate_all() | |
622 | { | |
afe96d41 FD |
623 | this->_M_invalidate_if([this](_Base_const_iterator __it) |
624 | { | |
625 | return __it != this->_M_base().cbefore_begin() | |
626 | && __it != this->_M_base().cend(); | |
627 | }); | |
b8b4301e | 628 | } |
8c9f4dfa FD |
629 | typedef __gnu_debug::_Safe_iterator_base _Safe_iterator_base; |
630 | static void | |
631 | _M_swap_aux(forward_list& __lhs, | |
632 | _Safe_iterator_base*& __lhs_iterators, | |
633 | forward_list& __rhs, | |
634 | _Safe_iterator_base*& __rhs_iterators); | |
635 | void _M_swap(forward_list& __list); | |
b8b4301e PC |
636 | }; |
637 | ||
8c9f4dfa FD |
638 | template<typename _Tp, typename _Alloc> |
639 | void | |
640 | forward_list<_Tp, _Alloc>:: | |
641 | _M_swap_aux(forward_list<_Tp, _Alloc>& __lhs, | |
642 | __gnu_debug::_Safe_iterator_base*& __lhs_iterators, | |
643 | forward_list<_Tp, _Alloc>& __rhs, | |
644 | __gnu_debug::_Safe_iterator_base*& __rhs_iterators) | |
645 | { | |
646 | using __gnu_debug::_Safe_iterator_base; | |
647 | _Safe_iterator_base* __bbegin_its = 0; | |
648 | _Safe_iterator_base* __last_bbegin = 0; | |
649 | for (_Safe_iterator_base* __iter = __lhs_iterators; __iter;) | |
650 | { | |
651 | // Even iterator are casted to const_iterator, not a problem. | |
652 | const_iterator* __victim = static_cast<const_iterator*>(__iter); | |
653 | __iter = __iter->_M_next; | |
654 | if (__victim->base() == __rhs._M_base().cbefore_begin()) | |
655 | { | |
656 | __victim->_M_unlink(); | |
657 | if (__lhs_iterators == __victim) | |
658 | __lhs_iterators = __victim->_M_next; | |
659 | if (__bbegin_its) | |
660 | { | |
661 | __victim->_M_next = __bbegin_its; | |
662 | __bbegin_its->_M_prior = __victim; | |
663 | } | |
664 | else | |
665 | __last_bbegin = __victim; | |
666 | __bbegin_its = __victim; | |
667 | } | |
668 | else | |
669 | __victim->_M_sequence = &__lhs; | |
670 | } | |
671 | ||
672 | if (__bbegin_its) | |
673 | { | |
674 | if (__rhs_iterators) | |
675 | { | |
676 | __rhs_iterators->_M_prior = __last_bbegin; | |
677 | __last_bbegin->_M_next = __rhs_iterators; | |
678 | } | |
679 | __rhs_iterators = __bbegin_its; | |
680 | } | |
681 | } | |
682 | ||
683 | /* Special forward_list _M_swap version that do not swap the | |
684 | * before-begin ownership.*/ | |
685 | template<typename _Tp, typename _Alloc> | |
686 | void | |
687 | forward_list<_Tp, _Alloc>:: | |
688 | _M_swap(forward_list<_Tp, _Alloc>& __list) | |
689 | { | |
690 | __gnu_cxx::__scoped_lock sentry(this->_M_get_mutex()); | |
691 | std::swap(this->_M_iterators, __list._M_iterators); | |
692 | std::swap(this->_M_const_iterators, __list._M_const_iterators); | |
693 | // Useless, always 1 on forward_list | |
694 | //std::swap(this->_M_version, __list._M_version); | |
695 | _Safe_iterator_base* __this_its = this->_M_iterators; | |
696 | _M_swap_aux(__list, __list._M_iterators, *this, this->_M_iterators); | |
697 | _Safe_iterator_base* __this_const_its = this->_M_const_iterators; | |
d3677132 PC |
698 | _M_swap_aux(__list, __list._M_const_iterators, *this, |
699 | this->_M_const_iterators); | |
8c9f4dfa FD |
700 | _M_swap_aux(*this, __this_its, __list, __list._M_iterators); |
701 | _M_swap_aux(*this, __this_const_its, __list, __list._M_const_iterators); | |
702 | } | |
703 | ||
b8b4301e PC |
704 | template<typename _Tp, typename _Alloc> |
705 | bool | |
706 | operator==(const forward_list<_Tp, _Alloc>& __lx, | |
707 | const forward_list<_Tp, _Alloc>& __ly) | |
708 | { return __lx._M_base() == __ly._M_base(); } | |
709 | ||
710 | template<typename _Tp, typename _Alloc> | |
711 | inline bool | |
712 | operator<(const forward_list<_Tp, _Alloc>& __lx, | |
713 | const forward_list<_Tp, _Alloc>& __ly) | |
714 | { return __lx._M_base() < __ly._M_base(); } | |
715 | ||
716 | template<typename _Tp, typename _Alloc> | |
717 | inline bool | |
718 | operator!=(const forward_list<_Tp, _Alloc>& __lx, | |
719 | const forward_list<_Tp, _Alloc>& __ly) | |
720 | { return !(__lx == __ly); } | |
721 | ||
722 | /// Based on operator< | |
723 | template<typename _Tp, typename _Alloc> | |
724 | inline bool | |
725 | operator>(const forward_list<_Tp, _Alloc>& __lx, | |
726 | const forward_list<_Tp, _Alloc>& __ly) | |
727 | { return (__ly < __lx); } | |
728 | ||
729 | /// Based on operator< | |
730 | template<typename _Tp, typename _Alloc> | |
731 | inline bool | |
732 | operator>=(const forward_list<_Tp, _Alloc>& __lx, | |
733 | const forward_list<_Tp, _Alloc>& __ly) | |
734 | { return !(__lx < __ly); } | |
735 | ||
736 | /// Based on operator< | |
737 | template<typename _Tp, typename _Alloc> | |
738 | inline bool | |
739 | operator<=(const forward_list<_Tp, _Alloc>& __lx, | |
740 | const forward_list<_Tp, _Alloc>& __ly) | |
741 | { return !(__ly < __lx); } | |
742 | ||
743 | /// See std::forward_list::swap(). | |
744 | template<typename _Tp, typename _Alloc> | |
745 | inline void | |
746 | swap(forward_list<_Tp, _Alloc>& __lx, | |
747 | forward_list<_Tp, _Alloc>& __ly) | |
748 | { __lx.swap(__ly); } | |
749 | ||
750 | } // namespace __debug | |
751 | } // namespace std | |
752 | ||
753 | namespace __gnu_debug | |
754 | { | |
755 | template<class _Tp, class _Alloc> | |
756 | struct _BeforeBeginHelper<std::__debug::forward_list<_Tp, _Alloc> > | |
757 | { | |
afe96d41 FD |
758 | typedef std::__debug::forward_list<_Tp, _Alloc> _Sequence; |
759 | typedef typename _Sequence::const_iterator _It; | |
760 | typedef typename _It::iterator_type _BaseIt; | |
b8b4301e PC |
761 | |
762 | static bool | |
079c74f3 | 763 | _S_Is(_BaseIt __it, const _Sequence* __seq) |
afe96d41 | 764 | { return __it == __seq->_M_base().cbefore_begin(); } |
079c74f3 PC |
765 | |
766 | static bool | |
767 | _S_Is_Beginnest(_BaseIt __it, const _Sequence* __seq) | |
768 | { return _S_Is(__it, __seq); } | |
b8b4301e PC |
769 | }; |
770 | } | |
771 | ||
772 | #endif |