slist revision 97403
197403Sobrien// Singly-linked list implementation -*- C++ -*- 297403Sobrien 397403Sobrien// Copyright (C) 2001, 2002 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 1897403Sobrien// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307, 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 4697403Sobrien * containing extensions from the HP/SGI STL subset). You should only 4797403Sobrien * include this header if you are using GCC 3 or later. 4897403Sobrien */ 4997403Sobrien 5097403Sobrien#ifndef __SGI_STL_INTERNAL_SLIST_H 5197403Sobrien#define __SGI_STL_INTERNAL_SLIST_H 5297403Sobrien 5397403Sobrien#include <bits/stl_algobase.h> 5497403Sobrien#include <bits/stl_alloc.h> 5597403Sobrien#include <bits/stl_construct.h> 5697403Sobrien#include <bits/stl_uninitialized.h> 5797403Sobrien#include <bits/concept_check.h> 5897403Sobrien 5997403Sobriennamespace __gnu_cxx 6097403Sobrien{ 6197403Sobrienusing std::size_t; 6297403Sobrienusing std::ptrdiff_t; 6397403Sobrienusing std::_Alloc_traits; 6497403Sobrienusing std::_Construct; 6597403Sobrienusing std::_Destroy; 6697403Sobrienusing std::allocator; 6797403Sobrien 6897403Sobrienstruct _Slist_node_base 6997403Sobrien{ 7097403Sobrien _Slist_node_base* _M_next; 7197403Sobrien}; 7297403Sobrien 7397403Sobrieninline _Slist_node_base* 7497403Sobrien__slist_make_link(_Slist_node_base* __prev_node, 7597403Sobrien _Slist_node_base* __new_node) 7697403Sobrien{ 7797403Sobrien __new_node->_M_next = __prev_node->_M_next; 7897403Sobrien __prev_node->_M_next = __new_node; 7997403Sobrien return __new_node; 8097403Sobrien} 8197403Sobrien 8297403Sobrieninline _Slist_node_base* 8397403Sobrien__slist_previous(_Slist_node_base* __head, 8497403Sobrien const _Slist_node_base* __node) 8597403Sobrien{ 8697403Sobrien while (__head && __head->_M_next != __node) 8797403Sobrien __head = __head->_M_next; 8897403Sobrien return __head; 8997403Sobrien} 9097403Sobrien 9197403Sobrieninline const _Slist_node_base* 9297403Sobrien__slist_previous(const _Slist_node_base* __head, 9397403Sobrien const _Slist_node_base* __node) 9497403Sobrien{ 9597403Sobrien while (__head && __head->_M_next != __node) 9697403Sobrien __head = __head->_M_next; 9797403Sobrien return __head; 9897403Sobrien} 9997403Sobrien 10097403Sobrieninline void __slist_splice_after(_Slist_node_base* __pos, 10197403Sobrien _Slist_node_base* __before_first, 10297403Sobrien _Slist_node_base* __before_last) 10397403Sobrien{ 10497403Sobrien if (__pos != __before_first && __pos != __before_last) { 10597403Sobrien _Slist_node_base* __first = __before_first->_M_next; 10697403Sobrien _Slist_node_base* __after = __pos->_M_next; 10797403Sobrien __before_first->_M_next = __before_last->_M_next; 10897403Sobrien __pos->_M_next = __first; 10997403Sobrien __before_last->_M_next = __after; 11097403Sobrien } 11197403Sobrien} 11297403Sobrien 11397403Sobrieninline void 11497403Sobrien__slist_splice_after(_Slist_node_base* __pos, _Slist_node_base* __head) 11597403Sobrien{ 11697403Sobrien _Slist_node_base* __before_last = __slist_previous(__head, 0); 11797403Sobrien if (__before_last != __head) { 11897403Sobrien _Slist_node_base* __after = __pos->_M_next; 11997403Sobrien __pos->_M_next = __head->_M_next; 12097403Sobrien __head->_M_next = 0; 12197403Sobrien __before_last->_M_next = __after; 12297403Sobrien } 12397403Sobrien} 12497403Sobrien 12597403Sobrieninline _Slist_node_base* __slist_reverse(_Slist_node_base* __node) 12697403Sobrien{ 12797403Sobrien _Slist_node_base* __result = __node; 12897403Sobrien __node = __node->_M_next; 12997403Sobrien __result->_M_next = 0; 13097403Sobrien while(__node) { 13197403Sobrien _Slist_node_base* __next = __node->_M_next; 13297403Sobrien __node->_M_next = __result; 13397403Sobrien __result = __node; 13497403Sobrien __node = __next; 13597403Sobrien } 13697403Sobrien return __result; 13797403Sobrien} 13897403Sobrien 13997403Sobrieninline size_t __slist_size(_Slist_node_base* __node) 14097403Sobrien{ 14197403Sobrien size_t __result = 0; 14297403Sobrien for ( ; __node != 0; __node = __node->_M_next) 14397403Sobrien ++__result; 14497403Sobrien return __result; 14597403Sobrien} 14697403Sobrien 14797403Sobrientemplate <class _Tp> 14897403Sobrienstruct _Slist_node : public _Slist_node_base 14997403Sobrien{ 15097403Sobrien _Tp _M_data; 15197403Sobrien}; 15297403Sobrien 15397403Sobrienstruct _Slist_iterator_base 15497403Sobrien{ 15597403Sobrien typedef size_t size_type; 15697403Sobrien typedef ptrdiff_t difference_type; 15797403Sobrien typedef std::forward_iterator_tag iterator_category; 15897403Sobrien 15997403Sobrien _Slist_node_base* _M_node; 16097403Sobrien 16197403Sobrien _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {} 16297403Sobrien void _M_incr() { _M_node = _M_node->_M_next; } 16397403Sobrien 16497403Sobrien bool operator==(const _Slist_iterator_base& __x) const { 16597403Sobrien return _M_node == __x._M_node; 16697403Sobrien } 16797403Sobrien bool operator!=(const _Slist_iterator_base& __x) const { 16897403Sobrien return _M_node != __x._M_node; 16997403Sobrien } 17097403Sobrien}; 17197403Sobrien 17297403Sobrientemplate <class _Tp, class _Ref, class _Ptr> 17397403Sobrienstruct _Slist_iterator : public _Slist_iterator_base 17497403Sobrien{ 17597403Sobrien typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 17697403Sobrien typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 17797403Sobrien typedef _Slist_iterator<_Tp, _Ref, _Ptr> _Self; 17897403Sobrien 17997403Sobrien typedef _Tp value_type; 18097403Sobrien typedef _Ptr pointer; 18197403Sobrien typedef _Ref reference; 18297403Sobrien typedef _Slist_node<_Tp> _Node; 18397403Sobrien 18497403Sobrien _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {} 18597403Sobrien _Slist_iterator() : _Slist_iterator_base(0) {} 18697403Sobrien _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {} 18797403Sobrien 18897403Sobrien reference operator*() const { return ((_Node*) _M_node)->_M_data; } 18997403Sobrien pointer operator->() const { return &(operator*()); } 19097403Sobrien 19197403Sobrien _Self& operator++() 19297403Sobrien { 19397403Sobrien _M_incr(); 19497403Sobrien return *this; 19597403Sobrien } 19697403Sobrien _Self operator++(int) 19797403Sobrien { 19897403Sobrien _Self __tmp = *this; 19997403Sobrien _M_incr(); 20097403Sobrien return __tmp; 20197403Sobrien } 20297403Sobrien}; 20397403Sobrien 20497403Sobrien 20597403Sobrien// Base class that encapsulates details of allocators. Three cases: 20697403Sobrien// an ordinary standard-conforming allocator, a standard-conforming 20797403Sobrien// allocator with no non-static data, and an SGI-style allocator. 20897403Sobrien// This complexity is necessary only because we're worrying about backward 20997403Sobrien// compatibility and because we want to avoid wasting storage on an 21097403Sobrien// allocator instance if it isn't necessary. 21197403Sobrien 21297403Sobrien// Base for general standard-conforming allocators. 21397403Sobrientemplate <class _Tp, class _Allocator, bool _IsStatic> 21497403Sobrienclass _Slist_alloc_base { 21597403Sobrienpublic: 21697403Sobrien typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type 21797403Sobrien allocator_type; 21897403Sobrien allocator_type get_allocator() const { return _M_node_allocator; } 21997403Sobrien 22097403Sobrien _Slist_alloc_base(const allocator_type& __a) : _M_node_allocator(__a) {} 22197403Sobrien 22297403Sobrienprotected: 22397403Sobrien _Slist_node<_Tp>* _M_get_node() 22497403Sobrien { return _M_node_allocator.allocate(1); } 22597403Sobrien void _M_put_node(_Slist_node<_Tp>* __p) 22697403Sobrien { _M_node_allocator.deallocate(__p, 1); } 22797403Sobrien 22897403Sobrienprotected: 22997403Sobrien typename _Alloc_traits<_Slist_node<_Tp>,_Allocator>::allocator_type 23097403Sobrien _M_node_allocator; 23197403Sobrien _Slist_node_base _M_head; 23297403Sobrien}; 23397403Sobrien 23497403Sobrien// Specialization for instanceless allocators. 23597403Sobrientemplate <class _Tp, class _Allocator> 23697403Sobrienclass _Slist_alloc_base<_Tp,_Allocator, true> { 23797403Sobrienpublic: 23897403Sobrien typedef typename _Alloc_traits<_Tp,_Allocator>::allocator_type 23997403Sobrien allocator_type; 24097403Sobrien allocator_type get_allocator() const { return allocator_type(); } 24197403Sobrien 24297403Sobrien _Slist_alloc_base(const allocator_type&) {} 24397403Sobrien 24497403Sobrienprotected: 24597403Sobrien typedef typename _Alloc_traits<_Slist_node<_Tp>, _Allocator>::_Alloc_type 24697403Sobrien _Alloc_type; 24797403Sobrien _Slist_node<_Tp>* _M_get_node() { return _Alloc_type::allocate(1); } 24897403Sobrien void _M_put_node(_Slist_node<_Tp>* __p) { _Alloc_type::deallocate(__p, 1); } 24997403Sobrien 25097403Sobrienprotected: 25197403Sobrien _Slist_node_base _M_head; 25297403Sobrien}; 25397403Sobrien 25497403Sobrien 25597403Sobrientemplate <class _Tp, class _Alloc> 25697403Sobrienstruct _Slist_base 25797403Sobrien : public _Slist_alloc_base<_Tp, _Alloc, 25897403Sobrien _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 25997403Sobrien{ 26097403Sobrien typedef _Slist_alloc_base<_Tp, _Alloc, 26197403Sobrien _Alloc_traits<_Tp, _Alloc>::_S_instanceless> 26297403Sobrien _Base; 26397403Sobrien typedef typename _Base::allocator_type allocator_type; 26497403Sobrien 26597403Sobrien _Slist_base(const allocator_type& __a) 26697403Sobrien : _Base(__a) { this->_M_head._M_next = 0; } 26797403Sobrien ~_Slist_base() { _M_erase_after(&this->_M_head, 0); } 26897403Sobrien 26997403Sobrienprotected: 27097403Sobrien 27197403Sobrien _Slist_node_base* _M_erase_after(_Slist_node_base* __pos) 27297403Sobrien { 27397403Sobrien _Slist_node<_Tp>* __next = (_Slist_node<_Tp>*) (__pos->_M_next); 27497403Sobrien _Slist_node_base* __next_next = __next->_M_next; 27597403Sobrien __pos->_M_next = __next_next; 27697403Sobrien _Destroy(&__next->_M_data); 27797403Sobrien _M_put_node(__next); 27897403Sobrien return __next_next; 27997403Sobrien } 28097403Sobrien _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*); 28197403Sobrien}; 28297403Sobrien 28397403Sobrientemplate <class _Tp, class _Alloc> 28497403Sobrien_Slist_node_base* 28597403Sobrien_Slist_base<_Tp,_Alloc>::_M_erase_after(_Slist_node_base* __before_first, 28697403Sobrien _Slist_node_base* __last_node) { 28797403Sobrien _Slist_node<_Tp>* __cur = (_Slist_node<_Tp>*) (__before_first->_M_next); 28897403Sobrien while (__cur != __last_node) { 28997403Sobrien _Slist_node<_Tp>* __tmp = __cur; 29097403Sobrien __cur = (_Slist_node<_Tp>*) __cur->_M_next; 29197403Sobrien _Destroy(&__tmp->_M_data); 29297403Sobrien _M_put_node(__tmp); 29397403Sobrien } 29497403Sobrien __before_first->_M_next = __last_node; 29597403Sobrien return __last_node; 29697403Sobrien} 29797403Sobrien 29897403Sobrientemplate <class _Tp, class _Alloc = allocator<_Tp> > 29997403Sobrienclass slist : private _Slist_base<_Tp,_Alloc> 30097403Sobrien{ 30197403Sobrien // concept requirements 30297403Sobrien __glibcpp_class_requires(_Tp, _SGIAssignableConcept) 30397403Sobrien 30497403Sobrienprivate: 30597403Sobrien typedef _Slist_base<_Tp,_Alloc> _Base; 30697403Sobrienpublic: 30797403Sobrien typedef _Tp value_type; 30897403Sobrien typedef value_type* pointer; 30997403Sobrien typedef const value_type* const_pointer; 31097403Sobrien typedef value_type& reference; 31197403Sobrien typedef const value_type& const_reference; 31297403Sobrien typedef size_t size_type; 31397403Sobrien typedef ptrdiff_t difference_type; 31497403Sobrien 31597403Sobrien typedef _Slist_iterator<_Tp, _Tp&, _Tp*> iterator; 31697403Sobrien typedef _Slist_iterator<_Tp, const _Tp&, const _Tp*> const_iterator; 31797403Sobrien 31897403Sobrien typedef typename _Base::allocator_type allocator_type; 31997403Sobrien allocator_type get_allocator() const { return _Base::get_allocator(); } 32097403Sobrien 32197403Sobrienprivate: 32297403Sobrien typedef _Slist_node<_Tp> _Node; 32397403Sobrien typedef _Slist_node_base _Node_base; 32497403Sobrien typedef _Slist_iterator_base _Iterator_base; 32597403Sobrien 32697403Sobrien _Node* _M_create_node(const value_type& __x) { 32797403Sobrien _Node* __node = this->_M_get_node(); 32897403Sobrien try { 32997403Sobrien _Construct(&__node->_M_data, __x); 33097403Sobrien __node->_M_next = 0; 33197403Sobrien } 33297403Sobrien catch(...) 33397403Sobrien { 33497403Sobrien this->_M_put_node(__node); 33597403Sobrien __throw_exception_again; 33697403Sobrien } 33797403Sobrien return __node; 33897403Sobrien } 33997403Sobrien 34097403Sobrien _Node* _M_create_node() { 34197403Sobrien _Node* __node = this->_M_get_node(); 34297403Sobrien try { 34397403Sobrien _Construct(&__node->_M_data); 34497403Sobrien __node->_M_next = 0; 34597403Sobrien } 34697403Sobrien catch(...) 34797403Sobrien { 34897403Sobrien this->_M_put_node(__node); 34997403Sobrien __throw_exception_again; 35097403Sobrien } 35197403Sobrien return __node; 35297403Sobrien } 35397403Sobrien 35497403Sobrienpublic: 35597403Sobrien explicit slist(const allocator_type& __a = allocator_type()) : _Base(__a) {} 35697403Sobrien 35797403Sobrien slist(size_type __n, const value_type& __x, 35897403Sobrien const allocator_type& __a = allocator_type()) : _Base(__a) 35997403Sobrien { _M_insert_after_fill(&this->_M_head, __n, __x); } 36097403Sobrien 36197403Sobrien explicit slist(size_type __n) : _Base(allocator_type()) 36297403Sobrien { _M_insert_after_fill(&this->_M_head, __n, value_type()); } 36397403Sobrien 36497403Sobrien // We don't need any dispatching tricks here, because _M_insert_after_range 36597403Sobrien // already does them. 36697403Sobrien template <class _InputIterator> 36797403Sobrien slist(_InputIterator __first, _InputIterator __last, 36897403Sobrien const allocator_type& __a = allocator_type()) : _Base(__a) 36997403Sobrien { _M_insert_after_range(&this->_M_head, __first, __last); } 37097403Sobrien 37197403Sobrien slist(const slist& __x) : _Base(__x.get_allocator()) 37297403Sobrien { _M_insert_after_range(&this->_M_head, __x.begin(), __x.end()); } 37397403Sobrien 37497403Sobrien slist& operator= (const slist& __x); 37597403Sobrien 37697403Sobrien ~slist() {} 37797403Sobrien 37897403Sobrienpublic: 37997403Sobrien // assign(), a generalized assignment member function. Two 38097403Sobrien // versions: one that takes a count, and one that takes a range. 38197403Sobrien // The range version is a member template, so we dispatch on whether 38297403Sobrien // or not the type is an integer. 38397403Sobrien 38497403Sobrien void assign(size_type __n, const _Tp& __val) 38597403Sobrien { _M_fill_assign(__n, __val); } 38697403Sobrien 38797403Sobrien void _M_fill_assign(size_type __n, const _Tp& __val); 38897403Sobrien 38997403Sobrien template <class _InputIterator> 39097403Sobrien void assign(_InputIterator __first, _InputIterator __last) { 39197403Sobrien typedef typename _Is_integer<_InputIterator>::_Integral _Integral; 39297403Sobrien _M_assign_dispatch(__first, __last, _Integral()); 39397403Sobrien } 39497403Sobrien 39597403Sobrien template <class _Integer> 39697403Sobrien void _M_assign_dispatch(_Integer __n, _Integer __val, __true_type) 39797403Sobrien { _M_fill_assign((size_type) __n, (_Tp) __val); } 39897403Sobrien 39997403Sobrien template <class _InputIterator> 40097403Sobrien void _M_assign_dispatch(_InputIterator __first, _InputIterator __last, 40197403Sobrien __false_type); 40297403Sobrien 40397403Sobrienpublic: 40497403Sobrien 40597403Sobrien iterator begin() { return iterator((_Node*)this->_M_head._M_next); } 40697403Sobrien const_iterator begin() const 40797403Sobrien { return const_iterator((_Node*)this->_M_head._M_next);} 40897403Sobrien 40997403Sobrien iterator end() { return iterator(0); } 41097403Sobrien const_iterator end() const { return const_iterator(0); } 41197403Sobrien 41297403Sobrien // Experimental new feature: before_begin() returns a 41397403Sobrien // non-dereferenceable iterator that, when incremented, yields 41497403Sobrien // begin(). This iterator may be used as the argument to 41597403Sobrien // insert_after, erase_after, etc. Note that even for an empty 41697403Sobrien // slist, before_begin() is not the same iterator as end(). It 41797403Sobrien // is always necessary to increment before_begin() at least once to 41897403Sobrien // obtain end(). 41997403Sobrien iterator before_begin() { return iterator((_Node*) &this->_M_head); } 42097403Sobrien const_iterator before_begin() const 42197403Sobrien { return const_iterator((_Node*) &this->_M_head); } 42297403Sobrien 42397403Sobrien size_type size() const { return __slist_size(this->_M_head._M_next); } 42497403Sobrien 42597403Sobrien size_type max_size() const { return size_type(-1); } 42697403Sobrien 42797403Sobrien bool empty() const { return this->_M_head._M_next == 0; } 42897403Sobrien 42997403Sobrien void swap(slist& __x) 43097403Sobrien { std::swap(this->_M_head._M_next, __x._M_head._M_next); } 43197403Sobrien 43297403Sobrienpublic: 43397403Sobrien 43497403Sobrien reference front() { return ((_Node*) this->_M_head._M_next)->_M_data; } 43597403Sobrien const_reference front() const 43697403Sobrien { return ((_Node*) this->_M_head._M_next)->_M_data; } 43797403Sobrien void push_front(const value_type& __x) { 43897403Sobrien __slist_make_link(&this->_M_head, _M_create_node(__x)); 43997403Sobrien } 44097403Sobrien void push_front() { __slist_make_link(&this->_M_head, _M_create_node()); } 44197403Sobrien void pop_front() { 44297403Sobrien _Node* __node = (_Node*) this->_M_head._M_next; 44397403Sobrien this->_M_head._M_next = __node->_M_next; 44497403Sobrien _Destroy(&__node->_M_data); 44597403Sobrien this->_M_put_node(__node); 44697403Sobrien } 44797403Sobrien 44897403Sobrien iterator previous(const_iterator __pos) { 44997403Sobrien return iterator((_Node*) __slist_previous(&this->_M_head, __pos._M_node)); 45097403Sobrien } 45197403Sobrien const_iterator previous(const_iterator __pos) const { 45297403Sobrien return const_iterator((_Node*) __slist_previous(&this->_M_head, 45397403Sobrien __pos._M_node)); 45497403Sobrien } 45597403Sobrien 45697403Sobrienprivate: 45797403Sobrien _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) { 45897403Sobrien return (_Node*) (__slist_make_link(__pos, _M_create_node(__x))); 45997403Sobrien } 46097403Sobrien 46197403Sobrien _Node* _M_insert_after(_Node_base* __pos) { 46297403Sobrien return (_Node*) (__slist_make_link(__pos, _M_create_node())); 46397403Sobrien } 46497403Sobrien 46597403Sobrien void _M_insert_after_fill(_Node_base* __pos, 46697403Sobrien size_type __n, const value_type& __x) { 46797403Sobrien for (size_type __i = 0; __i < __n; ++__i) 46897403Sobrien __pos = __slist_make_link(__pos, _M_create_node(__x)); 46997403Sobrien } 47097403Sobrien 47197403Sobrien // Check whether it's an integral type. If so, it's not an iterator. 47297403Sobrien template <class _InIter> 47397403Sobrien void _M_insert_after_range(_Node_base* __pos, 47497403Sobrien _InIter __first, _InIter __last) { 47597403Sobrien typedef typename _Is_integer<_InIter>::_Integral _Integral; 47697403Sobrien _M_insert_after_range(__pos, __first, __last, _Integral()); 47797403Sobrien } 47897403Sobrien 47997403Sobrien template <class _Integer> 48097403Sobrien void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x, 48197403Sobrien __true_type) { 48297403Sobrien _M_insert_after_fill(__pos, __n, __x); 48397403Sobrien } 48497403Sobrien 48597403Sobrien template <class _InIter> 48697403Sobrien void _M_insert_after_range(_Node_base* __pos, 48797403Sobrien _InIter __first, _InIter __last, 48897403Sobrien __false_type) { 48997403Sobrien while (__first != __last) { 49097403Sobrien __pos = __slist_make_link(__pos, _M_create_node(*__first)); 49197403Sobrien ++__first; 49297403Sobrien } 49397403Sobrien } 49497403Sobrien 49597403Sobrienpublic: 49697403Sobrien 49797403Sobrien iterator insert_after(iterator __pos, const value_type& __x) { 49897403Sobrien return iterator(_M_insert_after(__pos._M_node, __x)); 49997403Sobrien } 50097403Sobrien 50197403Sobrien iterator insert_after(iterator __pos) { 50297403Sobrien return insert_after(__pos, value_type()); 50397403Sobrien } 50497403Sobrien 50597403Sobrien void insert_after(iterator __pos, size_type __n, const value_type& __x) { 50697403Sobrien _M_insert_after_fill(__pos._M_node, __n, __x); 50797403Sobrien } 50897403Sobrien 50997403Sobrien // We don't need any dispatching tricks here, because _M_insert_after_range 51097403Sobrien // already does them. 51197403Sobrien template <class _InIter> 51297403Sobrien void insert_after(iterator __pos, _InIter __first, _InIter __last) { 51397403Sobrien _M_insert_after_range(__pos._M_node, __first, __last); 51497403Sobrien } 51597403Sobrien 51697403Sobrien iterator insert(iterator __pos, const value_type& __x) { 51797403Sobrien return iterator(_M_insert_after(__slist_previous(&this->_M_head, 51897403Sobrien __pos._M_node), 51997403Sobrien __x)); 52097403Sobrien } 52197403Sobrien 52297403Sobrien iterator insert(iterator __pos) { 52397403Sobrien return iterator(_M_insert_after(__slist_previous(&this->_M_head, 52497403Sobrien __pos._M_node), 52597403Sobrien value_type())); 52697403Sobrien } 52797403Sobrien 52897403Sobrien void insert(iterator __pos, size_type __n, const value_type& __x) { 52997403Sobrien _M_insert_after_fill(__slist_previous(&this->_M_head, __pos._M_node), 53097403Sobrien __n, __x); 53197403Sobrien } 53297403Sobrien 53397403Sobrien // We don't need any dispatching tricks here, because _M_insert_after_range 53497403Sobrien // already does them. 53597403Sobrien template <class _InIter> 53697403Sobrien void insert(iterator __pos, _InIter __first, _InIter __last) { 53797403Sobrien _M_insert_after_range(__slist_previous(&this->_M_head, __pos._M_node), 53897403Sobrien __first, __last); 53997403Sobrien } 54097403Sobrien 54197403Sobrienpublic: 54297403Sobrien iterator erase_after(iterator __pos) { 54397403Sobrien return iterator((_Node*) this->_M_erase_after(__pos._M_node)); 54497403Sobrien } 54597403Sobrien iterator erase_after(iterator __before_first, iterator __last) { 54697403Sobrien return iterator((_Node*) this->_M_erase_after(__before_first._M_node, 54797403Sobrien __last._M_node)); 54897403Sobrien } 54997403Sobrien 55097403Sobrien iterator erase(iterator __pos) { 55197403Sobrien return (_Node*) this->_M_erase_after(__slist_previous(&this->_M_head, 55297403Sobrien __pos._M_node)); 55397403Sobrien } 55497403Sobrien iterator erase(iterator __first, iterator __last) { 55597403Sobrien return (_Node*) this->_M_erase_after( 55697403Sobrien __slist_previous(&this->_M_head, __first._M_node), __last._M_node); 55797403Sobrien } 55897403Sobrien 55997403Sobrien void resize(size_type new_size, const _Tp& __x); 56097403Sobrien void resize(size_type new_size) { resize(new_size, _Tp()); } 56197403Sobrien void clear() { this->_M_erase_after(&this->_M_head, 0); } 56297403Sobrien 56397403Sobrienpublic: 56497403Sobrien // Moves the range [__before_first + 1, __before_last + 1) to *this, 56597403Sobrien // inserting it immediately after __pos. This is constant time. 56697403Sobrien void splice_after(iterator __pos, 56797403Sobrien iterator __before_first, iterator __before_last) 56897403Sobrien { 56997403Sobrien if (__before_first != __before_last) 57097403Sobrien __slist_splice_after(__pos._M_node, __before_first._M_node, 57197403Sobrien __before_last._M_node); 57297403Sobrien } 57397403Sobrien 57497403Sobrien // Moves the element that follows __prev to *this, inserting it immediately 57597403Sobrien // after __pos. This is constant time. 57697403Sobrien void splice_after(iterator __pos, iterator __prev) 57797403Sobrien { 57897403Sobrien __slist_splice_after(__pos._M_node, 57997403Sobrien __prev._M_node, __prev._M_node->_M_next); 58097403Sobrien } 58197403Sobrien 58297403Sobrien 58397403Sobrien // Removes all of the elements from the list __x to *this, inserting 58497403Sobrien // them immediately after __pos. __x must not be *this. Complexity: 58597403Sobrien // linear in __x.size(). 58697403Sobrien void splice_after(iterator __pos, slist& __x) 58797403Sobrien { 58897403Sobrien __slist_splice_after(__pos._M_node, &__x._M_head); 58997403Sobrien } 59097403Sobrien 59197403Sobrien // Linear in distance(begin(), __pos), and linear in __x.size(). 59297403Sobrien void splice(iterator __pos, slist& __x) { 59397403Sobrien if (__x._M_head._M_next) 59497403Sobrien __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 59597403Sobrien &__x._M_head, __slist_previous(&__x._M_head, 0)); 59697403Sobrien } 59797403Sobrien 59897403Sobrien // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i). 59997403Sobrien void splice(iterator __pos, slist& __x, iterator __i) { 60097403Sobrien __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 60197403Sobrien __slist_previous(&__x._M_head, __i._M_node), 60297403Sobrien __i._M_node); 60397403Sobrien } 60497403Sobrien 60597403Sobrien // Linear in distance(begin(), __pos), in distance(__x.begin(), __first), 60697403Sobrien // and in distance(__first, __last). 60797403Sobrien void splice(iterator __pos, slist& __x, iterator __first, iterator __last) 60897403Sobrien { 60997403Sobrien if (__first != __last) 61097403Sobrien __slist_splice_after(__slist_previous(&this->_M_head, __pos._M_node), 61197403Sobrien __slist_previous(&__x._M_head, __first._M_node), 61297403Sobrien __slist_previous(__first._M_node, __last._M_node)); 61397403Sobrien } 61497403Sobrien 61597403Sobrienpublic: 61697403Sobrien void reverse() { 61797403Sobrien if (this->_M_head._M_next) 61897403Sobrien this->_M_head._M_next = __slist_reverse(this->_M_head._M_next); 61997403Sobrien } 62097403Sobrien 62197403Sobrien void remove(const _Tp& __val); 62297403Sobrien void unique(); 62397403Sobrien void merge(slist& __x); 62497403Sobrien void sort(); 62597403Sobrien 62697403Sobrien template <class _Predicate> 62797403Sobrien void remove_if(_Predicate __pred); 62897403Sobrien 62997403Sobrien template <class _BinaryPredicate> 63097403Sobrien void unique(_BinaryPredicate __pred); 63197403Sobrien 63297403Sobrien template <class _StrictWeakOrdering> 63397403Sobrien void merge(slist&, _StrictWeakOrdering); 63497403Sobrien 63597403Sobrien template <class _StrictWeakOrdering> 63697403Sobrien void sort(_StrictWeakOrdering __comp); 63797403Sobrien}; 63897403Sobrien 63997403Sobrientemplate <class _Tp, class _Alloc> 64097403Sobrienslist<_Tp,_Alloc>& slist<_Tp,_Alloc>::operator=(const slist<_Tp,_Alloc>& __x) 64197403Sobrien{ 64297403Sobrien if (&__x != this) { 64397403Sobrien _Node_base* __p1 = &this->_M_head; 64497403Sobrien _Node* __n1 = (_Node*) this->_M_head._M_next; 64597403Sobrien const _Node* __n2 = (const _Node*) __x._M_head._M_next; 64697403Sobrien while (__n1 && __n2) { 64797403Sobrien __n1->_M_data = __n2->_M_data; 64897403Sobrien __p1 = __n1; 64997403Sobrien __n1 = (_Node*) __n1->_M_next; 65097403Sobrien __n2 = (const _Node*) __n2->_M_next; 65197403Sobrien } 65297403Sobrien if (__n2 == 0) 65397403Sobrien this->_M_erase_after(__p1, 0); 65497403Sobrien else 65597403Sobrien _M_insert_after_range(__p1, const_iterator((_Node*)__n2), 65697403Sobrien const_iterator(0)); 65797403Sobrien } 65897403Sobrien return *this; 65997403Sobrien} 66097403Sobrien 66197403Sobrientemplate <class _Tp, class _Alloc> 66297403Sobrienvoid slist<_Tp, _Alloc>::_M_fill_assign(size_type __n, const _Tp& __val) { 66397403Sobrien _Node_base* __prev = &this->_M_head; 66497403Sobrien _Node* __node = (_Node*) this->_M_head._M_next; 66597403Sobrien for ( ; __node != 0 && __n > 0 ; --__n) { 66697403Sobrien __node->_M_data = __val; 66797403Sobrien __prev = __node; 66897403Sobrien __node = (_Node*) __node->_M_next; 66997403Sobrien } 67097403Sobrien if (__n > 0) 67197403Sobrien _M_insert_after_fill(__prev, __n, __val); 67297403Sobrien else 67397403Sobrien this->_M_erase_after(__prev, 0); 67497403Sobrien} 67597403Sobrien 67697403Sobrientemplate <class _Tp, class _Alloc> template <class _InputIter> 67797403Sobrienvoid 67897403Sobrienslist<_Tp, _Alloc>::_M_assign_dispatch(_InputIter __first, _InputIter __last, 67997403Sobrien __false_type) 68097403Sobrien{ 68197403Sobrien _Node_base* __prev = &this->_M_head; 68297403Sobrien _Node* __node = (_Node*) this->_M_head._M_next; 68397403Sobrien while (__node != 0 && __first != __last) { 68497403Sobrien __node->_M_data = *__first; 68597403Sobrien __prev = __node; 68697403Sobrien __node = (_Node*) __node->_M_next; 68797403Sobrien ++__first; 68897403Sobrien } 68997403Sobrien if (__first != __last) 69097403Sobrien _M_insert_after_range(__prev, __first, __last); 69197403Sobrien else 69297403Sobrien this->_M_erase_after(__prev, 0); 69397403Sobrien} 69497403Sobrien 69597403Sobrientemplate <class _Tp, class _Alloc> 69697403Sobrieninline bool 69797403Sobrienoperator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) 69897403Sobrien{ 69997403Sobrien typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator; 70097403Sobrien const_iterator __end1 = _SL1.end(); 70197403Sobrien const_iterator __end2 = _SL2.end(); 70297403Sobrien 70397403Sobrien const_iterator __i1 = _SL1.begin(); 70497403Sobrien const_iterator __i2 = _SL2.begin(); 70597403Sobrien while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) { 70697403Sobrien ++__i1; 70797403Sobrien ++__i2; 70897403Sobrien } 70997403Sobrien return __i1 == __end1 && __i2 == __end2; 71097403Sobrien} 71197403Sobrien 71297403Sobrien 71397403Sobrientemplate <class _Tp, class _Alloc> 71497403Sobrieninline bool 71597403Sobrienoperator<(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) 71697403Sobrien{ 71797403Sobrien return std::lexicographical_compare(_SL1.begin(), _SL1.end(), 71897403Sobrien _SL2.begin(), _SL2.end()); 71997403Sobrien} 72097403Sobrien 72197403Sobrientemplate <class _Tp, class _Alloc> 72297403Sobrieninline bool 72397403Sobrienoperator!=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { 72497403Sobrien return !(_SL1 == _SL2); 72597403Sobrien} 72697403Sobrien 72797403Sobrientemplate <class _Tp, class _Alloc> 72897403Sobrieninline bool 72997403Sobrienoperator>(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { 73097403Sobrien return _SL2 < _SL1; 73197403Sobrien} 73297403Sobrien 73397403Sobrientemplate <class _Tp, class _Alloc> 73497403Sobrieninline bool 73597403Sobrienoperator<=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { 73697403Sobrien return !(_SL2 < _SL1); 73797403Sobrien} 73897403Sobrien 73997403Sobrientemplate <class _Tp, class _Alloc> 74097403Sobrieninline bool 74197403Sobrienoperator>=(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2) { 74297403Sobrien return !(_SL1 < _SL2); 74397403Sobrien} 74497403Sobrien 74597403Sobrientemplate <class _Tp, class _Alloc> 74697403Sobrieninline void swap(slist<_Tp,_Alloc>& __x, slist<_Tp,_Alloc>& __y) { 74797403Sobrien __x.swap(__y); 74897403Sobrien} 74997403Sobrien 75097403Sobrien 75197403Sobrientemplate <class _Tp, class _Alloc> 75297403Sobrienvoid slist<_Tp,_Alloc>::resize(size_type __len, const _Tp& __x) 75397403Sobrien{ 75497403Sobrien _Node_base* __cur = &this->_M_head; 75597403Sobrien while (__cur->_M_next != 0 && __len > 0) { 75697403Sobrien --__len; 75797403Sobrien __cur = __cur->_M_next; 75897403Sobrien } 75997403Sobrien if (__cur->_M_next) 76097403Sobrien this->_M_erase_after(__cur, 0); 76197403Sobrien else 76297403Sobrien _M_insert_after_fill(__cur, __len, __x); 76397403Sobrien} 76497403Sobrien 76597403Sobrientemplate <class _Tp, class _Alloc> 76697403Sobrienvoid slist<_Tp,_Alloc>::remove(const _Tp& __val) 76797403Sobrien{ 76897403Sobrien _Node_base* __cur = &this->_M_head; 76997403Sobrien while (__cur && __cur->_M_next) { 77097403Sobrien if (((_Node*) __cur->_M_next)->_M_data == __val) 77197403Sobrien this->_M_erase_after(__cur); 77297403Sobrien else 77397403Sobrien __cur = __cur->_M_next; 77497403Sobrien } 77597403Sobrien} 77697403Sobrien 77797403Sobrientemplate <class _Tp, class _Alloc> 77897403Sobrienvoid slist<_Tp,_Alloc>::unique() 77997403Sobrien{ 78097403Sobrien _Node_base* __cur = this->_M_head._M_next; 78197403Sobrien if (__cur) { 78297403Sobrien while (__cur->_M_next) { 78397403Sobrien if (((_Node*)__cur)->_M_data == 78497403Sobrien ((_Node*)(__cur->_M_next))->_M_data) 78597403Sobrien this->_M_erase_after(__cur); 78697403Sobrien else 78797403Sobrien __cur = __cur->_M_next; 78897403Sobrien } 78997403Sobrien } 79097403Sobrien} 79197403Sobrien 79297403Sobrientemplate <class _Tp, class _Alloc> 79397403Sobrienvoid slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x) 79497403Sobrien{ 79597403Sobrien _Node_base* __n1 = &this->_M_head; 79697403Sobrien while (__n1->_M_next && __x._M_head._M_next) { 79797403Sobrien if (((_Node*) __x._M_head._M_next)->_M_data < 79897403Sobrien ((_Node*) __n1->_M_next)->_M_data) 79997403Sobrien __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); 80097403Sobrien __n1 = __n1->_M_next; 80197403Sobrien } 80297403Sobrien if (__x._M_head._M_next) { 80397403Sobrien __n1->_M_next = __x._M_head._M_next; 80497403Sobrien __x._M_head._M_next = 0; 80597403Sobrien } 80697403Sobrien} 80797403Sobrien 80897403Sobrientemplate <class _Tp, class _Alloc> 80997403Sobrienvoid slist<_Tp,_Alloc>::sort() 81097403Sobrien{ 81197403Sobrien if (this->_M_head._M_next && this->_M_head._M_next->_M_next) { 81297403Sobrien slist __carry; 81397403Sobrien slist __counter[64]; 81497403Sobrien int __fill = 0; 81597403Sobrien while (!empty()) { 81697403Sobrien __slist_splice_after(&__carry._M_head, 81797403Sobrien &this->_M_head, this->_M_head._M_next); 81897403Sobrien int __i = 0; 81997403Sobrien while (__i < __fill && !__counter[__i].empty()) { 82097403Sobrien __counter[__i].merge(__carry); 82197403Sobrien __carry.swap(__counter[__i]); 82297403Sobrien ++__i; 82397403Sobrien } 82497403Sobrien __carry.swap(__counter[__i]); 82597403Sobrien if (__i == __fill) 82697403Sobrien ++__fill; 82797403Sobrien } 82897403Sobrien 82997403Sobrien for (int __i = 1; __i < __fill; ++__i) 83097403Sobrien __counter[__i].merge(__counter[__i-1]); 83197403Sobrien this->swap(__counter[__fill-1]); 83297403Sobrien } 83397403Sobrien} 83497403Sobrien 83597403Sobrientemplate <class _Tp, class _Alloc> 83697403Sobrientemplate <class _Predicate> 83797403Sobrienvoid slist<_Tp,_Alloc>::remove_if(_Predicate __pred) 83897403Sobrien{ 83997403Sobrien _Node_base* __cur = &this->_M_head; 84097403Sobrien while (__cur->_M_next) { 84197403Sobrien if (__pred(((_Node*) __cur->_M_next)->_M_data)) 84297403Sobrien this->_M_erase_after(__cur); 84397403Sobrien else 84497403Sobrien __cur = __cur->_M_next; 84597403Sobrien } 84697403Sobrien} 84797403Sobrien 84897403Sobrientemplate <class _Tp, class _Alloc> template <class _BinaryPredicate> 84997403Sobrienvoid slist<_Tp,_Alloc>::unique(_BinaryPredicate __pred) 85097403Sobrien{ 85197403Sobrien _Node* __cur = (_Node*) this->_M_head._M_next; 85297403Sobrien if (__cur) { 85397403Sobrien while (__cur->_M_next) { 85497403Sobrien if (__pred(((_Node*)__cur)->_M_data, 85597403Sobrien ((_Node*)(__cur->_M_next))->_M_data)) 85697403Sobrien this->_M_erase_after(__cur); 85797403Sobrien else 85897403Sobrien __cur = (_Node*) __cur->_M_next; 85997403Sobrien } 86097403Sobrien } 86197403Sobrien} 86297403Sobrien 86397403Sobrientemplate <class _Tp, class _Alloc> template <class _StrictWeakOrdering> 86497403Sobrienvoid slist<_Tp,_Alloc>::merge(slist<_Tp,_Alloc>& __x, 86597403Sobrien _StrictWeakOrdering __comp) 86697403Sobrien{ 86797403Sobrien _Node_base* __n1 = &this->_M_head; 86897403Sobrien while (__n1->_M_next && __x._M_head._M_next) { 86997403Sobrien if (__comp(((_Node*) __x._M_head._M_next)->_M_data, 87097403Sobrien ((_Node*) __n1->_M_next)->_M_data)) 87197403Sobrien __slist_splice_after(__n1, &__x._M_head, __x._M_head._M_next); 87297403Sobrien __n1 = __n1->_M_next; 87397403Sobrien } 87497403Sobrien if (__x._M_head._M_next) { 87597403Sobrien __n1->_M_next = __x._M_head._M_next; 87697403Sobrien __x._M_head._M_next = 0; 87797403Sobrien } 87897403Sobrien} 87997403Sobrien 88097403Sobrientemplate <class _Tp, class _Alloc> template <class _StrictWeakOrdering> 88197403Sobrienvoid slist<_Tp,_Alloc>::sort(_StrictWeakOrdering __comp) 88297403Sobrien{ 88397403Sobrien if (this->_M_head._M_next && this->_M_head._M_next->_M_next) { 88497403Sobrien slist __carry; 88597403Sobrien slist __counter[64]; 88697403Sobrien int __fill = 0; 88797403Sobrien while (!empty()) { 88897403Sobrien __slist_splice_after(&__carry._M_head, 88997403Sobrien &this->_M_head, this->_M_head._M_next); 89097403Sobrien int __i = 0; 89197403Sobrien while (__i < __fill && !__counter[__i].empty()) { 89297403Sobrien __counter[__i].merge(__carry, __comp); 89397403Sobrien __carry.swap(__counter[__i]); 89497403Sobrien ++__i; 89597403Sobrien } 89697403Sobrien __carry.swap(__counter[__i]); 89797403Sobrien if (__i == __fill) 89897403Sobrien ++__fill; 89997403Sobrien } 90097403Sobrien 90197403Sobrien for (int __i = 1; __i < __fill; ++__i) 90297403Sobrien __counter[__i].merge(__counter[__i-1], __comp); 90397403Sobrien this->swap(__counter[__fill-1]); 90497403Sobrien } 90597403Sobrien} 90697403Sobrien 90797403Sobrien} // namespace __gnu_cxx 90897403Sobrien 90997403Sobriennamespace std 91097403Sobrien{ 91197403Sobrien// Specialization of insert_iterator so that insertions will be constant 91297403Sobrien// time rather than linear time. 91397403Sobrien 91497403Sobrientemplate <class _Tp, class _Alloc> 91597403Sobrienclass insert_iterator<__gnu_cxx::slist<_Tp, _Alloc> > { 91697403Sobrienprotected: 91797403Sobrien typedef __gnu_cxx::slist<_Tp, _Alloc> _Container; 91897403Sobrien _Container* container; 91997403Sobrien typename _Container::iterator iter; 92097403Sobrienpublic: 92197403Sobrien typedef _Container container_type; 92297403Sobrien typedef output_iterator_tag iterator_category; 92397403Sobrien typedef void value_type; 92497403Sobrien typedef void difference_type; 92597403Sobrien typedef void pointer; 92697403Sobrien typedef void reference; 92797403Sobrien 92897403Sobrien insert_iterator(_Container& __x, typename _Container::iterator __i) 92997403Sobrien : container(&__x) { 93097403Sobrien if (__i == __x.begin()) 93197403Sobrien iter = __x.before_begin(); 93297403Sobrien else 93397403Sobrien iter = __x.previous(__i); 93497403Sobrien } 93597403Sobrien 93697403Sobrien insert_iterator<_Container>& 93797403Sobrien operator=(const typename _Container::value_type& __value) { 93897403Sobrien iter = container->insert_after(iter, __value); 93997403Sobrien return *this; 94097403Sobrien } 94197403Sobrien insert_iterator<_Container>& operator*() { return *this; } 94297403Sobrien insert_iterator<_Container>& operator++() { return *this; } 94397403Sobrien insert_iterator<_Container>& operator++(int) { return *this; } 94497403Sobrien}; 94597403Sobrien 94697403Sobrien} // namespace std 94797403Sobrien 94897403Sobrien#endif /* __SGI_STL_INTERNAL_SLIST_H */ 94997403Sobrien 95097403Sobrien// Local Variables: 95197403Sobrien// mode:C++ 95297403Sobrien// End: 953