Dead
[official-gcc.git] / gomp-20050608-branch / libstdc++-v3 / include / bits / list.tcc
blobf2849fb6e52a280d820830540317bb30e734ca54
1 // List implementation (out of line) -*- C++ -*-
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.
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.
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.
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.
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  */
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  */
62 #ifndef _LIST_TCC
63 #define _LIST_TCC 1
65 _GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD)
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     }
83   template<typename _Tp, typename _Alloc>
84     typename list<_Tp, _Alloc>::iterator
85     list<_Tp, _Alloc>::
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     }
93   template<typename _Tp, typename _Alloc>
94     typename list<_Tp, _Alloc>::iterator
95     list<_Tp, _Alloc>::
96     erase(iterator __position)
97     {
98       iterator __ret = iterator(__position._M_node->_M_next);
99       _M_erase(__position);
100       return __ret;
101     }
103   template<typename _Tp, typename _Alloc>
104     void
105     list<_Tp, _Alloc>::
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     }
118   template<typename _Tp, typename _Alloc>
119     list<_Tp, _Alloc>&
120     list<_Tp, _Alloc>::
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     }
140   template<typename _Tp, typename _Alloc>
141     void
142     list<_Tp, _Alloc>::
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     }
154   template<typename _Tp, typename _Alloc>
155     template <typename _InputIterator>
156       void
157       list<_Tp, _Alloc>::
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       }
172   template<typename _Tp, typename _Alloc>
173     void
174     list<_Tp, _Alloc>::
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     }
189   template<typename _Tp, typename _Alloc>
190     void
191     list<_Tp, _Alloc>::
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     }
209   template<typename _Tp, typename _Alloc>
210     void
211     list<_Tp, _Alloc>::
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); 
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     }
238   template<typename _Tp, typename _Alloc>
239     template <typename _StrictWeakOrdering>
240       void
241       list<_Tp, _Alloc>::
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);
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       }
268   template<typename _Tp, typename _Alloc>
269     void
270     list<_Tp, _Alloc>::
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;
282         do
283           {
284             __carry.splice(__carry.begin(), *this, begin());
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() );
299         for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
300           __counter->merge(*(__counter - 1));
301         swap( *(__fill - 1) );
302       }
303     }
305   template<typename _Tp, typename _Alloc>
306     template <typename _Predicate>
307       void
308       list<_Tp, _Alloc>::
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       }
323   template<typename _Tp, typename _Alloc>
324     template <typename _BinaryPredicate>
325       void
326       list<_Tp, _Alloc>::
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       }
344   template<typename _Tp, typename _Alloc>
345     template <typename _StrictWeakOrdering>
346       void
347       list<_Tp, _Alloc>::
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;
359             do
360               {
361                 __carry.splice(__carry.begin(), *this, begin());
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() );
376             for (__counter = &__tmp[1]; __counter != __fill; ++__counter)
377               __counter->merge(*(__counter - 1), __comp);
378             swap(*(__fill - 1));
379           }
380       }
382 _GLIBCXX_END_NESTED_NAMESPACE
384 #endif /* _LIST_TCC */