list.tcc revision 132720
1117397Skan// List implementation (out of line) -*- C++ -*- 2117397Skan 3132720Skan// Copyright (C) 2001, 2002, 2003, 2004 Free Software Foundation, Inc. 4117397Skan// 5117397Skan// This file is part of the GNU ISO C++ Library. This library is free 6117397Skan// software; you can redistribute it and/or modify it under the 7117397Skan// terms of the GNU General Public License as published by the 8117397Skan// Free Software Foundation; either version 2, or (at your option) 9117397Skan// any later version. 10117397Skan 11117397Skan// This library is distributed in the hope that it will be useful, 12117397Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 13117397Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 14117397Skan// GNU General Public License for more details. 15117397Skan 16117397Skan// You should have received a copy of the GNU General Public License along 17117397Skan// with this library; see the file COPYING. If not, write to the Free 18117397Skan// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 19117397Skan// USA. 20117397Skan 21117397Skan// As a special exception, you may use this file as part of a free software 22117397Skan// library without restriction. Specifically, if other files instantiate 23117397Skan// templates or use macros or inline functions from this file, or you compile 24117397Skan// this file and link it with other files to produce an executable, this 25117397Skan// file does not by itself cause the resulting executable to be covered by 26117397Skan// the GNU General Public License. This exception does not however 27117397Skan// invalidate any other reasons why the executable file might be covered by 28117397Skan// the GNU General Public License. 29117397Skan 30117397Skan/* 31117397Skan * 32117397Skan * Copyright (c) 1994 33117397Skan * Hewlett-Packard Company 34117397Skan * 35117397Skan * Permission to use, copy, modify, distribute and sell this software 36117397Skan * and its documentation for any purpose is hereby granted without fee, 37117397Skan * provided that the above copyright notice appear in all copies and 38117397Skan * that both that copyright notice and this permission notice appear 39117397Skan * in supporting documentation. Hewlett-Packard Company makes no 40117397Skan * representations about the suitability of this software for any 41117397Skan * purpose. It is provided "as is" without express or implied warranty. 42117397Skan * 43117397Skan * 44117397Skan * Copyright (c) 1996,1997 45117397Skan * Silicon Graphics Computer Systems, Inc. 46117397Skan * 47117397Skan * Permission to use, copy, modify, distribute and sell this software 48117397Skan * and its documentation for any purpose is hereby granted without fee, 49117397Skan * provided that the above copyright notice appear in all copies and 50117397Skan * that both that copyright notice and this permission notice appear 51117397Skan * in supporting documentation. Silicon Graphics makes no 52117397Skan * representations about the suitability of this software for any 53117397Skan * purpose. It is provided "as is" without express or implied warranty. 54117397Skan */ 55117397Skan 56117397Skan/** @file list.tcc 57117397Skan * This is an internal header file, included by other library headers. 58117397Skan * You should not attempt to use it directly. 59117397Skan */ 60117397Skan 61132720Skan#ifndef _LIST_TCC 62132720Skan#define _LIST_TCC 1 63117397Skan 64132720Skannamespace _GLIBCXX_STD 65117397Skan{ 66117397Skan template<typename _Tp, typename _Alloc> 67117397Skan void 68117397Skan _List_base<_Tp,_Alloc>:: 69132720Skan _M_clear() 70117397Skan { 71117397Skan typedef _List_node<_Tp> _Node; 72132720Skan _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next); 73132720Skan while (__cur != &this->_M_impl._M_node) 74117397Skan { 75117397Skan _Node* __tmp = __cur; 76117397Skan __cur = static_cast<_Node*>(__cur->_M_next); 77132720Skan std::_Destroy(&__tmp->_M_data); 78117397Skan _M_put_node(__tmp); 79117397Skan } 80117397Skan } 81132720Skan 82117397Skan template<typename _Tp, typename _Alloc> 83117397Skan typename list<_Tp,_Alloc>::iterator 84117397Skan list<_Tp,_Alloc>:: 85117397Skan insert(iterator __position, const value_type& __x) 86117397Skan { 87117397Skan _Node* __tmp = _M_create_node(__x); 88132720Skan __tmp->hook(__position._M_node); 89117397Skan return __tmp; 90117397Skan } 91132720Skan 92117397Skan template<typename _Tp, typename _Alloc> 93117397Skan typename list<_Tp,_Alloc>::iterator 94117397Skan list<_Tp,_Alloc>:: 95117397Skan erase(iterator __position) 96117397Skan { 97132720Skan iterator __ret = __position._M_node->_M_next; 98132720Skan _M_erase(__position); 99132720Skan return __ret; 100117397Skan } 101132720Skan 102117397Skan template<typename _Tp, typename _Alloc> 103117397Skan void 104117397Skan list<_Tp,_Alloc>:: 105117397Skan resize(size_type __new_size, const value_type& __x) 106117397Skan { 107117397Skan iterator __i = begin(); 108117397Skan size_type __len = 0; 109117397Skan for ( ; __i != end() && __len < __new_size; ++__i, ++__len) 110117397Skan ; 111117397Skan if (__len == __new_size) 112117397Skan erase(__i, end()); 113117397Skan else // __i == end() 114117397Skan insert(end(), __new_size - __len, __x); 115117397Skan } 116132720Skan 117117397Skan template<typename _Tp, typename _Alloc> 118117397Skan list<_Tp,_Alloc>& 119117397Skan list<_Tp,_Alloc>:: 120117397Skan operator=(const list& __x) 121117397Skan { 122117397Skan if (this != &__x) 123132720Skan { 124132720Skan iterator __first1 = begin(); 125132720Skan iterator __last1 = end(); 126132720Skan const_iterator __first2 = __x.begin(); 127132720Skan const_iterator __last2 = __x.end(); 128132720Skan while (__first1 != __last1 && __first2 != __last2) 129132720Skan *__first1++ = *__first2++; 130132720Skan if (__first2 == __last2) 131132720Skan erase(__first1, __last1); 132132720Skan else 133132720Skan insert(__last1, __first2, __last2); 134132720Skan } 135117397Skan return *this; 136117397Skan } 137132720Skan 138117397Skan template<typename _Tp, typename _Alloc> 139117397Skan void 140117397Skan list<_Tp,_Alloc>:: 141117397Skan _M_fill_assign(size_type __n, const value_type& __val) 142117397Skan { 143117397Skan iterator __i = begin(); 144117397Skan for ( ; __i != end() && __n > 0; ++__i, --__n) 145117397Skan *__i = __val; 146117397Skan if (__n > 0) 147117397Skan insert(end(), __n, __val); 148117397Skan else 149117397Skan erase(__i, end()); 150117397Skan } 151132720Skan 152117397Skan template<typename _Tp, typename _Alloc> 153132720Skan template <typename _InputIterator> 154117397Skan void 155117397Skan list<_Tp,_Alloc>:: 156132720Skan _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 157132720Skan __false_type) 158117397Skan { 159117397Skan iterator __first1 = begin(); 160117397Skan iterator __last1 = end(); 161132720Skan for (; __first1 != __last1 && __first2 != __last2; 162132720Skan ++__first1, ++__first2) 163117397Skan *__first1 = *__first2; 164117397Skan if (__first2 == __last2) 165117397Skan erase(__first1, __last1); 166117397Skan else 167117397Skan insert(__last1, __first2, __last2); 168117397Skan } 169132720Skan 170117397Skan template<typename _Tp, typename _Alloc> 171117397Skan void 172117397Skan list<_Tp,_Alloc>:: 173117397Skan remove(const value_type& __value) 174117397Skan { 175117397Skan iterator __first = begin(); 176117397Skan iterator __last = end(); 177117397Skan while (__first != __last) 178117397Skan { 179117397Skan iterator __next = __first; 180117397Skan ++__next; 181117397Skan if (*__first == __value) 182132720Skan _M_erase(__first); 183117397Skan __first = __next; 184117397Skan } 185117397Skan } 186132720Skan 187117397Skan template<typename _Tp, typename _Alloc> 188117397Skan void 189117397Skan list<_Tp,_Alloc>:: 190117397Skan unique() 191117397Skan { 192117397Skan iterator __first = begin(); 193117397Skan iterator __last = end(); 194132720Skan if (__first == __last) 195132720Skan return; 196117397Skan iterator __next = __first; 197117397Skan while (++__next != __last) 198117397Skan { 199117397Skan if (*__first == *__next) 200132720Skan _M_erase(__next); 201117397Skan else 202117397Skan __first = __next; 203117397Skan __next = __first; 204117397Skan } 205117397Skan } 206132720Skan 207117397Skan template<typename _Tp, typename _Alloc> 208117397Skan void 209117397Skan list<_Tp,_Alloc>:: 210117397Skan merge(list& __x) 211117397Skan { 212132720Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 213132720Skan // 300. list::merge() specification incomplete 214132720Skan if (this != &__x) 215132720Skan { 216132720Skan iterator __first1 = begin(); 217132720Skan iterator __last1 = end(); 218132720Skan iterator __first2 = __x.begin(); 219132720Skan iterator __last2 = __x.end(); 220132720Skan while (__first1 != __last1 && __first2 != __last2) 221132720Skan if (*__first2 < *__first1) 222132720Skan { 223132720Skan iterator __next = __first2; 224132720Skan _M_transfer(__first1, __first2, ++__next); 225132720Skan __first2 = __next; 226132720Skan } 227132720Skan else 228132720Skan ++__first1; 229132720Skan if (__first2 != __last2) 230132720Skan _M_transfer(__last1, __first2, __last2); 231132720Skan } 232117397Skan } 233132720Skan 234117397Skan template<typename _Tp, typename _Alloc> 235117397Skan void 236117397Skan list<_Tp,_Alloc>:: 237117397Skan sort() 238117397Skan { 239117397Skan // Do nothing if the list has length 0 or 1. 240132720Skan if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 241132720Skan && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 242117397Skan { 243117397Skan list __carry; 244132720Skan list __tmp[64]; 245132720Skan list * __fill = &__tmp[0]; 246132720Skan list * __counter; 247132720Skan 248132720Skan do 249132720Skan { 250132720Skan __carry.splice(__carry.begin(), *this, begin()); 251132720Skan 252132720Skan for(__counter = &__tmp[0]; 253132720Skan (__counter != __fill) && !__counter->empty(); 254132720Skan ++__counter) 255132720Skan { 256132720Skan __counter->merge(__carry); 257132720Skan __carry.swap(*__counter); 258132720Skan } 259132720Skan __carry.swap(*__counter); 260132720Skan if (__counter == __fill) 261132720Skan ++__fill; 262132720Skan } 263132720Skan while ( !empty() ); 264132720Skan 265132720Skan for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 266132720Skan __counter->merge( *(__counter-1) ); 267132720Skan swap( *(__fill-1) ); 268117397Skan } 269117397Skan } 270132720Skan 271117397Skan template<typename _Tp, typename _Alloc> 272117397Skan template <typename _Predicate> 273117397Skan void 274117397Skan list<_Tp,_Alloc>:: 275117397Skan remove_if(_Predicate __pred) 276117397Skan { 277117397Skan iterator __first = begin(); 278117397Skan iterator __last = end(); 279117397Skan while (__first != __last) 280117397Skan { 281117397Skan iterator __next = __first; 282117397Skan ++__next; 283132720Skan if (__pred(*__first)) 284132720Skan _M_erase(__first); 285117397Skan __first = __next; 286117397Skan } 287117397Skan } 288132720Skan 289117397Skan template<typename _Tp, typename _Alloc> 290117397Skan template <typename _BinaryPredicate> 291117397Skan void 292117397Skan list<_Tp,_Alloc>:: 293117397Skan unique(_BinaryPredicate __binary_pred) 294117397Skan { 295117397Skan iterator __first = begin(); 296117397Skan iterator __last = end(); 297117397Skan if (__first == __last) return; 298117397Skan iterator __next = __first; 299117397Skan while (++__next != __last) 300117397Skan { 301117397Skan if (__binary_pred(*__first, *__next)) 302132720Skan _M_erase(__next); 303117397Skan else 304117397Skan __first = __next; 305117397Skan __next = __first; 306117397Skan } 307117397Skan } 308132720Skan 309117397Skan template<typename _Tp, typename _Alloc> 310117397Skan template <typename _StrictWeakOrdering> 311117397Skan void 312117397Skan list<_Tp,_Alloc>:: 313117397Skan merge(list& __x, _StrictWeakOrdering __comp) 314117397Skan { 315132720Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 316132720Skan // 300. list::merge() specification incomplete 317132720Skan if (this != &__x) 318132720Skan { 319132720Skan iterator __first1 = begin(); 320132720Skan iterator __last1 = end(); 321132720Skan iterator __first2 = __x.begin(); 322132720Skan iterator __last2 = __x.end(); 323132720Skan while (__first1 != __last1 && __first2 != __last2) 324132720Skan if (__comp(*__first2, *__first1)) 325132720Skan { 326132720Skan iterator __next = __first2; 327132720Skan _M_transfer(__first1, __first2, ++__next); 328132720Skan __first2 = __next; 329132720Skan } 330132720Skan else 331132720Skan ++__first1; 332132720Skan if (__first2 != __last2) 333132720Skan _M_transfer(__last1, __first2, __last2); 334132720Skan } 335117397Skan } 336132720Skan 337117397Skan template<typename _Tp, typename _Alloc> 338117397Skan template <typename _StrictWeakOrdering> 339132720Skan void 340132720Skan list<_Tp,_Alloc>:: 341132720Skan sort(_StrictWeakOrdering __comp) 342117397Skan { 343132720Skan // Do nothing if the list has length 0 or 1. 344132720Skan if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 345132720Skan && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 346132720Skan { 347132720Skan list __carry; 348132720Skan list __tmp[64]; 349132720Skan list * __fill = &__tmp[0]; 350132720Skan list * __counter; 351132720Skan 352132720Skan do 353132720Skan { 354132720Skan __carry.splice(__carry.begin(), *this, begin()); 355132720Skan 356132720Skan for(__counter = &__tmp[0]; 357132720Skan (__counter != __fill) && !__counter->empty(); 358132720Skan ++__counter) 359132720Skan { 360132720Skan __counter->merge(__carry, __comp); 361132720Skan __carry.swap(*__counter); 362132720Skan } 363132720Skan __carry.swap(*__counter); 364132720Skan if (__counter == __fill) 365132720Skan ++__fill; 366132720Skan } 367132720Skan while ( !empty() ); 368132720Skan 369132720Skan for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 370132720Skan __counter->merge( *(__counter-1), __comp ); 371132720Skan swap( *(__fill-1) ); 372132720Skan } 373117397Skan } 374117397Skan} // namespace std 375117397Skan 376132720Skan#endif /* _LIST_TCC */ 377132720Skan 378