1 _list.c |
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 #if defined (__WATCOMC__) || defined (_STLP_USE_TRAP_LEAVE) |
|
34 #include <vector> |
|
35 #endif |
|
36 |
|
37 # undef list |
|
38 # define list __WORKAROUND_DBG_RENAME(list) |
|
39 |
|
40 _STLP_BEGIN_NAMESPACE |
|
41 |
|
42 # if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION) |
|
43 |
|
44 template <class _Dummy> |
|
45 void _STLP_CALL |
|
46 _List_global<_Dummy>::_Transfer(_List_node_base* __position, |
|
47 _List_node_base* __first, _List_node_base* __last) { |
|
48 if (__position != __last) { |
|
49 // Remove [first, last) from its old position. |
|
50 ((_Node*) (__last->_M_prev))->_M_next = __position; |
|
51 ((_Node*) (__first->_M_prev))->_M_next = __last; |
|
52 ((_Node*) (__position->_M_prev))->_M_next = __first; |
|
53 |
|
54 // Splice [first, last) into its new position. |
|
55 _Node* __tmp = (_Node*) (__position->_M_prev); |
|
56 __position->_M_prev = __last->_M_prev; |
|
57 __last->_M_prev = __first->_M_prev; |
|
58 __first->_M_prev = __tmp; |
|
59 } |
|
60 } |
|
61 |
|
62 #endif /* defined (__BUILDING_STLPORT) || ! defined (_STLP_OWN_IOSTREAMS) */ |
|
63 |
|
64 |
|
65 template <class _Tp, class _Alloc> |
|
66 void |
|
67 _List_base<_Tp,_Alloc>::clear() |
|
68 { |
|
69 _List_node<_Tp>* __cur = this->_M_node._M_data; |
|
70 if (!__cur) |
|
71 return; |
|
72 __cur = (_List_node<_Tp>*)__cur->_M_next; |
|
73 while (__cur != this->_M_node._M_data) { |
|
74 _List_node<_Tp>* __tmp = __cur; |
|
75 __cur = (_List_node<_Tp>*) __cur->_M_next; |
|
76 _STLP_STD::_Destroy(&__tmp->_M_data); |
|
77 this->_M_node.deallocate(__tmp, 1); |
|
78 } |
|
79 this->_M_node._M_data->_M_next = this->_M_node._M_data; |
|
80 this->_M_node._M_data->_M_prev = this->_M_node._M_data; |
|
81 } |
|
82 |
|
83 # if defined (_STLP_NESTED_TYPE_PARAM_BUG) |
|
84 # define size_type size_t |
|
85 # endif |
|
86 |
|
87 template <class _Tp, class _Alloc> |
|
88 void list<_Tp, _Alloc>::resize(size_type __new_size, _Tp __x) |
|
89 { |
|
90 iterator __i = begin(); |
|
91 size_type __len = 0; |
|
92 for ( ; __i != end() && __len < __new_size; ++__i, ++__len); |
|
93 |
|
94 if (__len == __new_size) |
|
95 erase(__i, end()); |
|
96 else // __i == end() |
|
97 insert(end(), __new_size - __len, __x); |
|
98 } |
|
99 |
|
100 template <class _Tp, class _Alloc> |
|
101 list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x) |
|
102 { |
|
103 if (this != &__x) { |
|
104 iterator __first1 = begin(); |
|
105 iterator __last1 = end(); |
|
106 const_iterator __first2 = __x.begin(); |
|
107 const_iterator __last2 = __x.end(); |
|
108 while (__first1 != __last1 && __first2 != __last2) |
|
109 *__first1++ = *__first2++; |
|
110 if (__first2 == __last2) |
|
111 erase(__first1, __last1); |
|
112 else |
|
113 insert(__last1, __first2, __last2); |
|
114 } |
|
115 return *this; |
|
116 } |
|
117 |
|
118 template <class _Tp, class _Alloc> |
|
119 void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { |
|
120 iterator __i = begin(); |
|
121 for ( ; __i != end() && __n > 0; ++__i, --__n) |
|
122 *__i = __val; |
|
123 if (__n > 0) |
|
124 insert(end(), __n, __val); |
|
125 else |
|
126 erase(__i, end()); |
|
127 } |
|
128 |
|
129 template <class _Tp, class _Alloc, class _Predicate> |
|
130 void _S_remove_if(list<_Tp, _Alloc>& __that, _Predicate __pred) { |
|
131 typename list<_Tp, _Alloc>::iterator __first = __that.begin(); |
|
132 typename list<_Tp, _Alloc>::iterator __last = __that.end(); |
|
133 while (__first != __last) { |
|
134 typename list<_Tp, _Alloc>::iterator __next = __first; |
|
135 ++__next; |
|
136 if (__pred(*__first)) __that.erase(__first); |
|
137 __first = __next; |
|
138 } |
|
139 } |
|
140 |
|
141 template <class _Tp, class _Alloc, class _BinaryPredicate> |
|
142 void _S_unique(list<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred) { |
|
143 typename list<_Tp, _Alloc>::iterator __first = __that.begin(); |
|
144 typename list<_Tp, _Alloc>::iterator __last = __that.end(); |
|
145 if (__first == __last) return; |
|
146 typename list<_Tp, _Alloc>::iterator __next = __first; |
|
147 while (++__next != __last) { |
|
148 if (__binary_pred(*__first, *__next)) |
|
149 __that.erase(__next); |
|
150 else |
|
151 __first = __next; |
|
152 __next = __first; |
|
153 } |
|
154 } |
|
155 |
|
156 template <class _Tp, class _Alloc, class _StrictWeakOrdering> |
|
157 void _S_merge(list<_Tp, _Alloc>& __that, list<_Tp, _Alloc>& __x, |
|
158 _StrictWeakOrdering __comp) { |
|
159 typedef typename list<_Tp, _Alloc>::iterator _Literator; |
|
160 _Literator __first1 = __that.begin(); |
|
161 _Literator __last1 = __that.end(); |
|
162 _Literator __first2 = __x.begin(); |
|
163 _Literator __last2 = __x.end(); |
|
164 while (__first1 != __last1 && __first2 != __last2) |
|
165 if (__comp(*__first2, *__first1)) { |
|
166 _Literator __next = __first2; |
|
167 _List_global_inst::_Transfer(__first1._M_node, __first2._M_node, (++__next)._M_node); |
|
168 __first2 = __next; |
|
169 } |
|
170 else |
|
171 ++__first1; |
|
172 if (__first2 != __last2) _List_global_inst::_Transfer(__last1._M_node, __first2._M_node, __last2._M_node); |
|
173 } |
|
174 |
|
175 template <class _Tp, class _Alloc, class _StrictWeakOrdering> |
|
176 void _S_sort(list<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp) { |
|
177 // Do nothing if the list has length 0 or 1. |
|
178 if (__that._M_node._M_data->_M_next != __that._M_node._M_data && |
|
179 (__that._M_node._M_data->_M_next)->_M_next != __that._M_node._M_data) { |
|
180 |
|
181 #if !defined (__WATCOMC__) |
|
182 #ifdef _STLP_USE_TRAP_LEAVE |
|
183 typedef vector<list<_Tp, _Alloc>*, _Alloc> _TmpVec; |
|
184 _TmpVec* __pTmp = new _TmpVec(); |
|
185 _TmpVec& __counter = *__pTmp; |
|
186 for (int i = 0; 1< 64; ++i) { |
|
187 list<_Tp, _Alloc>* __pTmp2 = new list<_Tp, _Alloc>; |
|
188 __counter.push_back (__pTmp2); |
|
189 } |
|
190 list<_Tp, _Alloc>* __pcarry = new list<_Tp, _Alloc>; |
|
191 list<_Tp, _Alloc>& __carry = *__pcarry; |
|
192 #else |
|
193 list<_Tp, _Alloc> __counter[64]; |
|
194 list<_Tp, _Alloc> __carry; |
|
195 #endif |
|
196 #else |
|
197 list<_Tp, _Alloc> __carry; |
|
198 __vector__<list<_Tp, _Alloc>, _Alloc> __counter(64); |
|
199 #endif |
|
200 int __fill = 0; |
|
201 #ifdef _STLP_USE_TRAP_LEAVE |
|
202 while (!__that.empty()) { |
|
203 __carry.splice(__carry.begin(), __that, __that.begin()); |
|
204 int __i = 0; |
|
205 |
|
206 while(__i < __fill && !__counter[__i]->empty()) { |
|
207 _S_merge(*__counter[__i], __carry, __comp); |
|
208 __carry.swap(*__counter[__i++]); |
|
209 } |
|
210 __carry.swap(*__counter[__i]); |
|
211 if (__i == __fill) ++__fill; |
|
212 } |
|
213 |
|
214 for (int __i = 1; __i < __fill; ++__i) |
|
215 _S_merge(*__counter[__i], *__counter[__i-1], __comp); |
|
216 __that.swap(*__counter[__fill-1]); |
|
217 |
|
218 // those objects won't just go away |
|
219 __counter.clear(); |
|
220 CleanupStack::Pop(66); |
|
221 } |
|
222 # else |
|
223 while (!__that.empty()) { |
|
224 __carry.splice(__carry.begin(), __that, __that.begin()); |
|
225 int __i = 0; |
|
226 |
|
227 while(__i < __fill && !__counter[__i].empty()) { |
|
228 _S_merge(__counter[__i], __carry, __comp); |
|
229 __carry.swap(__counter[__i++]); |
|
230 } |
|
231 __carry.swap(__counter[__i]); |
|
232 if (__i == __fill) ++__fill; |
|
233 } |
|
234 |
|
235 for (int __i = 1; __i < __fill; ++__i) |
|
236 _S_merge(__counter[__i], __counter[__i-1], __comp); |
|
237 __that.swap(__counter[__fill-1]); |
|
238 } |
|
239 # endif |
|
240 |
|
241 } |
|
242 |
|
243 # undef list |
|
244 # undef size_type |
|
245 |
|
246 _STLP_END_NAMESPACE |
|
247 |
|
248 #endif /* _STLP_LIST_C */ |
|
249 |
|
250 // Local Variables: |
|
251 // mode:C++ |
|
252 // End: |