]>
Commit | Line | Data |
---|---|---|
42526146 PE |
1 | // Singly-linked list implementation -*- C++ -*- |
2 | ||
a945c346 | 3 | // Copyright (C) 2001-2024 Free Software Foundation, Inc. |
42526146 PE |
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 | |
748086b7 | 8 | // Free Software Foundation; either version 3, or (at your option) |
42526146 PE |
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 | ||
748086b7 JJ |
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. | |
42526146 | 19 | |
748086b7 JJ |
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/>. | |
42526146 | 24 | |
725dc051 BK |
25 | /* |
26 | * Copyright (c) 1997 | |
27 | * Silicon Graphics Computer Systems, Inc. | |
28 | * | |
29 | * Permission to use, copy, modify, distribute and sell this software | |
30 | * and its documentation for any purpose is hereby granted without fee, | |
31 | * provided that the above copyright notice appear in all copies and | |
32 | * that both that copyright notice and this permission notice appear | |
33 | * in supporting documentation. Silicon Graphics makes no | |
34 | * representations about the suitability of this software for any | |
35 | * purpose. It is provided "as is" without express or implied warranty. | |
36 | * | |
37 | */ | |
38 | ||
ffe94f83 PE |
39 | /** @file ext/slist |
40 | * This file is a GNU extension to the Standard C++ Library (possibly | |
0aa06b18 | 41 | * containing extensions from the HP/SGI STL subset). |
725dc051 BK |
42 | */ |
43 | ||
b2acb86f BK |
44 | #ifndef _SLIST |
45 | #define _SLIST 1 | |
725dc051 | 46 | |
18f176d0 AA |
47 | #include <bits/requires_hosted.h> // std::allocator |
48 | ||
bd1a56a0 | 49 | #include <algorithm> |
1ff9402d | 50 | #include <bits/allocator.h> |
673af03a PS |
51 | #include <bits/stl_construct.h> |
52 | #include <bits/stl_uninitialized.h> | |
30a20a1e | 53 | #include <bits/concept_check.h> |
603aec67 | 54 | #include <ext/alloc_traits.h> |
725dc051 | 55 | |
12ffa228 BK |
56 | namespace __gnu_cxx _GLIBCXX_VISIBILITY(default) |
57 | { | |
58 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
3cbc7af0 | 59 | |
14ba6d00 | 60 | struct _Slist_node_base |
725dc051 | 61 | { |
14ba6d00 PC |
62 | _Slist_node_base* _M_next; |
63 | }; | |
64 | ||
65 | inline _Slist_node_base* | |
66 | __slist_make_link(_Slist_node_base* __prev_node, | |
67 | _Slist_node_base* __new_node) | |
725dc051 | 68 | { |
14ba6d00 PC |
69 | __new_node->_M_next = __prev_node->_M_next; |
70 | __prev_node->_M_next = __new_node; | |
71 | return __new_node; | |
725dc051 | 72 | } |
725dc051 | 73 | |
14ba6d00 PC |
74 | inline _Slist_node_base* |
75 | __slist_previous(_Slist_node_base* __head, | |
76 | const _Slist_node_base* __node) | |
77 | { | |
78 | while (__head && __head->_M_next != __node) | |
79 | __head = __head->_M_next; | |
80 | return __head; | |
34c87829 | 81 | } |
725dc051 | 82 | |
14ba6d00 PC |
83 | inline const _Slist_node_base* |
84 | __slist_previous(const _Slist_node_base* __head, | |
85 | const _Slist_node_base* __node) | |
725dc051 | 86 | { |
14ba6d00 PC |
87 | while (__head && __head->_M_next != __node) |
88 | __head = __head->_M_next; | |
89 | return __head; | |
725dc051 | 90 | } |
725dc051 | 91 | |
14ba6d00 PC |
92 | inline void |
93 | __slist_splice_after(_Slist_node_base* __pos, | |
94 | _Slist_node_base* __before_first, | |
95 | _Slist_node_base* __before_last) | |
96 | { | |
97 | if (__pos != __before_first && __pos != __before_last) | |
322821b9 | 98 | { |
14ba6d00 PC |
99 | _Slist_node_base* __first = __before_first->_M_next; |
100 | _Slist_node_base* __after = __pos->_M_next; | |
101 | __before_first->_M_next = __before_last->_M_next; | |
102 | __pos->_M_next = __first; | |
103 | __before_last->_M_next = __after; | |
322821b9 | 104 | } |
725dc051 | 105 | } |
fa30fe72 | 106 | |
14ba6d00 PC |
107 | inline void |
108 | __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head) | |
109 | { | |
110 | _Slist_node_base* __before_last = __slist_previous(__head, 0); | |
111 | if (__before_last != __head) | |
322821b9 | 112 | { |
14ba6d00 PC |
113 | _Slist_node_base* __after = __pos->_M_next; |
114 | __pos->_M_next = __head->_M_next; | |
115 | __head->_M_next = 0; | |
116 | __before_last->_M_next = __after; | |
322821b9 | 117 | } |
725dc051 BK |
118 | } |
119 | ||
14ba6d00 PC |
120 | inline _Slist_node_base* |
121 | __slist_reverse(_Slist_node_base* __node) | |
122 | { | |
123 | _Slist_node_base* __result = __node; | |
124 | __node = __node->_M_next; | |
125 | __result->_M_next = 0; | |
126 | while(__node) | |
127 | { | |
128 | _Slist_node_base* __next = __node->_M_next; | |
129 | __node->_M_next = __result; | |
130 | __result = __node; | |
131 | __node = __next; | |
132 | } | |
133 | return __result; | |
fa30fe72 | 134 | } |
725dc051 | 135 | |
3263fb9c | 136 | inline std::size_t |
14ba6d00 PC |
137 | __slist_size(_Slist_node_base* __node) |
138 | { | |
3263fb9c | 139 | std::size_t __result = 0; |
14ba6d00 PC |
140 | for (; __node != 0; __node = __node->_M_next) |
141 | ++__result; | |
142 | return __result; | |
725dc051 BK |
143 | } |
144 | ||
14ba6d00 PC |
145 | template <class _Tp> |
146 | struct _Slist_node : public _Slist_node_base | |
147 | { | |
148 | _Tp _M_data; | |
149 | }; | |
725dc051 | 150 | |
14ba6d00 | 151 | struct _Slist_iterator_base |
725dc051 | 152 | { |
3263fb9c JW |
153 | typedef std::size_t size_type; |
154 | typedef std::ptrdiff_t difference_type; | |
14ba6d00 PC |
155 | typedef std::forward_iterator_tag iterator_category; |
156 | ||
157 | _Slist_node_base* _M_node; | |
158 | ||
159 | _Slist_iterator_base(_Slist_node_base* __x) | |
160 | : _M_node(__x) {} | |
161 | ||
162 | void | |
163 | _M_incr() | |
164 | { _M_node = _M_node->_M_next; } | |
165 | ||
166 | bool | |
167 | operator==(const _Slist_iterator_base& __x) const | |
168 | { return _M_node == __x._M_node; } | |
169 | ||
170 | bool | |
171 | operator!=(const _Slist_iterator_base& __x) const | |
172 | { return _M_node != __x._M_node; } | |
173 | }; | |
174 | ||
175 | template <class _Tp, class _Ref, class _Ptr> | |
176 | struct _Slist_iterator : public _Slist_iterator_base | |
177 | { | |
178 | typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; | |
179 | typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; | |
180 | typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; | |
181 | ||
182 | typedef _Tp value_type; | |
183 | typedef _Ptr pointer; | |
184 | typedef _Ref reference; | |
185 | typedef _Slist_node<_Tp> _Node; | |
186 | ||
e182017e | 187 | explicit |
14ba6d00 PC |
188 | _Slist_iterator(_Node* __x) |
189 | : _Slist_iterator_base(__x) {} | |
190 | ||
191 | _Slist_iterator() | |
192 | : _Slist_iterator_base(0) {} | |
193 | ||
194 | _Slist_iterator(const iterator& __x) | |
195 | : _Slist_iterator_base(__x._M_node) {} | |
196 | ||
197 | reference | |
198 | operator*() const | |
199 | { return ((_Node*) _M_node)->_M_data; } | |
200 | ||
201 | pointer | |
202 | operator->() const | |
203 | { return &(operator*()); } | |
204 | ||
205 | _Self& | |
206 | operator++() | |
207 | { | |
208 | _M_incr(); | |
209 | return *this; | |
210 | } | |
725dc051 | 211 | |
14ba6d00 PC |
212 | _Self |
213 | operator++(int) | |
214 | { | |
215 | _Self __tmp = *this; | |
216 | _M_incr(); | |
217 | return __tmp; | |
218 | } | |
219 | }; | |
220 | ||
221 | template <class _Tp, class _Alloc> | |
222 | struct _Slist_base | |
2cae56bd | 223 | : public __alloc_traits<_Alloc>::template rebind<_Slist_node<_Tp> >::other |
14ba6d00 | 224 | { |
2cae56bd JW |
225 | typedef typename __alloc_traits<_Alloc>::template |
226 | rebind<_Slist_node<_Tp> >::other _Node_alloc; | |
14ba6d00 PC |
227 | typedef _Alloc allocator_type; |
228 | ||
229 | allocator_type | |
230 | get_allocator() const | |
231 | { return *static_cast<const _Node_alloc*>(this); } | |
232 | ||
233 | _Slist_base(const allocator_type& __a) | |
234 | : _Node_alloc(__a) | |
235 | { this->_M_head._M_next = 0; } | |
236 | ||
237 | ~_Slist_base() | |
238 | { _M_erase_after(&this->_M_head, 0); } | |
239 | ||
240 | protected: | |
241 | _Slist_node_base _M_head; | |
242 | ||
243 | _Slist_node<_Tp>* | |
244 | _M_get_node() | |
245 | { return _Node_alloc::allocate(1); } | |
246 | ||
247 | void | |
248 | _M_put_node(_Slist_node<_Tp>* __p) | |
249 | { _Node_alloc::deallocate(__p, 1); } | |
250 | ||
251 | protected: | |
252 | _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) | |
253 | { | |
254 | _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); | |
255 | _Slist_node_base* __next_next = __next->_M_next; | |
256 | __pos->_M_next = __next_next; | |
603aec67 JW |
257 | allocator_type __a = get_allocator(); |
258 | __alloc_traits<allocator_type>::destroy(__a, &__next->_M_data); | |
14ba6d00 PC |
259 | _M_put_node(__next); |
260 | return __next_next; | |
261 | } | |
262 | _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); | |
263 | }; | |
264 | ||
265 | template <class _Tp, class _Alloc> | |
266 | _Slist_node_base* | |
267 | _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, | |
268 | _Slist_node_base* __last_node) | |
269 | { | |
270 | _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); | |
271 | while (__cur != __last_node) | |
272 | { | |
273 | _Slist_node<_Tp>* __tmp = __cur; | |
274 | __cur = (_Slist_node<_Tp>*) __cur->_M_next; | |
603aec67 JW |
275 | allocator_type __a = get_allocator(); |
276 | __alloc_traits<allocator_type>::destroy(__a, &__tmp->_M_data); | |
14ba6d00 PC |
277 | _M_put_node(__tmp); |
278 | } | |
279 | __before_first->_M_next = __last_node; | |
280 | return __last_node; | |
281 | } | |
725dc051 | 282 | |
14ba6d00 PC |
283 | /** |
284 | * This is an SGI extension. | |
285 | * @ingroup SGIextensions | |
286 | * @doctodo | |
287 | */ | |
3263fb9c | 288 | template <class _Tp, class _Alloc = std::allocator<_Tp> > |
14ba6d00 PC |
289 | class slist : private _Slist_base<_Tp,_Alloc> |
290 | { | |
291 | // concept requirements | |
292 | __glibcxx_class_requires(_Tp, _SGIAssignableConcept) | |
293 | ||
294 | private: | |
295 | typedef _Slist_base<_Tp,_Alloc> _Base; | |
296 | ||
297 | public: | |
298 | typedef _Tp value_type; | |
299 | typedef value_type* pointer; | |
300 | typedef const value_type* const_pointer; | |
301 | typedef value_type& reference; | |
302 | typedef const value_type& const_reference; | |
3263fb9c JW |
303 | typedef std::size_t size_type; |
304 | typedef std::ptrdiff_t difference_type; | |
14ba6d00 PC |
305 | |
306 | typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; | |
307 | typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; | |
308 | ||
309 | typedef typename _Base::allocator_type allocator_type; | |
310 | ||
311 | allocator_type | |
312 | get_allocator() const | |
313 | { return _Base::get_allocator(); } | |
314 | ||
315 | private: | |
316 | typedef _Slist_node<_Tp> _Node; | |
317 | typedef _Slist_node_base _Node_base; | |
318 | typedef _Slist_iterator_base _Iterator_base; | |
319 | ||
320 | _Node* | |
321 | _M_create_node(const value_type& __x) | |
322 | { | |
323 | _Node* __node = this->_M_get_node(); | |
bc2631e0 | 324 | __try |
14ba6d00 | 325 | { |
603aec67 JW |
326 | allocator_type __a = get_allocator(); |
327 | __alloc_traits<allocator_type>::construct(__a, &__node->_M_data, | |
328 | __x); | |
14ba6d00 PC |
329 | __node->_M_next = 0; |
330 | } | |
bc2631e0 | 331 | __catch(...) |
14ba6d00 PC |
332 | { |
333 | this->_M_put_node(__node); | |
334 | __throw_exception_again; | |
335 | } | |
336 | return __node; | |
337 | } | |
725dc051 | 338 | |
14ba6d00 PC |
339 | _Node* |
340 | _M_create_node() | |
341 | { | |
342 | _Node* __node = this->_M_get_node(); | |
bc2631e0 | 343 | __try |
14ba6d00 | 344 | { |
603aec67 JW |
345 | allocator_type __a = get_allocator(); |
346 | __alloc_traits<allocator_type>::construct(__a, &__node->_M_data, | |
347 | value_type()); | |
14ba6d00 PC |
348 | __node->_M_next = 0; |
349 | } | |
bc2631e0 | 350 | __catch(...) |
14ba6d00 PC |
351 | { |
352 | this->_M_put_node(__node); | |
353 | __throw_exception_again; | |
354 | } | |
355 | return __node; | |
356 | } | |
725dc051 | 357 | |
14ba6d00 PC |
358 | public: |
359 | explicit | |
360 | slist(const allocator_type& __a = allocator_type()) | |
361 | : _Base(__a) {} | |
362 | ||
363 | slist(size_type __n, const value_type& __x, | |
364 | const allocator_type& __a = allocator_type()) | |
365 | : _Base(__a) | |
366 | { _M_insert_after_fill(&this->_M_head, __n, __x); } | |
367 | ||
368 | explicit | |
369 | slist(size_type __n) | |
370 | : _Base(allocator_type()) | |
371 | { _M_insert_after_fill(&this->_M_head, __n, value_type()); } | |
372 | ||
373 | // We don't need any dispatching tricks here, because | |
374 | // _M_insert_after_range already does them. | |
375 | template <class _InputIterator> | |
376 | slist(_InputIterator __first, _InputIterator __last, | |
377 | const allocator_type& __a = allocator_type()) | |
378 | : _Base(__a) | |
379 | { _M_insert_after_range(&this->_M_head, __first, __last); } | |
380 | ||
381 | slist(const slist& __x) | |
382 | : _Base(__x.get_allocator()) | |
383 | { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); } | |
384 | ||
385 | slist& | |
386 | operator= (const slist& __x); | |
387 | ||
388 | ~slist() {} | |
389 | ||
390 | public: | |
391 | // assign(), a generalized assignment member function. Two | |
392 | // versions: one that takes a count, and one that takes a range. | |
393 | // The range version is a member template, so we dispatch on whether | |
394 | // or not the type is an integer. | |
395 | ||
396 | void | |
397 | assign(size_type __n, const _Tp& __val) | |
398 | { _M_fill_assign(__n, __val); } | |
399 | ||
400 | void | |
401 | _M_fill_assign(size_type __n, const _Tp& __val); | |
402 | ||
403 | template <class _InputIterator> | |
404 | void | |
405 | assign(_InputIterator __first, _InputIterator __last) | |
406 | { | |
c0736a9d | 407 | typedef typename std::__is_integer<_InputIterator>::__type _Integral; |
14ba6d00 PC |
408 | _M_assign_dispatch(__first, __last, _Integral()); |
409 | } | |
410 | ||
411 | template <class _Integer> | |
412 | void | |
3263fb9c | 413 | _M_assign_dispatch(_Integer __n, _Integer __val, std::__true_type) |
14ba6d00 PC |
414 | { _M_fill_assign((size_type) __n, (_Tp) __val); } |
415 | ||
416 | template <class _InputIterator> | |
417 | void | |
418 | _M_assign_dispatch(_InputIterator __first, _InputIterator __last, | |
3263fb9c | 419 | std::__false_type); |
14ba6d00 PC |
420 | |
421 | public: | |
422 | ||
423 | iterator | |
424 | begin() | |
425 | { return iterator((_Node*)this->_M_head._M_next); } | |
426 | ||
427 | const_iterator | |
428 | begin() const | |
429 | { return const_iterator((_Node*)this->_M_head._M_next);} | |
430 | ||
431 | iterator | |
432 | end() | |
433 | { return iterator(0); } | |
434 | ||
435 | const_iterator | |
436 | end() const | |
437 | { return const_iterator(0); } | |
438 | ||
439 | // Experimental new feature: before_begin() returns a | |
440 | // non-dereferenceable iterator that, when incremented, yields | |
441 | // begin(). This iterator may be used as the argument to | |
442 | // insert_after, erase_after, etc. Note that even for an empty | |
443 | // slist, before_begin() is not the same iterator as end(). It | |
444 | // is always necessary to increment before_begin() at least once to | |
445 | // obtain end(). | |
446 | iterator | |
447 | before_begin() | |
448 | { return iterator((_Node*) &this->_M_head); } | |
449 | ||
450 | const_iterator | |
451 | before_begin() const | |
452 | { return const_iterator((_Node*) &this->_M_head); } | |
453 | ||
454 | size_type | |
455 | size() const | |
456 | { return __slist_size(this->_M_head._M_next); } | |
457 | ||
458 | size_type | |
459 | max_size() const | |
460 | { return size_type(-1); } | |
461 | ||
d715f554 | 462 | _GLIBCXX_NODISCARD bool |
14ba6d00 PC |
463 | empty() const |
464 | { return this->_M_head._M_next == 0; } | |
465 | ||
466 | void | |
467 | swap(slist& __x) | |
468 | { std::swap(this->_M_head._M_next, __x._M_head._M_next); } | |
469 | ||
470 | public: | |
471 | ||
472 | reference | |
473 | front() | |
474 | { return ((_Node*) this->_M_head._M_next)->_M_data; } | |
475 | ||
476 | const_reference | |
477 | front() const | |
478 | { return ((_Node*) this->_M_head._M_next)->_M_data; } | |
479 | ||
480 | void | |
481 | push_front(const value_type& __x) | |
482 | { __slist_make_link(&this->_M_head, _M_create_node(__x)); } | |
483 | ||
484 | void | |
485 | push_front() | |
486 | { __slist_make_link(&this->_M_head, _M_create_node()); } | |
487 | ||
488 | void | |
489 | pop_front() | |
490 | { | |
491 | _Node* __node = (_Node*) this->_M_head._M_next; | |
492 | this->_M_head._M_next = __node->_M_next; | |
603aec67 JW |
493 | allocator_type __a = get_allocator(); |
494 | __alloc_traits<allocator_type>::destroy(__a, &__node->_M_data); | |
14ba6d00 PC |
495 | this->_M_put_node(__node); |
496 | } | |
725dc051 | 497 | |
14ba6d00 PC |
498 | iterator |
499 | previous(const_iterator __pos) | |
500 | { return iterator((_Node*) __slist_previous(&this->_M_head, | |
501 | __pos._M_node)); } | |
725dc051 | 502 | |
14ba6d00 PC |
503 | const_iterator |
504 | previous(const_iterator __pos) const | |
505 | { return const_iterator((_Node*) __slist_previous(&this->_M_head, | |
506 | __pos._M_node)); } | |
725dc051 | 507 | |
14ba6d00 PC |
508 | private: |
509 | _Node* | |
510 | _M_insert_after(_Node_base* __pos, const value_type& __x) | |
511 | { return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); } | |
725dc051 | 512 | |
14ba6d00 PC |
513 | _Node* |
514 | _M_insert_after(_Node_base* __pos) | |
515 | { return (_Node*) (__slist_make_link(__pos, _M_create_node())); } | |
725dc051 | 516 | |
14ba6d00 PC |
517 | void |
518 | _M_insert_after_fill(_Node_base* __pos, | |
519 | size_type __n, const value_type& __x) | |
520 | { | |
521 | for (size_type __i = 0; __i < __n; ++__i) | |
522 | __pos = __slist_make_link(__pos, _M_create_node(__x)); | |
523 | } | |
725dc051 | 524 | |
14ba6d00 PC |
525 | // Check whether it's an integral type. If so, it's not an iterator. |
526 | template <class _InIterator> | |
527 | void | |
528 | _M_insert_after_range(_Node_base* __pos, | |
529 | _InIterator __first, _InIterator __last) | |
530 | { | |
c0736a9d | 531 | typedef typename std::__is_integer<_InIterator>::__type _Integral; |
14ba6d00 PC |
532 | _M_insert_after_range(__pos, __first, __last, _Integral()); |
533 | } | |
534 | ||
535 | template <class _Integer> | |
536 | void | |
537 | _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x, | |
3263fb9c | 538 | std::__true_type) |
14ba6d00 PC |
539 | { _M_insert_after_fill(__pos, __n, __x); } |
540 | ||
541 | template <class _InIterator> | |
542 | void | |
543 | _M_insert_after_range(_Node_base* __pos, | |
544 | _InIterator __first, _InIterator __last, | |
3263fb9c | 545 | std::__false_type) |
14ba6d00 PC |
546 | { |
547 | while (__first != __last) | |
548 | { | |
549 | __pos = __slist_make_link(__pos, _M_create_node(*__first)); | |
550 | ++__first; | |
551 | } | |
552 | } | |
553 | ||
554 | public: | |
555 | iterator | |
556 | insert_after(iterator __pos, const value_type& __x) | |
557 | { return iterator(_M_insert_after(__pos._M_node, __x)); } | |
558 | ||
559 | iterator | |
560 | insert_after(iterator __pos) | |
561 | { return insert_after(__pos, value_type()); } | |
562 | ||
563 | void | |
564 | insert_after(iterator __pos, size_type __n, const value_type& __x) | |
565 | { _M_insert_after_fill(__pos._M_node, __n, __x); } | |
566 | ||
567 | // We don't need any dispatching tricks here, because | |
568 | // _M_insert_after_range already does them. | |
569 | template <class _InIterator> | |
570 | void | |
571 | insert_after(iterator __pos, _InIterator __first, _InIterator __last) | |
572 | { _M_insert_after_range(__pos._M_node, __first, __last); } | |
573 | ||
574 | iterator | |
575 | insert(iterator __pos, const value_type& __x) | |
576 | { return iterator(_M_insert_after(__slist_previous(&this->_M_head, | |
577 | __pos._M_node), | |
578 | __x)); } | |
579 | ||
580 | iterator | |
581 | insert(iterator __pos) | |
582 | { return iterator(_M_insert_after(__slist_previous(&this->_M_head, | |
583 | __pos._M_node), | |
584 | value_type())); } | |
585 | ||
586 | void | |
587 | insert(iterator __pos, size_type __n, const value_type& __x) | |
588 | { _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node), | |
589 | __n, __x); } | |
590 | ||
591 | // We don't need any dispatching tricks here, because | |
592 | // _M_insert_after_range already does them. | |
593 | template <class _InIterator> | |
594 | void | |
595 | insert(iterator __pos, _InIterator __first, _InIterator __last) | |
596 | { _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), | |
597 | __first, __last); } | |
598 | ||
599 | public: | |
600 | iterator | |
601 | erase_after(iterator __pos) | |
602 | { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); } | |
603 | ||
604 | iterator | |
605 | erase_after(iterator __before_first, iterator __last) | |
e182017e PC |
606 | { |
607 | return iterator((_Node*) this->_M_erase_after(__before_first._M_node, | |
608 | __last._M_node)); | |
609 | } | |
14ba6d00 PC |
610 | |
611 | iterator | |
612 | erase(iterator __pos) | |
e182017e PC |
613 | { |
614 | return iterator((_Node*) this->_M_erase_after | |
615 | (__slist_previous(&this->_M_head, __pos._M_node))); | |
616 | } | |
14ba6d00 PC |
617 | |
618 | iterator | |
619 | erase(iterator __first, iterator __last) | |
e182017e PC |
620 | { |
621 | return iterator((_Node*) this->_M_erase_after | |
622 | (__slist_previous(&this->_M_head, __first._M_node), | |
623 | __last._M_node)); | |
624 | } | |
625 | ||
14ba6d00 PC |
626 | void |
627 | resize(size_type new_size, const _Tp& __x); | |
628 | ||
629 | void | |
630 | resize(size_type new_size) | |
631 | { resize(new_size, _Tp()); } | |
632 | ||
633 | void | |
634 | clear() | |
635 | { this->_M_erase_after(&this->_M_head, 0); } | |
636 | ||
637 | public: | |
638 | // Moves the range [__before_first + 1, __before_last + 1) to *this, | |
639 | // inserting it immediately after __pos. This is constant time. | |
640 | void | |
641 | splice_after(iterator __pos, | |
642 | iterator __before_first, iterator __before_last) | |
643 | { | |
644 | if (__before_first != __before_last) | |
645 | __slist_splice_after(__pos._M_node, __before_first._M_node, | |
646 | __before_last._M_node); | |
647 | } | |
725dc051 | 648 | |
14ba6d00 PC |
649 | // Moves the element that follows __prev to *this, inserting it |
650 | // immediately after __pos. This is constant time. | |
651 | void | |
652 | splice_after(iterator __pos, iterator __prev) | |
653 | { __slist_splice_after(__pos._M_node, | |
654 | __prev._M_node, __prev._M_node->_M_next); } | |
655 | ||
656 | // Removes all of the elements from the list __x to *this, inserting | |
657 | // them immediately after __pos. __x must not be *this. Complexity: | |
658 | // linear in __x.size(). | |
659 | void | |
660 | splice_after(iterator __pos, slist& __x) | |
661 | { __slist_splice_after(__pos._M_node, &__x._M_head); } | |
662 | ||
663 | // Linear in distance(begin(), __pos), and linear in __x.size(). | |
664 | void | |
665 | splice(iterator __pos, slist& __x) | |
666 | { | |
667 | if (__x._M_head._M_next) | |
668 | __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), | |
669 | &__x._M_head, | |
670 | __slist_previous(&__x._M_head, 0)); } | |
671 | ||
672 | // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i). | |
673 | void | |
674 | splice(iterator __pos, slist& __x, iterator __i) | |
675 | { __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), | |
676 | __slist_previous(&__x._M_head, __i._M_node), | |
677 | __i._M_node); } | |
678 | ||
679 | // Linear in distance(begin(), __pos), in distance(__x.begin(), __first), | |
680 | // and in distance(__first, __last). | |
681 | void | |
682 | splice(iterator __pos, slist& __x, iterator __first, iterator __last) | |
683 | { | |
684 | if (__first != __last) | |
685 | __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), | |
686 | __slist_previous(&__x._M_head, __first._M_node), | |
687 | __slist_previous(__first._M_node, | |
688 | __last._M_node)); | |
689 | } | |
725dc051 | 690 | |
14ba6d00 PC |
691 | public: |
692 | void | |
693 | reverse() | |
694 | { | |
695 | if (this->_M_head._M_next) | |
696 | this->_M_head._M_next = __slist_reverse(this->_M_head._M_next); | |
697 | } | |
725dc051 | 698 | |
14ba6d00 PC |
699 | void |
700 | remove(const _Tp& __val); | |
701 | ||
702 | void | |
703 | unique(); | |
704 | ||
705 | void | |
706 | merge(slist& __x); | |
707 | ||
708 | void | |
709 | sort(); | |
710 | ||
711 | template <class _Predicate> | |
712 | void | |
713 | remove_if(_Predicate __pred); | |
714 | ||
715 | template <class _BinaryPredicate> | |
716 | void | |
717 | unique(_BinaryPredicate __pred); | |
718 | ||
719 | template <class _StrictWeakOrdering> | |
720 | void | |
721 | merge(slist&, _StrictWeakOrdering); | |
722 | ||
723 | template <class _StrictWeakOrdering> | |
724 | void | |
725 | sort(_StrictWeakOrdering __comp); | |
726 | }; | |
727 | ||
728 | template <class _Tp, class _Alloc> | |
729 | slist<_Tp, _Alloc>& | |
730 | slist<_Tp, _Alloc>::operator=(const slist<_Tp, _Alloc>& __x) | |
731 | { | |
732 | if (&__x != this) | |
733 | { | |
734 | _Node_base* __p1 = &this->_M_head; | |
735 | _Node* __n1 = (_Node*) this->_M_head._M_next; | |
736 | const _Node* __n2 = (const _Node*) __x._M_head._M_next; | |
737 | while (__n1 && __n2) | |
738 | { | |
739 | __n1->_M_data = __n2->_M_data; | |
740 | __p1 = __n1; | |
741 | __n1 = (_Node*) __n1->_M_next; | |
742 | __n2 = (const _Node*) __n2->_M_next; | |
743 | } | |
744 | if (__n2 == 0) | |
745 | this->_M_erase_after(__p1, 0); | |
746 | else | |
747 | _M_insert_after_range(__p1, const_iterator((_Node*)__n2), | |
725dc051 | 748 | const_iterator(0)); |
14ba6d00 PC |
749 | } |
750 | return *this; | |
751 | } | |
725dc051 | 752 | |
14ba6d00 PC |
753 | template <class _Tp, class _Alloc> |
754 | void | |
755 | slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) | |
756 | { | |
757 | _Node_base* __prev = &this->_M_head; | |
758 | _Node* __node = (_Node*) this->_M_head._M_next; | |
759 | for (; __node != 0 && __n > 0; --__n) | |
760 | { | |
761 | __node->_M_data = __val; | |
762 | __prev = __node; | |
763 | __node = (_Node*) __node->_M_next; | |
764 | } | |
765 | if (__n > 0) | |
766 | _M_insert_after_fill(__prev, __n, __val); | |
767 | else | |
768 | this->_M_erase_after(__prev, 0); | |
769 | } | |
770 | ||
771 | template <class _Tp, class _Alloc> | |
772 | template <class _InputIterator> | |
773 | void | |
774 | slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first, | |
775 | _InputIterator __last, | |
3263fb9c | 776 | std::__false_type) |
14ba6d00 PC |
777 | { |
778 | _Node_base* __prev = &this->_M_head; | |
779 | _Node* __node = (_Node*) this->_M_head._M_next; | |
780 | while (__node != 0 && __first != __last) | |
781 | { | |
782 | __node->_M_data = *__first; | |
783 | __prev = __node; | |
784 | __node = (_Node*) __node->_M_next; | |
785 | ++__first; | |
786 | } | |
787 | if (__first != __last) | |
788 | _M_insert_after_range(__prev, __first, __last); | |
789 | else | |
790 | this->_M_erase_after(__prev, 0); | |
791 | } | |
792 | ||
793 | template <class _Tp, class _Alloc> | |
794 | inline bool | |
795 | operator==(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) | |
796 | { | |
797 | typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator; | |
798 | const_iterator __end1 = _SL1.end(); | |
799 | const_iterator __end2 = _SL2.end(); | |
800 | ||
801 | const_iterator __i1 = _SL1.begin(); | |
802 | const_iterator __i2 = _SL2.begin(); | |
803 | while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) | |
804 | { | |
805 | ++__i1; | |
806 | ++__i2; | |
807 | } | |
808 | return __i1 == __end1 && __i2 == __end2; | |
809 | } | |
725dc051 | 810 | |
725dc051 | 811 | |
14ba6d00 PC |
812 | template <class _Tp, class _Alloc> |
813 | inline bool | |
814 | operator<(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) | |
815 | { return std::lexicographical_compare(_SL1.begin(), _SL1.end(), | |
816 | _SL2.begin(), _SL2.end()); } | |
817 | ||
818 | template <class _Tp, class _Alloc> | |
819 | inline bool | |
820 | operator!=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) | |
821 | { return !(_SL1 == _SL2); } | |
822 | ||
823 | template <class _Tp, class _Alloc> | |
824 | inline bool | |
825 | operator>(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) | |
826 | { return _SL2 < _SL1; } | |
827 | ||
828 | template <class _Tp, class _Alloc> | |
829 | inline bool | |
830 | operator<=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) | |
831 | { return !(_SL2 < _SL1); } | |
832 | ||
833 | template <class _Tp, class _Alloc> | |
834 | inline bool | |
835 | operator>=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) | |
836 | { return !(_SL1 < _SL2); } | |
837 | ||
838 | template <class _Tp, class _Alloc> | |
839 | inline void | |
840 | swap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y) | |
841 | { __x.swap(__y); } | |
842 | ||
843 | template <class _Tp, class _Alloc> | |
844 | void | |
845 | slist<_Tp, _Alloc>::resize(size_type __len, const _Tp& __x) | |
846 | { | |
847 | _Node_base* __cur = &this->_M_head; | |
848 | while (__cur->_M_next != 0 && __len > 0) | |
849 | { | |
850 | --__len; | |
851 | __cur = __cur->_M_next; | |
852 | } | |
853 | if (__cur->_M_next) | |
854 | this->_M_erase_after(__cur, 0); | |
725dc051 | 855 | else |
14ba6d00 | 856 | _M_insert_after_fill(__cur, __len, __x); |
725dc051 | 857 | } |
725dc051 | 858 | |
14ba6d00 PC |
859 | template <class _Tp, class _Alloc> |
860 | void | |
861 | slist<_Tp, _Alloc>::remove(const _Tp& __val) | |
862 | { | |
863 | _Node_base* __cur = &this->_M_head; | |
864 | while (__cur && __cur->_M_next) | |
865 | { | |
866 | if (((_Node*) __cur->_M_next)->_M_data == __val) | |
867 | this->_M_erase_after(__cur); | |
868 | else | |
869 | __cur = __cur->_M_next; | |
870 | } | |
725dc051 BK |
871 | } |
872 | ||
14ba6d00 PC |
873 | template <class _Tp, class _Alloc> |
874 | void | |
875 | slist<_Tp, _Alloc>::unique() | |
876 | { | |
877 | _Node_base* __cur = this->_M_head._M_next; | |
878 | if (__cur) | |
879 | { | |
880 | while (__cur->_M_next) | |
881 | { | |
882 | if (((_Node*)__cur)->_M_data | |
883 | == ((_Node*)(__cur->_M_next))->_M_data) | |
884 | this->_M_erase_after(__cur); | |
885 | else | |
886 | __cur = __cur->_M_next; | |
887 | } | |
888 | } | |
889 | } | |
725dc051 | 890 | |
14ba6d00 PC |
891 | template <class _Tp, class _Alloc> |
892 | void | |
893 | slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x) | |
894 | { | |
895 | _Node_base* __n1 = &this->_M_head; | |
896 | while (__n1->_M_next && __x._M_head._M_next) | |
897 | { | |
898 | if (((_Node*) __x._M_head._M_next)->_M_data | |
899 | < ((_Node*) __n1->_M_next)->_M_data) | |
900 | __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); | |
901 | __n1 = __n1->_M_next; | |
902 | } | |
903 | if (__x._M_head._M_next) | |
904 | { | |
905 | __n1->_M_next = __x._M_head._M_next; | |
906 | __x._M_head._M_next = 0; | |
907 | } | |
908 | } | |
725dc051 | 909 | |
14ba6d00 PC |
910 | template <class _Tp, class _Alloc> |
911 | void | |
912 | slist<_Tp, _Alloc>::sort() | |
913 | { | |
914 | if (this->_M_head._M_next && this->_M_head._M_next->_M_next) | |
915 | { | |
916 | slist __carry; | |
917 | slist __counter[64]; | |
918 | int __fill = 0; | |
919 | while (!empty()) | |
920 | { | |
921 | __slist_splice_after(&__carry._M_head, | |
922 | &this->_M_head, this->_M_head._M_next); | |
923 | int __i = 0; | |
924 | while (__i < __fill && !__counter[__i].empty()) | |
925 | { | |
926 | __counter[__i].merge(__carry); | |
927 | __carry.swap(__counter[__i]); | |
928 | ++__i; | |
929 | } | |
930 | __carry.swap(__counter[__i]); | |
931 | if (__i == __fill) | |
932 | ++__fill; | |
933 | } | |
934 | ||
935 | for (int __i = 1; __i < __fill; ++__i) | |
936 | __counter[__i].merge(__counter[__i-1]); | |
937 | this->swap(__counter[__fill-1]); | |
938 | } | |
725dc051 | 939 | } |
725dc051 | 940 | |
14ba6d00 PC |
941 | template <class _Tp, class _Alloc> |
942 | template <class _Predicate> | |
943 | void slist<_Tp, _Alloc>::remove_if(_Predicate __pred) | |
944 | { | |
945 | _Node_base* __cur = &this->_M_head; | |
946 | while (__cur->_M_next) | |
947 | { | |
948 | if (__pred(((_Node*) __cur->_M_next)->_M_data)) | |
949 | this->_M_erase_after(__cur); | |
950 | else | |
951 | __cur = __cur->_M_next; | |
952 | } | |
953 | } | |
725dc051 | 954 | |
14ba6d00 PC |
955 | template <class _Tp, class _Alloc> |
956 | template <class _BinaryPredicate> | |
957 | void | |
958 | slist<_Tp, _Alloc>::unique(_BinaryPredicate __pred) | |
959 | { | |
960 | _Node* __cur = (_Node*) this->_M_head._M_next; | |
961 | if (__cur) | |
962 | { | |
963 | while (__cur->_M_next) | |
964 | { | |
965 | if (__pred(((_Node*)__cur)->_M_data, | |
966 | ((_Node*)(__cur->_M_next))->_M_data)) | |
967 | this->_M_erase_after(__cur); | |
968 | else | |
969 | __cur = (_Node*) __cur->_M_next; | |
970 | } | |
971 | } | |
725dc051 | 972 | } |
725dc051 | 973 | |
14ba6d00 PC |
974 | template <class _Tp, class _Alloc> |
975 | template <class _StrictWeakOrdering> | |
976 | void | |
977 | slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x, | |
978 | _StrictWeakOrdering __comp) | |
979 | { | |
980 | _Node_base* __n1 = &this->_M_head; | |
981 | while (__n1->_M_next && __x._M_head._M_next) | |
982 | { | |
983 | if (__comp(((_Node*) __x._M_head._M_next)->_M_data, | |
984 | ((_Node*) __n1->_M_next)->_M_data)) | |
985 | __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); | |
986 | __n1 = __n1->_M_next; | |
987 | } | |
988 | if (__x._M_head._M_next) | |
989 | { | |
990 | __n1->_M_next = __x._M_head._M_next; | |
991 | __x._M_head._M_next = 0; | |
992 | } | |
993 | } | |
994 | ||
995 | template <class _Tp, class _Alloc> | |
996 | template <class _StrictWeakOrdering> | |
997 | void | |
998 | slist<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp) | |
999 | { | |
1000 | if (this->_M_head._M_next && this->_M_head._M_next->_M_next) | |
1001 | { | |
1002 | slist __carry; | |
1003 | slist __counter[64]; | |
1004 | int __fill = 0; | |
1005 | while (!empty()) | |
1006 | { | |
1007 | __slist_splice_after(&__carry._M_head, | |
1008 | &this->_M_head, this->_M_head._M_next); | |
1009 | int __i = 0; | |
1010 | while (__i < __fill && !__counter[__i].empty()) | |
1011 | { | |
1012 | __counter[__i].merge(__carry, __comp); | |
1013 | __carry.swap(__counter[__i]); | |
1014 | ++__i; | |
1015 | } | |
1016 | __carry.swap(__counter[__i]); | |
1017 | if (__i == __fill) | |
1018 | ++__fill; | |
1019 | } | |
1020 | ||
1021 | for (int __i = 1; __i < __fill; ++__i) | |
1022 | __counter[__i].merge(__counter[__i-1], __comp); | |
1023 | this->swap(__counter[__fill-1]); | |
1024 | } | |
1025 | } | |
725dc051 | 1026 | |
12ffa228 BK |
1027 | _GLIBCXX_END_NAMESPACE_VERSION |
1028 | } // namespace | |
3cbc7af0 | 1029 | |
12ffa228 BK |
1030 | namespace std _GLIBCXX_VISIBILITY(default) |
1031 | { | |
1032 | _GLIBCXX_BEGIN_NAMESPACE_VERSION | |
63fea34e | 1033 | |
14ba6d00 PC |
1034 | // Specialization of insert_iterator so that insertions will be constant |
1035 | // time rather than linear time. | |
14ba6d00 PC |
1036 | template <class _Tp, class _Alloc> |
1037 | class insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> > | |
1038 | { | |
1039 | protected: | |
1040 | typedef __gnu_cxx::slist<_Tp, _Alloc> _Container; | |
1041 | _Container* container; | |
1042 | typename _Container::iterator iter; | |
1043 | ||
1044 | public: | |
1045 | typedef _Container container_type; | |
1046 | typedef output_iterator_tag iterator_category; | |
1047 | typedef void value_type; | |
1048 | typedef void difference_type; | |
1049 | typedef void pointer; | |
1050 | typedef void reference; | |
1051 | ||
1052 | insert_iterator(_Container& __x, typename _Container::iterator __i) | |
1053 | : container(&__x) | |
1054 | { | |
1055 | if (__i == __x.begin()) | |
1056 | iter = __x.before_begin(); | |
1057 | else | |
1058 | iter = __x.previous(__i); | |
1059 | } | |
725dc051 | 1060 | |
14ba6d00 PC |
1061 | insert_iterator<_Container>& |
1062 | operator=(const typename _Container::value_type& __value) | |
1063 | { | |
1064 | iter = container->insert_after(iter, __value); | |
1065 | return *this; | |
1066 | } | |
1067 | ||
1068 | insert_iterator<_Container>& | |
1069 | operator*() | |
1070 | { return *this; } | |
1071 | ||
1072 | insert_iterator<_Container>& | |
1073 | operator++() | |
1074 | { return *this; } | |
1075 | ||
1076 | insert_iterator<_Container>& | |
1077 | operator++(int) | |
1078 | { return *this; } | |
3cbc7af0 BK |
1079 | }; |
1080 | ||
12ffa228 BK |
1081 | _GLIBCXX_END_NAMESPACE_VERSION |
1082 | } // namespace | |
725dc051 | 1083 | |
fa30fe72 | 1084 | #endif |