Line data Source code
1 : // List implementation (out of line) -*- C++ -*-
2 :
3 : // Copyright (C) 2001-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 : /*
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 748 : _List_base<_Tp, _Alloc>::
66 : _M_clear()
67 : {
68 : typedef _List_node<_Tp> _Node;
69 748 : _Node* __cur = static_cast<_Node*>(_M_impl._M_node._M_next);
70 11588 : while (__cur != &_M_impl._M_node)
71 : {
72 10092 : _Node* __tmp = __cur;
73 10092 : __cur = static_cast<_Node*>(__cur->_M_next);
74 : #if __cplusplus >= 201103L
75 10092 : _M_get_Node_allocator().destroy(__tmp);
76 : #else
77 : _M_get_Tp_allocator().destroy(std::__addressof(__tmp->_M_data));
78 : #endif
79 10092 : _M_put_node(__tmp);
80 : }
81 748 : }
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(iterator __position, _Args&&... __args)
89 : {
90 : _Node* __tmp = _M_create_node(std::forward<_Args>(__args)...);
91 : __tmp->_M_hook(__position._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 : insert(iterator __position, const value_type& __x)
100 : {
101 : _Node* __tmp = _M_create_node(__x);
102 : __tmp->_M_hook(__position._M_node);
103 : return iterator(__tmp);
104 : }
105 :
106 : template<typename _Tp, typename _Alloc>
107 : typename list<_Tp, _Alloc>::iterator
108 270953 : list<_Tp, _Alloc>::
109 : erase(iterator __position)
110 : {
111 270953 : iterator __ret = iterator(__position._M_node->_M_next);
112 270990 : _M_erase(__position);
113 271000 : return __ret;
114 : }
115 :
116 : #if __cplusplus >= 201103L
117 : template<typename _Tp, typename _Alloc>
118 : void
119 : list<_Tp, _Alloc>::
120 : _M_default_append(size_type __n)
121 : {
122 : size_type __i = 0;
123 : __try
124 : {
125 : for (; __i < __n; ++__i)
126 : emplace_back();
127 : }
128 : __catch(...)
129 : {
130 : for (; __i; --__i)
131 : pop_back();
132 : __throw_exception_again;
133 : }
134 : }
135 :
136 : template<typename _Tp, typename _Alloc>
137 : void
138 : list<_Tp, _Alloc>::
139 : resize(size_type __new_size)
140 : {
141 : iterator __i = begin();
142 : size_type __len = 0;
143 : for (; __i != end() && __len < __new_size; ++__i, ++__len)
144 : ;
145 : if (__len == __new_size)
146 : erase(__i, end());
147 : else // __i == end()
148 : _M_default_append(__new_size - __len);
149 : }
150 :
151 : template<typename _Tp, typename _Alloc>
152 : void
153 : list<_Tp, _Alloc>::
154 : resize(size_type __new_size, const value_type& __x)
155 : {
156 : iterator __i = begin();
157 : size_type __len = 0;
158 : for (; __i != end() && __len < __new_size; ++__i, ++__len)
159 : ;
160 : if (__len == __new_size)
161 : erase(__i, end());
162 : else // __i == end()
163 : insert(end(), __new_size - __len, __x);
164 : }
165 : #else
166 : template<typename _Tp, typename _Alloc>
167 : void
168 : list<_Tp, _Alloc>::
169 : resize(size_type __new_size, value_type __x)
170 : {
171 : iterator __i = begin();
172 : size_type __len = 0;
173 : for (; __i != end() && __len < __new_size; ++__i, ++__len)
174 : ;
175 : if (__len == __new_size)
176 : erase(__i, end());
177 : else // __i == end()
178 : insert(end(), __new_size - __len, __x);
179 : }
180 : #endif
181 :
182 : template<typename _Tp, typename _Alloc>
183 : list<_Tp, _Alloc>&
184 : list<_Tp, _Alloc>::
185 : operator=(const list& __x)
186 : {
187 : if (this != &__x)
188 : {
189 : iterator __first1 = begin();
190 : iterator __last1 = end();
191 : const_iterator __first2 = __x.begin();
192 : const_iterator __last2 = __x.end();
193 : for (; __first1 != __last1 && __first2 != __last2;
194 : ++__first1, ++__first2)
195 : *__first1 = *__first2;
196 : if (__first2 == __last2)
197 : erase(__first1, __last1);
198 : else
199 : insert(__last1, __first2, __last2);
200 : }
201 : return *this;
202 : }
203 :
204 : template<typename _Tp, typename _Alloc>
205 : void
206 : list<_Tp, _Alloc>::
207 : _M_fill_assign(size_type __n, const value_type& __val)
208 : {
209 : iterator __i = begin();
210 : for (; __i != end() && __n > 0; ++__i, --__n)
211 : *__i = __val;
212 : if (__n > 0)
213 : insert(end(), __n, __val);
214 : else
215 : erase(__i, end());
216 : }
217 :
218 : template<typename _Tp, typename _Alloc>
219 : template <typename _InputIterator>
220 : void
221 : list<_Tp, _Alloc>::
222 : _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
223 : __false_type)
224 : {
225 : iterator __first1 = begin();
226 : iterator __last1 = end();
227 : for (; __first1 != __last1 && __first2 != __last2;
228 : ++__first1, ++__first2)
229 : *__first1 = *__first2;
230 : if (__first2 == __last2)
231 : erase(__first1, __last1);
232 : else
233 : insert(__last1, __first2, __last2);
234 : }
235 :
236 : template<typename _Tp, typename _Alloc>
237 : void
238 : list<_Tp, _Alloc>::
239 : remove(const value_type& __value)
240 : {
241 : iterator __first = begin();
242 : iterator __last = end();
243 : iterator __extra = __last;
244 : while (__first != __last)
245 : {
246 : iterator __next = __first;
247 : ++__next;
248 : if (*__first == __value)
249 : {
250 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
251 : // 526. Is it undefined if a function in the standard changes
252 : // in parameters?
253 : if (std::__addressof(*__first) != std::__addressof(__value))
254 : _M_erase(__first);
255 : else
256 : __extra = __first;
257 : }
258 : __first = __next;
259 : }
260 : if (__extra != __last)
261 : _M_erase(__extra);
262 : }
263 :
264 : template<typename _Tp, typename _Alloc>
265 : void
266 : list<_Tp, _Alloc>::
267 : unique()
268 : {
269 : iterator __first = begin();
270 : iterator __last = end();
271 : if (__first == __last)
272 : return;
273 : iterator __next = __first;
274 : while (++__next != __last)
275 : {
276 : if (*__first == *__next)
277 : _M_erase(__next);
278 : else
279 : __first = __next;
280 : __next = __first;
281 : }
282 : }
283 :
284 : template<typename _Tp, typename _Alloc>
285 : void
286 : list<_Tp, _Alloc>::
287 : #if __cplusplus >= 201103L
288 : merge(list&& __x)
289 : #else
290 : merge(list& __x)
291 : #endif
292 : {
293 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
294 : // 300. list::merge() specification incomplete
295 : if (this != &__x)
296 : {
297 : _M_check_equal_allocators(__x);
298 :
299 : iterator __first1 = begin();
300 : iterator __last1 = end();
301 : iterator __first2 = __x.begin();
302 : iterator __last2 = __x.end();
303 : while (__first1 != __last1 && __first2 != __last2)
304 : if (*__first2 < *__first1)
305 : {
306 : iterator __next = __first2;
307 : _M_transfer(__first1, __first2, ++__next);
308 : __first2 = __next;
309 : }
310 : else
311 : ++__first1;
312 : if (__first2 != __last2)
313 : _M_transfer(__last1, __first2, __last2);
314 : }
315 : }
316 :
317 : template<typename _Tp, typename _Alloc>
318 : template <typename _StrictWeakOrdering>
319 : void
320 : list<_Tp, _Alloc>::
321 : #if __cplusplus >= 201103L
322 : merge(list&& __x, _StrictWeakOrdering __comp)
323 : #else
324 : merge(list& __x, _StrictWeakOrdering __comp)
325 : #endif
326 : {
327 : // _GLIBCXX_RESOLVE_LIB_DEFECTS
328 : // 300. list::merge() specification incomplete
329 : if (this != &__x)
330 : {
331 : _M_check_equal_allocators(__x);
332 :
333 : iterator __first1 = begin();
334 : iterator __last1 = end();
335 : iterator __first2 = __x.begin();
336 : iterator __last2 = __x.end();
337 : while (__first1 != __last1 && __first2 != __last2)
338 : if (__comp(*__first2, *__first1))
339 : {
340 : iterator __next = __first2;
341 : _M_transfer(__first1, __first2, ++__next);
342 : __first2 = __next;
343 : }
344 : else
345 : ++__first1;
346 : if (__first2 != __last2)
347 : _M_transfer(__last1, __first2, __last2);
348 : }
349 : }
350 :
351 : template<typename _Tp, typename _Alloc>
352 : void
353 : list<_Tp, _Alloc>::
354 : sort()
355 : {
356 : // Do nothing if the list has length 0 or 1.
357 : if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
358 : && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
359 : {
360 : list __carry;
361 : list __tmp[64];
362 : list * __fill = &__tmp[0];
363 : list * __counter;
364 :
365 : do
366 : {
367 : __carry.splice(__carry.begin(), *this, begin());
368 :
369 : for(__counter = &__tmp[0];
370 : __counter != __fill && !__counter->empty();
371 : ++__counter)
372 : {
373 : __counter->merge(__carry);
374 : __carry.swap(*__counter);
375 : }
376 : __carry.swap(*__counter);
377 : if (__counter == __fill)
378 : ++__fill;
379 : }
380 : while ( !empty() );
381 :
382 : for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
383 : __counter->merge(*(__counter - 1));
384 : swap( *(__fill - 1) );
385 : }
386 : }
387 :
388 : template<typename _Tp, typename _Alloc>
389 : template <typename _Predicate>
390 : void
391 : list<_Tp, _Alloc>::
392 : remove_if(_Predicate __pred)
393 : {
394 : iterator __first = begin();
395 : iterator __last = end();
396 : while (__first != __last)
397 : {
398 : iterator __next = __first;
399 : ++__next;
400 : if (__pred(*__first))
401 : _M_erase(__first);
402 : __first = __next;
403 : }
404 : }
405 :
406 : template<typename _Tp, typename _Alloc>
407 : template <typename _BinaryPredicate>
408 : void
409 : list<_Tp, _Alloc>::
410 : unique(_BinaryPredicate __binary_pred)
411 : {
412 : iterator __first = begin();
413 : iterator __last = end();
414 : if (__first == __last)
415 : return;
416 : iterator __next = __first;
417 : while (++__next != __last)
418 : {
419 : if (__binary_pred(*__first, *__next))
420 : _M_erase(__next);
421 : else
422 : __first = __next;
423 : __next = __first;
424 : }
425 : }
426 :
427 : template<typename _Tp, typename _Alloc>
428 : template <typename _StrictWeakOrdering>
429 : void
430 : list<_Tp, _Alloc>::
431 : sort(_StrictWeakOrdering __comp)
432 : {
433 : // Do nothing if the list has length 0 or 1.
434 : if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
435 : && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
436 : {
437 : list __carry;
438 : list __tmp[64];
439 : list * __fill = &__tmp[0];
440 : list * __counter;
441 :
442 : do
443 : {
444 : __carry.splice(__carry.begin(), *this, begin());
445 :
446 : for(__counter = &__tmp[0];
447 : __counter != __fill && !__counter->empty();
448 : ++__counter)
449 : {
450 : __counter->merge(__carry, __comp);
451 : __carry.swap(*__counter);
452 : }
453 : __carry.swap(*__counter);
454 : if (__counter == __fill)
455 : ++__fill;
456 : }
457 : while ( !empty() );
458 :
459 : for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
460 : __counter->merge(*(__counter - 1), __comp);
461 : swap(*(__fill - 1));
462 : }
463 : }
464 :
465 : _GLIBCXX_END_NAMESPACE_CONTAINER
466 : } // namespace std
467 :
468 : #endif /* _LIST_TCC */
469 :
|
