1.1 --- a/epoc32/include/stdapis/stlport/stl/_slist.h Tue Nov 24 13:55:44 2009 +0000
1.2 +++ b/epoc32/include/stdapis/stlport/stl/_slist.h Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -1,1 +1,786 @@
1.4 -_slist.h
1.5 +/*
1.6 + *
1.7 + * Copyright (c) 1996,1997
1.8 + * Silicon Graphics Computer Systems, Inc.
1.9 + *
1.10 + * Copyright (c) 1997
1.11 + * Moscow Center for SPARC Technology
1.12 + *
1.13 + * Copyright (c) 1999
1.14 + * Boris Fomitchev
1.15 + *
1.16 + * This material is provided "as is", with absolutely no warranty expressed
1.17 + * or implied. Any use is at your own risk.
1.18 + *
1.19 + * Permission to use or copy this software for any purpose is hereby granted
1.20 + * without fee, provided the above notices are retained on all copies.
1.21 + * Permission to modify the code and to distribute modified code is granted,
1.22 + * provided the above notices are retained, and a notice that the code was
1.23 + * modified is included with the above copyright notice.
1.24 + *
1.25 + */
1.26 +
1.27 +/* NOTE: This is an internal header file, included by other STL headers.
1.28 + * You should not attempt to use it directly.
1.29 + */
1.30 +
1.31 +#ifndef _STLP_INTERNAL_SLIST_H
1.32 +#define _STLP_INTERNAL_SLIST_H
1.33 +
1.34 +
1.35 +# ifndef _STLP_INTERNAL_ALGOBASE_H
1.36 +# include <stl/_algobase.h>
1.37 +# endif
1.38 +
1.39 +# ifndef _STLP_INTERNAL_ALLOC_H
1.40 +# include <stl/_alloc.h>
1.41 +# endif
1.42 +
1.43 +# ifndef _STLP_INTERNAL_ITERATOR_H
1.44 +# include <stl/_iterator.h>
1.45 +# endif
1.46 +
1.47 +# ifndef _STLP_INTERNAL_CONSTRUCT_H
1.48 +# include <stl/_construct.h>
1.49 +# endif
1.50 +
1.51 +# ifndef _STLP_INTERNAL_SLIST_BASE_H
1.52 +# include <stl/_slist_base.h>
1.53 +# endif
1.54 +
1.55 +# undef slist
1.56 +# define slist __WORKAROUND_DBG_RENAME(slist)
1.57 +
1.58 +_STLP_BEGIN_NAMESPACE
1.59 +
1.60 +template <class _Tp>
1.61 +struct _Slist_node : public _Slist_node_base
1.62 +{
1.63 + _Tp _M_data;
1.64 + __TRIVIAL_STUFF(_Slist_node)
1.65 +};
1.66 +
1.67 +struct _Slist_iterator_base {
1.68 +
1.69 + typedef size_t size_type;
1.70 + typedef ptrdiff_t difference_type;
1.71 + typedef forward_iterator_tag iterator_category;
1.72 +
1.73 + _Slist_node_base* _M_node;
1.74 +
1.75 + _Slist_iterator_base(_Slist_node_base* __x) : _M_node(__x) {}
1.76 +
1.77 + void _M_incr() {
1.78 +// _STLP_VERBOSE_ASSERT(_M_node != 0, _StlMsg_INVALID_ADVANCE)
1.79 + _M_node = _M_node->_M_next;
1.80 + }
1.81 + bool operator==(const _Slist_iterator_base& __y ) const {
1.82 + return _M_node == __y._M_node;
1.83 + }
1.84 + bool operator!=(const _Slist_iterator_base& __y ) const {
1.85 + return _M_node != __y._M_node;
1.86 + }
1.87 +};
1.88 +
1.89 +# ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
1.90 +inline ptrdiff_t* _STLP_CALL distance_type(const _Slist_iterator_base&) { return 0; }
1.91 +inline forward_iterator_tag _STLP_CALL iterator_category(const _Slist_iterator_base&) { return forward_iterator_tag(); }
1.92 +#endif
1.93 +
1.94 +template <class _Tp, class _Traits>
1.95 +struct _Slist_iterator : public _Slist_iterator_base
1.96 +{
1.97 + typedef _Tp value_type;
1.98 + typedef typename _Traits::pointer pointer;
1.99 + typedef typename _Traits::reference reference;
1.100 + typedef forward_iterator_tag iterator_category;
1.101 + typedef size_t size_type;
1.102 + typedef ptrdiff_t difference_type;
1.103 +
1.104 + typedef _Slist_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
1.105 + typedef _Slist_iterator<_Tp, _Const_traits<_Tp> > const_iterator;
1.106 + typedef _Slist_iterator<_Tp, _Traits> _Self;
1.107 +
1.108 + typedef _Slist_node<value_type> _Node;
1.109 +
1.110 + _Slist_iterator(_Node* __x) : _Slist_iterator_base(__x) {}
1.111 + _Slist_iterator() : _Slist_iterator_base(0) {}
1.112 + _Slist_iterator(const iterator& __x) : _Slist_iterator_base(__x._M_node) {}
1.113 +
1.114 + reference operator*() const { return ((_Node*) _M_node)->_M_data; }
1.115 +
1.116 + _STLP_DEFINE_ARROW_OPERATOR
1.117 +
1.118 + _Self& operator++()
1.119 + {
1.120 + _M_incr();
1.121 + return *this;
1.122 + }
1.123 + _Self operator++(int)
1.124 + {
1.125 + _Self __tmp = *this;
1.126 + _M_incr();
1.127 + return __tmp;
1.128 + }
1.129 +};
1.130 +
1.131 +#ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
1.132 +template <class _Tp, class _Traits>
1.133 +inline _Tp* _STLP_CALL value_type(const _Slist_iterator<_Tp, _Traits>&) { return (_Tp*)0; }
1.134 +#endif /* OLD_QUERIES */
1.135 +
1.136 +// Base class that encapsulates details of allocators and simplifies EH
1.137 +
1.138 +template <class _Tp, class _Alloc>
1.139 +struct _Slist_base
1.140 +{
1.141 + _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
1.142 + typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
1.143 + typedef _Slist_node<_Tp> _Node;
1.144 +
1.145 + _Slist_base(const allocator_type& __a) :
1.146 + _M_head(_STLP_CONVERT_ALLOCATOR(__a, _Node), _Slist_node_base() ) {
1.147 + _M_head._M_data._M_next = 0;
1.148 + }
1.149 + ~_Slist_base() { _M_erase_after(&_M_head._M_data, 0); }
1.150 +
1.151 +protected:
1.152 + typedef typename _Alloc_traits<_Node,_Alloc>::allocator_type _M_node_allocator_type;
1.153 +
1.154 + _Slist_node_base* _M_erase_after(_Slist_node_base* __pos)
1.155 + {
1.156 + _Node* __next = (_Node*) (__pos->_M_next);
1.157 + _Slist_node_base* __next_next = __next->_M_next;
1.158 + __pos->_M_next = __next_next;
1.159 + _STLP_STD::_Destroy(&__next->_M_data);
1.160 + _M_head.deallocate(__next,1);
1.161 + return __next_next;
1.162 + }
1.163 + _Slist_node_base* _M_erase_after(_Slist_node_base*, _Slist_node_base*);
1.164 +
1.165 +public:
1.166 + allocator_type get_allocator() const {
1.167 + return _STLP_CONVERT_ALLOCATOR((const _M_node_allocator_type&)_M_head, _Tp);
1.168 + }
1.169 + _STLP_alloc_proxy<_Slist_node_base, _Node, _M_node_allocator_type> _M_head;
1.170 +};
1.171 +
1.172 +template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
1.173 +class slist : public _Slist_base<_Tp,_Alloc>
1.174 +{
1.175 +private:
1.176 + typedef _Slist_base<_Tp,_Alloc> _Base;
1.177 + typedef slist<_Tp,_Alloc> _Self;
1.178 +public:
1.179 + typedef _Tp value_type;
1.180 + typedef value_type* pointer;
1.181 + typedef const value_type* const_pointer;
1.182 + typedef value_type& reference;
1.183 + typedef const value_type& const_reference;
1.184 + typedef size_t size_type;
1.185 + typedef ptrdiff_t difference_type;
1.186 + typedef forward_iterator_tag _Iterator_category;
1.187 +
1.188 + typedef _Slist_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
1.189 + typedef _Slist_iterator<_Tp, _Const_traits<_Tp> > const_iterator;
1.190 +
1.191 + _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
1.192 + typedef typename _Base::allocator_type allocator_type;
1.193 +
1.194 +
1.195 +private:
1.196 + typedef _Slist_node<_Tp> _Node;
1.197 + typedef _Slist_node_base _Node_base;
1.198 + typedef _Slist_iterator_base _Iterator_base;
1.199 +
1.200 + _Node* _M_create_node(const value_type& __x) {
1.201 + _Node* __node = this->_M_head.allocate(1);
1.202 + _STLP_TRY {
1.203 + _Construct(&__node->_M_data, __x);
1.204 + __node->_M_next = 0;
1.205 + }
1.206 + _STLP_UNWIND(this->_M_head.deallocate(__node, 1));
1.207 + return __node;
1.208 + }
1.209 +
1.210 + _Node* _M_create_node() {
1.211 + _Node* __node = this->_M_head.allocate(1);
1.212 + _STLP_TRY {
1.213 + _Construct(&__node->_M_data);
1.214 + __node->_M_next = 0;
1.215 + }
1.216 + _STLP_UNWIND(this->_M_head.deallocate(__node, 1));
1.217 + return __node;
1.218 + }
1.219 +
1.220 +public:
1.221 + allocator_type get_allocator() const { return _Base::get_allocator(); }
1.222 +
1.223 + explicit slist(const allocator_type& __a = allocator_type()) : _Slist_base<_Tp,_Alloc>(__a) {
1.224 + _STLP_POP_IF_CHECK
1.225 + }
1.226 +
1.227 + slist(size_type __n, const value_type& __x,
1.228 + const allocator_type& __a = allocator_type()) : _Slist_base<_Tp,_Alloc>(__a)
1.229 + {
1.230 + _STLP_PUSH_CLEANUP_ITEM(_Base, this)
1.231 + _M_insert_after_fill(&this->_M_head._M_data, __n, __x);
1.232 + _STLP_POP_CLEANUP_ITEM
1.233 + }
1.234 +
1.235 + explicit slist(size_type __n) : _Slist_base<_Tp,_Alloc>(allocator_type())
1.236 + {
1.237 +# ifdef _STLP_USE_TRAP_LEAVE
1.238 + _STLP_PUSH_CLEANUP_ITEM(_Base, this)
1.239 + _Tp __p;
1.240 + _STLP_PUSH_CLEANUP_ITEM(_Tp, &__p)
1.241 + _M_insert_after_fill(&this->_M_head._M_data, __n, __p);
1.242 + // unconditional for __p
1.243 + CleanupStack::Pop();
1.244 + _STLP_POP_CLEANUP_ITEM
1.245 +# else
1.246 + _M_insert_after_fill(&this->_M_head._M_data, __n, value_type());
1.247 +# endif
1.248 + }
1.249 +
1.250 +#ifdef _STLP_MEMBER_TEMPLATES
1.251 + // We don't need any dispatching tricks here, because _M_insert_after_range
1.252 + // already does them.
1.253 + template <class _InputIterator>
1.254 + slist(_InputIterator __first, _InputIterator __last,
1.255 + const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) :
1.256 + _Slist_base<_Tp,_Alloc>(__a)
1.257 + {
1.258 + _STLP_PUSH_CLEANUP_ITEM(_Base, this)
1.259 + _M_insert_after_range(&this->_M_head._M_data, __first, __last);
1.260 + _STLP_POP_CLEANUP_ITEM
1.261 + }
1.262 +# ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
1.263 + // VC++ needs this crazyness
1.264 + template <class _InputIterator>
1.265 + slist(_InputIterator __first, _InputIterator __last) :
1.266 + _Slist_base<_Tp,_Alloc>(allocator_type())
1.267 + {
1.268 + _STLP_PUSH_CLEANUP_ITEM(_Base, this)
1.269 + _M_insert_after_range(&this->_M_head._M_data, __first, __last);
1.270 + _STLP_POP_CLEANUP_ITEM
1.271 + }
1.272 +# endif
1.273 +#else /* _STLP_MEMBER_TEMPLATES */
1.274 + slist(const_iterator __first, const_iterator __last,
1.275 + const allocator_type& __a = allocator_type() ) :
1.276 + _Slist_base<_Tp,_Alloc>(__a)
1.277 + {
1.278 + _STLP_PUSH_CLEANUP_ITEM(_Base, this)
1.279 + _M_insert_after_range(&this->_M_head._M_data, __first, __last);
1.280 + _STLP_POP_CLEANUP_ITEM
1.281 + }
1.282 + slist(const value_type* __first, const value_type* __last,
1.283 + const allocator_type& __a = allocator_type()) :
1.284 + _Slist_base<_Tp,_Alloc>(__a)
1.285 + {
1.286 + _STLP_PUSH_CLEANUP_ITEM(_Base, this)
1.287 + _M_insert_after_range(&this->_M_head._M_data, __first, __last);
1.288 + _STLP_POP_CLEANUP_ITEM
1.289 + }
1.290 +#endif /* _STLP_MEMBER_TEMPLATES */
1.291 +
1.292 + slist(const _Self& __x) : _Slist_base<_Tp,_Alloc>(__x.get_allocator())
1.293 + {
1.294 + _STLP_PUSH_CLEANUP_ITEM(_Base, this)
1.295 + _M_insert_after_range(&this->_M_head._M_data, __x.begin(), __x.end());
1.296 + _STLP_POP_CLEANUP_ITEM
1.297 + }
1.298 +
1.299 + _Self& operator= (const _Self& __x);
1.300 +
1.301 + ~slist() {}
1.302 +
1.303 +#ifdef _STLP_USE_TRAP_LEAVE
1.304 +public:
1.305 + static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper<bool>::_NewLC(__n); }
1.306 + static void* operator new (size_t __n) { return _STLP_StackHelper<bool>::_NewLC(__n); }
1.307 +#endif
1.308 +
1.309 +public:
1.310 + // assign(), a generalized assignment member function. Two
1.311 + // versions: one that takes a count, and one that takes a range.
1.312 + // The range version is a member template, so we dispatch on whether
1.313 + // or not the type is an integer.
1.314 +
1.315 + void assign(size_type __n, const _Tp& __val)
1.316 + { _M_fill_assign(__n, __val); }
1.317 +
1.318 + void _M_fill_assign(size_type __n, const _Tp& __val);
1.319 +
1.320 +#ifdef _STLP_MEMBER_TEMPLATES
1.321 +
1.322 + template <class _InputIterator>
1.323 + void assign(_InputIterator __first, _InputIterator __last) {
1.324 + typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
1.325 + _M_assign_dispatch(__first, __last, _Integral());
1.326 + }
1.327 +
1.328 + template <class _Integer>
1.329 + void _M_assign_dispatch(_Integer __n, _Integer __val, const __true_type&)
1.330 + { _M_fill_assign((size_type) __n, (_Tp) __val); }
1.331 +
1.332 + template <class _InputIter>
1.333 + void
1.334 + _M_assign_dispatch(_InputIter __first, _InputIter __last,
1.335 + const __false_type&) {
1.336 + _Node_base* __prev = &this->_M_head._M_data;
1.337 + _Node* __node = (_Node*) this->_M_head._M_data._M_next;
1.338 + while (__node != 0 && __first != __last) {
1.339 + __node->_M_data = *__first;
1.340 + __prev = __node;
1.341 + __node = (_Node*) __node->_M_next;
1.342 + ++__first;
1.343 + }
1.344 + if (__first != __last)
1.345 + _M_insert_after_range(__prev, __first, __last);
1.346 + else
1.347 + this->_M_erase_after(__prev, 0);
1.348 + }
1.349 +#endif /* _STLP_MEMBER_TEMPLATES */
1.350 +
1.351 +public:
1.352 +
1.353 + // Experimental new feature: before_begin() returns a
1.354 + // non-dereferenceable iterator that, when incremented, yields
1.355 + // begin(). This iterator may be used as the argument to
1.356 + // insert_after, erase_after, etc. Note that even for an empty
1.357 + // slist, before_begin() is not the same iterator as end(). It
1.358 + // is always necessary to increment before_begin() at least once to
1.359 + // obtain end().
1.360 + iterator before_begin() { return iterator((_Node*) &this->_M_head._M_data); }
1.361 + const_iterator before_begin() const
1.362 + { return const_iterator((_Node*) &this->_M_head._M_data); }
1.363 +
1.364 + iterator begin() { return iterator((_Node*)this->_M_head._M_data._M_next); }
1.365 + const_iterator begin() const
1.366 + { return const_iterator((_Node*)this->_M_head._M_data._M_next);}
1.367 +
1.368 + iterator end() { return iterator(0); }
1.369 + const_iterator end() const { return const_iterator(0); }
1.370 +
1.371 + size_type size() const { return _Sl_global_inst::size(this->_M_head._M_data._M_next); }
1.372 +
1.373 + size_type max_size() const { return size_type(-1); }
1.374 +
1.375 + bool empty() const { return this->_M_head._M_data._M_next == 0; }
1.376 +
1.377 + void swap(_Self& __x) {
1.378 + _STLP_STD::swap(this->_M_head, __x._M_head);
1.379 + }
1.380 +
1.381 +public:
1.382 + reference front() { return ((_Node*) this->_M_head._M_data._M_next)->_M_data; }
1.383 + const_reference front() const
1.384 + { return ((_Node*) this->_M_head._M_data._M_next)->_M_data; }
1.385 + void push_front(const value_type& __x) {
1.386 + __slist_make_link(&this->_M_head._M_data, _M_create_node(__x));
1.387 + }
1.388 +
1.389 +# ifndef _STLP_NO_ANACHRONISMS
1.390 + void push_front() { __slist_make_link(&this->_M_head._M_data, _M_create_node());}
1.391 +# endif
1.392 +
1.393 + void pop_front() {
1.394 + _Node* __node = (_Node*) this->_M_head._M_data._M_next;
1.395 + this->_M_head._M_data._M_next = __node->_M_next;
1.396 + _STLP_STD::_Destroy(&__node->_M_data);
1.397 + this->_M_head.deallocate(__node, 1);
1.398 + }
1.399 +
1.400 + iterator previous(const_iterator __pos) {
1.401 + return iterator((_Node*) _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node));
1.402 + }
1.403 + const_iterator previous(const_iterator __pos) const {
1.404 + return const_iterator((_Node*) _Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node));
1.405 + }
1.406 +
1.407 +private:
1.408 + _Node* _M_insert_after(_Node_base* __pos, const value_type& __x) {
1.409 + return (_Node*) (__slist_make_link(__pos, _M_create_node(__x)));
1.410 + }
1.411 +
1.412 + _Node* _M_insert_after(_Node_base* __pos) {
1.413 + return (_Node*) (__slist_make_link(__pos, _M_create_node()));
1.414 + }
1.415 +
1.416 + void _M_insert_after_fill(_Node_base* __pos,
1.417 + size_type __n, const value_type& __x) {
1.418 + for (size_type __i = 0; __i < __n; ++__i)
1.419 + __pos = __slist_make_link(__pos, _M_create_node(__x));
1.420 + }
1.421 +
1.422 +#ifdef _STLP_MEMBER_TEMPLATES
1.423 +
1.424 + // Check whether it's an integral type. If so, it's not an iterator.
1.425 + template <class _InIter>
1.426 + void _M_insert_after_range(_Node_base* __pos,
1.427 + _InIter __first, _InIter __last) {
1.428 + typedef typename _Is_integer<_InIter>::_Integral _Integral;
1.429 + _M_insert_after_range(__pos, __first, __last, _Integral());
1.430 + }
1.431 +
1.432 + template <class _Integer>
1.433 + void _M_insert_after_range(_Node_base* __pos, _Integer __n, _Integer __x,
1.434 + const __true_type&) {
1.435 + _M_insert_after_fill(__pos, __n, __x);
1.436 + }
1.437 +
1.438 + template <class _InIter>
1.439 + void _M_insert_after_range(_Node_base* __pos,
1.440 + _InIter __first, _InIter __last,
1.441 + const __false_type&) {
1.442 + while (__first != __last) {
1.443 + __pos = __slist_make_link(__pos, _M_create_node(*__first));
1.444 + ++__first;
1.445 + }
1.446 + }
1.447 +
1.448 +#else /* _STLP_MEMBER_TEMPLATES */
1.449 +
1.450 + void _M_insert_after_range(_Node_base* __pos,
1.451 + const_iterator __first, const_iterator __last) {
1.452 + while (__first != __last) {
1.453 + __pos = __slist_make_link(__pos, _M_create_node(*__first));
1.454 + ++__first;
1.455 + }
1.456 + }
1.457 + void _M_insert_after_range(_Node_base* __pos,
1.458 + const value_type* __first,
1.459 + const value_type* __last) {
1.460 + while (__first != __last) {
1.461 + __pos = __slist_make_link(__pos, _M_create_node(*__first));
1.462 + ++__first;
1.463 + }
1.464 + }
1.465 +
1.466 +#endif /* _STLP_MEMBER_TEMPLATES */
1.467 +
1.468 +public:
1.469 +
1.470 + iterator insert_after(iterator __pos, const value_type& __x) {
1.471 + return iterator(_M_insert_after(__pos._M_node, __x));
1.472 + }
1.473 +
1.474 + iterator insert_after(iterator __pos) {
1.475 + return insert_after(__pos, value_type());
1.476 + }
1.477 +
1.478 + void insert_after(iterator __pos, size_type __n, const value_type& __x) {
1.479 + _M_insert_after_fill(__pos._M_node, __n, __x);
1.480 + }
1.481 +
1.482 +#ifdef _STLP_MEMBER_TEMPLATES
1.483 +
1.484 + // We don't need any dispatching tricks here, because _M_insert_after_range
1.485 + // already does them.
1.486 + template <class _InIter>
1.487 + void insert_after(iterator __pos, _InIter __first, _InIter __last) {
1.488 + _M_insert_after_range(__pos._M_node, __first, __last);
1.489 + }
1.490 +
1.491 +#else /* _STLP_MEMBER_TEMPLATES */
1.492 +
1.493 + void insert_after(iterator __pos,
1.494 + const_iterator __first, const_iterator __last) {
1.495 + _M_insert_after_range(__pos._M_node, __first, __last);
1.496 + }
1.497 + void insert_after(iterator __pos,
1.498 + const value_type* __first, const value_type* __last) {
1.499 + _M_insert_after_range(__pos._M_node, __first, __last);
1.500 + }
1.501 +
1.502 +#endif /* _STLP_MEMBER_TEMPLATES */
1.503 +
1.504 + iterator insert(iterator __pos, const value_type& __x) {
1.505 + return iterator(_M_insert_after(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
1.506 + __x));
1.507 + }
1.508 +
1.509 + iterator insert(iterator __pos) {
1.510 + return iterator(_M_insert_after(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
1.511 + value_type()));
1.512 + }
1.513 +
1.514 + void insert(iterator __pos, size_type __n, const value_type& __x) {
1.515 + _M_insert_after_fill(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node), __n, __x);
1.516 + }
1.517 +
1.518 +#ifdef _STLP_MEMBER_TEMPLATES
1.519 +
1.520 + // We don't need any dispatching tricks here, because _M_insert_after_range
1.521 + // already does them.
1.522 + template <class _InIter>
1.523 + void insert(iterator __pos, _InIter __first, _InIter __last) {
1.524 + _M_insert_after_range(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
1.525 + __first, __last);
1.526 + }
1.527 +
1.528 +#else /* _STLP_MEMBER_TEMPLATES */
1.529 +
1.530 + void insert(iterator __pos, const_iterator __first, const_iterator __last) {
1.531 + _M_insert_after_range(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
1.532 + __first, __last);
1.533 + }
1.534 + void insert(iterator __pos, const value_type* __first,
1.535 + const value_type* __last) {
1.536 + _M_insert_after_range(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
1.537 + __first, __last);
1.538 + }
1.539 +
1.540 +#endif /* _STLP_MEMBER_TEMPLATES */
1.541 +
1.542 +
1.543 +public:
1.544 + iterator erase_after(iterator __pos) {
1.545 + return iterator((_Node*) this->_M_erase_after(__pos._M_node));
1.546 + }
1.547 + iterator erase_after(iterator __before_first, iterator __last) {
1.548 + return iterator((_Node*) this->_M_erase_after(__before_first._M_node,
1.549 + __last._M_node));
1.550 + }
1.551 +
1.552 + iterator erase(iterator __pos) {
1.553 + return iterator((_Node*) this->_M_erase_after(_Sl_global_inst::__previous(&this->_M_head._M_data,
1.554 + __pos._M_node)));
1.555 + }
1.556 + iterator erase(iterator __first, iterator __last) {
1.557 + return iterator((_Node*) this->_M_erase_after(
1.558 + _Sl_global_inst::__previous(&this->_M_head._M_data, __first._M_node), __last._M_node));
1.559 + }
1.560 +
1.561 + void resize(size_type new_size, const _Tp& __x);
1.562 + void resize(size_type new_size) { resize(new_size, _Tp()); }
1.563 + void clear() {
1.564 + this->_M_erase_after(&this->_M_head._M_data, 0);
1.565 + }
1.566 +
1.567 +public:
1.568 + // Moves the range [__before_first + 1, __before_last + 1) to *this,
1.569 + // inserting it immediately after __pos. This is constant time.
1.570 + void splice_after(iterator __pos,
1.571 + iterator __before_first, iterator __before_last)
1.572 + {
1.573 + if (__before_first != __before_last) {
1.574 + _Sl_global_inst::__splice_after(__pos._M_node, __before_first._M_node,
1.575 + __before_last._M_node);
1.576 + }
1.577 + }
1.578 +
1.579 + // Moves the element that follows __prev to *this, inserting it immediately
1.580 + // after __pos. This is constant time.
1.581 + void splice_after(iterator __pos, iterator __prev)
1.582 + {
1.583 + _Sl_global_inst::__splice_after(__pos._M_node,
1.584 + __prev._M_node, __prev._M_node->_M_next);
1.585 + }
1.586 +
1.587 + // Removes all of the elements from the list __x to *this, inserting
1.588 + // them immediately after __pos. __x must not be *this. Complexity:
1.589 + // linear in __x.size().
1.590 + void splice_after(iterator __pos, _Self& __x)
1.591 + {
1.592 + _Sl_global_inst::__splice_after(__pos._M_node, &__x._M_head._M_data);
1.593 + }
1.594 +
1.595 + // Linear in distance(begin(), __pos), and linear in __x.size().
1.596 + void splice(iterator __pos, _Self& __x) {
1.597 + if (__x._M_head._M_data._M_next)
1.598 + _Sl_global_inst::__splice_after(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
1.599 + &__x._M_head._M_data, _Sl_global_inst::__previous(&__x._M_head._M_data, 0));
1.600 + }
1.601 +
1.602 + // Linear in distance(begin(), __pos), and in distance(__x.begin(), __i).
1.603 + void splice(iterator __pos, _Self& __x, iterator __i) {
1.604 + _Sl_global_inst::__splice_after(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
1.605 + _Sl_global_inst::__previous(&__x._M_head._M_data, __i._M_node),
1.606 + __i._M_node);
1.607 + }
1.608 +
1.609 + // Linear in distance(begin(), __pos), in distance(__x.begin(), __first),
1.610 + // and in distance(__first, __last).
1.611 + void splice(iterator __pos, _Self& __x, iterator __first, iterator __last)
1.612 + {
1.613 + if (__first != __last)
1.614 + _Sl_global_inst::__splice_after(_Sl_global_inst::__previous(&this->_M_head._M_data, __pos._M_node),
1.615 + _Sl_global_inst::__previous(&__x._M_head._M_data, __first._M_node),
1.616 + _Sl_global_inst::__previous(__first._M_node, __last._M_node));
1.617 + }
1.618 +
1.619 +public:
1.620 + void reverse() {
1.621 + if (this->_M_head._M_data._M_next)
1.622 + this->_M_head._M_data._M_next = _Sl_global_inst::__reverse(this->_M_head._M_data._M_next);
1.623 + }
1.624 +
1.625 + void remove(const _Tp& __val);
1.626 + void unique();
1.627 + void merge(_Self& __x);
1.628 + void sort();
1.629 +
1.630 +#ifdef _STLP_MEMBER_TEMPLATES
1.631 + template <class _Predicate>
1.632 + void remove_if(_Predicate __pred) {
1.633 + _Node_base* __cur = &this->_M_head._M_data;
1.634 + while (__cur->_M_next) {
1.635 + if (__pred(((_Node*) __cur->_M_next)->_M_data))
1.636 + this->_M_erase_after(__cur);
1.637 + else
1.638 + __cur = __cur->_M_next;
1.639 + }
1.640 + }
1.641 +
1.642 + template <class _BinaryPredicate>
1.643 + void unique(_BinaryPredicate __pred) {
1.644 + _Node* __cur = (_Node*) this->_M_head._M_data._M_next;
1.645 + if (__cur) {
1.646 + while (__cur->_M_next) {
1.647 + if (__pred(((_Node*)__cur)->_M_data,
1.648 + ((_Node*)(__cur->_M_next))->_M_data))
1.649 + this->_M_erase_after(__cur);
1.650 + else
1.651 + __cur = (_Node*) __cur->_M_next;
1.652 + }
1.653 + }
1.654 + }
1.655 +
1.656 + template <class _StrictWeakOrdering>
1.657 + void merge(slist<_Tp,_Alloc>& __x,
1.658 + _StrictWeakOrdering __comp) {
1.659 + _Node_base* __n1 = &this->_M_head._M_data;
1.660 + while (__n1->_M_next && __x._M_head._M_data._M_next) {
1.661 + if (__comp(((_Node*) __x._M_head._M_data._M_next)->_M_data,
1.662 + ((_Node*) __n1->_M_next)->_M_data))
1.663 + _Sl_global_inst::__splice_after(__n1, &__x._M_head._M_data, __x._M_head._M_data._M_next);
1.664 + __n1 = __n1->_M_next;
1.665 + }
1.666 + if (__x._M_head._M_data._M_next) {
1.667 + __n1->_M_next = __x._M_head._M_data._M_next;
1.668 + __x._M_head._M_data._M_next = 0;
1.669 + }
1.670 + }
1.671 +
1.672 + template <class _StrictWeakOrdering>
1.673 + void sort(_StrictWeakOrdering __comp) {
1.674 + if (this->_M_head._M_data._M_next && this->_M_head._M_data._M_next->_M_next) {
1.675 + slist __carry;
1.676 + slist __counter[64];
1.677 + int __fill = 0;
1.678 + while (!empty()) {
1.679 + _Sl_global_inst::__splice_after(&__carry._M_head._M_data, &this->_M_head._M_data, this->_M_head._M_data._M_next);
1.680 + int __i = 0;
1.681 + while (__i < __fill && !__counter[__i].empty()) {
1.682 + __counter[__i].merge(__carry, __comp);
1.683 + __carry.swap(__counter[__i]);
1.684 + ++__i;
1.685 + }
1.686 + __carry.swap(__counter[__i]);
1.687 + if (__i == __fill)
1.688 + ++__fill;
1.689 + }
1.690 +
1.691 + for (int __i = 1; __i < __fill; ++__i)
1.692 + __counter[__i].merge(__counter[__i-1], __comp);
1.693 + this->swap(__counter[__fill-1]);
1.694 + }
1.695 + }
1.696 +#endif /* _STLP_MEMBER_TEMPLATES */
1.697 +
1.698 +};
1.699 +
1.700 +template <class _Tp, class _Alloc>
1.701 +inline bool _STLP_CALL
1.702 +operator==(const slist<_Tp,_Alloc>& _SL1, const slist<_Tp,_Alloc>& _SL2)
1.703 +{
1.704 + typedef typename slist<_Tp,_Alloc>::const_iterator const_iterator;
1.705 + const_iterator __end1 = _SL1.end();
1.706 + const_iterator __end2 = _SL2.end();
1.707 +
1.708 + const_iterator __i1 = _SL1.begin();
1.709 + const_iterator __i2 = _SL2.begin();
1.710 + while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
1.711 + ++__i1;
1.712 + ++__i2;
1.713 + }
1.714 + return __i1 == __end1 && __i2 == __end2;
1.715 +}
1.716 +
1.717 +# define _STLP_EQUAL_OPERATOR_SPECIALIZED
1.718 +# define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc>
1.719 +# define _STLP_TEMPLATE_CONTAINER slist<_Tp, _Alloc>
1.720 +# include <stl/_relops_cont.h>
1.721 +# undef _STLP_TEMPLATE_CONTAINER
1.722 +# undef _STLP_TEMPLATE_HEADER
1.723 +# undef _STLP_EQUAL_OPERATOR_SPECIALIZED
1.724 +
1.725 +_STLP_END_NAMESPACE
1.726 +
1.727 +# if !defined (_STLP_LINK_TIME_INSTANTIATION)
1.728 +# include <stl/_slist.c>
1.729 +# endif
1.730 +
1.731 +# undef slist
1.732 +# define __slist__ __FULL_NAME(slist)
1.733 +
1.734 +#if defined (_STLP_DEBUG) && !defined (_STLP_INTERNAL_DBG_SLIST_H)
1.735 +# include <stl/debug/_slist.h>
1.736 +#endif
1.737 +
1.738 +_STLP_BEGIN_NAMESPACE
1.739 +// Specialization of insert_iterator so that insertions will be constant
1.740 +// time rather than linear time.
1.741 +
1.742 +#ifdef _STLP_CLASS_PARTIAL_SPECIALIZATION
1.743 +
1.744 +template <class _Tp, class _Alloc>
1.745 +class insert_iterator<slist<_Tp, _Alloc> > {
1.746 +protected:
1.747 + typedef slist<_Tp, _Alloc> _Container;
1.748 + _Container* container;
1.749 + typename _Container::iterator iter;
1.750 +public:
1.751 + typedef _Container container_type;
1.752 + typedef output_iterator_tag iterator_category;
1.753 + typedef void value_type;
1.754 + typedef void difference_type;
1.755 + typedef void pointer;
1.756 + typedef void reference;
1.757 +
1.758 + insert_iterator(_Container& __x, typename _Container::iterator __i)
1.759 + : container(&__x) {
1.760 + if (__i == __x.begin())
1.761 + iter = __x.before_begin();
1.762 + else
1.763 + iter = __x.previous(__i);
1.764 + }
1.765 +
1.766 + insert_iterator<_Container>&
1.767 + operator=(const typename _Container::value_type& __val) {
1.768 + iter = container->insert_after(iter, __val);
1.769 + return *this;
1.770 + }
1.771 + insert_iterator<_Container>& operator*() { return *this; }
1.772 + insert_iterator<_Container>& operator++() { return *this; }
1.773 + insert_iterator<_Container>& operator++(int) { return *this; }
1.774 +};
1.775 +
1.776 +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.777 +
1.778 +_STLP_END_NAMESPACE
1.779 +
1.780 +
1.781 +# if defined ( _STLP_USE_WRAPPER_FOR_ALLOC_PARAM )
1.782 +# include <stl/wrappers/_slist.h>
1.783 +# endif
1.784 +
1.785 +#endif /* _STLP_INTERNAL_SLIST_H */
1.786 +
1.787 +// Local Variables:
1.788 +// mode:C++
1.789 +// End:
1.790 +