list.tcc revision 132720 
1// List implementation (out of line) -*- C++ -*-
2
3// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc.
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
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
61#ifndef _LIST_TCC
62#define _LIST_TCC 1
63
64namespace _GLIBCXX_STD
65{
66  template<typename _Tp, typename _Alloc>
67    void
68    _List_base<_Tp,_Alloc>::
69    _M_clear()
70    {
71      typedef _List_node<_Tp>  _Node;
72      _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next);
73      while (__cur != &this->_M_impl._M_node)
74      {
75        _Node* __tmp = __cur;
76        __cur = static_cast<_Node*>(__cur->_M_next);
77        std::_Destroy(&__tmp->_M_data);
78        _M_put_node(__tmp);
79      }
80    }
81
82  template<typename _Tp, typename _Alloc>
83    typename list<_Tp,_Alloc>::iterator
84    list<_Tp,_Alloc>::
85    insert(iterator __position, const value_type& __x)
86    {
87      _Node* __tmp = _M_create_node(__x);
88      __tmp->hook(__position._M_node);
89      return __tmp;
90    }
91
92  template<typename _Tp, typename _Alloc>
93    typename list<_Tp,_Alloc>::iterator
94    list<_Tp,_Alloc>::
95    erase(iterator __position)
96    {
97      iterator __ret = __position._M_node->_M_next;
98      _M_erase(__position);
99      return __ret;
100    }
101
102  template<typename _Tp, typename _Alloc>
103    void
104    list<_Tp,_Alloc>::
105    resize(size_type __new_size, const value_type& __x)
106    {
107      iterator __i = begin();
108      size_type __len = 0;
109      for ( ; __i != end() && __len < __new_size; ++__i, ++__len)
110        ;
111      if (__len == __new_size)
112        erase(__i, end());
113      else                          // __i == end()
114        insert(end(), __new_size - __len, __x);
115    }
116
117  template<typename _Tp, typename _Alloc>
118    list<_Tp,_Alloc>&
119    list<_Tp,_Alloc>::
120    operator=(const list& __x)
121    {
122      if (this != &__x)
123	{
124	  iterator __first1 = begin();
125	  iterator __last1 = end();
126	  const_iterator __first2 = __x.begin();
127	  const_iterator __last2 = __x.end();
128	  while (__first1 != __last1 && __first2 != __last2)
129	    *__first1++ = *__first2++;
130	  if (__first2 == __last2)
131	    erase(__first1, __last1);
132	  else
133	    insert(__last1, __first2, __last2);
134	}
135      return *this;
136    }
137
138  template<typename _Tp, typename _Alloc>
139    void
140    list<_Tp,_Alloc>::
141    _M_fill_assign(size_type __n, const value_type& __val)
142    {
143      iterator __i = begin();
144      for ( ; __i != end() && __n > 0; ++__i, --__n)
145        *__i = __val;
146      if (__n > 0)
147        insert(end(), __n, __val);
148      else
149        erase(__i, end());
150    }
151
152  template<typename _Tp, typename _Alloc>
153    template <typename _InputIterator>
154      void
155      list<_Tp,_Alloc>::
156      _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
157			 __false_type)
158      {
159        iterator __first1 = begin();
160        iterator __last1 = end();
161        for (; __first1 != __last1 && __first2 != __last2;
162	     ++__first1, ++__first2)
163          *__first1 = *__first2;
164        if (__first2 == __last2)
165          erase(__first1, __last1);
166        else
167          insert(__last1, __first2, __last2);
168      }
169
170  template<typename _Tp, typename _Alloc>
171    void
172    list<_Tp,_Alloc>::
173    remove(const value_type& __value)
174    {
175      iterator __first = begin();
176      iterator __last = end();
177      while (__first != __last)
178      {
179        iterator __next = __first;
180        ++__next;
181        if (*__first == __value)
182          _M_erase(__first);
183        __first = __next;
184      }
185    }
186
187  template<typename _Tp, typename _Alloc>
188    void
189    list<_Tp,_Alloc>::
190    unique()
191    {
192      iterator __first = begin();
193      iterator __last = end();
194      if (__first == __last)
195	return;
196      iterator __next = __first;
197      while (++__next != __last)
198      {
199        if (*__first == *__next)
200          _M_erase(__next);
201        else
202          __first = __next;
203        __next = __first;
204      }
205    }
206
207  template<typename _Tp, typename _Alloc>
208    void
209    list<_Tp,_Alloc>::
210    merge(list& __x)
211    {
212      // _GLIBCXX_RESOLVE_LIB_DEFECTS
213      // 300. list::merge() specification incomplete
214      if (this != &__x)
215	{
216	  iterator __first1 = begin();
217	  iterator __last1 = end();
218	  iterator __first2 = __x.begin();
219	  iterator __last2 = __x.end();
220	  while (__first1 != __last1 && __first2 != __last2)
221	    if (*__first2 < *__first1)
222	      {
223		iterator __next = __first2;
224		_M_transfer(__first1, __first2, ++__next);
225		__first2 = __next;
226	      }
227	    else
228	      ++__first1;
229	  if (__first2 != __last2)
230	    _M_transfer(__last1, __first2, __last2);
231	}
232    }
233
234  template<typename _Tp, typename _Alloc>
235    void
236    list<_Tp,_Alloc>::
237    sort()
238    {
239      // Do nothing if the list has length 0 or 1.
240      if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
241	  && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
242      {
243        list __carry;
244        list __tmp[64];
245        list * __fill = &__tmp[0];
246        list * __counter;
247
248        do
249	  {
250	    __carry.splice(__carry.begin(), *this, begin());
251
252	    for(__counter = &__tmp[0];
253		(__counter != __fill) && !__counter->empty();
254		++__counter)
255	      {
256		__counter->merge(__carry);
257		__carry.swap(*__counter);
258	      }
259	    __carry.swap(*__counter);
260	    if (__counter == __fill)
261	      ++__fill;
262	  }
263	while ( !empty() );
264
265        for (__counter =  &__tmp[1]; __counter != __fill; ++__counter)
266          __counter->merge( *(__counter-1) );
267        swap( *(__fill-1) );
268      }
269    }
270
271  template<typename _Tp, typename _Alloc>
272    template <typename _Predicate>
273      void
274      list<_Tp,_Alloc>::
275      remove_if(_Predicate __pred)
276      {
277        iterator __first = begin();
278        iterator __last = end();
279        while (__first != __last)
280        {
281          iterator __next = __first;
282          ++__next;
283          if (__pred(*__first))
284	    _M_erase(__first);
285          __first = __next;
286        }
287      }
288
289  template<typename _Tp, typename _Alloc>
290    template <typename _BinaryPredicate>
291      void
292      list<_Tp,_Alloc>::
293      unique(_BinaryPredicate __binary_pred)
294      {
295        iterator __first = begin();
296        iterator __last = end();
297        if (__first == __last) return;
298        iterator __next = __first;
299        while (++__next != __last)
300        {
301          if (__binary_pred(*__first, *__next))
302            _M_erase(__next);
303          else
304            __first = __next;
305          __next = __first;
306        }
307      }
308
309  template<typename _Tp, typename _Alloc>
310    template <typename _StrictWeakOrdering>
311      void
312      list<_Tp,_Alloc>::
313      merge(list& __x, _StrictWeakOrdering __comp)
314      {
315	// _GLIBCXX_RESOLVE_LIB_DEFECTS
316	// 300. list::merge() specification incomplete
317	if (this != &__x)
318	  {
319	    iterator __first1 = begin();
320	    iterator __last1 = end();
321	    iterator __first2 = __x.begin();
322	    iterator __last2 = __x.end();
323	    while (__first1 != __last1 && __first2 != __last2)
324	      if (__comp(*__first2, *__first1))
325		{
326		  iterator __next = __first2;
327		  _M_transfer(__first1, __first2, ++__next);
328		  __first2 = __next;
329		}
330	      else
331		++__first1;
332	    if (__first2 != __last2)
333	      _M_transfer(__last1, __first2, __last2);
334	  }
335      }
336
337  template<typename _Tp, typename _Alloc>
338    template <typename _StrictWeakOrdering>
339      void
340      list<_Tp,_Alloc>::
341      sort(_StrictWeakOrdering __comp)
342      {
343	// Do nothing if the list has length 0 or 1.
344	if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node
345	    && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node)
346	  {
347	    list __carry;
348	    list __tmp[64];
349	    list * __fill = &__tmp[0];
350	    list * __counter;
351
352	    do
353	      {
354		__carry.splice(__carry.begin(), *this, begin());
355
356		for(__counter = &__tmp[0];
357		    (__counter != __fill) && !__counter->empty();
358		    ++__counter)
359		  {
360		    __counter->merge(__carry, __comp);
361		    __carry.swap(*__counter);
362		  }
363		__carry.swap(*__counter);
364		if (__counter == __fill)
365		  ++__fill;
366	      }
367	    while ( !empty() );
368
369	    for (__counter =  &__tmp[1]; __counter != __fill; ++__counter)
370	      __counter->merge( *(__counter-1), __comp );
371	    swap( *(__fill-1) );
372	  }
373      }
374} // namespace std
375
376#endif /* _LIST_TCC */
377
378