1/*
2 *
3 *
4 * Copyright (c) 1994
5 * Hewlett-Packard Company
6 *
7 * Copyright (c) 1996,1997
8 * Silicon Graphics Computer Systems, Inc.
9 *
10 * Copyright (c) 1997
11 * Moscow Center for SPARC Technology
12 *
13 * Copyright (c) 1999
14 * Boris Fomitchev
15 *
16 * This material is provided "as is", with absolutely no warranty expressed
17 * or implied. Any use is at your own risk.
18 *
19 * Permission to use or copy this software for any purpose is hereby granted
20 * without fee, provided the above notices are retained on all copies.
21 * Permission to modify the code and to distribute modified code is granted,
22 * provided the above notices are retained, and a notice that the code was
23 * modified is included with the above copyright notice.
24 *
25 */
26#ifndef _STLP_LIST_C
27#define _STLP_LIST_C
28
29#ifndef _STLP_INTERNAL_LIST_H
30#  include <stl/_list.h>
31#endif
32
33#ifndef _STLP_CARRAY_H
34#  include <stl/_carray.h>
35#endif
36
37#ifndef _STLP_RANGE_ERRORS_H
38#  include <stl/_range_errors.h>
39#endif
40
41_STLP_BEGIN_NAMESPACE
42
43_STLP_MOVE_TO_PRIV_NAMESPACE
44
45#if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
46template <class _Dummy>
47void _STLP_CALL
48_List_global<_Dummy>::_Transfer(_List_node_base* __position,
49                                _List_node_base* __first, _List_node_base* __last) {
50  if (__position != __last) {
51    // Remove [first, last) from its old position.
52    __last->_M_prev->_M_next     = __position;
53    __first->_M_prev->_M_next    = __last;
54    __position->_M_prev->_M_next = __first;
55
56    // Splice [first, last) into its new position.
57    _Node_base* __tmp = __position->_M_prev;
58    __position->_M_prev = __last->_M_prev;
59    __last->_M_prev     = __first->_M_prev;
60    __first->_M_prev    = __tmp;
61  }
62}
63#endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */
64
65template <class _Tp, class _Alloc>
66void _List_base<_Tp,_Alloc>::clear() {
67  _Node* __cur = __STATIC_CAST(_Node*, _M_node._M_data._M_next);
68  while (
69#if defined (__BORLANDC__) // runtime error
70         __cur &&
71#endif
72         __cur != &(_M_node._M_data)) {
73    _Node* __tmp = __cur;
74    __cur = __STATIC_CAST(_Node*, __cur->_M_next);
75    _STLP_STD::_Destroy(&__tmp->_M_data);
76    this->_M_node.deallocate(__tmp, 1);
77  }
78  _M_node._M_data._M_next = &_M_node._M_data;
79  _M_node._M_data._M_prev = &_M_node._M_data;
80}
81
82#if defined (_STLP_NESTED_TYPE_PARAM_BUG)
83#  define size_type size_t
84#endif
85
86#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
87#  define list _STLP_PTR_IMPL_NAME(list)
88#elif defined (_STLP_DEBUG)
89#  define list _STLP_NON_DBG_NAME(list)
90#else
91_STLP_MOVE_TO_STD_NAMESPACE
92#endif
93
94template <class _Tp, class _Alloc>
95void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x) {
96  iterator __i = begin();
97  size_type __len = 0;
98  for ( ; __i != end() && __len < __new_size; ++__i, ++__len);
99
100  if (__len == __new_size)
101    erase(__i, end());
102  else // __i == end()
103    insert(end(), __new_size - __len, __x);
104}
105
106template <class _Tp, class _Alloc>
107list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x) {
108  if (this != &__x) {
109    iterator __first1 = begin();
110    iterator __last1 = end();
111    const_iterator __first2 = __x.begin();
112    const_iterator __last2 = __x.end();
113    while (__first1 != __last1 && __first2 != __last2)
114      *__first1++ = *__first2++;
115    if (__first2 == __last2)
116      erase(__first1, __last1);
117    else
118      insert(__last1, __first2, __last2);
119  }
120  return *this;
121}
122
123template <class _Tp, class _Alloc>
124void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
125  iterator __i = begin();
126  for ( ; __i != end() && __n > 0; ++__i, --__n)
127    *__i = __val;
128  if (__n > 0)
129    insert(end(), __n, __val);
130  else
131    erase(__i, end());
132}
133
134#if !defined (list)
135_STLP_MOVE_TO_PRIV_NAMESPACE
136#endif
137
138template <class _Tp, class _Alloc, class _Predicate>
139void _S_remove_if(list<_Tp, _Alloc>& __that, _Predicate __pred)  {
140  typedef typename list<_Tp, _Alloc>::iterator _Literator;
141  _Literator __first = __that.begin();
142  _Literator __last = __that.end();
143  while (__first != __last) {
144    _Literator __next = __first;
145    ++__next;
146    if (__pred(*__first)) __that.erase(__first);
147    __first = __next;
148  }
149}
150
151template <class _Tp, class _Alloc, class _BinaryPredicate>
152void _S_unique(list<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred) {
153  typedef typename list<_Tp, _Alloc>::iterator _Literator;
154  _Literator __first = __that.begin();
155  _Literator __last = __that.end();
156  if (__first == __last) return;
157  _Literator __next = __first;
158  while (++__next != __last) {
159    if (__binary_pred(*__first, *__next))
160      __that.erase(__next);
161    else
162      __first = __next;
163    __next = __first;
164  }
165}
166
167template <class _Tp, class _Alloc, class _StrictWeakOrdering>
168void _S_merge(list<_Tp, _Alloc>& __that, list<_Tp, _Alloc>& __x,
169              _StrictWeakOrdering __comp) {
170  typedef typename list<_Tp, _Alloc>::iterator _Literator;
171  _Literator __first1 = __that.begin();
172  _Literator __last1 = __that.end();
173  _Literator __first2 = __x.begin();
174  _Literator __last2 = __x.end();
175  if (__that.get_allocator() == __x.get_allocator()) {
176    while (__first1 != __last1 && __first2 != __last2) {
177      if (__comp(*__first2, *__first1)) {
178        _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
179        _Literator __next = __first2;
180        _List_global_inst::_Transfer(__first1._M_node, __first2._M_node, (++__next)._M_node);
181        __first2 = __next;
182      }
183      else
184        ++__first1;
185    }
186    if (__first2 != __last2)
187      _List_global_inst::_Transfer(__last1._M_node, __first2._M_node, __last2._M_node);
188  }
189  else {
190    while (__first1 != __last1 && __first2 != __last2) {
191      if (__comp(*__first2, *__first1)) {
192        _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
193        __first1 = __that.insert(__first1, *__first2);
194      }
195      else
196        ++__first1;
197    }
198    if (__first2 != __last2) {
199      __that.insert(__first1, __first2, __last2);
200    }
201    __x.clear();
202  }
203}
204
205template <class _Tp, class _Alloc, class _StrictWeakOrdering>
206void _S_sort(list<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp) {
207  // Do nothing if the list has length 0 or 1.
208  if (__that._M_node._M_data._M_next == &__that._M_node._M_data ||
209      __that._M_node._M_data._M_next->_M_next == &__that._M_node._M_data)
210    return;
211
212  list<_Tp, _Alloc> __carry(__that.get_allocator());
213  const int NB = 64;
214  _STLP_PRIV _CArray<list<_Tp, _Alloc>, NB> __counter(__carry);
215  int __fill = 0;
216  while (!__that.empty()) {
217    __carry.splice(__carry.begin(), __that, __that.begin());
218    int __i = 0;
219    while (__i < __fill && !__counter[__i].empty()) {
220      _S_merge(__counter[__i], __carry, __comp);
221      __carry.swap(__counter[__i++]);
222    }
223    __carry.swap(__counter[__i]);
224    if (__i == __fill) {
225      ++__fill;
226      if (__fill >= NB) {
227        //Looks like the list has too many elements to be sorted with this algorithm:
228        __stl_throw_overflow_error("list::sort");
229      }
230    }
231  }
232
233  for (int __i = 1; __i < __fill; ++__i)
234    _S_merge(__counter[__i], __counter[__i - 1], __comp);
235  __that.swap(__counter[__fill - 1]);
236}
237
238#if defined (list)
239#  undef list
240#endif
241
242_STLP_MOVE_TO_STD_NAMESPACE
243
244_STLP_END_NAMESPACE
245
246#endif /*  _STLP_LIST_C */
247
248// Local Variables:
249// mode:C++
250// End:
251