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