1 // List implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001, 2002 Free Software Foundation, Inc. 4 // 5 // This file is part of the GNU ISO C++ Library. This library is free 6 // software; you can redistribute it and/or modify it under the 7 // terms of the GNU General Public License as published by the 8 // Free Software Foundation; either version 2, or (at your option) 9 // any later version. 10 11 // This library is distributed in the hope that it will be useful, 12 // but WITHOUT ANY WARRANTY; without even the implied warranty of 13 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14 // GNU General Public License for more details. 15 16 // You should have received a copy of the GNU General Public License along 17 // with this library; see the file COPYING. If not, write to the Free 18 // Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19 // USA. 20 21 // As a special exception, you may use this file as part of a free software 22 // library without restriction. Specifically, if other files instantiate 23 // templates or use macros or inline functions from this file, or you compile 24 // this file and link it with other files to produce an executable, this 25 // file does not by itself cause the resulting executable to be covered by 26 // the GNU General Public License. This exception does not however 27 // invalidate any other reasons why the executable file might be covered by 28 // the GNU General Public License. 29 30 /* 31 * 32 * Copyright (c) 1994 33 * Hewlett-Packard Company 34 * 35 * Permission to use, copy, modify, distribute and sell this software 36 * and its documentation for any purpose is hereby granted without fee, 37 * provided that the above copyright notice appear in all copies and 38 * that both that copyright notice and this permission notice appear 39 * in supporting documentation. Hewlett-Packard Company makes no 40 * representations about the suitability of this software for any 41 * purpose. It is provided "as is" without express or implied warranty. 42 * 43 * 44 * Copyright (c) 1996,1997 45 * Silicon Graphics Computer Systems, Inc. 46 * 47 * Permission to use, copy, modify, distribute and sell this software 48 * and its documentation for any purpose is hereby granted without fee, 49 * provided that the above copyright notice appear in all copies and 50 * that both that copyright notice and this permission notice appear 51 * in supporting documentation. Silicon Graphics makes no 52 * representations about the suitability of this software for any 53 * purpose. It is provided "as is" without express or implied warranty. 54 */ 55 56 /** @file list.tcc 57 * This is an internal header file, included by other library headers. 58 * You should not attempt to use it directly. 59 */ 60 61 #ifndef __GLIBCPP_INTERNAL_LIST_TCC 62 #define __GLIBCPP_INTERNAL_LIST_TCC 63 64 namespace std 65 { 66 template<typename _Tp, typename _Alloc> 67 void 68 _List_base<_Tp,_Alloc>:: __clear()69 __clear() 70 { 71 typedef _List_node<_Tp> _Node; 72 _Node* __cur = static_cast<_Node*>(_M_node->_M_next); 73 while (__cur != _M_node) 74 { 75 _Node* __tmp = __cur; 76 __cur = static_cast<_Node*>(__cur->_M_next); 77 _Destroy(&__tmp->_M_data); 78 _M_put_node(__tmp); 79 } 80 _M_node->_M_next = _M_node; 81 _M_node->_M_prev = _M_node; 82 } 83 84 template<typename _Tp, typename _Alloc> 85 typename list<_Tp,_Alloc>::iterator 86 list<_Tp,_Alloc>:: insert(iterator __position,const value_type & __x)87 insert(iterator __position, const value_type& __x) 88 { 89 _Node* __tmp = _M_create_node(__x); 90 __tmp->_M_next = __position._M_node; 91 __tmp->_M_prev = __position._M_node->_M_prev; 92 __position._M_node->_M_prev->_M_next = __tmp; 93 __position._M_node->_M_prev = __tmp; 94 return __tmp; 95 } 96 97 template<typename _Tp, typename _Alloc> 98 typename list<_Tp,_Alloc>::iterator 99 list<_Tp,_Alloc>:: erase(iterator __position)100 erase(iterator __position) 101 { 102 _List_node_base* __next_node = __position._M_node->_M_next; 103 _List_node_base* __prev_node = __position._M_node->_M_prev; 104 _Node* __n = static_cast<_Node*>(__position._M_node); 105 __prev_node->_M_next = __next_node; 106 __next_node->_M_prev = __prev_node; 107 _Destroy(&__n->_M_data); 108 _M_put_node(__n); 109 return iterator(static_cast<_Node*>(__next_node)); 110 } 111 112 template<typename _Tp, typename _Alloc> 113 void 114 list<_Tp,_Alloc>:: resize(size_type __new_size,const value_type & __x)115 resize(size_type __new_size, const value_type& __x) 116 { 117 iterator __i = begin(); 118 size_type __len = 0; 119 for ( ; __i != end() && __len < __new_size; ++__i, ++__len) 120 ; 121 if (__len == __new_size) 122 erase(__i, end()); 123 else // __i == end() 124 insert(end(), __new_size - __len, __x); 125 } 126 127 template<typename _Tp, typename _Alloc> 128 list<_Tp,_Alloc>& 129 list<_Tp,_Alloc>:: operator =(const list & __x)130 operator=(const list& __x) 131 { 132 if (this != &__x) 133 { 134 iterator __first1 = begin(); 135 iterator __last1 = end(); 136 const_iterator __first2 = __x.begin(); 137 const_iterator __last2 = __x.end(); 138 while (__first1 != __last1 && __first2 != __last2) 139 *__first1++ = *__first2++; 140 if (__first2 == __last2) 141 erase(__first1, __last1); 142 else 143 insert(__last1, __first2, __last2); 144 } 145 return *this; 146 } 147 148 template<typename _Tp, typename _Alloc> 149 void 150 list<_Tp,_Alloc>:: _M_fill_assign(size_type __n,const value_type & __val)151 _M_fill_assign(size_type __n, const value_type& __val) 152 { 153 iterator __i = begin(); 154 for ( ; __i != end() && __n > 0; ++__i, --__n) 155 *__i = __val; 156 if (__n > 0) 157 insert(end(), __n, __val); 158 else 159 erase(__i, end()); 160 } 161 162 template<typename _Tp, typename _Alloc> 163 template <typename _InputIter> 164 void 165 list<_Tp,_Alloc>:: _M_assign_dispatch(_InputIter __first2,_InputIter __last2,__false_type)166 _M_assign_dispatch(_InputIter __first2, _InputIter __last2, __false_type) 167 { 168 iterator __first1 = begin(); 169 iterator __last1 = end(); 170 for (; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2) 171 *__first1 = *__first2; 172 if (__first2 == __last2) 173 erase(__first1, __last1); 174 else 175 insert(__last1, __first2, __last2); 176 } 177 178 template<typename _Tp, typename _Alloc> 179 void 180 list<_Tp,_Alloc>:: remove(const value_type & __value)181 remove(const value_type& __value) 182 { 183 iterator __first = begin(); 184 iterator __last = end(); 185 while (__first != __last) 186 { 187 iterator __next = __first; 188 ++__next; 189 if (*__first == __value) 190 erase(__first); 191 __first = __next; 192 } 193 } 194 195 template<typename _Tp, typename _Alloc> 196 void 197 list<_Tp,_Alloc>:: unique()198 unique() 199 { 200 iterator __first = begin(); 201 iterator __last = end(); 202 if (__first == __last) return; 203 iterator __next = __first; 204 while (++__next != __last) 205 { 206 if (*__first == *__next) 207 erase(__next); 208 else 209 __first = __next; 210 __next = __first; 211 } 212 } 213 214 template<typename _Tp, typename _Alloc> 215 void 216 list<_Tp,_Alloc>:: merge(list & __x)217 merge(list& __x) 218 { 219 // _GLIBCXX_RESOLVE_LIB_DEFECTS 220 // 300. list::merge() specification incomplete 221 if (this != &__x) 222 { 223 iterator __first1 = begin(); 224 iterator __last1 = end(); 225 iterator __first2 = __x.begin(); 226 iterator __last2 = __x.end(); 227 while (__first1 != __last1 && __first2 != __last2) 228 if (*__first2 < *__first1) 229 { 230 iterator __next = __first2; 231 _M_transfer(__first1, __first2, ++__next); 232 __first2 = __next; 233 } 234 else 235 ++__first1; 236 if (__first2 != __last2) 237 _M_transfer(__last1, __first2, __last2); 238 } 239 } 240 241 // FIXME put this somewhere else 242 inline void __List_base_reverse(_List_node_base * __p)243 __List_base_reverse(_List_node_base* __p) 244 { 245 _List_node_base* __tmp = __p; 246 do { 247 std::swap(__tmp->_M_next, __tmp->_M_prev); 248 __tmp = __tmp->_M_prev; // Old next node is now prev. 249 } while (__tmp != __p); 250 } 251 252 template<typename _Tp, typename _Alloc> 253 void 254 list<_Tp,_Alloc>:: sort()255 sort() 256 { 257 // Do nothing if the list has length 0 or 1. 258 if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) 259 { 260 list __carry; 261 list __counter[64]; 262 int __fill = 0; 263 while (!empty()) 264 { 265 __carry.splice(__carry.begin(), *this, begin()); 266 int __i = 0; 267 while(__i < __fill && !__counter[__i].empty()) 268 { 269 __counter[__i].merge(__carry); 270 __carry.swap(__counter[__i++]); 271 } 272 __carry.swap(__counter[__i]); 273 if (__i == __fill) ++__fill; 274 } 275 276 for (int __i = 1; __i < __fill; ++__i) 277 __counter[__i].merge(__counter[__i-1]); 278 swap(__counter[__fill-1]); 279 } 280 } 281 282 template<typename _Tp, typename _Alloc> 283 template <typename _Predicate> 284 void 285 list<_Tp,_Alloc>:: remove_if(_Predicate __pred)286 remove_if(_Predicate __pred) 287 { 288 iterator __first = begin(); 289 iterator __last = end(); 290 while (__first != __last) 291 { 292 iterator __next = __first; 293 ++__next; 294 if (__pred(*__first)) erase(__first); 295 __first = __next; 296 } 297 } 298 299 template<typename _Tp, typename _Alloc> 300 template <typename _BinaryPredicate> 301 void 302 list<_Tp,_Alloc>:: unique(_BinaryPredicate __binary_pred)303 unique(_BinaryPredicate __binary_pred) 304 { 305 iterator __first = begin(); 306 iterator __last = end(); 307 if (__first == __last) return; 308 iterator __next = __first; 309 while (++__next != __last) 310 { 311 if (__binary_pred(*__first, *__next)) 312 erase(__next); 313 else 314 __first = __next; 315 __next = __first; 316 } 317 } 318 319 template<typename _Tp, typename _Alloc> 320 template <typename _StrictWeakOrdering> 321 void 322 list<_Tp,_Alloc>:: merge(list & __x,_StrictWeakOrdering __comp)323 merge(list& __x, _StrictWeakOrdering __comp) 324 { 325 // _GLIBCXX_RESOLVE_LIB_DEFECTS 326 // 300. list::merge() specification incomplete 327 if (this != &__x) 328 { 329 iterator __first1 = begin(); 330 iterator __last1 = end(); 331 iterator __first2 = __x.begin(); 332 iterator __last2 = __x.end(); 333 while (__first1 != __last1 && __first2 != __last2) 334 if (__comp(*__first2, *__first1)) 335 { 336 iterator __next = __first2; 337 _M_transfer(__first1, __first2, ++__next); 338 __first2 = __next; 339 } 340 else 341 ++__first1; 342 if (__first2 != __last2) _M_transfer(__last1, __first2, __last2); 343 } 344 } 345 346 template<typename _Tp, typename _Alloc> 347 template <typename _StrictWeakOrdering> 348 void 349 list<_Tp,_Alloc>:: sort(_StrictWeakOrdering __comp)350 sort(_StrictWeakOrdering __comp) 351 { 352 // Do nothing if the list has length 0 or 1. 353 if (_M_node->_M_next != _M_node && _M_node->_M_next->_M_next != _M_node) 354 { 355 list __carry; 356 list __counter[64]; 357 int __fill = 0; 358 while (!empty()) 359 { 360 __carry.splice(__carry.begin(), *this, begin()); 361 int __i = 0; 362 while(__i < __fill && !__counter[__i].empty()) 363 { 364 __counter[__i].merge(__carry, __comp); 365 __carry.swap(__counter[__i++]); 366 } 367 __carry.swap(__counter[__i]); 368 if (__i == __fill) ++__fill; 369 } 370 371 for (int __i = 1; __i < __fill; ++__i) 372 __counter[__i].merge(__counter[__i-1], __comp); 373 swap(__counter[__fill-1]); 374 } 375 } 376 } // namespace std 377 378 #endif /* __GLIBCPP_INTERNAL_LIST_TCC */ 379