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