1 | // List implementation (out of line) -*- C++ -*- |
2 | |
3 | // Copyright (C) 2001-2014 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 | /* |
26 | * |
27 | * Copyright (c) 1994 |
28 | * Hewlett-Packard Company |
29 | * |
30 | * Permission to use, copy, modify, distribute and sell this software |
31 | * and its documentation for any purpose is hereby granted without fee, |
32 | * provided that the above copyright notice appear in all copies and |
33 | * that both that copyright notice and this permission notice appear |
34 | * in supporting documentation. Hewlett-Packard Company makes no |
35 | * representations about the suitability of this software for any |
36 | * purpose. It is provided "as is" without express or implied warranty. |
37 | * |
38 | * |
39 | * Copyright (c) 1996,1997 |
40 | * Silicon Graphics Computer Systems, Inc. |
41 | * |
42 | * Permission to use, copy, modify, distribute and sell this software |
43 | * and its documentation for any purpose is hereby granted without fee, |
44 | * provided that the above copyright notice appear in all copies and |
45 | * that both that copyright notice and this permission notice appear |
46 | * in supporting documentation. Silicon Graphics makes no |
47 | * representations about the suitability of this software for any |
48 | * purpose. It is provided "as is" without express or implied warranty. |
49 | */ |
50 | |
51 | /** @file bits/list.tcc |
52 | * This is an internal header file, included by other library headers. |
53 | * Do not attempt to use it directly. @headername{list} |
54 | */ |
55 | |
56 | #ifndef _LIST_TCC |
57 | #define _LIST_TCC 1 |
58 | |
59 | namespace std _GLIBCXX_VISIBILITY(default) |
60 | { |
61 | _GLIBCXX_BEGIN_NAMESPACE_CONTAINER |
62 | |
63 | template<typename _Tp, typename _Alloc> |
64 | void |
65 | _List_base<_Tp, _Alloc>:: |
66 | _M_clear() _GLIBCXX_NOEXCEPT |
67 | { |
68 | typedef _List_node<_Tp> _Node; |
69 | _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next); |
70 | while (__cur != &_M_impl._M_node) |
71 | { |
72 | _Node* __tmp = __cur; |
73 | __cur = static_cast<_Node*>(__cur->_M_next); |
74 | #if __cplusplus >= 201103L |
75 | _M_get_Node_allocator().destroy(__tmp); |
76 | #else |
77 | _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data)); |
78 | #endif |
79 | _M_put_node(__tmp); |
80 | } |
81 | } |
82 | |
83 | #if __cplusplus >= 201103L |
84 | template<typename _Tp, typename _Alloc> |
85 | template<typename... _Args> |
86 | typename list<_Tp, _Alloc>::iterator |
87 | list<_Tp, _Alloc>:: |
88 | emplace(const_iterator __position, _Args&&... __args) |
89 | { |
90 | _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...); |
91 | __tmp->_M_hook(__position._M_const_cast()._M_node); |
92 | return iterator(__tmp); |
93 | } |
94 | #endif |
95 | |
96 | template<typename _Tp, typename _Alloc> |
97 | typename list<_Tp, _Alloc>::iterator |
98 | list<_Tp, _Alloc>:: |
99 | #if __cplusplus >= 201103L |
100 | insert(const_iterator __position, const value_type& __x) |
101 | #else |
102 | insert(iterator __position, const value_type& __x) |
103 | #endif |
104 | { |
105 | _Node* __tmp = _M_create_node(__x); |
106 | __tmp->_M_hook(__position._M_const_cast()._M_node); |
107 | return iterator(__tmp); |
108 | } |
109 | |
110 | #if __cplusplus >= 201103L |
111 | template<typename _Tp, typename _Alloc> |
112 | typename list<_Tp, _Alloc>::iterator |
113 | list<_Tp, _Alloc>:: |
114 | insert(const_iterator __position, size_type __n, const value_type& __x) |
115 | { |
116 | if (__n) |
117 | { |
118 | list __tmp(__n, __x, get_allocator()); |
119 | iterator __it = __tmp.begin(); |
120 | splice(__position, __tmp); |
121 | return __it; |
122 | } |
123 | return __position._M_const_cast(); |
124 | } |
125 | |
126 | template<typename _Tp, typename _Alloc> |
127 | template<typename _InputIterator, typename> |
128 | typename list<_Tp, _Alloc>::iterator |
129 | list<_Tp, _Alloc>:: |
130 | insert(const_iterator __position, _InputIterator __first, |
131 | _InputIterator __last) |
132 | { |
133 | list __tmp(__first, __last, get_allocator()); |
134 | if (!__tmp.empty()) |
135 | { |
136 | iterator __it = __tmp.begin(); |
137 | splice(__position, __tmp); |
138 | return __it; |
139 | } |
140 | return __position._M_const_cast(); |
141 | } |
142 | #endif |
143 | |
144 | template<typename _Tp, typename _Alloc> |
145 | typename list<_Tp, _Alloc>::iterator |
146 | list<_Tp, _Alloc>:: |
147 | #if __cplusplus >= 201103L |
148 | erase(const_iterator __position) noexcept |
149 | #else |
150 | erase(iterator __position) |
151 | #endif |
152 | { |
153 | iterator __ret = iterator(__position._M_node->_M_next); |
154 | _M_erase(__position._M_const_cast()); |
155 | return __ret; |
156 | } |
157 | |
158 | #if __cplusplus >= 201103L |
159 | template<typename _Tp, typename _Alloc> |
160 | void |
161 | list<_Tp, _Alloc>:: |
162 | _M_default_append(size_type __n) |
163 | { |
164 | size_type __i = 0; |
165 | __try |
166 | { |
167 | for (; __i < __n; ++__i) |
168 | emplace_back(); |
169 | } |
170 | __catch(...) |
171 | { |
172 | for (; __i; --__i) |
173 | pop_back(); |
174 | __throw_exception_again; |
175 | } |
176 | } |
177 | |
178 | template<typename _Tp, typename _Alloc> |
179 | void |
180 | list<_Tp, _Alloc>:: |
181 | resize(size_type __new_size) |
182 | { |
183 | iterator __i = begin(); |
184 | size_type __len = 0; |
185 | for (; __i != end() && __len < __new_size; ++__i, ++__len) |
186 | ; |
187 | if (__len == __new_size) |
188 | erase(__i, end()); |
189 | else // __i == end() |
190 | _M_default_append(__new_size - __len); |
191 | } |
192 | |
193 | template<typename _Tp, typename _Alloc> |
194 | void |
195 | list<_Tp, _Alloc>:: |
196 | resize(size_type __new_size, const value_type& __x) |
197 | { |
198 | iterator __i = begin(); |
199 | size_type __len = 0; |
200 | for (; __i != end() && __len < __new_size; ++__i, ++__len) |
201 | ; |
202 | if (__len == __new_size) |
203 | erase(__i, end()); |
204 | else // __i == end() |
205 | insert(end(), __new_size - __len, __x); |
206 | } |
207 | #else |
208 | template<typename _Tp, typename _Alloc> |
209 | void |
210 | list<_Tp, _Alloc>:: |
211 | resize(size_type __new_size, value_type __x) |
212 | { |
213 | iterator __i = begin(); |
214 | size_type __len = 0; |
215 | for (; __i != end() && __len < __new_size; ++__i, ++__len) |
216 | ; |
217 | if (__len == __new_size) |
218 | erase(__i, end()); |
219 | else // __i == end() |
220 | insert(end(), __new_size - __len, __x); |
221 | } |
222 | #endif |
223 | |
224 | template<typename _Tp, typename _Alloc> |
225 | list<_Tp, _Alloc>& |
226 | list<_Tp, _Alloc>:: |
227 | operator=(const list& __x) |
228 | { |
229 | if (this != &__x) |
230 | { |
231 | iterator __first1 = begin(); |
232 | iterator __last1 = end(); |
233 | const_iterator __first2 = __x.begin(); |
234 | const_iterator __last2 = __x.end(); |
235 | for (; __first1 != __last1 && __first2 != __last2; |
236 | ++__first1, ++__first2) |
237 | *__first1 = *__first2; |
238 | if (__first2 == __last2) |
239 | erase(__first1, __last1); |
240 | else |
241 | insert(__last1, __first2, __last2); |
242 | } |
243 | return *this; |
244 | } |
245 | |
246 | template<typename _Tp, typename _Alloc> |
247 | void |
248 | list<_Tp, _Alloc>:: |
249 | _M_fill_assign(size_type __n, const value_type& __val) |
250 | { |
251 | iterator __i = begin(); |
252 | for (; __i != end() && __n > 0; ++__i, --__n) |
253 | *__i = __val; |
254 | if (__n > 0) |
255 | insert(end(), __n, __val); |
256 | else |
257 | erase(__i, end()); |
258 | } |
259 | |
260 | template<typename _Tp, typename _Alloc> |
261 | template <typename _InputIterator> |
262 | void |
263 | list<_Tp, _Alloc>:: |
264 | _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, |
265 | __false_type) |
266 | { |
267 | iterator __first1 = begin(); |
268 | iterator __last1 = end(); |
269 | for (; __first1 != __last1 && __first2 != __last2; |
270 | ++__first1, ++__first2) |
271 | *__first1 = *__first2; |
272 | if (__first2 == __last2) |
273 | erase(__first1, __last1); |
274 | else |
275 | insert(__last1, __first2, __last2); |
276 | } |
277 | |
278 | template<typename _Tp, typename _Alloc> |
279 | void |
280 | list<_Tp, _Alloc>:: |
281 | remove(const value_type& __value) |
282 | { |
283 | iterator __first = begin(); |
284 | iterator __last = end(); |
285 | iterator = __last; |
286 | while (__first != __last) |
287 | { |
288 | iterator __next = __first; |
289 | ++__next; |
290 | if (*__first == __value) |
291 | { |
292 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
293 | // 526. Is it undefined if a function in the standard changes |
294 | // in parameters? |
295 | if (std::__addressof(*__first) != std::__addressof(__value)) |
296 | _M_erase(__first); |
297 | else |
298 | __extra = __first; |
299 | } |
300 | __first = __next; |
301 | } |
302 | if (__extra != __last) |
303 | _M_erase(__extra); |
304 | } |
305 | |
306 | template<typename _Tp, typename _Alloc> |
307 | void |
308 | list<_Tp, _Alloc>:: |
309 | unique() |
310 | { |
311 | iterator __first = begin(); |
312 | iterator __last = end(); |
313 | if (__first == __last) |
314 | return; |
315 | iterator __next = __first; |
316 | while (++__next != __last) |
317 | { |
318 | if (*__first == *__next) |
319 | _M_erase(__next); |
320 | else |
321 | __first = __next; |
322 | __next = __first; |
323 | } |
324 | } |
325 | |
326 | template<typename _Tp, typename _Alloc> |
327 | void |
328 | list<_Tp, _Alloc>:: |
329 | #if __cplusplus >= 201103L |
330 | merge(list&& __x) |
331 | #else |
332 | merge(list& __x) |
333 | #endif |
334 | { |
335 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
336 | // 300. list::merge() specification incomplete |
337 | if (this != &__x) |
338 | { |
339 | _M_check_equal_allocators(__x); |
340 | |
341 | iterator __first1 = begin(); |
342 | iterator __last1 = end(); |
343 | iterator __first2 = __x.begin(); |
344 | iterator __last2 = __x.end(); |
345 | while (__first1 != __last1 && __first2 != __last2) |
346 | if (*__first2 < *__first1) |
347 | { |
348 | iterator __next = __first2; |
349 | _M_transfer(__first1, __first2, ++__next); |
350 | __first2 = __next; |
351 | } |
352 | else |
353 | ++__first1; |
354 | if (__first2 != __last2) |
355 | _M_transfer(__last1, __first2, __last2); |
356 | } |
357 | } |
358 | |
359 | template<typename _Tp, typename _Alloc> |
360 | template <typename _StrictWeakOrdering> |
361 | void |
362 | list<_Tp, _Alloc>:: |
363 | #if __cplusplus >= 201103L |
364 | merge(list&& __x, _StrictWeakOrdering __comp) |
365 | #else |
366 | merge(list& __x, _StrictWeakOrdering __comp) |
367 | #endif |
368 | { |
369 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
370 | // 300. list::merge() specification incomplete |
371 | if (this != &__x) |
372 | { |
373 | _M_check_equal_allocators(__x); |
374 | |
375 | iterator __first1 = begin(); |
376 | iterator __last1 = end(); |
377 | iterator __first2 = __x.begin(); |
378 | iterator __last2 = __x.end(); |
379 | while (__first1 != __last1 && __first2 != __last2) |
380 | if (__comp(*__first2, *__first1)) |
381 | { |
382 | iterator __next = __first2; |
383 | _M_transfer(__first1, __first2, ++__next); |
384 | __first2 = __next; |
385 | } |
386 | else |
387 | ++__first1; |
388 | if (__first2 != __last2) |
389 | _M_transfer(__last1, __first2, __last2); |
390 | } |
391 | } |
392 | |
393 | template<typename _Tp, typename _Alloc> |
394 | void |
395 | list<_Tp, _Alloc>:: |
396 | sort() |
397 | { |
398 | // Do nothing if the list has length 0 or 1. |
399 | if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node |
400 | && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) |
401 | { |
402 | list __carry; |
403 | list __tmp[64]; |
404 | list * __fill = &__tmp[0]; |
405 | list * __counter; |
406 | |
407 | do |
408 | { |
409 | __carry.splice(__carry.begin(), *this, begin()); |
410 | |
411 | for(__counter = &__tmp[0]; |
412 | __counter != __fill && !__counter->empty(); |
413 | ++__counter) |
414 | { |
415 | __counter->merge(__carry); |
416 | __carry.swap(*__counter); |
417 | } |
418 | __carry.swap(*__counter); |
419 | if (__counter == __fill) |
420 | ++__fill; |
421 | } |
422 | while ( !empty() ); |
423 | |
424 | for (__counter = &__tmp[1]; __counter != __fill; ++__counter) |
425 | __counter->merge(*(__counter - 1)); |
426 | swap( *(__fill - 1) ); |
427 | } |
428 | } |
429 | |
430 | template<typename _Tp, typename _Alloc> |
431 | template <typename _Predicate> |
432 | void |
433 | list<_Tp, _Alloc>:: |
434 | remove_if(_Predicate __pred) |
435 | { |
436 | iterator __first = begin(); |
437 | iterator __last = end(); |
438 | while (__first != __last) |
439 | { |
440 | iterator __next = __first; |
441 | ++__next; |
442 | if (__pred(*__first)) |
443 | _M_erase(__first); |
444 | __first = __next; |
445 | } |
446 | } |
447 | |
448 | template<typename _Tp, typename _Alloc> |
449 | template <typename _BinaryPredicate> |
450 | void |
451 | list<_Tp, _Alloc>:: |
452 | unique(_BinaryPredicate __binary_pred) |
453 | { |
454 | iterator __first = begin(); |
455 | iterator __last = end(); |
456 | if (__first == __last) |
457 | return; |
458 | iterator __next = __first; |
459 | while (++__next != __last) |
460 | { |
461 | if (__binary_pred(*__first, *__next)) |
462 | _M_erase(__next); |
463 | else |
464 | __first = __next; |
465 | __next = __first; |
466 | } |
467 | } |
468 | |
469 | template<typename _Tp, typename _Alloc> |
470 | template <typename _StrictWeakOrdering> |
471 | void |
472 | list<_Tp, _Alloc>:: |
473 | sort(_StrictWeakOrdering __comp) |
474 | { |
475 | // Do nothing if the list has length 0 or 1. |
476 | if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node |
477 | && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) |
478 | { |
479 | list __carry; |
480 | list __tmp[64]; |
481 | list * __fill = &__tmp[0]; |
482 | list * __counter; |
483 | |
484 | do |
485 | { |
486 | __carry.splice(__carry.begin(), *this, begin()); |
487 | |
488 | for(__counter = &__tmp[0]; |
489 | __counter != __fill && !__counter->empty(); |
490 | ++__counter) |
491 | { |
492 | __counter->merge(__carry, __comp); |
493 | __carry.swap(*__counter); |
494 | } |
495 | __carry.swap(*__counter); |
496 | if (__counter == __fill) |
497 | ++__fill; |
498 | } |
499 | while ( !empty() ); |
500 | |
501 | for (__counter = &__tmp[1]; __counter != __fill; ++__counter) |
502 | __counter->merge(*(__counter - 1), __comp); |
503 | swap(*(__fill - 1)); |
504 | } |
505 | } |
506 | |
507 | _GLIBCXX_END_NAMESPACE_CONTAINER |
508 | } // namespace std |
509 | |
510 | #endif /* _LIST_TCC */ |
511 | |
512 | |