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 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> 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> 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> 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> 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> 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> 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> 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
