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)
46 template <class _Dummy>
47 void _STLP_CALL
_Transfer(_List_node_base * __position,_List_node_base * __first,_List_node_base * __last)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
65 template <class _Tp, class _Alloc>
clear()66 void _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
94 template <class _Tp, class _Alloc>
resize(size_type __new_size,const _Tp & __x)95 void 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
106 template <class _Tp, class _Alloc>
107 list<_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
123 template <class _Tp, class _Alloc>
_M_fill_assign(size_type __n,const _Tp & __val)124 void 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
138 template <class _Tp, class _Alloc, class _Predicate>
_S_remove_if(list<_Tp,_Alloc> & __that,_Predicate __pred)139 void _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
151 template <class _Tp, class _Alloc, class _BinaryPredicate>
_S_unique(list<_Tp,_Alloc> & __that,_BinaryPredicate __binary_pred)152 void _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
167 template <class _Tp, class _Alloc, class _StrictWeakOrdering>
_S_merge(list<_Tp,_Alloc> & __that,list<_Tp,_Alloc> & __x,_StrictWeakOrdering __comp)168 void _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
205 template <class _Tp, class _Alloc, class _StrictWeakOrdering>
_S_sort(list<_Tp,_Alloc> & __that,_StrictWeakOrdering __comp)206 void _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