1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/tools/stlport/stl/_list.c Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,246 @@
1.4 +/*
1.5 + *
1.6 + *
1.7 + * Copyright (c) 1994
1.8 + * Hewlett-Packard Company
1.9 + *
1.10 + * Copyright (c) 1996,1997
1.11 + * Silicon Graphics Computer Systems, Inc.
1.12 + *
1.13 + * Copyright (c) 1997
1.14 + * Moscow Center for SPARC Technology
1.15 + *
1.16 + * Copyright (c) 1999
1.17 + * Boris Fomitchev
1.18 + *
1.19 + * This material is provided "as is", with absolutely no warranty expressed
1.20 + * or implied. Any use is at your own risk.
1.21 + *
1.22 + * Permission to use or copy this software for any purpose is hereby granted
1.23 + * without fee, provided the above notices are retained on all copies.
1.24 + * Permission to modify the code and to distribute modified code is granted,
1.25 + * provided the above notices are retained, and a notice that the code was
1.26 + * modified is included with the above copyright notice.
1.27 + *
1.28 + */
1.29 +#ifndef _STLP_LIST_C
1.30 +#define _STLP_LIST_C
1.31 +
1.32 +#ifndef _STLP_INTERNAL_LIST_H
1.33 +# include <stl/_list.h>
1.34 +#endif
1.35 +
1.36 +#ifndef _STLP_CARRAY_H
1.37 +# include <stl/_carray.h>
1.38 +#endif
1.39 +
1.40 +#ifndef _STLP_RANGE_ERRORS_H
1.41 +# include <stl/_range_errors.h>
1.42 +#endif
1.43 +
1.44 +_STLP_BEGIN_NAMESPACE
1.45 +
1.46 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.47 +
1.48 +#if defined (_STLP_EXPOSE_GLOBALS_IMPLEMENTATION)
1.49 +template <class _Dummy>
1.50 +void _STLP_CALL
1.51 +_List_global<_Dummy>::_Transfer(_List_node_base* __position,
1.52 + _List_node_base* __first, _List_node_base* __last) {
1.53 + if (__position != __last) {
1.54 + // Remove [first, last) from its old position.
1.55 + __last->_M_prev->_M_next = __position;
1.56 + __first->_M_prev->_M_next = __last;
1.57 + __position->_M_prev->_M_next = __first;
1.58 +
1.59 + // Splice [first, last) into its new position.
1.60 + _Node_base* __tmp = __position->_M_prev;
1.61 + __position->_M_prev = __last->_M_prev;
1.62 + __last->_M_prev = __first->_M_prev;
1.63 + __first->_M_prev = __tmp;
1.64 + }
1.65 +}
1.66 +#endif /* _STLP_EXPOSE_GLOBALS_IMPLEMENTATION */
1.67 +
1.68 +template <class _Tp, class _Alloc>
1.69 +void _List_base<_Tp,_Alloc>::clear() {
1.70 + _Node* __cur = __STATIC_CAST(_Node*, _M_node._M_data._M_next);
1.71 + while (__cur != &(_M_node._M_data)) {
1.72 + _Node* __tmp = __cur;
1.73 + __cur = __STATIC_CAST(_Node*, __cur->_M_next);
1.74 + _STLP_STD::_Destroy(&__tmp->_M_data);
1.75 + this->_M_node.deallocate(__tmp, 1);
1.76 + }
1.77 + _M_node._M_data._M_next = &_M_node._M_data;
1.78 + _M_node._M_data._M_prev = &_M_node._M_data;
1.79 +}
1.80 +
1.81 +#if defined (_STLP_NESTED_TYPE_PARAM_BUG)
1.82 +# define size_type size_t
1.83 +#endif
1.84 +
1.85 +#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
1.86 +# define list _STLP_PTR_IMPL_NAME(list)
1.87 +#elif defined (_STLP_DEBUG)
1.88 +# define list _STLP_NON_DBG_NAME(list)
1.89 +#else
1.90 +_STLP_MOVE_TO_STD_NAMESPACE
1.91 +#endif
1.92 +
1.93 +template <class _Tp, class _Alloc>
1.94 +void list<_Tp, _Alloc>::resize(size_type __new_size, const _Tp& __x) {
1.95 + iterator __i = begin();
1.96 + size_type __len = 0;
1.97 + for ( ; __i != end() && __len < __new_size; ++__i, ++__len);
1.98 +
1.99 + if (__len == __new_size)
1.100 + erase(__i, end());
1.101 + else // __i == end()
1.102 + insert(end(), __new_size - __len, __x);
1.103 +}
1.104 +
1.105 +template <class _Tp, class _Alloc>
1.106 +list<_Tp, _Alloc>& list<_Tp, _Alloc>::operator=(const list<_Tp, _Alloc>& __x) {
1.107 + if (this != &__x) {
1.108 + iterator __first1 = begin();
1.109 + iterator __last1 = end();
1.110 + const_iterator __first2 = __x.begin();
1.111 + const_iterator __last2 = __x.end();
1.112 + while (__first1 != __last1 && __first2 != __last2)
1.113 + *__first1++ = *__first2++;
1.114 + if (__first2 == __last2)
1.115 + erase(__first1, __last1);
1.116 + else
1.117 + insert(__last1, __first2, __last2);
1.118 + }
1.119 + return *this;
1.120 +}
1.121 +
1.122 +template <class _Tp, class _Alloc>
1.123 +void list<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) {
1.124 + iterator __i = begin();
1.125 + for ( ; __i != end() && __n > 0; ++__i, --__n)
1.126 + *__i = __val;
1.127 + if (__n > 0)
1.128 + insert(end(), __n, __val);
1.129 + else
1.130 + erase(__i, end());
1.131 +}
1.132 +
1.133 +#if !defined (list)
1.134 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.135 +#endif
1.136 +
1.137 +template <class _Tp, class _Alloc, class _Predicate>
1.138 +void _S_remove_if(list<_Tp, _Alloc>& __that, _Predicate __pred) {
1.139 + typedef typename list<_Tp, _Alloc>::iterator _Literator;
1.140 + _Literator __first = __that.begin();
1.141 + _Literator __last = __that.end();
1.142 + while (__first != __last) {
1.143 + _Literator __next = __first;
1.144 + ++__next;
1.145 + if (__pred(*__first)) __that.erase(__first);
1.146 + __first = __next;
1.147 + }
1.148 +}
1.149 +
1.150 +template <class _Tp, class _Alloc, class _BinaryPredicate>
1.151 +void _S_unique(list<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred) {
1.152 + typedef typename list<_Tp, _Alloc>::iterator _Literator;
1.153 + _Literator __first = __that.begin();
1.154 + _Literator __last = __that.end();
1.155 + if (__first == __last) return;
1.156 + _Literator __next = __first;
1.157 + while (++__next != __last) {
1.158 + if (__binary_pred(*__first, *__next))
1.159 + __that.erase(__next);
1.160 + else
1.161 + __first = __next;
1.162 + __next = __first;
1.163 + }
1.164 +}
1.165 +
1.166 +template <class _Tp, class _Alloc, class _StrictWeakOrdering>
1.167 +void _S_merge(list<_Tp, _Alloc>& __that, list<_Tp, _Alloc>& __x,
1.168 + _StrictWeakOrdering __comp) {
1.169 + typedef typename list<_Tp, _Alloc>::iterator _Literator;
1.170 + _Literator __first1 = __that.begin();
1.171 + _Literator __last1 = __that.end();
1.172 + _Literator __first2 = __x.begin();
1.173 + _Literator __last2 = __x.end();
1.174 + if (__that.get_allocator() == __x.get_allocator()) {
1.175 + while (__first1 != __last1 && __first2 != __last2) {
1.176 + if (__comp(*__first2, *__first1)) {
1.177 + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.178 + _Literator __next = __first2;
1.179 + _List_global_inst::_Transfer(__first1._M_node, __first2._M_node, (++__next)._M_node);
1.180 + __first2 = __next;
1.181 + }
1.182 + else
1.183 + ++__first1;
1.184 + }
1.185 + if (__first2 != __last2)
1.186 + _List_global_inst::_Transfer(__last1._M_node, __first2._M_node, __last2._M_node);
1.187 + }
1.188 + else {
1.189 + while (__first1 != __last1 && __first2 != __last2) {
1.190 + if (__comp(*__first2, *__first1)) {
1.191 + _STLP_VERBOSE_ASSERT(!__comp(*__first1, *__first2), _StlMsg_INVALID_STRICT_WEAK_PREDICATE)
1.192 + __first1 = __that.insert(__first1, *__first2);
1.193 + }
1.194 + else
1.195 + ++__first1;
1.196 + }
1.197 + if (__first2 != __last2) {
1.198 + __that.insert(__first1, __first2, __last2);
1.199 + }
1.200 + __x.clear();
1.201 + }
1.202 +}
1.203 +
1.204 +template <class _Tp, class _Alloc, class _StrictWeakOrdering>
1.205 +void _S_sort(list<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp) {
1.206 + // Do nothing if the list has length 0 or 1.
1.207 + if (__that._M_node._M_data._M_next == &__that._M_node._M_data ||
1.208 + __that._M_node._M_data._M_next->_M_next == &__that._M_node._M_data)
1.209 + return;
1.210 +
1.211 + list<_Tp, _Alloc> __carry(__that.get_allocator());
1.212 + const int NB = 64;
1.213 + _STLP_PRIV _CArray<list<_Tp, _Alloc>, NB> __counter(__carry);
1.214 + int __fill = 0;
1.215 + while (!__that.empty()) {
1.216 + __carry.splice(__carry.begin(), __that, __that.begin());
1.217 + int __i = 0;
1.218 + while (__i < __fill && !__counter[__i].empty()) {
1.219 + _S_merge(__counter[__i], __carry, __comp);
1.220 + __carry.swap(__counter[__i++]);
1.221 + }
1.222 + __carry.swap(__counter[__i]);
1.223 + if (__i == __fill) {
1.224 + ++__fill;
1.225 + if (__fill >= NB) {
1.226 + //Looks like the list has too many elements to be sorted with this algorithm:
1.227 + __stl_throw_overflow_error("list::sort");
1.228 + }
1.229 + }
1.230 + }
1.231 +
1.232 + for (int __i = 1; __i < __fill; ++__i)
1.233 + _S_merge(__counter[__i], __counter[__i - 1], __comp);
1.234 + __that.swap(__counter[__fill - 1]);
1.235 +}
1.236 +
1.237 +#if defined (list)
1.238 +# undef list
1.239 +#endif
1.240 +
1.241 +_STLP_MOVE_TO_STD_NAMESPACE
1.242 +
1.243 +_STLP_END_NAMESPACE
1.244 +
1.245 +#endif /* _STLP_LIST_C */
1.246 +
1.247 +// Local Variables:
1.248 +// mode:C++
1.249 +// End: