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