1 // List implementation (out of line) -*- C++ -*- 2 3 // Copyright (C) 2001, 2002, 2003, 2004 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 _LIST_TCC 62 #define _LIST_TCC 1 63 64 namespace _GLIBCXX_STD 65 { 66 template<typename _Tp, typename _Alloc> 67 void 68 _List_base<_Tp,_Alloc>:: 69 _M_clear() 70 { 71 typedef _List_node<_Tp> _Node; 72 _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next); 73 while (__cur != &this->_M_impl._M_node) 74 { 75 _Node* __tmp = __cur; 76 __cur = static_cast<_Node*>(__cur->_M_next); 77 std::_Destroy(&__tmp->_M_data); 78 _M_put_node(__tmp); 79 } 80 } 81 82 template<typename _Tp, typename _Alloc> 83 typename list<_Tp,_Alloc>::iterator 84 list<_Tp,_Alloc>:: 85 insert(iterator __position, const value_type& __x) 86 { 87 _Node* __tmp = _M_create_node(__x); 88 __tmp->hook(__position._M_node); 89 return __tmp; 90 } 91 92 template<typename _Tp, typename _Alloc> 93 typename list<_Tp,_Alloc>::iterator 94 list<_Tp,_Alloc>:: 95 erase(iterator __position) 96 { 97 iterator __ret = __position._M_node->_M_next; 98 _M_erase(__position); 99 return __ret; 100 } 101 102 template<typename _Tp, typename _Alloc> 103 void 104 list<_Tp,_Alloc>:: 105 resize(size_type __new_size, const value_type& __x) 106 { 107 iterator __i = begin(); 108 size_type __len = 0; 109 for ( ; __i != end() && __len < __new_size; ++__i, ++__len) 110 ; 111 if (__len == __new_size) 112 erase(__i, end()); 113 else // __i == end() 114 insert(end(), __new_size - __len, __x); 115 } 116 117 template<typename _Tp, typename _Alloc> 118 list<_Tp,_Alloc>& 119 list<_Tp,_Alloc>:: 120 operator=(const list& __x) 121 { 122 if (this != &__x) 123 { 124 iterator __first1 = begin(); 125 iterator __last1 = end(); 126 const_iterator __first2 = __x.begin(); 127 const_iterator __last2 = __x.end(); 128 while (__first1 != __last1 && __first2 != __last2) 129 *__first1++ = *__first2++; 130 if (__first2 == __last2) 131 erase(__first1, __last1); 132 else 133 insert(__last1, __first2, __last2); 134 } 135 return *this; 136 } 137 138 template<typename _Tp, typename _Alloc> 139 void 140 list<_Tp,_Alloc>:: 141 _M_fill_assign(size_type __n, const value_type& __val) 142 { 143 iterator __i = begin(); 144 for ( ; __i != end() && __n > 0; ++__i, --__n) 145 *__i = __val; 146 if (__n > 0) 147 insert(end(), __n, __val); 148 else 149 erase(__i, end()); 150 } 151 152 template<typename _Tp, typename _Alloc> 153 template <typename _InputIterator> 154 void 155 list<_Tp,_Alloc>:: 156 _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 157 __false_type) 158 { 159 iterator __first1 = begin(); 160 iterator __last1 = end(); 161 for (; __first1 != __last1 && __first2 != __last2; 162 ++__first1, ++__first2) 163 *__first1 = *__first2; 164 if (__first2 == __last2) 165 erase(__first1, __last1); 166 else 167 insert(__last1, __first2, __last2); 168 } 169 170 template<typename _Tp, typename _Alloc> 171 void 172 list<_Tp,_Alloc>:: 173 remove(const value_type& __value) 174 { 175 iterator __first = begin(); 176 iterator __last = end(); 177 while (__first != __last) 178 { 179 iterator __next = __first; 180 ++__next; 181 if (*__first == __value) 182 _M_erase(__first); 183 __first = __next; 184 } 185 } 186 187 template<typename _Tp, typename _Alloc> 188 void 189 list<_Tp,_Alloc>:: 190 unique() 191 { 192 iterator __first = begin(); 193 iterator __last = end(); 194 if (__first == __last) 195 return; 196 iterator __next = __first; 197 while (++__next != __last) 198 { 199 if (*__first == *__next) 200 _M_erase(__next); 201 else 202 __first = __next; 203 __next = __first; 204 } 205 } 206 207 template<typename _Tp, typename _Alloc> 208 void 209 list<_Tp,_Alloc>:: 210 merge(list& __x) 211 { 212 // _GLIBCXX_RESOLVE_LIB_DEFECTS 213 // 300. list::merge() specification incomplete 214 if (this != &__x) 215 { 216 iterator __first1 = begin(); 217 iterator __last1 = end(); 218 iterator __first2 = __x.begin(); 219 iterator __last2 = __x.end(); 220 while (__first1 != __last1 && __first2 != __last2) 221 if (*__first2 < *__first1) 222 { 223 iterator __next = __first2; 224 _M_transfer(__first1, __first2, ++__next); 225 __first2 = __next; 226 } 227 else 228 ++__first1; 229 if (__first2 != __last2) 230 _M_transfer(__last1, __first2, __last2); 231 } 232 } 233 234 template<typename _Tp, typename _Alloc> 235 void 236 list<_Tp,_Alloc>:: 237 sort() 238 { 239 // Do nothing if the list has length 0 or 1. 240 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 241 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 242 { 243 list __carry; 244 list __tmp[64]; 245 list * __fill = &__tmp[0]; 246 list * __counter; 247 248 do 249 { 250 __carry.splice(__carry.begin(), *this, begin()); 251 252 for(__counter = &__tmp[0]; 253 (__counter != __fill) && !__counter->empty(); 254 ++__counter) 255 { 256 __counter->merge(__carry); 257 __carry.swap(*__counter); 258 } 259 __carry.swap(*__counter); 260 if (__counter == __fill) 261 ++__fill; 262 } 263 while ( !empty() ); 264 265 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 266 __counter->merge( *(__counter-1) ); 267 swap( *(__fill-1) ); 268 } 269 } 270 271 template<typename _Tp, typename _Alloc> 272 template <typename _Predicate> 273 void 274 list<_Tp,_Alloc>:: 275 remove_if(_Predicate __pred) 276 { 277 iterator __first = begin(); 278 iterator __last = end(); 279 while (__first != __last) 280 { 281 iterator __next = __first; 282 ++__next; 283 if (__pred(*__first)) 284 _M_erase(__first); 285 __first = __next; 286 } 287 } 288 289 template<typename _Tp, typename _Alloc> 290 template <typename _BinaryPredicate> 291 void 292 list<_Tp,_Alloc>:: 293 unique(_BinaryPredicate __binary_pred) 294 { 295 iterator __first = begin(); 296 iterator __last = end(); 297 if (__first == __last) return; 298 iterator __next = __first; 299 while (++__next != __last) 300 { 301 if (__binary_pred(*__first, *__next)) 302 _M_erase(__next); 303 else 304 __first = __next; 305 __next = __first; 306 } 307 } 308 309 template<typename _Tp, typename _Alloc> 310 template <typename _StrictWeakOrdering> 311 void 312 list<_Tp,_Alloc>:: 313 merge(list& __x, _StrictWeakOrdering __comp) 314 { 315 // _GLIBCXX_RESOLVE_LIB_DEFECTS 316 // 300. list::merge() specification incomplete 317 if (this != &__x) 318 { 319 iterator __first1 = begin(); 320 iterator __last1 = end(); 321 iterator __first2 = __x.begin(); 322 iterator __last2 = __x.end(); 323 while (__first1 != __last1 && __first2 != __last2) 324 if (__comp(*__first2, *__first1)) 325 { 326 iterator __next = __first2; 327 _M_transfer(__first1, __first2, ++__next); 328 __first2 = __next; 329 } 330 else 331 ++__first1; 332 if (__first2 != __last2) 333 _M_transfer(__last1, __first2, __last2); 334 } 335 } 336 337 template<typename _Tp, typename _Alloc> 338 template <typename _StrictWeakOrdering> 339 void 340 list<_Tp,_Alloc>:: 341 sort(_StrictWeakOrdering __comp) 342 { 343 // Do nothing if the list has length 0 or 1. 344 if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 345 && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 346 { 347 list __carry; 348 list __tmp[64]; 349 list * __fill = &__tmp[0]; 350 list * __counter; 351 352 do 353 { 354 __carry.splice(__carry.begin(), *this, begin()); 355 356 for(__counter = &__tmp[0]; 357 (__counter != __fill) && !__counter->empty(); 358 ++__counter) 359 { 360 __counter->merge(__carry, __comp); 361 __carry.swap(*__counter); 362 } 363 __carry.swap(*__counter); 364 if (__counter == __fill) 365 ++__fill; 366 } 367 while ( !empty() ); 368 369 for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 370 __counter->merge( *(__counter-1), __comp ); 371 swap( *(__fill-1) ); 372 } 373 } 374 } // namespace std 375 376 #endif /* _LIST_TCC */ 377 378