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