]>
Commit | Line | Data |
---|---|---|
83144cfc PE |
1 | // List implementation (out of line) -*- C++ -*- |
2 | ||
2fecaef4 | 3 | // Copyright (C) 2001, 2002, 2003, 2004, 2005 Free Software Foundation, Inc. |
83144cfc 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 | |
83f51799 | 18 | // Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, |
83144cfc PE |
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 | ||
30 | /* | |
31 | * | |
32 | * Copyright (c) 1994 | |
33 | * Hewlett-Packard Company | |
34 | * | |
35 | * Permission to use, copy, modify, distribute and sell this software | |
36 | * and its documentation for any purpose is hereby granted without fee, | |
37 | * provided that the above copyright notice appear in all copies and | |
38 | * that both that copyright notice and this permission notice appear | |
39 | * in supporting documentation. Hewlett-Packard Company makes no | |
40 | * representations about the suitability of this software for any | |
41 | * purpose. It is provided "as is" without express or implied warranty. | |
42 | * | |
43 | * | |
44 | * Copyright (c) 1996,1997 | |
45 | * Silicon Graphics Computer Systems, Inc. | |
46 | * | |
47 | * Permission to use, copy, modify, distribute and sell this software | |
48 | * and its documentation for any purpose is hereby granted without fee, | |
49 | * provided that the above copyright notice appear in all copies and | |
50 | * that both that copyright notice and this permission notice appear | |
51 | * in supporting documentation. Silicon Graphics makes no | |
52 | * representations about the suitability of this software for any | |
53 | * purpose. It is provided "as is" without express or implied warranty. | |
54 | */ | |
55 | ||
56 | /** @file list.tcc | |
57 | * This is an internal header file, included by other library headers. | |
58 | * You should not attempt to use it directly. | |
59 | */ | |
60 | ||
3d7c150e BK |
61 | #ifndef _LIST_TCC |
62 | #define _LIST_TCC 1 | |
83144cfc | 63 | |
3cbc7af0 BK |
64 | _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) |
65 | ||
3971a4d2 PE |
66 | template<typename _Tp, typename _Alloc> |
67 | void | |
6e0a7f2b | 68 | _List_base<_Tp, _Alloc>:: |
4d54539c | 69 | _M_clear() |
83144cfc | 70 | { |
3971a4d2 | 71 | typedef _List_node<_Tp> _Node; |
03f9ea44 DM |
72 | _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next); |
73 | while (__cur != &this->_M_impl._M_node) | |
6e0a7f2b PC |
74 | { |
75 | _Node* __tmp = __cur; | |
76 | __cur = static_cast<_Node*>(__cur->_M_next); | |
4fd20a8f | 77 | _M_get_Tp_allocator().destroy(&__tmp->_M_data); |
6e0a7f2b PC |
78 | _M_put_node(__tmp); |
79 | } | |
e3d51be2 | 80 | } |
ed6814f7 | 81 | |
3971a4d2 | 82 | template<typename _Tp, typename _Alloc> |
6e0a7f2b PC |
83 | typename list<_Tp, _Alloc>::iterator |
84 | list<_Tp, _Alloc>:: | |
3971a4d2 | 85 | insert(iterator __position, const value_type& __x) |
83144cfc | 86 | { |
3971a4d2 | 87 | _Node* __tmp = _M_create_node(__x); |
e135a038 | 88 | __tmp->hook(__position._M_node); |
e182017e | 89 | return iterator(__tmp); |
83144cfc | 90 | } |
ed6814f7 | 91 | |
3971a4d2 | 92 | template<typename _Tp, typename _Alloc> |
6e0a7f2b PC |
93 | typename list<_Tp, _Alloc>::iterator |
94 | list<_Tp, _Alloc>:: | |
3971a4d2 | 95 | erase(iterator __position) |
83144cfc | 96 | { |
e182017e | 97 | iterator __ret = iterator(__position._M_node->_M_next); |
e135a038 BK |
98 | _M_erase(__position); |
99 | return __ret; | |
83144cfc | 100 | } |
ed6814f7 | 101 | |
3971a4d2 PE |
102 | template<typename _Tp, typename _Alloc> |
103 | void | |
6e0a7f2b | 104 | list<_Tp, _Alloc>:: |
2fecaef4 | 105 | resize(size_type __new_size, value_type __x) |
83144cfc | 106 | { |
3971a4d2 PE |
107 | iterator __i = begin(); |
108 | size_type __len = 0; | |
6e0a7f2b | 109 | for (; __i != end() && __len < __new_size; ++__i, ++__len) |
3971a4d2 PE |
110 | ; |
111 | if (__len == __new_size) | |
112 | erase(__i, end()); | |
113 | else // __i == end() | |
114 | insert(end(), __new_size - __len, __x); | |
83144cfc | 115 | } |
ed6814f7 | 116 | |
3971a4d2 | 117 | template<typename _Tp, typename _Alloc> |
6e0a7f2b PC |
118 | list<_Tp, _Alloc>& |
119 | list<_Tp, _Alloc>:: | |
3971a4d2 | 120 | operator=(const list& __x) |
83144cfc | 121 | { |
3971a4d2 | 122 | if (this != &__x) |
f6592a9e PC |
123 | { |
124 | iterator __first1 = begin(); | |
125 | iterator __last1 = end(); | |
126 | const_iterator __first2 = __x.begin(); | |
127 | const_iterator __last2 = __x.end(); | |
4681bebd PC |
128 | for (; __first1 != __last1 && __first2 != __last2; |
129 | ++__first1, ++__first2) | |
130 | *__first1 = *__first2; | |
f6592a9e PC |
131 | if (__first2 == __last2) |
132 | erase(__first1, __last1); | |
133 | else | |
134 | insert(__last1, __first2, __last2); | |
135 | } | |
3971a4d2 PE |
136 | return *this; |
137 | } | |
ed6814f7 | 138 | |
3971a4d2 PE |
139 | template<typename _Tp, typename _Alloc> |
140 | void | |
6e0a7f2b | 141 | list<_Tp, _Alloc>:: |
3971a4d2 | 142 | _M_fill_assign(size_type __n, const value_type& __val) |
83144cfc | 143 | { |
3971a4d2 | 144 | iterator __i = begin(); |
6e0a7f2b | 145 | for (; __i != end() && __n > 0; ++__i, --__n) |
3971a4d2 PE |
146 | *__i = __val; |
147 | if (__n > 0) | |
148 | insert(end(), __n, __val); | |
149 | else | |
150 | erase(__i, end()); | |
151 | } | |
ed6814f7 | 152 | |
3971a4d2 | 153 | template<typename _Tp, typename _Alloc> |
08addde6 | 154 | template <typename _InputIterator> |
3971a4d2 | 155 | void |
6e0a7f2b | 156 | list<_Tp, _Alloc>:: |
ed6814f7 | 157 | _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, |
4d54539c | 158 | __false_type) |
83144cfc | 159 | { |
3971a4d2 PE |
160 | iterator __first1 = begin(); |
161 | iterator __last1 = end(); | |
ed6814f7 | 162 | for (; __first1 != __last1 && __first2 != __last2; |
4d54539c | 163 | ++__first1, ++__first2) |
3971a4d2 PE |
164 | *__first1 = *__first2; |
165 | if (__first2 == __last2) | |
166 | erase(__first1, __last1); | |
167 | else | |
168 | insert(__last1, __first2, __last2); | |
83144cfc | 169 | } |
ed6814f7 | 170 | |
3971a4d2 | 171 | template<typename _Tp, typename _Alloc> |
83144cfc | 172 | void |
6e0a7f2b | 173 | list<_Tp, _Alloc>:: |
3971a4d2 | 174 | remove(const value_type& __value) |
83144cfc PE |
175 | { |
176 | iterator __first = begin(); | |
177 | iterator __last = end(); | |
178 | while (__first != __last) | |
6e0a7f2b PC |
179 | { |
180 | iterator __next = __first; | |
181 | ++__next; | |
182 | if (*__first == __value) | |
183 | _M_erase(__first); | |
184 | __first = __next; | |
185 | } | |
83144cfc | 186 | } |
ed6814f7 | 187 | |
3971a4d2 | 188 | template<typename _Tp, typename _Alloc> |
83144cfc | 189 | void |
6e0a7f2b | 190 | list<_Tp, _Alloc>:: |
3971a4d2 | 191 | unique() |
83144cfc PE |
192 | { |
193 | iterator __first = begin(); | |
194 | iterator __last = end(); | |
f6592a9e PC |
195 | if (__first == __last) |
196 | return; | |
83144cfc PE |
197 | iterator __next = __first; |
198 | while (++__next != __last) | |
6e0a7f2b PC |
199 | { |
200 | if (*__first == *__next) | |
201 | _M_erase(__next); | |
202 | else | |
203 | __first = __next; | |
204 | __next = __first; | |
205 | } | |
83144cfc | 206 | } |
ed6814f7 | 207 | |
3971a4d2 | 208 | template<typename _Tp, typename _Alloc> |
83144cfc | 209 | void |
6e0a7f2b | 210 | list<_Tp, _Alloc>:: |
3971a4d2 | 211 | merge(list& __x) |
83144cfc | 212 | { |
41d3a0c3 PC |
213 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
214 | // 300. list::merge() specification incomplete | |
215 | if (this != &__x) | |
216 | { | |
217 | iterator __first1 = begin(); | |
218 | iterator __last1 = end(); | |
219 | iterator __first2 = __x.begin(); | |
220 | iterator __last2 = __x.end(); | |
221 | while (__first1 != __last1 && __first2 != __last2) | |
222 | if (*__first2 < *__first1) | |
223 | { | |
224 | iterator __next = __first2; | |
225 | _M_transfer(__first1, __first2, ++__next); | |
226 | __first2 = __next; | |
227 | } | |
228 | else | |
229 | ++__first1; | |
230 | if (__first2 != __last2) | |
231 | _M_transfer(__last1, __first2, __last2); | |
232 | } | |
83144cfc | 233 | } |
ed6814f7 | 234 | |
3971a4d2 PE |
235 | template<typename _Tp, typename _Alloc> |
236 | void | |
6e0a7f2b | 237 | list<_Tp, _Alloc>:: |
3971a4d2 | 238 | sort() |
83144cfc | 239 | { |
3971a4d2 | 240 | // Do nothing if the list has length 0 or 1. |
03f9ea44 DM |
241 | if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node |
242 | && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) | |
83144cfc | 243 | { |
3971a4d2 | 244 | list __carry; |
e135a038 BK |
245 | list __tmp[64]; |
246 | list * __fill = &__tmp[0]; | |
247 | list * __counter; | |
248 | ||
249 | do | |
f6592a9e PC |
250 | { |
251 | __carry.splice(__carry.begin(), *this, begin()); | |
ed6814f7 | 252 | |
f6592a9e | 253 | for(__counter = &__tmp[0]; |
6e0a7f2b | 254 | __counter != __fill && !__counter->empty(); |
f6592a9e PC |
255 | ++__counter) |
256 | { | |
257 | __counter->merge(__carry); | |
258 | __carry.swap(*__counter); | |
259 | } | |
260 | __carry.swap(*__counter); | |
261 | if (__counter == __fill) | |
262 | ++__fill; | |
263 | } | |
264 | while ( !empty() ); | |
e135a038 | 265 | |
6e0a7f2b PC |
266 | for (__counter = &__tmp[1]; __counter != __fill; ++__counter) |
267 | __counter->merge(*(__counter - 1)); | |
268 | swap( *(__fill - 1) ); | |
3971a4d2 PE |
269 | } |
270 | } | |
ed6814f7 | 271 | |
3971a4d2 PE |
272 | template<typename _Tp, typename _Alloc> |
273 | template <typename _Predicate> | |
274 | void | |
6e0a7f2b | 275 | list<_Tp, _Alloc>:: |
3971a4d2 PE |
276 | remove_if(_Predicate __pred) |
277 | { | |
278 | iterator __first = begin(); | |
279 | iterator __last = end(); | |
280 | while (__first != __last) | |
6e0a7f2b PC |
281 | { |
282 | iterator __next = __first; | |
283 | ++__next; | |
284 | if (__pred(*__first)) | |
285 | _M_erase(__first); | |
286 | __first = __next; | |
287 | } | |
3971a4d2 | 288 | } |
ed6814f7 | 289 | |
3971a4d2 PE |
290 | template<typename _Tp, typename _Alloc> |
291 | template <typename _BinaryPredicate> | |
292 | void | |
6e0a7f2b | 293 | list<_Tp, _Alloc>:: |
3971a4d2 PE |
294 | unique(_BinaryPredicate __binary_pred) |
295 | { | |
296 | iterator __first = begin(); | |
297 | iterator __last = end(); | |
6e0a7f2b PC |
298 | if (__first == __last) |
299 | return; | |
3971a4d2 PE |
300 | iterator __next = __first; |
301 | while (++__next != __last) | |
6e0a7f2b PC |
302 | { |
303 | if (__binary_pred(*__first, *__next)) | |
304 | _M_erase(__next); | |
305 | else | |
306 | __first = __next; | |
307 | __next = __first; | |
308 | } | |
3971a4d2 | 309 | } |
ed6814f7 | 310 | |
3971a4d2 PE |
311 | template<typename _Tp, typename _Alloc> |
312 | template <typename _StrictWeakOrdering> | |
313 | void | |
6e0a7f2b | 314 | list<_Tp, _Alloc>:: |
3971a4d2 PE |
315 | merge(list& __x, _StrictWeakOrdering __comp) |
316 | { | |
41d3a0c3 | 317 | // _GLIBCXX_RESOLVE_LIB_DEFECTS |
ed6814f7 | 318 | // 300. list::merge() specification incomplete |
41d3a0c3 PC |
319 | if (this != &__x) |
320 | { | |
321 | iterator __first1 = begin(); | |
322 | iterator __last1 = end(); | |
323 | iterator __first2 = __x.begin(); | |
324 | iterator __last2 = __x.end(); | |
325 | while (__first1 != __last1 && __first2 != __last2) | |
326 | if (__comp(*__first2, *__first1)) | |
327 | { | |
328 | iterator __next = __first2; | |
329 | _M_transfer(__first1, __first2, ++__next); | |
330 | __first2 = __next; | |
331 | } | |
332 | else | |
333 | ++__first1; | |
334 | if (__first2 != __last2) | |
335 | _M_transfer(__last1, __first2, __last2); | |
336 | } | |
3971a4d2 | 337 | } |
ed6814f7 | 338 | |
3971a4d2 PE |
339 | template<typename _Tp, typename _Alloc> |
340 | template <typename _StrictWeakOrdering> | |
f6592a9e | 341 | void |
6e0a7f2b | 342 | list<_Tp, _Alloc>:: |
f6592a9e | 343 | sort(_StrictWeakOrdering __comp) |
3971a4d2 | 344 | { |
f6592a9e | 345 | // Do nothing if the list has length 0 or 1. |
03f9ea44 DM |
346 | if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node |
347 | && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) | |
f6592a9e PC |
348 | { |
349 | list __carry; | |
350 | list __tmp[64]; | |
351 | list * __fill = &__tmp[0]; | |
352 | list * __counter; | |
ed6814f7 | 353 | |
f6592a9e PC |
354 | do |
355 | { | |
356 | __carry.splice(__carry.begin(), *this, begin()); | |
ed6814f7 | 357 | |
f6592a9e | 358 | for(__counter = &__tmp[0]; |
6e0a7f2b | 359 | __counter != __fill && !__counter->empty(); |
f6592a9e PC |
360 | ++__counter) |
361 | { | |
362 | __counter->merge(__carry, __comp); | |
363 | __carry.swap(*__counter); | |
364 | } | |
365 | __carry.swap(*__counter); | |
366 | if (__counter == __fill) | |
367 | ++__fill; | |
368 | } | |
369 | while ( !empty() ); | |
ed6814f7 | 370 | |
6e0a7f2b PC |
371 | for (__counter = &__tmp[1]; __counter != __fill; ++__counter) |
372 | __counter->merge(*(__counter - 1), __comp); | |
373 | swap(*(__fill - 1)); | |
f6592a9e | 374 | } |
83144cfc | 375 | } |
3cbc7af0 BK |
376 | |
377 | _GLIBCXX_END_NESTED_NAMESPACE | |
83144cfc | 378 | |
3d7c150e | 379 | #endif /* _LIST_TCC */ |
e135a038 | 380 |