1117397Skan// List implementation (out of line) -*- C++ -*- 2117397Skan 3169691Skan// Copyright (C) 2001, 2002, 2003, 2004, 2005, 2006 4169691Skan// Free Software Foundation, Inc. 5117397Skan// 6117397Skan// This file is part of the GNU ISO C++ Library. This library is free 7117397Skan// software; you can redistribute it and/or modify it under the 8117397Skan// terms of the GNU General Public License as published by the 9117397Skan// Free Software Foundation; either version 2, or (at your option) 10117397Skan// any later version. 11117397Skan 12117397Skan// This library is distributed in the hope that it will be useful, 13117397Skan// but WITHOUT ANY WARRANTY; without even the implied warranty of 14117397Skan// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 15117397Skan// GNU General Public License for more details. 16117397Skan 17117397Skan// You should have received a copy of the GNU General Public License along 18117397Skan// with this library; see the file COPYING. If not, write to the Free 19169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 20117397Skan// USA. 21117397Skan 22117397Skan// As a special exception, you may use this file as part of a free software 23117397Skan// library without restriction. Specifically, if other files instantiate 24117397Skan// templates or use macros or inline functions from this file, or you compile 25117397Skan// this file and link it with other files to produce an executable, this 26117397Skan// file does not by itself cause the resulting executable to be covered by 27117397Skan// the GNU General Public License. This exception does not however 28117397Skan// invalidate any other reasons why the executable file might be covered by 29117397Skan// the GNU General Public License. 30117397Skan 31117397Skan/* 32117397Skan * 33117397Skan * Copyright (c) 1994 34117397Skan * Hewlett-Packard Company 35117397Skan * 36117397Skan * Permission to use, copy, modify, distribute and sell this software 37117397Skan * and its documentation for any purpose is hereby granted without fee, 38117397Skan * provided that the above copyright notice appear in all copies and 39117397Skan * that both that copyright notice and this permission notice appear 40117397Skan * in supporting documentation. Hewlett-Packard Company makes no 41117397Skan * representations about the suitability of this software for any 42117397Skan * purpose. It is provided "as is" without express or implied warranty. 43117397Skan * 44117397Skan * 45117397Skan * Copyright (c) 1996,1997 46117397Skan * Silicon Graphics Computer Systems, Inc. 47117397Skan * 48117397Skan * Permission to use, copy, modify, distribute and sell this software 49117397Skan * and its documentation for any purpose is hereby granted without fee, 50117397Skan * provided that the above copyright notice appear in all copies and 51117397Skan * that both that copyright notice and this permission notice appear 52117397Skan * in supporting documentation. Silicon Graphics makes no 53117397Skan * representations about the suitability of this software for any 54117397Skan * purpose. It is provided "as is" without express or implied warranty. 55117397Skan */ 56117397Skan 57117397Skan/** @file list.tcc 58117397Skan * This is an internal header file, included by other library headers. 59117397Skan * You should not attempt to use it directly. 60117397Skan */ 61117397Skan 62132720Skan#ifndef _LIST_TCC 63132720Skan#define _LIST_TCC 1 64117397Skan 65169691Skan_GLIBCXX_BEGIN_NESTED_NAMESPACE(std, _GLIBCXX_STD) 66169691Skan 67117397Skan template<typename _Tp, typename _Alloc> 68117397Skan void 69169691Skan _List_base<_Tp, _Alloc>:: 70132720Skan _M_clear() 71117397Skan { 72117397Skan typedef _List_node<_Tp> _Node; 73132720Skan _Node* __cur = static_cast<_Node*>(this->_M_impl._M_node._M_next); 74132720Skan while (__cur != &this->_M_impl._M_node) 75169691Skan { 76169691Skan _Node* __tmp = __cur; 77169691Skan __cur = static_cast<_Node*>(__cur->_M_next); 78169691Skan _M_get_Tp_allocator().destroy(&__tmp->_M_data); 79169691Skan _M_put_node(__tmp); 80169691Skan } 81117397Skan } 82132720Skan 83117397Skan template<typename _Tp, typename _Alloc> 84169691Skan typename list<_Tp, _Alloc>::iterator 85169691Skan list<_Tp, _Alloc>:: 86117397Skan insert(iterator __position, const value_type& __x) 87117397Skan { 88117397Skan _Node* __tmp = _M_create_node(__x); 89132720Skan __tmp->hook(__position._M_node); 90169691Skan return iterator(__tmp); 91117397Skan } 92132720Skan 93117397Skan template<typename _Tp, typename _Alloc> 94169691Skan typename list<_Tp, _Alloc>::iterator 95169691Skan list<_Tp, _Alloc>:: 96117397Skan erase(iterator __position) 97117397Skan { 98169691Skan iterator __ret = iterator(__position._M_node->_M_next); 99132720Skan _M_erase(__position); 100132720Skan return __ret; 101117397Skan } 102132720Skan 103117397Skan template<typename _Tp, typename _Alloc> 104117397Skan void 105169691Skan list<_Tp, _Alloc>:: 106169691Skan resize(size_type __new_size, value_type __x) 107117397Skan { 108117397Skan iterator __i = begin(); 109117397Skan size_type __len = 0; 110169691Skan for (; __i != end() && __len < __new_size; ++__i, ++__len) 111117397Skan ; 112117397Skan if (__len == __new_size) 113117397Skan erase(__i, end()); 114117397Skan else // __i == end() 115117397Skan insert(end(), __new_size - __len, __x); 116117397Skan } 117132720Skan 118117397Skan template<typename _Tp, typename _Alloc> 119169691Skan list<_Tp, _Alloc>& 120169691Skan list<_Tp, _Alloc>:: 121117397Skan operator=(const list& __x) 122117397Skan { 123117397Skan if (this != &__x) 124132720Skan { 125132720Skan iterator __first1 = begin(); 126132720Skan iterator __last1 = end(); 127132720Skan const_iterator __first2 = __x.begin(); 128132720Skan const_iterator __last2 = __x.end(); 129169691Skan for (; __first1 != __last1 && __first2 != __last2; 130169691Skan ++__first1, ++__first2) 131169691Skan *__first1 = *__first2; 132132720Skan if (__first2 == __last2) 133132720Skan erase(__first1, __last1); 134132720Skan else 135132720Skan insert(__last1, __first2, __last2); 136132720Skan } 137117397Skan return *this; 138117397Skan } 139132720Skan 140117397Skan template<typename _Tp, typename _Alloc> 141117397Skan void 142169691Skan list<_Tp, _Alloc>:: 143117397Skan _M_fill_assign(size_type __n, const value_type& __val) 144117397Skan { 145117397Skan iterator __i = begin(); 146169691Skan for (; __i != end() && __n > 0; ++__i, --__n) 147117397Skan *__i = __val; 148117397Skan if (__n > 0) 149117397Skan insert(end(), __n, __val); 150117397Skan else 151117397Skan erase(__i, end()); 152117397Skan } 153132720Skan 154117397Skan template<typename _Tp, typename _Alloc> 155132720Skan template <typename _InputIterator> 156117397Skan void 157169691Skan list<_Tp, _Alloc>:: 158132720Skan _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2, 159132720Skan __false_type) 160117397Skan { 161117397Skan iterator __first1 = begin(); 162117397Skan iterator __last1 = end(); 163132720Skan for (; __first1 != __last1 && __first2 != __last2; 164132720Skan ++__first1, ++__first2) 165117397Skan *__first1 = *__first2; 166117397Skan if (__first2 == __last2) 167117397Skan erase(__first1, __last1); 168117397Skan else 169117397Skan insert(__last1, __first2, __last2); 170117397Skan } 171132720Skan 172117397Skan template<typename _Tp, typename _Alloc> 173117397Skan void 174169691Skan list<_Tp, _Alloc>:: 175117397Skan remove(const value_type& __value) 176117397Skan { 177117397Skan iterator __first = begin(); 178117397Skan iterator __last = end(); 179117397Skan while (__first != __last) 180169691Skan { 181169691Skan iterator __next = __first; 182169691Skan ++__next; 183169691Skan if (*__first == __value) 184169691Skan _M_erase(__first); 185169691Skan __first = __next; 186169691Skan } 187117397Skan } 188132720Skan 189117397Skan template<typename _Tp, typename _Alloc> 190117397Skan void 191169691Skan list<_Tp, _Alloc>:: 192117397Skan unique() 193117397Skan { 194117397Skan iterator __first = begin(); 195117397Skan iterator __last = end(); 196132720Skan if (__first == __last) 197132720Skan return; 198117397Skan iterator __next = __first; 199117397Skan while (++__next != __last) 200169691Skan { 201169691Skan if (*__first == *__next) 202169691Skan _M_erase(__next); 203169691Skan else 204169691Skan __first = __next; 205169691Skan __next = __first; 206169691Skan } 207117397Skan } 208132720Skan 209117397Skan template<typename _Tp, typename _Alloc> 210117397Skan void 211169691Skan list<_Tp, _Alloc>:: 212117397Skan merge(list& __x) 213117397Skan { 214132720Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 215132720Skan // 300. list::merge() specification incomplete 216132720Skan if (this != &__x) 217132720Skan { 218169691Skan _M_check_equal_allocators(__x); 219169691Skan 220132720Skan iterator __first1 = begin(); 221132720Skan iterator __last1 = end(); 222132720Skan iterator __first2 = __x.begin(); 223132720Skan iterator __last2 = __x.end(); 224132720Skan while (__first1 != __last1 && __first2 != __last2) 225132720Skan if (*__first2 < *__first1) 226132720Skan { 227132720Skan iterator __next = __first2; 228132720Skan _M_transfer(__first1, __first2, ++__next); 229132720Skan __first2 = __next; 230132720Skan } 231132720Skan else 232132720Skan ++__first1; 233132720Skan if (__first2 != __last2) 234132720Skan _M_transfer(__last1, __first2, __last2); 235132720Skan } 236117397Skan } 237132720Skan 238117397Skan template<typename _Tp, typename _Alloc> 239169691Skan template <typename _StrictWeakOrdering> 240169691Skan void 241169691Skan list<_Tp, _Alloc>:: 242169691Skan merge(list& __x, _StrictWeakOrdering __comp) 243169691Skan { 244169691Skan // _GLIBCXX_RESOLVE_LIB_DEFECTS 245169691Skan // 300. list::merge() specification incomplete 246169691Skan if (this != &__x) 247169691Skan { 248169691Skan _M_check_equal_allocators(__x); 249169691Skan 250169691Skan iterator __first1 = begin(); 251169691Skan iterator __last1 = end(); 252169691Skan iterator __first2 = __x.begin(); 253169691Skan iterator __last2 = __x.end(); 254169691Skan while (__first1 != __last1 && __first2 != __last2) 255169691Skan if (__comp(*__first2, *__first1)) 256169691Skan { 257169691Skan iterator __next = __first2; 258169691Skan _M_transfer(__first1, __first2, ++__next); 259169691Skan __first2 = __next; 260169691Skan } 261169691Skan else 262169691Skan ++__first1; 263169691Skan if (__first2 != __last2) 264169691Skan _M_transfer(__last1, __first2, __last2); 265169691Skan } 266169691Skan } 267169691Skan 268169691Skan template<typename _Tp, typename _Alloc> 269117397Skan void 270169691Skan list<_Tp, _Alloc>:: 271117397Skan sort() 272117397Skan { 273117397Skan // Do nothing if the list has length 0 or 1. 274132720Skan if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 275132720Skan && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 276117397Skan { 277117397Skan list __carry; 278132720Skan list __tmp[64]; 279132720Skan list * __fill = &__tmp[0]; 280132720Skan list * __counter; 281132720Skan 282132720Skan do 283132720Skan { 284132720Skan __carry.splice(__carry.begin(), *this, begin()); 285132720Skan 286132720Skan for(__counter = &__tmp[0]; 287169691Skan __counter != __fill && !__counter->empty(); 288132720Skan ++__counter) 289132720Skan { 290132720Skan __counter->merge(__carry); 291132720Skan __carry.swap(*__counter); 292132720Skan } 293132720Skan __carry.swap(*__counter); 294132720Skan if (__counter == __fill) 295132720Skan ++__fill; 296132720Skan } 297132720Skan while ( !empty() ); 298132720Skan 299169691Skan for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 300169691Skan __counter->merge(*(__counter - 1)); 301169691Skan swap( *(__fill - 1) ); 302117397Skan } 303117397Skan } 304132720Skan 305117397Skan template<typename _Tp, typename _Alloc> 306117397Skan template <typename _Predicate> 307117397Skan void 308169691Skan list<_Tp, _Alloc>:: 309117397Skan remove_if(_Predicate __pred) 310117397Skan { 311117397Skan iterator __first = begin(); 312117397Skan iterator __last = end(); 313117397Skan while (__first != __last) 314169691Skan { 315169691Skan iterator __next = __first; 316169691Skan ++__next; 317169691Skan if (__pred(*__first)) 318169691Skan _M_erase(__first); 319169691Skan __first = __next; 320169691Skan } 321117397Skan } 322132720Skan 323117397Skan template<typename _Tp, typename _Alloc> 324117397Skan template <typename _BinaryPredicate> 325117397Skan void 326169691Skan list<_Tp, _Alloc>:: 327117397Skan unique(_BinaryPredicate __binary_pred) 328117397Skan { 329117397Skan iterator __first = begin(); 330117397Skan iterator __last = end(); 331169691Skan if (__first == __last) 332169691Skan return; 333117397Skan iterator __next = __first; 334117397Skan while (++__next != __last) 335132720Skan { 336169691Skan if (__binary_pred(*__first, *__next)) 337169691Skan _M_erase(__next); 338169691Skan else 339169691Skan __first = __next; 340169691Skan __next = __first; 341132720Skan } 342117397Skan } 343132720Skan 344117397Skan template<typename _Tp, typename _Alloc> 345117397Skan template <typename _StrictWeakOrdering> 346132720Skan void 347169691Skan list<_Tp, _Alloc>:: 348132720Skan sort(_StrictWeakOrdering __comp) 349117397Skan { 350132720Skan // Do nothing if the list has length 0 or 1. 351132720Skan if (this->_M_impl._M_node._M_next != &this->_M_impl._M_node 352132720Skan && this->_M_impl._M_node._M_next->_M_next != &this->_M_impl._M_node) 353132720Skan { 354132720Skan list __carry; 355132720Skan list __tmp[64]; 356132720Skan list * __fill = &__tmp[0]; 357132720Skan list * __counter; 358132720Skan 359132720Skan do 360132720Skan { 361132720Skan __carry.splice(__carry.begin(), *this, begin()); 362132720Skan 363132720Skan for(__counter = &__tmp[0]; 364169691Skan __counter != __fill && !__counter->empty(); 365132720Skan ++__counter) 366132720Skan { 367132720Skan __counter->merge(__carry, __comp); 368132720Skan __carry.swap(*__counter); 369132720Skan } 370132720Skan __carry.swap(*__counter); 371132720Skan if (__counter == __fill) 372132720Skan ++__fill; 373132720Skan } 374132720Skan while ( !empty() ); 375132720Skan 376169691Skan for (__counter = &__tmp[1]; __counter != __fill; ++__counter) 377169691Skan __counter->merge(*(__counter - 1), __comp); 378169691Skan swap(*(__fill - 1)); 379132720Skan } 380117397Skan } 381117397Skan 382169691Skan_GLIBCXX_END_NESTED_NAMESPACE 383169691Skan 384132720Skan#endif /* _LIST_TCC */ 385132720Skan 386