1.1 --- a/epoc32/include/stdapis/stlportv5/stl/_list.c Wed Mar 31 12:27:01 2010 +0100
1.2 +++ b/epoc32/include/stdapis/stlportv5/stl/_list.c Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -10,13 +10,13 @@
1.4 * Copyright (c) 1997
1.5 * Moscow Center for SPARC Technology
1.6 *
1.7 - * Copyright (c) 1999
1.8 + * Copyright (c) 1999
1.9 * Boris Fomitchev
1.10 *
1.11 * This material is provided "as is", with absolutely no warranty expressed
1.12 * or implied. Any use is at your own risk.
1.13 *
1.14 - * Permission to use or copy this software for any purpose is hereby granted
1.15 + * Permission to use or copy this software for any purpose is hereby granted
1.16 * without fee, provided the above notices are retained on all copies.
1.17 * Permission to modify the code and to distribute modified code is granted,
1.18 * provided the above notices are retained, and a notice that the code was
1.19 @@ -27,85 +27,86 @@
1.20 #define _STLP_LIST_C
1.21
1.22 #ifndef _STLP_INTERNAL_LIST_H
1.23 -# include <stl/_list.h>
1.24 +# include <stl/_list.h>
1.25 #endif
1.26
1.27 -#if defined (__WATCOMC__) || defined (_STLP_USE_TRAP_LEAVE)
1.28 -#include <vector>
1.29 +#ifndef _STLP_CARRAY_H
1.30 +# include <stl/_carray.h>
1.31 #endif
1.32
1.33 -# undef list
1.34 -# define list __WORKAROUND_DBG_RENAME(list)
1.35 +#ifndef _STLP_RANGE_ERRORS_H
1.36 +# include <stl/_range_errors.h>
1.37 +#endif
1.38
1.39 _STLP_BEGIN_NAMESPACE
1.40
1.41 -# if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
1.42 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.43
1.44 +#if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
1.45 template <class _Dummy>
1.46 void _STLP_CALL
1.47 -_List_global<_Dummy>::_Transfer(_List_node_base* __position,
1.48 - _List_node_base* __first, _List_node_base* __last) {
1.49 +_List_global<_Dummy>::_Transfer(_List_node_base* __position,
1.50 + _List_node_base* __first, _List_node_base* __last) {
1.51 if (__position != __last) {
1.52 // Remove [first, last) from its old position.
1.53 - ((_Node*) (__last->_M_prev))->_M_next = __position;
1.54 - ((_Node*) (__first->_M_prev))->_M_next = __last;
1.55 - ((_Node*) (__position->_M_prev))->_M_next = __first;
1.56 -
1.57 + __last->_M_prev->_M_next = __position;
1.58 + __first->_M_prev->_M_next = __last;
1.59 + __position->_M_prev->_M_next = __first;
1.60 +
1.61 // Splice [first, last) into its new position.
1.62 - _Node* __tmp = (_Node*) (__position->_M_prev);
1.63 + _Node_base* __tmp = __position->_M_prev;
1.64 __position->_M_prev = __last->_M_prev;
1.65 - __last->_M_prev = __first->_M_prev;
1.66 + __last->_M_prev = __first->_M_prev;
1.67 __first->_M_prev = __tmp;
1.68 }
1.69 }
1.70 -
1.71 -#endif /* defined (__BUILDING_STLPORT) || ! defined (_STLP_OWN_IOSTREAMS) */
1.72 -
1.73 +#endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */
1.74
1.75 template <class _Tp, class _Alloc>
1.76 -void
1.77 -_List_base<_Tp,_Alloc>::clear()
1.78 -{
1.79 - _List_node<_Tp>* __cur = this->_M_node._M_data;
1.80 - if (!__cur)
1.81 - return;
1.82 - __cur = (_List_node<_Tp>*)__cur->_M_next;
1.83 - while (__cur != this->_M_node._M_data) {
1.84 - _List_node<_Tp>* __tmp = __cur;
1.85 - __cur = (_List_node<_Tp>*) __cur->_M_next;
1.86 +void _List_base<_Tp,_Alloc>::clear() {
1.87 + _Node* __cur = __STATIC_CAST(_Node*, _M_node._M_data._M_next);
1.88 + while (__cur != &(_M_node._M_data)) {
1.89 + _Node* __tmp = __cur;
1.90 + __cur = __STATIC_CAST(_Node*, __cur->_M_next);
1.91 _STLP_STD::_Destroy(&__tmp->_M_data);
1.92 this->_M_node.deallocate(__tmp, 1);
1.93 }
1.94 - this->_M_node._M_data->_M_next = this->_M_node._M_data;
1.95 - this->_M_node._M_data->_M_prev = this->_M_node._M_data;
1.96 + _M_node._M_data._M_next = &_M_node._M_data;
1.97 + _M_node._M_data._M_prev = &_M_node._M_data;
1.98 }
1.99
1.100 -# if defined (_STLP_NESTED_TYPE_PARAM_BUG)
1.101 -# define size_type size_t
1.102 -# endif
1.103 +#if defined (_STLP_NESTED_TYPE_PARAM_BUG)
1.104 +# define size_type size_t
1.105 +#endif
1.106 +
1.107 +#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
1.108 +# define list _STLP_PTR_IMPL_NAME(list)
1.109 +#elif defined (_STLP_DEBUG)
1.110 +# define list _STLP_NON_DBG_NAME(list)
1.111 +#else
1.112 +_STLP_MOVE_TO_STD_NAMESPACE
1.113 +#endif
1.114
1.115 template <class _Tp, class _Alloc>
1.116 -void list<_Tp, _Alloc>::resize(size_type __new_size, _Tp __x)
1.117 -{
1.118 +void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x) {
1.119 iterator __i = begin();
1.120 size_type __len = 0;
1.121 for ( ; __i != end() && __len < __new_size; ++__i, ++__len);
1.122
1.123 if (__len == __new_size)
1.124 erase(__i, end());
1.125 - else // __i == end()
1.126 + else // __i == end()
1.127 insert(end(), __new_size - __len, __x);
1.128 }
1.129
1.130 template <class _Tp, class _Alloc>
1.131 -list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x)
1.132 -{
1.133 +list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x) {
1.134 if (this != &__x) {
1.135 iterator __first1 = begin();
1.136 iterator __last1 = end();
1.137 const_iterator __first2 = __x.begin();
1.138 const_iterator __last2 = __x.end();
1.139 - while (__first1 != __last1 && __first2 != __last2)
1.140 + while (__first1 != __last1 && __first2 != __last2)
1.141 *__first1++ = *__first2++;
1.142 if (__first2 == __last2)
1.143 erase(__first1, __last1);
1.144 @@ -126,12 +127,17 @@
1.145 erase(__i, end());
1.146 }
1.147
1.148 -template <class _Tp, class _Alloc, class _Predicate>
1.149 +#if !defined (list)
1.150 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.151 +#endif
1.152 +
1.153 +template <class _Tp, class _Alloc, class _Predicate>
1.154 void _S_remove_if(list<_Tp, _Alloc>& __that, _Predicate __pred) {
1.155 - typename list<_Tp, _Alloc>::iterator __first = __that.begin();
1.156 - typename list<_Tp, _Alloc>::iterator __last = __that.end();
1.157 + typedef typename list<_Tp, _Alloc>::iterator _Literator;
1.158 + _Literator __first = __that.begin();
1.159 + _Literator __last = __that.end();
1.160 while (__first != __last) {
1.161 - typename list<_Tp, _Alloc>::iterator __next = __first;
1.162 + _Literator __next = __first;
1.163 ++__next;
1.164 if (__pred(*__first)) __that.erase(__first);
1.165 __first = __next;
1.166 @@ -140,10 +146,11 @@
1.167
1.168 template <class _Tp, class _Alloc, class _BinaryPredicate>
1.169 void _S_unique(list<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred) {
1.170 - typename list<_Tp, _Alloc>::iterator __first = __that.begin();
1.171 - typename list<_Tp, _Alloc>::iterator __last = __that.end();
1.172 + typedef typename list<_Tp, _Alloc>::iterator _Literator;
1.173 + _Literator __first = __that.begin();
1.174 + _Literator __last = __that.end();
1.175 if (__first == __last) return;
1.176 - typename list<_Tp, _Alloc>::iterator __next = __first;
1.177 + _Literator __next = __first;
1.178 while (++__next != __last) {
1.179 if (__binary_pred(*__first, *__next))
1.180 __that.erase(__next);
1.181 @@ -155,93 +162,80 @@
1.182
1.183 template <class _Tp, class _Alloc, class _StrictWeakOrdering>
1.184 void _S_merge(list<_Tp, _Alloc>& __that, list<_Tp, _Alloc>& __x,
1.185 - _StrictWeakOrdering __comp) {
1.186 + _StrictWeakOrdering __comp) {
1.187 typedef typename list<_Tp, _Alloc>::iterator _Literator;
1.188 _Literator __first1 = __that.begin();
1.189 _Literator __last1 = __that.end();
1.190 _Literator __first2 = __x.begin();
1.191 _Literator __last2 = __x.end();
1.192 - while (__first1 != __last1 && __first2 != __last2)
1.193 - if (__comp(*__first2, *__first1)) {
1.194 - _Literator __next = __first2;
1.195 - _List_global_inst::_Transfer(__first1._M_node, __first2._M_node, (++__next)._M_node);
1.196 - __first2 = __next;
1.197 + if (__that.get_allocator() == __x.get_allocator()) {
1.198 + while (__first1 != __last1 && __first2 != __last2) {
1.199 + if (__comp(*__first2, *__first1)) {
1.200 + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.201 + _Literator __next = __first2;
1.202 + _List_global_inst::_Transfer(__first1._M_node, __first2._M_node, (++__next)._M_node);
1.203 + __first2 = __next;
1.204 + }
1.205 + else
1.206 + ++__first1;
1.207 }
1.208 - else
1.209 - ++__first1;
1.210 - if (__first2 != __last2) _List_global_inst::_Transfer(__last1._M_node, __first2._M_node, __last2._M_node);
1.211 + if (__first2 != __last2)
1.212 + _List_global_inst::_Transfer(__last1._M_node, __first2._M_node, __last2._M_node);
1.213 + }
1.214 + else {
1.215 + while (__first1 != __last1 && __first2 != __last2) {
1.216 + if (__comp(*__first2, *__first1)) {
1.217 + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.218 + __first1 = __that.insert(__first1, *__first2);
1.219 + }
1.220 + else
1.221 + ++__first1;
1.222 + }
1.223 + if (__first2 != __last2) {
1.224 + __that.insert(__first1, __first2, __last2);
1.225 + }
1.226 + __x.clear();
1.227 + }
1.228 }
1.229
1.230 template <class _Tp, class _Alloc, class _StrictWeakOrdering>
1.231 void _S_sort(list<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp) {
1.232 // Do nothing if the list has length 0 or 1.
1.233 - if (__that._M_node._M_data->_M_next != __that._M_node._M_data &&
1.234 - (__that._M_node._M_data->_M_next)->_M_next != __that._M_node._M_data) {
1.235 + if (__that._M_node._M_data._M_next == &__that._M_node._M_data ||
1.236 + __that._M_node._M_data._M_next->_M_next == &__that._M_node._M_data)
1.237 + return;
1.238
1.239 -#if !defined (__WATCOMC__)
1.240 -#ifdef _STLP_USE_TRAP_LEAVE
1.241 - typedef vector<list<_Tp, _Alloc>*, _Alloc> _TmpVec;
1.242 - _TmpVec* __pTmp = new _TmpVec();
1.243 - _TmpVec& __counter = *__pTmp;
1.244 - for (int i = 0; 1< 64; ++i) {
1.245 - list<_Tp, _Alloc>* __pTmp2 = new list<_Tp, _Alloc>;
1.246 - __counter.push_back (__pTmp2);
1.247 + list<_Tp, _Alloc> __carry(__that.get_allocator());
1.248 + const int NB = 64;
1.249 + _STLP_PRIV _CArray<list<_Tp, _Alloc>, NB> __counter(__carry);
1.250 + int __fill = 0;
1.251 + while (!__that.empty()) {
1.252 + __carry.splice(__carry.begin(), __that, __that.begin());
1.253 + int __i = 0;
1.254 + while (__i < __fill && !__counter[__i].empty()) {
1.255 + _S_merge(__counter[__i], __carry, __comp);
1.256 + __carry.swap(__counter[__i++]);
1.257 }
1.258 - list<_Tp, _Alloc>* __pcarry = new list<_Tp, _Alloc>;
1.259 - list<_Tp, _Alloc>& __carry = *__pcarry;
1.260 -#else
1.261 - list<_Tp, _Alloc> __counter[64];
1.262 - list<_Tp, _Alloc> __carry;
1.263 -#endif
1.264 -#else
1.265 - list<_Tp, _Alloc> __carry;
1.266 - __vector__<list<_Tp, _Alloc>, _Alloc> __counter(64);
1.267 -#endif
1.268 - int __fill = 0;
1.269 -#ifdef _STLP_USE_TRAP_LEAVE
1.270 - while (!__that.empty()) {
1.271 - __carry.splice(__carry.begin(), __that, __that.begin());
1.272 - int __i = 0;
1.273 + __carry.swap(__counter[__i]);
1.274 + if (__i == __fill) {
1.275 + ++__fill;
1.276 + if (__fill >= NB) {
1.277 + //Looks like the list has too many elements to be sorted with this algorithm:
1.278 + __stl_throw_overflow_error("list::sort");
1.279 + }
1.280 + }
1.281 + }
1.282
1.283 - while(__i < __fill && !__counter[__i]->empty()) {
1.284 - _S_merge(*__counter[__i], __carry, __comp);
1.285 - __carry.swap(*__counter[__i++]);
1.286 - }
1.287 - __carry.swap(*__counter[__i]);
1.288 - if (__i == __fill) ++__fill;
1.289 - }
1.290 -
1.291 - for (int __i = 1; __i < __fill; ++__i)
1.292 - _S_merge(*__counter[__i], *__counter[__i-1], __comp);
1.293 - __that.swap(*__counter[__fill-1]);
1.294 -
1.295 - // those objects won't just go away
1.296 - __counter.clear();
1.297 - CleanupStack::Pop(66);
1.298 - }
1.299 -# else
1.300 - while (!__that.empty()) {
1.301 - __carry.splice(__carry.begin(), __that, __that.begin());
1.302 - int __i = 0;
1.303 -
1.304 - while(__i < __fill && !__counter[__i].empty()) {
1.305 - _S_merge(__counter[__i], __carry, __comp);
1.306 - __carry.swap(__counter[__i++]);
1.307 - }
1.308 - __carry.swap(__counter[__i]);
1.309 - if (__i == __fill) ++__fill;
1.310 - }
1.311 -
1.312 - for (int __i = 1; __i < __fill; ++__i)
1.313 - _S_merge(__counter[__i], __counter[__i-1], __comp);
1.314 - __that.swap(__counter[__fill-1]);
1.315 - }
1.316 -# endif
1.317 -
1.318 + for (int __i = 1; __i < __fill; ++__i)
1.319 + _S_merge(__counter[__i], __counter[__i - 1], __comp);
1.320 + __that.swap(__counter[__fill - 1]);
1.321 }
1.322
1.323 -# undef list
1.324 -# undef size_type
1.325 +#if defined (list)
1.326 +# undef list
1.327 +#endif
1.328 +
1.329 +_STLP_MOVE_TO_STD_NAMESPACE
1.330
1.331 _STLP_END_NAMESPACE
1.332