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