slist revision 169691
197403Sobrien// Singly-linked list implementation -*- C++ -*- 297403Sobrien 3169691Skan// Copyright (C) 2001, 2002, 2004, 2005 Free Software Foundation, Inc. 497403Sobrien// 597403Sobrien// This file is part of the GNU ISO C++ Library. This library is free 697403Sobrien// software; you can redistribute it and/or modify it under the 797403Sobrien// terms of the GNU General Public License as published by the 897403Sobrien// Free Software Foundation; either version 2, or (at your option) 997403Sobrien// any later version. 1097403Sobrien 1197403Sobrien// This library is distributed in the hope that it will be useful, 1297403Sobrien// but WITHOUT ANY WARRANTY; without even the implied warranty of 1397403Sobrien// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the 1497403Sobrien// GNU General Public License for more details. 1597403Sobrien 1697403Sobrien// You should have received a copy of the GNU General Public License along 1797403Sobrien// with this library; see the file COPYING. If not, write to the Free 18169691Skan// Software Foundation, 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, 1997403Sobrien// USA. 2097403Sobrien 2197403Sobrien// As a special exception, you may use this file as part of a free software 2297403Sobrien// library without restriction. Specifically, if other files instantiate 2397403Sobrien// templates or use macros or inline functions from this file, or you compile 2497403Sobrien// this file and link it with other files to produce an executable, this 2597403Sobrien// file does not by itself cause the resulting executable to be covered by 2697403Sobrien// the GNU General Public License. This exception does not however 2797403Sobrien// invalidate any other reasons why the executable file might be covered by 2897403Sobrien// the GNU General Public License. 2997403Sobrien 3097403Sobrien/* 3197403Sobrien * Copyright (c) 1997 3297403Sobrien * Silicon Graphics Computer Systems, Inc. 3397403Sobrien * 3497403Sobrien * Permission to use, copy, modify, distribute and sell this software 3597403Sobrien * and its documentation for any purpose is hereby granted without fee, 3697403Sobrien * provided that the above copyright notice appear in all copies and 3797403Sobrien * that both that copyright notice and this permission notice appear 3897403Sobrien * in supporting documentation. Silicon Graphics makes no 3997403Sobrien * representations about the suitability of this software for any 4097403Sobrien * purpose. It is provided "as is" without express or implied warranty. 4197403Sobrien * 4297403Sobrien */ 4397403Sobrien 4497403Sobrien/** @file ext/slist 4597403Sobrien * This file is a GNU extension to the Standard C++ Library (possibly 46169691Skan * containing extensions from the HP/SGI STL subset). 4797403Sobrien */ 4897403Sobrien 49132720Skan#ifndef _SLIST 50132720Skan#define _SLIST 1 5197403Sobrien 5297403Sobrien#include <bits/stl_algobase.h> 53132720Skan#include <bits/allocator.h> 5497403Sobrien#include <bits/stl_construct.h> 5597403Sobrien#include <bits/stl_uninitialized.h> 5697403Sobrien#include <bits/concept_check.h> 5797403Sobrien 58169691Skan_GLIBCXX_BEGIN_NAMESPACE(__gnu_cxx) 5997403Sobrien 60169691Skan using std::size_t; 61169691Skan using std::ptrdiff_t; 62169691Skan using std::_Construct; 63169691Skan using std::_Destroy; 64169691Skan using std::allocator; 65169691Skan using std::__true_type; 66169691Skan using std::__false_type; 6797403Sobrien 68169691Skan struct _Slist_node_base 69169691Skan { 70169691Skan _Slist_node_base* _M_next; 71169691Skan }; 72169691Skan 73169691Skan inline _Slist_node_base* 74169691Skan __slist_make_link(_Slist_node_base* __prev_node, 75169691Skan _Slist_node_base* __new_node) 76169691Skan { 77169691Skan __new_node->_M_next = __prev_node->_M_next; 78169691Skan __prev_node->_M_next = __new_node; 79169691Skan return __new_node; 80169691Skan } 8197403Sobrien 82169691Skan inline _Slist_node_base* 83169691Skan __slist_previous(_Slist_node_base* __head, 84169691Skan const _Slist_node_base* __node) 85169691Skan { 86169691Skan while (__head && __head->_M_next != __node) 87169691Skan __head = __head->_M_next; 88169691Skan return __head; 89169691Skan } 9097403Sobrien 91169691Skan inline const _Slist_node_base* 92169691Skan __slist_previous(const _Slist_node_base* __head, 93169691Skan const _Slist_node_base* __node) 94169691Skan { 95169691Skan while (__head && __head->_M_next != __node) 96169691Skan __head = __head->_M_next; 97169691Skan return __head; 98169691Skan } 9997403Sobrien 100169691Skan inline void 101169691Skan __slist_splice_after(_Slist_node_base* __pos, 102169691Skan _Slist_node_base* __before_first, 103169691Skan _Slist_node_base* __before_last) 104169691Skan { 105169691Skan if (__pos != __before_first && __pos != __before_last) 106169691Skan { 107169691Skan _Slist_node_base* __first = __before_first->_M_next; 108169691Skan _Slist_node_base* __after = __pos->_M_next; 109169691Skan __before_first->_M_next = __before_last->_M_next; 110169691Skan __pos->_M_next = __first; 111169691Skan __before_last->_M_next = __after; 112169691Skan } 11397403Sobrien } 11497403Sobrien 115169691Skan inline void 116169691Skan __slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head) 117169691Skan { 118169691Skan _Slist_node_base* __before_last = __slist_previous(__head, 0); 119169691Skan if (__before_last != __head) 120169691Skan { 121169691Skan _Slist_node_base* __after = __pos->_M_next; 122169691Skan __pos->_M_next = __head->_M_next; 123169691Skan __head->_M_next = 0; 124169691Skan __before_last->_M_next = __after; 125169691Skan } 12697403Sobrien } 12797403Sobrien 128169691Skan inline _Slist_node_base* 129169691Skan __slist_reverse(_Slist_node_base* __node) 130169691Skan { 131169691Skan _Slist_node_base* __result = __node; 132169691Skan __node = __node->_M_next; 133169691Skan __result->_M_next = 0; 134169691Skan while(__node) 135169691Skan { 136169691Skan _Slist_node_base* __next = __node->_M_next; 137169691Skan __node->_M_next = __result; 138169691Skan __result = __node; 139169691Skan __node = __next; 140169691Skan } 141169691Skan return __result; 14297403Sobrien } 14397403Sobrien 144169691Skan inline size_t 145169691Skan __slist_size(_Slist_node_base* __node) 146169691Skan { 147169691Skan size_t __result = 0; 148169691Skan for (; __node != 0; __node = __node->_M_next) 149169691Skan ++__result; 150169691Skan return __result; 151169691Skan } 15297403Sobrien 153169691Skan template <class _Tp> 154169691Skan struct _Slist_node : public _Slist_node_base 155169691Skan { 156169691Skan _Tp _M_data; 157169691Skan }; 15897403Sobrien 159169691Skan struct _Slist_iterator_base 160169691Skan { 161169691Skan typedef size_t size_type; 162169691Skan typedef ptrdiff_t difference_type; 163169691Skan typedef std::forward_iterator_tag iterator_category; 16497403Sobrien 165169691Skan _Slist_node_base* _M_node; 166169691Skan 167169691Skan _Slist_iterator_base(_Slist_node_base* __x) 168169691Skan : _M_node(__x) {} 16997403Sobrien 170169691Skan void 171169691Skan _M_incr() 172169691Skan { _M_node = _M_node->_M_next; } 17397403Sobrien 174169691Skan bool 175169691Skan operator==(const _Slist_iterator_base& __x) const 176169691Skan { return _M_node == __x._M_node; } 17797403Sobrien 178169691Skan bool 179169691Skan operator!=(const _Slist_iterator_base& __x) const 180169691Skan { return _M_node != __x._M_node; } 181169691Skan }; 18297403Sobrien 183169691Skan template <class _Tp, class _Ref, class _Ptr> 184169691Skan struct _Slist_iterator : public _Slist_iterator_base 185169691Skan { 186169691Skan typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 187169691Skan typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 188169691Skan typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; 18997403Sobrien 190169691Skan typedef _Tp value_type; 191169691Skan typedef _Ptr pointer; 192169691Skan typedef _Ref reference; 193169691Skan typedef _Slist_node<_Tp> _Node; 19497403Sobrien 195169691Skan explicit 196169691Skan _Slist_iterator(_Node* __x) 197169691Skan : _Slist_iterator_base(__x) {} 19897403Sobrien 199169691Skan _Slist_iterator() 200169691Skan : _Slist_iterator_base(0) {} 20197403Sobrien 202169691Skan _Slist_iterator(const iterator& __x) 203169691Skan : _Slist_iterator_base(__x._M_node) {} 20497403Sobrien 205169691Skan reference 206169691Skan operator*() const 207169691Skan { return ((_Node*) _M_node)->_M_data; } 20897403Sobrien 209169691Skan pointer 210169691Skan operator->() const 211169691Skan { return &(operator*()); } 21297403Sobrien 213169691Skan _Self& 214169691Skan operator++() 215169691Skan { 216169691Skan _M_incr(); 217169691Skan return *this; 218169691Skan } 219132720Skan 220169691Skan _Self 221169691Skan operator++(int) 222169691Skan { 223169691Skan _Self __tmp = *this; 224169691Skan _M_incr(); 225169691Skan return __tmp; 226169691Skan } 227169691Skan }; 22897403Sobrien 229169691Skan template <class _Tp, class _Alloc> 230169691Skan struct _Slist_base 231169691Skan : public _Alloc::template rebind<_Slist_node<_Tp> >::other 232169691Skan { 233169691Skan typedef typename _Alloc::template rebind<_Slist_node<_Tp> >::other 234169691Skan _Node_alloc; 235169691Skan typedef _Alloc allocator_type; 23697403Sobrien 237169691Skan allocator_type 238169691Skan get_allocator() const 239169691Skan { return *static_cast<const _Node_alloc*>(this); } 24097403Sobrien 241169691Skan _Slist_base(const allocator_type& __a) 242169691Skan : _Node_alloc(__a) 243169691Skan { this->_M_head._M_next = 0; } 24497403Sobrien 245169691Skan ~_Slist_base() 246169691Skan { _M_erase_after(&this->_M_head, 0); } 24797403Sobrien 248169691Skan protected: 249169691Skan _Slist_node_base _M_head; 25097403Sobrien 251169691Skan _Slist_node<_Tp>* 252169691Skan _M_get_node() 253169691Skan { return _Node_alloc::allocate(1); } 254169691Skan 255169691Skan void 256169691Skan _M_put_node(_Slist_node<_Tp>* __p) 257169691Skan { _Node_alloc::deallocate(__p, 1); } 25897403Sobrien 259169691Skan protected: 260169691Skan _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) 26197403Sobrien { 262169691Skan _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); 263169691Skan _Slist_node_base* __next_next = __next->_M_next; 264169691Skan __pos->_M_next = __next_next; 265169691Skan get_allocator().destroy(&__next->_M_data); 266169691Skan _M_put_node(__next); 267169691Skan return __next_next; 26897403Sobrien } 269169691Skan _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); 270169691Skan }; 271132720Skan 272169691Skan template <class _Tp, class _Alloc> 273169691Skan _Slist_node_base* 274169691Skan _Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, 275169691Skan _Slist_node_base* __last_node) 276169691Skan { 277169691Skan _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); 278169691Skan while (__cur != __last_node) 279169691Skan { 280169691Skan _Slist_node<_Tp>* __tmp = __cur; 281169691Skan __cur = (_Slist_node<_Tp>*) __cur->_M_next; 282169691Skan get_allocator().destroy(&__tmp->_M_data); 283169691Skan _M_put_node(__tmp); 284169691Skan } 285169691Skan __before_first->_M_next = __last_node; 286169691Skan return __last_node; 28797403Sobrien } 288169691Skan 289169691Skan /** 290169691Skan * This is an SGI extension. 291169691Skan * @ingroup SGIextensions 292169691Skan * @doctodo 293169691Skan */ 294169691Skan template <class _Tp, class _Alloc = allocator<_Tp> > 295169691Skan class slist : private _Slist_base<_Tp,_Alloc> 296169691Skan { 297169691Skan // concept requirements 298169691Skan __glibcxx_class_requires(_Tp, _SGIAssignableConcept) 299169691Skan 300169691Skan private: 301169691Skan typedef _Slist_base<_Tp,_Alloc> _Base; 302169691Skan 303169691Skan public: 304169691Skan typedef _Tp value_type; 305169691Skan typedef value_type* pointer; 306169691Skan typedef const value_type* const_pointer; 307169691Skan typedef value_type& reference; 308169691Skan typedef const value_type& const_reference; 309169691Skan typedef size_t size_type; 310169691Skan typedef ptrdiff_t difference_type; 311169691Skan 312169691Skan typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 313169691Skan typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 314169691Skan 315169691Skan typedef typename _Base::allocator_type allocator_type; 316169691Skan 317169691Skan allocator_type 318169691Skan get_allocator() const 319169691Skan { return _Base::get_allocator(); } 320169691Skan 321169691Skan private: 322169691Skan typedef _Slist_node<_Tp> _Node; 323169691Skan typedef _Slist_node_base _Node_base; 324169691Skan typedef _Slist_iterator_base _Iterator_base; 325169691Skan 326169691Skan _Node* 327169691Skan _M_create_node(const value_type& __x) 32897403Sobrien { 329169691Skan _Node* __node = this->_M_get_node(); 330169691Skan try 331169691Skan { 332169691Skan get_allocator().construct(&__node->_M_data, __x); 333169691Skan __node->_M_next = 0; 334169691Skan } 335169691Skan catch(...) 336169691Skan { 337169691Skan this->_M_put_node(__node); 338169691Skan __throw_exception_again; 339169691Skan } 340169691Skan return __node; 34197403Sobrien } 34297403Sobrien 343169691Skan _Node* 344169691Skan _M_create_node() 345169691Skan { 346169691Skan _Node* __node = this->_M_get_node(); 347169691Skan try 348169691Skan { 349169691Skan get_allocator().construct(&__node->_M_data, value_type()); 350169691Skan __node->_M_next = 0; 351169691Skan } 352169691Skan catch(...) 353169691Skan { 354169691Skan this->_M_put_node(__node); 355169691Skan __throw_exception_again; 356169691Skan } 357169691Skan return __node; 358169691Skan } 35997403Sobrien 360169691Skan public: 361169691Skan explicit 362169691Skan slist(const allocator_type& __a = allocator_type()) 363169691Skan : _Base(__a) {} 36497403Sobrien 365169691Skan slist(size_type __n, const value_type& __x, 366169691Skan const allocator_type& __a = allocator_type()) 367169691Skan : _Base(__a) 368169691Skan { _M_insert_after_fill(&this->_M_head, __n, __x); } 36997403Sobrien 370169691Skan explicit 371169691Skan slist(size_type __n) 372169691Skan : _Base(allocator_type()) 373169691Skan { _M_insert_after_fill(&this->_M_head, __n, value_type()); } 37497403Sobrien 375169691Skan // We don't need any dispatching tricks here, because 376169691Skan // _M_insert_after_range already does them. 377169691Skan template <class _InputIterator> 378169691Skan slist(_InputIterator __first, _InputIterator __last, 379169691Skan const allocator_type& __a = allocator_type()) 380169691Skan : _Base(__a) 381169691Skan { _M_insert_after_range(&this->_M_head, __first, __last); } 38297403Sobrien 383169691Skan slist(const slist& __x) 384169691Skan : _Base(__x.get_allocator()) 385169691Skan { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); } 38697403Sobrien 387169691Skan slist& 388169691Skan operator= (const slist& __x); 38997403Sobrien 390169691Skan ~slist() {} 39197403Sobrien 392169691Skan public: 393169691Skan // assign(), a generalized assignment member function. Two 394169691Skan // versions: one that takes a count, and one that takes a range. 395169691Skan // The range version is a member template, so we dispatch on whether 396169691Skan // or not the type is an integer. 397169691Skan 398169691Skan void 399169691Skan assign(size_type __n, const _Tp& __val) 400169691Skan { _M_fill_assign(__n, __val); } 40197403Sobrien 402169691Skan void 403169691Skan _M_fill_assign(size_type __n, const _Tp& __val); 40497403Sobrien 405169691Skan template <class _InputIterator> 406169691Skan void 407169691Skan assign(_InputIterator __first, _InputIterator __last) 408169691Skan { 409169691Skan typedef typename std::__is_integer<_InputIterator>::__type _Integral; 410169691Skan _M_assign_dispatch(__first, __last, _Integral()); 411169691Skan } 41297403Sobrien 413169691Skan template <class _Integer> 414169691Skan void 415169691Skan _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 416169691Skan { _M_fill_assign((size_type) __n, (_Tp) __val); } 41797403Sobrien 418169691Skan template <class _InputIterator> 419169691Skan void 420169691Skan _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 421169691Skan __false_type); 42297403Sobrien 423169691Skan public: 42497403Sobrien 425169691Skan iterator 426169691Skan begin() 427169691Skan { return iterator((_Node*)this->_M_head._M_next); } 42897403Sobrien 429169691Skan const_iterator 430169691Skan begin() const 431169691Skan { return const_iterator((_Node*)this->_M_head._M_next);} 43297403Sobrien 433169691Skan iterator 434169691Skan end() 435169691Skan { return iterator(0); } 43697403Sobrien 437169691Skan const_iterator 438169691Skan end() const 439169691Skan { return const_iterator(0); } 440132720Skan 441169691Skan // Experimental new feature: before_begin() returns a 442169691Skan // non-dereferenceable iterator that, when incremented, yields 443169691Skan // begin(). This iterator may be used as the argument to 444169691Skan // insert_after, erase_after, etc. Note that even for an empty 445169691Skan // slist, before_begin() is not the same iterator as end(). It 446169691Skan // is always necessary to increment before_begin() at least once to 447169691Skan // obtain end(). 448169691Skan iterator 449169691Skan before_begin() 450169691Skan { return iterator((_Node*) &this->_M_head); } 45197403Sobrien 452169691Skan const_iterator 453169691Skan before_begin() const 454169691Skan { return const_iterator((_Node*) &this->_M_head); } 45597403Sobrien 456169691Skan size_type 457169691Skan size() const 458169691Skan { return __slist_size(this->_M_head._M_next); } 45997403Sobrien 460169691Skan size_type 461169691Skan max_size() const 462169691Skan { return size_type(-1); } 46397403Sobrien 464169691Skan bool 465169691Skan empty() const 466169691Skan { return this->_M_head._M_next == 0; } 46797403Sobrien 468169691Skan void 469169691Skan swap(slist& __x) 470169691Skan { std::swap(this->_M_head._M_next, __x._M_head._M_next); } 47197403Sobrien 472169691Skan public: 47397403Sobrien 474169691Skan reference 475169691Skan front() 476169691Skan { return ((_Node*) this->_M_head._M_next)->_M_data; } 47797403Sobrien 478169691Skan const_reference 479169691Skan front() const 480169691Skan { return ((_Node*) this->_M_head._M_next)->_M_data; } 48197403Sobrien 482169691Skan void 483169691Skan push_front(const value_type& __x) 484169691Skan { __slist_make_link(&this->_M_head, _M_create_node(__x)); } 48597403Sobrien 486169691Skan void 487169691Skan push_front() 488169691Skan { __slist_make_link(&this->_M_head, _M_create_node()); } 48997403Sobrien 490169691Skan void 491169691Skan pop_front() 492169691Skan { 493169691Skan _Node* __node = (_Node*) this->_M_head._M_next; 494169691Skan this->_M_head._M_next = __node->_M_next; 495169691Skan get_allocator().destroy(&__node->_M_data); 496169691Skan this->_M_put_node(__node); 497169691Skan } 49897403Sobrien 499169691Skan iterator 500169691Skan previous(const_iterator __pos) 501169691Skan { return iterator((_Node*) __slist_previous(&this->_M_head, 502169691Skan __pos._M_node)); } 50397403Sobrien 504169691Skan const_iterator 505169691Skan previous(const_iterator __pos) const 506169691Skan { return const_iterator((_Node*) __slist_previous(&this->_M_head, 507169691Skan __pos._M_node)); } 50897403Sobrien 509169691Skan private: 510169691Skan _Node* 511169691Skan _M_insert_after(_Node_base* __pos, const value_type& __x) 512169691Skan { return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); } 51397403Sobrien 514169691Skan _Node* 515169691Skan _M_insert_after(_Node_base* __pos) 516169691Skan { return (_Node*) (__slist_make_link(__pos, _M_create_node())); } 51797403Sobrien 518169691Skan void 519169691Skan _M_insert_after_fill(_Node_base* __pos, 520169691Skan size_type __n, const value_type& __x) 521169691Skan { 522169691Skan for (size_type __i = 0; __i < __n; ++__i) 523169691Skan __pos = __slist_make_link(__pos, _M_create_node(__x)); 524169691Skan } 52597403Sobrien 526169691Skan // Check whether it's an integral type. If so, it's not an iterator. 527169691Skan template <class _InIterator> 528169691Skan void 529169691Skan _M_insert_after_range(_Node_base* __pos, 530169691Skan _InIterator __first, _InIterator __last) 531169691Skan { 532169691Skan typedef typename std::__is_integer<_InIterator>::__type _Integral; 533169691Skan _M_insert_after_range(__pos, __first, __last, _Integral()); 534169691Skan } 53597403Sobrien 536169691Skan template <class _Integer> 537169691Skan void 538169691Skan _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x, 539169691Skan __true_type) 540169691Skan { _M_insert_after_fill(__pos, __n, __x); } 54197403Sobrien 542169691Skan template <class _InIterator> 543169691Skan void 544169691Skan _M_insert_after_range(_Node_base* __pos, 545169691Skan _InIterator __first, _InIterator __last, 546169691Skan __false_type) 547169691Skan { 548169691Skan while (__first != __last) 549169691Skan { 550169691Skan __pos = __slist_make_link(__pos, _M_create_node(*__first)); 551169691Skan ++__first; 552169691Skan } 553169691Skan } 554132720Skan 555169691Skan public: 556169691Skan iterator 557169691Skan insert_after(iterator __pos, const value_type& __x) 558169691Skan { return iterator(_M_insert_after(__pos._M_node, __x)); } 55997403Sobrien 560169691Skan iterator 561169691Skan insert_after(iterator __pos) 562169691Skan { return insert_after(__pos, value_type()); } 56397403Sobrien 564169691Skan void 565169691Skan insert_after(iterator __pos, size_type __n, const value_type& __x) 566169691Skan { _M_insert_after_fill(__pos._M_node, __n, __x); } 56797403Sobrien 568169691Skan // We don't need any dispatching tricks here, because 569169691Skan // _M_insert_after_range already does them. 570169691Skan template <class _InIterator> 571169691Skan void 572169691Skan insert_after(iterator __pos, _InIterator __first, _InIterator __last) 573169691Skan { _M_insert_after_range(__pos._M_node, __first, __last); } 57497403Sobrien 575169691Skan iterator 576169691Skan insert(iterator __pos, const value_type& __x) 577169691Skan { return iterator(_M_insert_after(__slist_previous(&this->_M_head, 578169691Skan __pos._M_node), 579169691Skan __x)); } 58097403Sobrien 581169691Skan iterator 582169691Skan insert(iterator __pos) 583169691Skan { return iterator(_M_insert_after(__slist_previous(&this->_M_head, 584169691Skan __pos._M_node), 585169691Skan value_type())); } 58697403Sobrien 587169691Skan void 588169691Skan insert(iterator __pos, size_type __n, const value_type& __x) 589169691Skan { _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node), 590169691Skan __n, __x); } 59197403Sobrien 592169691Skan // We don't need any dispatching tricks here, because 593169691Skan // _M_insert_after_range already does them. 594169691Skan template <class _InIterator> 595169691Skan void 596169691Skan insert(iterator __pos, _InIterator __first, _InIterator __last) 597169691Skan { _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 598169691Skan __first, __last); } 59997403Sobrien 600169691Skan public: 601169691Skan iterator 602169691Skan erase_after(iterator __pos) 603169691Skan { return iterator((_Node*) this->_M_erase_after(__pos._M_node)); } 60497403Sobrien 605169691Skan iterator 606169691Skan erase_after(iterator __before_first, iterator __last) 607169691Skan { 608169691Skan return iterator((_Node*) this->_M_erase_after(__before_first._M_node, 609169691Skan __last._M_node)); 610169691Skan } 61197403Sobrien 612169691Skan iterator 613169691Skan erase(iterator __pos) 614169691Skan { 615169691Skan return iterator((_Node*) this->_M_erase_after 616169691Skan (__slist_previous(&this->_M_head, __pos._M_node))); 617169691Skan } 61897403Sobrien 619169691Skan iterator 620169691Skan erase(iterator __first, iterator __last) 621169691Skan { 622169691Skan return iterator((_Node*) this->_M_erase_after 623169691Skan (__slist_previous(&this->_M_head, __first._M_node), 624169691Skan __last._M_node)); 625169691Skan } 626169691Skan 627169691Skan void 628169691Skan resize(size_type new_size, const _Tp& __x); 62997403Sobrien 630169691Skan void 631169691Skan resize(size_type new_size) 632169691Skan { resize(new_size, _Tp()); } 63397403Sobrien 634169691Skan void 635169691Skan clear() 636169691Skan { this->_M_erase_after(&this->_M_head, 0); } 63797403Sobrien 638169691Skan public: 639169691Skan // Moves the range [__before_first + 1, __before_last + 1) to *this, 640169691Skan // inserting it immediately after __pos. This is constant time. 641169691Skan void 642169691Skan splice_after(iterator __pos, 643169691Skan iterator __before_first, iterator __before_last) 644169691Skan { 645169691Skan if (__before_first != __before_last) 646169691Skan __slist_splice_after(__pos._M_node, __before_first._M_node, 647169691Skan __before_last._M_node); 648169691Skan } 64997403Sobrien 650169691Skan // Moves the element that follows __prev to *this, inserting it 651169691Skan // immediately after __pos. This is constant time. 652169691Skan void 653169691Skan splice_after(iterator __pos, iterator __prev) 654169691Skan { __slist_splice_after(__pos._M_node, 655169691Skan __prev._M_node, __prev._M_node->_M_next); } 65697403Sobrien 657169691Skan // Removes all of the elements from the list __x to *this, inserting 658169691Skan // them immediately after __pos. __x must not be *this. Complexity: 659169691Skan // linear in __x.size(). 660169691Skan void 661169691Skan splice_after(iterator __pos, slist& __x) 662169691Skan { __slist_splice_after(__pos._M_node, &__x._M_head); } 66397403Sobrien 664169691Skan // Linear in distance(begin(), __pos), and linear in __x.size(). 665169691Skan void 666169691Skan splice(iterator __pos, slist& __x) 667169691Skan { 668169691Skan if (__x._M_head._M_next) 669169691Skan __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 670169691Skan &__x._M_head, 671169691Skan __slist_previous(&__x._M_head, 0)); } 67297403Sobrien 673169691Skan // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i). 674169691Skan void 675169691Skan splice(iterator __pos, slist& __x, iterator __i) 676169691Skan { __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 677169691Skan __slist_previous(&__x._M_head, __i._M_node), 678169691Skan __i._M_node); } 67997403Sobrien 680169691Skan // Linear in distance(begin(), __pos), in distance(__x.begin(), __first), 681169691Skan // and in distance(__first, __last). 682169691Skan void 683169691Skan splice(iterator __pos, slist& __x, iterator __first, iterator __last) 684169691Skan { 685169691Skan if (__first != __last) 686169691Skan __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 687169691Skan __slist_previous(&__x._M_head, __first._M_node), 688169691Skan __slist_previous(__first._M_node, 689169691Skan __last._M_node)); 690169691Skan } 69197403Sobrien 692169691Skan public: 693169691Skan void 694169691Skan reverse() 695169691Skan { 696169691Skan if (this->_M_head._M_next) 697169691Skan this->_M_head._M_next = __slist_reverse(this->_M_head._M_next); 698169691Skan } 69997403Sobrien 700169691Skan void 701169691Skan remove(const _Tp& __val); 70297403Sobrien 703169691Skan void 704169691Skan unique(); 705169691Skan 706169691Skan void 707169691Skan merge(slist& __x); 708169691Skan 709169691Skan void 710169691Skan sort(); 71197403Sobrien 712169691Skan template <class _Predicate> 713169691Skan void 714169691Skan remove_if(_Predicate __pred); 71597403Sobrien 716169691Skan template <class _BinaryPredicate> 717169691Skan void 718169691Skan unique(_BinaryPredicate __pred); 71997403Sobrien 720169691Skan template <class _StrictWeakOrdering> 721169691Skan void 722169691Skan merge(slist&, _StrictWeakOrdering); 72397403Sobrien 724169691Skan template <class _StrictWeakOrdering> 725169691Skan void 726169691Skan sort(_StrictWeakOrdering __comp); 727169691Skan }; 72897403Sobrien 729169691Skan template <class _Tp, class _Alloc> 730169691Skan slist<_Tp, _Alloc>& 731169691Skan slist<_Tp, _Alloc>::operator=(const slist<_Tp, _Alloc>& __x) 732169691Skan { 733169691Skan if (&__x != this) 734169691Skan { 735169691Skan _Node_base* __p1 = &this->_M_head; 736169691Skan _Node* __n1 = (_Node*) this->_M_head._M_next; 737169691Skan const _Node* __n2 = (const _Node*) __x._M_head._M_next; 738169691Skan while (__n1 && __n2) 739169691Skan { 740169691Skan __n1->_M_data = __n2->_M_data; 741169691Skan __p1 = __n1; 742169691Skan __n1 = (_Node*) __n1->_M_next; 743169691Skan __n2 = (const _Node*) __n2->_M_next; 744169691Skan } 745169691Skan if (__n2 == 0) 746169691Skan this->_M_erase_after(__p1, 0); 747169691Skan else 748169691Skan _M_insert_after_range(__p1, const_iterator((_Node*)__n2), 749169691Skan const_iterator(0)); 750169691Skan } 751169691Skan return *this; 752169691Skan } 75397403Sobrien 754169691Skan template <class _Tp, class _Alloc> 755169691Skan void 756169691Skan slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) 757169691Skan { 758169691Skan _Node_base* __prev = &this->_M_head; 759169691Skan _Node* __node = (_Node*) this->_M_head._M_next; 760169691Skan for (; __node != 0 && __n > 0; --__n) 761169691Skan { 762169691Skan __node->_M_data = __val; 763169691Skan __prev = __node; 764169691Skan __node = (_Node*) __node->_M_next; 765169691Skan } 766169691Skan if (__n > 0) 767169691Skan _M_insert_after_fill(__prev, __n, __val); 768169691Skan else 769169691Skan this->_M_erase_after(__prev, 0); 770169691Skan } 771169691Skan 772169691Skan template <class _Tp, class _Alloc> 773169691Skan template <class _InputIterator> 774169691Skan void 775169691Skan slist<_Tp, _Alloc>::_M_assign_dispatch(_InputIterator __first, 776169691Skan _InputIterator __last, 777169691Skan __false_type) 778169691Skan { 779169691Skan _Node_base* __prev = &this->_M_head; 780169691Skan _Node* __node = (_Node*) this->_M_head._M_next; 781169691Skan while (__node != 0 && __first != __last) 782169691Skan { 783169691Skan __node->_M_data = *__first; 784169691Skan __prev = __node; 785169691Skan __node = (_Node*) __node->_M_next; 786169691Skan ++__first; 787169691Skan } 788169691Skan if (__first != __last) 789169691Skan _M_insert_after_range(__prev, __first, __last); 790169691Skan else 791169691Skan this->_M_erase_after(__prev, 0); 792169691Skan } 793169691Skan 794169691Skan template <class _Tp, class _Alloc> 795169691Skan inline bool 796169691Skan operator==(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 797169691Skan { 798169691Skan typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator; 799169691Skan const_iterator __end1 = _SL1.end(); 800169691Skan const_iterator __end2 = _SL2.end(); 801169691Skan 802169691Skan const_iterator __i1 = _SL1.begin(); 803169691Skan const_iterator __i2 = _SL2.begin(); 804169691Skan while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) 805169691Skan { 806169691Skan ++__i1; 807169691Skan ++__i2; 808169691Skan } 809169691Skan return __i1 == __end1 && __i2 == __end2; 810169691Skan } 81197403Sobrien 81297403Sobrien 813169691Skan template <class _Tp, class _Alloc> 814169691Skan inline bool 815169691Skan operator<(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 816169691Skan { return std::lexicographical_compare(_SL1.begin(), _SL1.end(), 817169691Skan _SL2.begin(), _SL2.end()); } 81897403Sobrien 819169691Skan template <class _Tp, class _Alloc> 820169691Skan inline bool 821169691Skan operator!=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 822169691Skan { return !(_SL1 == _SL2); } 82397403Sobrien 824169691Skan template <class _Tp, class _Alloc> 825169691Skan inline bool 826169691Skan operator>(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 827169691Skan { return _SL2 < _SL1; } 828169691Skan 829169691Skan template <class _Tp, class _Alloc> 830169691Skan inline bool 831169691Skan operator<=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 832169691Skan { return !(_SL2 < _SL1); } 833169691Skan 834169691Skan template <class _Tp, class _Alloc> 835169691Skan inline bool 836169691Skan operator>=(const slist<_Tp, _Alloc>& _SL1, const slist<_Tp, _Alloc>& _SL2) 837169691Skan { return !(_SL1 < _SL2); } 838169691Skan 839169691Skan template <class _Tp, class _Alloc> 840169691Skan inline void 841169691Skan swap(slist<_Tp, _Alloc>& __x, slist<_Tp, _Alloc>& __y) 842169691Skan { __x.swap(__y); } 843169691Skan 844169691Skan template <class _Tp, class _Alloc> 845169691Skan void 846169691Skan slist<_Tp, _Alloc>::resize(size_type __len, const _Tp& __x) 847169691Skan { 848169691Skan _Node_base* __cur = &this->_M_head; 849169691Skan while (__cur->_M_next != 0 && __len > 0) 850169691Skan { 851169691Skan --__len; 852169691Skan __cur = __cur->_M_next; 853169691Skan } 854169691Skan if (__cur->_M_next) 855169691Skan this->_M_erase_after(__cur, 0); 85697403Sobrien else 857169691Skan _M_insert_after_fill(__cur, __len, __x); 85897403Sobrien } 85997403Sobrien 860169691Skan template <class _Tp, class _Alloc> 861169691Skan void 862169691Skan slist<_Tp, _Alloc>::remove(const _Tp& __val) 863169691Skan { 864169691Skan _Node_base* __cur = &this->_M_head; 865169691Skan while (__cur && __cur->_M_next) 866169691Skan { 867169691Skan if (((_Node*) __cur->_M_next)->_M_data == __val) 868169691Skan this->_M_erase_after(__cur); 869169691Skan else 870169691Skan __cur = __cur->_M_next; 871169691Skan } 872169691Skan } 87397403Sobrien 874169691Skan template <class _Tp, class _Alloc> 875169691Skan void 876169691Skan slist<_Tp, _Alloc>::unique() 877169691Skan { 878169691Skan _Node_base* __cur = this->_M_head._M_next; 879169691Skan if (__cur) 880169691Skan { 881169691Skan while (__cur->_M_next) 882169691Skan { 883169691Skan if (((_Node*)__cur)->_M_data 884169691Skan == ((_Node*)(__cur->_M_next))->_M_data) 885169691Skan this->_M_erase_after(__cur); 886169691Skan else 887169691Skan __cur = __cur->_M_next; 888169691Skan } 889169691Skan } 89097403Sobrien } 89197403Sobrien 892169691Skan template <class _Tp, class _Alloc> 893169691Skan void 894169691Skan slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x) 895169691Skan { 896169691Skan _Node_base* __n1 = &this->_M_head; 897169691Skan while (__n1->_M_next && __x._M_head._M_next) 898169691Skan { 899169691Skan if (((_Node*) __x._M_head._M_next)->_M_data 900169691Skan < ((_Node*) __n1->_M_next)->_M_data) 901169691Skan __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); 902169691Skan __n1 = __n1->_M_next; 903169691Skan } 904169691Skan if (__x._M_head._M_next) 905169691Skan { 906169691Skan __n1->_M_next = __x._M_head._M_next; 907169691Skan __x._M_head._M_next = 0; 908169691Skan } 909169691Skan } 91097403Sobrien 911169691Skan template <class _Tp, class _Alloc> 912169691Skan void 913169691Skan slist<_Tp, _Alloc>::sort() 914169691Skan { 915169691Skan if (this->_M_head._M_next && this->_M_head._M_next->_M_next) 916169691Skan { 917169691Skan slist __carry; 918169691Skan slist __counter[64]; 919169691Skan int __fill = 0; 920169691Skan while (!empty()) 921169691Skan { 922169691Skan __slist_splice_after(&__carry._M_head, 923169691Skan &this->_M_head, this->_M_head._M_next); 924169691Skan int __i = 0; 925169691Skan while (__i < __fill && !__counter[__i].empty()) 926169691Skan { 927169691Skan __counter[__i].merge(__carry); 928169691Skan __carry.swap(__counter[__i]); 929169691Skan ++__i; 930169691Skan } 931169691Skan __carry.swap(__counter[__i]); 932169691Skan if (__i == __fill) 933169691Skan ++__fill; 934169691Skan } 935169691Skan 936169691Skan for (int __i = 1; __i < __fill; ++__i) 937169691Skan __counter[__i].merge(__counter[__i-1]); 938169691Skan this->swap(__counter[__fill-1]); 939169691Skan } 94097403Sobrien } 94197403Sobrien 942169691Skan template <class _Tp, class _Alloc> 943169691Skan template <class _Predicate> 944169691Skan void slist<_Tp, _Alloc>::remove_if(_Predicate __pred) 945169691Skan { 946169691Skan _Node_base* __cur = &this->_M_head; 947169691Skan while (__cur->_M_next) 948169691Skan { 949169691Skan if (__pred(((_Node*) __cur->_M_next)->_M_data)) 950169691Skan this->_M_erase_after(__cur); 951169691Skan else 952169691Skan __cur = __cur->_M_next; 953169691Skan } 954169691Skan } 95597403Sobrien 956169691Skan template <class _Tp, class _Alloc> 957169691Skan template <class _BinaryPredicate> 958169691Skan void 959169691Skan slist<_Tp, _Alloc>::unique(_BinaryPredicate __pred) 960169691Skan { 961169691Skan _Node* __cur = (_Node*) this->_M_head._M_next; 962169691Skan if (__cur) 963169691Skan { 964169691Skan while (__cur->_M_next) 965169691Skan { 966169691Skan if (__pred(((_Node*)__cur)->_M_data, 967169691Skan ((_Node*)(__cur->_M_next))->_M_data)) 968169691Skan this->_M_erase_after(__cur); 969169691Skan else 970169691Skan __cur = (_Node*) __cur->_M_next; 971169691Skan } 972169691Skan } 97397403Sobrien } 97497403Sobrien 975169691Skan template <class _Tp, class _Alloc> 976169691Skan template <class _StrictWeakOrdering> 977169691Skan void 978169691Skan slist<_Tp, _Alloc>::merge(slist<_Tp, _Alloc>& __x, 979169691Skan _StrictWeakOrdering __comp) 980169691Skan { 981169691Skan _Node_base* __n1 = &this->_M_head; 982169691Skan while (__n1->_M_next && __x._M_head._M_next) 983169691Skan { 984169691Skan if (__comp(((_Node*) __x._M_head._M_next)->_M_data, 985169691Skan ((_Node*) __n1->_M_next)->_M_data)) 986169691Skan __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); 987169691Skan __n1 = __n1->_M_next; 988169691Skan } 989169691Skan if (__x._M_head._M_next) 990169691Skan { 991169691Skan __n1->_M_next = __x._M_head._M_next; 992169691Skan __x._M_head._M_next = 0; 993169691Skan } 994169691Skan } 99597403Sobrien 996169691Skan template <class _Tp, class _Alloc> 997169691Skan template <class _StrictWeakOrdering> 998169691Skan void 999169691Skan slist<_Tp, _Alloc>::sort(_StrictWeakOrdering __comp) 1000169691Skan { 1001169691Skan if (this->_M_head._M_next && this->_M_head._M_next->_M_next) 1002169691Skan { 1003169691Skan slist __carry; 1004169691Skan slist __counter[64]; 1005169691Skan int __fill = 0; 1006169691Skan while (!empty()) 1007169691Skan { 1008169691Skan __slist_splice_after(&__carry._M_head, 1009169691Skan &this->_M_head, this->_M_head._M_next); 1010169691Skan int __i = 0; 1011169691Skan while (__i < __fill && !__counter[__i].empty()) 1012169691Skan { 1013169691Skan __counter[__i].merge(__carry, __comp); 1014169691Skan __carry.swap(__counter[__i]); 1015169691Skan ++__i; 1016169691Skan } 1017169691Skan __carry.swap(__counter[__i]); 1018169691Skan if (__i == __fill) 1019169691Skan ++__fill; 1020169691Skan } 102197403Sobrien 1022169691Skan for (int __i = 1; __i < __fill; ++__i) 1023169691Skan __counter[__i].merge(__counter[__i-1], __comp); 1024169691Skan this->swap(__counter[__fill-1]); 1025169691Skan } 1026169691Skan } 102797403Sobrien 1028169691Skan_GLIBCXX_END_NAMESPACE 102997403Sobrien 1030169691Skan_GLIBCXX_BEGIN_NAMESPACE(std) 103197403Sobrien 1032169691Skan // Specialization of insert_iterator so that insertions will be constant 1033169691Skan // time rather than linear time. 1034169691Skan template <class _Tp, class _Alloc> 1035169691Skan class insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> > 1036169691Skan { 1037169691Skan protected: 1038169691Skan typedef __gnu_cxx::slist<_Tp, _Alloc> _Container; 1039169691Skan _Container* container; 1040169691Skan typename _Container::iterator iter; 104197403Sobrien 1042169691Skan public: 1043169691Skan typedef _Container container_type; 1044169691Skan typedef output_iterator_tag iterator_category; 1045169691Skan typedef void value_type; 1046169691Skan typedef void difference_type; 1047169691Skan typedef void pointer; 1048169691Skan typedef void reference; 104997403Sobrien 1050169691Skan insert_iterator(_Container& __x, typename _Container::iterator __i) 1051169691Skan : container(&__x) 1052169691Skan { 1053169691Skan if (__i == __x.begin()) 1054169691Skan iter = __x.before_begin(); 1055169691Skan else 1056169691Skan iter = __x.previous(__i); 1057169691Skan } 1058169691Skan 1059169691Skan insert_iterator<_Container>& 1060169691Skan operator=(const typename _Container::value_type& __value) 1061169691Skan { 1062169691Skan iter = container->insert_after(iter, __value); 1063169691Skan return *this; 1064169691Skan } 1065169691Skan 1066169691Skan insert_iterator<_Container>& 1067169691Skan operator*() 1068169691Skan { return *this; } 1069169691Skan 1070169691Skan insert_iterator<_Container>& 1071169691Skan operator++() 1072169691Skan { return *this; } 1073169691Skan 1074169691Skan insert_iterator<_Container>& 1075169691Skan operator++(int) 1076169691Skan { return *this; } 1077169691Skan }; 1078169691Skan 1079169691Skan_GLIBCXX_END_NAMESPACE 1080169691Skan 1081132720Skan#endif 1082