1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/epoc32/include/tools/stlport/stl/_list.h Wed Mar 31 12:33:34 2010 +0100
1.3 @@ -0,0 +1,732 @@
1.4 +/*
1.5 + *
1.6 + * Copyright (c) 1994
1.7 + * Hewlett-Packard Company
1.8 + *
1.9 + * Copyright (c) 1996,1997
1.10 + * Silicon Graphics Computer Systems, Inc.
1.11 + *
1.12 + * Copyright (c) 1997
1.13 + * Moscow Center for SPARC Technology
1.14 + *
1.15 + * Copyright (c) 1999
1.16 + * Boris Fomitchev
1.17 + *
1.18 + * This material is provided "as is", with absolutely no warranty expressed
1.19 + * or implied. Any use is at your own risk.
1.20 + *
1.21 + * Permission to use or copy this software for any purpose is hereby granted
1.22 + * without fee, provided the above notices are retained on all copies.
1.23 + * Permission to modify the code and to distribute modified code is granted,
1.24 + * provided the above notices are retained, and a notice that the code was
1.25 + * modified is included with the above copyright notice.
1.26 + *
1.27 + */
1.28 +
1.29 +/* NOTE: This is an internal header file, included by other STL headers.
1.30 + * You should not attempt to use it directly.
1.31 + */
1.32 +
1.33 +#ifndef _STLP_INTERNAL_LIST_IMPL_H
1.34 +#define _STLP_INTERNAL_LIST_IMPL_H
1.35 +
1.36 +#ifndef _STLP_INTERNAL_ALGOBASE_H
1.37 +# include <stl/_algobase.h>
1.38 +#endif
1.39 +
1.40 +#ifndef _STLP_INTERNAL_ALLOC_H
1.41 +# include <stl/_alloc.h>
1.42 +#endif
1.43 +
1.44 +#ifndef _STLP_INTERNAL_ITERATOR_H
1.45 +# include <stl/_iterator.h>
1.46 +#endif
1.47 +
1.48 +#ifndef _STLP_INTERNAL_CONSTRUCT_H
1.49 +# include <stl/_construct.h>
1.50 +#endif
1.51 +
1.52 +#ifndef _STLP_INTERNAL_FUNCTION_BASE_H
1.53 +# include <stl/_function_base.h>
1.54 +#endif
1.55 +
1.56 +_STLP_BEGIN_NAMESPACE
1.57 +
1.58 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.59 +
1.60 +struct _List_node_base {
1.61 + _List_node_base* _M_next;
1.62 + _List_node_base* _M_prev;
1.63 +};
1.64 +
1.65 +template <class _Dummy>
1.66 +class _List_global {
1.67 +public:
1.68 + typedef _List_node_base _Node_base;
1.69 + static void _STLP_CALL _Transfer(_Node_base* __pos,
1.70 + _Node_base* __first, _Node_base* __last);
1.71 +};
1.72 +
1.73 +#if defined (_STLP_USE_TEMPLATE_EXPORT)
1.74 +_STLP_EXPORT_TEMPLATE_CLASS _List_global<bool>;
1.75 +#endif
1.76 +typedef _List_global<bool> _List_global_inst;
1.77 +
1.78 +template <class _Tp>
1.79 +class _List_node : public _List_node_base {
1.80 +public:
1.81 + _Tp _M_data;
1.82 + __TRIVIAL_STUFF(_List_node)
1.83 +};
1.84 +
1.85 +struct _List_iterator_base {
1.86 + typedef size_t size_type;
1.87 + typedef ptrdiff_t difference_type;
1.88 + typedef bidirectional_iterator_tag iterator_category;
1.89 +
1.90 + _List_node_base* _M_node;
1.91 +
1.92 + _List_iterator_base(_List_node_base* __x) : _M_node(__x) {}
1.93 +
1.94 + void _M_incr() { _M_node = _M_node->_M_next; }
1.95 + void _M_decr() { _M_node = _M_node->_M_prev; }
1.96 +};
1.97 +
1.98 +
1.99 +template<class _Tp, class _Traits>
1.100 +struct _List_iterator : public _List_iterator_base {
1.101 + typedef _Tp value_type;
1.102 + typedef typename _Traits::pointer pointer;
1.103 + typedef typename _Traits::reference reference;
1.104 +
1.105 + typedef _List_iterator<_Tp, _Traits> _Self;
1.106 + typedef typename _Traits::_NonConstTraits _NonConstTraits;
1.107 + typedef _List_iterator<_Tp, _NonConstTraits> iterator;
1.108 + typedef typename _Traits::_ConstTraits _ConstTraits;
1.109 + typedef _List_iterator<_Tp, _ConstTraits> const_iterator;
1.110 +
1.111 + typedef bidirectional_iterator_tag iterator_category;
1.112 + typedef _List_node<_Tp> _Node;
1.113 + typedef size_t size_type;
1.114 + typedef ptrdiff_t difference_type;
1.115 +
1.116 + explicit _List_iterator(_List_node_base* __x) : _List_iterator_base(__x) {}
1.117 + _List_iterator() : _List_iterator_base(0) {}
1.118 + //copy constructor for iterator and constructor from iterator for const_iterator
1.119 + _List_iterator(const iterator& __x) : _List_iterator_base(__x._M_node) {}
1.120 +
1.121 + reference operator*() const { return __STATIC_CAST(_Node*, this->_M_node)->_M_data; }
1.122 +
1.123 + _STLP_DEFINE_ARROW_OPERATOR
1.124 +
1.125 + _Self& operator++() {
1.126 + this->_M_incr();
1.127 + return *this;
1.128 + }
1.129 + _Self operator++(int) {
1.130 + _Self __tmp = *this;
1.131 + this->_M_incr();
1.132 + return __tmp;
1.133 + }
1.134 + _Self& operator--() {
1.135 + this->_M_decr();
1.136 + return *this;
1.137 + }
1.138 + _Self operator--(int) {
1.139 + _Self __tmp = *this;
1.140 + this->_M_decr();
1.141 + return __tmp;
1.142 + }
1.143 + bool operator==(const_iterator __y ) const {
1.144 + return this->_M_node == __y._M_node;
1.145 + }
1.146 + bool operator!=(const_iterator __y ) const {
1.147 + return this->_M_node != __y._M_node;
1.148 + }
1.149 +};
1.150 +
1.151 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.152 +_STLP_MOVE_TO_STD_NAMESPACE
1.153 +template <class _Tp, class _Traits>
1.154 +struct __type_traits<_STLP_PRIV _List_iterator<_Tp, _Traits> > {
1.155 + typedef __false_type has_trivial_default_constructor;
1.156 + typedef __true_type has_trivial_copy_constructor;
1.157 + typedef __true_type has_trivial_assignment_operator;
1.158 + typedef __true_type has_trivial_destructor;
1.159 + typedef __false_type is_POD_type;
1.160 +};
1.161 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.162 +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.163 +
1.164 +#if defined (_STLP_USE_OLD_HP_ITERATOR_QUERIES)
1.165 +_STLP_MOVE_TO_STD_NAMESPACE
1.166 +template <class _Tp, class _Traits>
1.167 +inline _Tp* value_type(const _STLP_PRIV _List_iterator<_Tp, _Traits>&) { return 0; }
1.168 +inline bidirectional_iterator_tag iterator_category(const _STLP_PRIV _List_iterator_base&) { return bidirectional_iterator_tag();}
1.169 +inline ptrdiff_t* distance_type(const _STLP_PRIV _List_iterator_base&) { return 0; }
1.170 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.171 +#endif
1.172 +
1.173 +// Base class that encapsulates details of allocators and helps
1.174 +// to simplify EH
1.175 +
1.176 +template <class _Tp, class _Alloc>
1.177 +class _List_base {
1.178 +protected:
1.179 + _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
1.180 + typedef _List_node_base _Node_base;
1.181 + typedef _List_node<_Tp> _Node;
1.182 + typedef _List_base<_Tp, _Alloc> _Self;
1.183 + typedef typename _Alloc_traits<_Node, _Alloc>::allocator_type _Node_allocator_type;
1.184 +public:
1.185 + typedef _STLP_alloc_proxy<_Node_base, _Node, _Node_allocator_type> _AllocProxy;
1.186 + typedef typename _Alloc_traits<_Tp, _Alloc>::allocator_type allocator_type;
1.187 +
1.188 + allocator_type get_allocator() const
1.189 + { return _STLP_CONVERT_ALLOCATOR((const _Node_allocator_type&)_M_node, _Tp); }
1.190 +
1.191 + _List_base(const allocator_type& __a) : _M_node(_STLP_CONVERT_ALLOCATOR(__a, _Node), _Node_base())
1.192 + { _M_empty_initialize(); }
1.193 + _List_base(__move_source<_Self> src) :
1.194 + _M_node(__move_source<_AllocProxy>(src.get()._M_node)) {
1.195 + if (src.get().empty())
1.196 + //We force this to empty.
1.197 + _M_empty_initialize();
1.198 + else {
1.199 + src.get()._M_empty_initialize();
1.200 + _M_node._M_data._M_prev->_M_next = _M_node._M_data._M_next->_M_prev = &_M_node._M_data;
1.201 + }
1.202 + }
1.203 +
1.204 + ~_List_base()
1.205 + { clear(); }
1.206 +
1.207 + void clear();
1.208 + bool empty() const { return _M_node._M_data._M_next == &_M_node._M_data; }
1.209 +
1.210 + void _M_empty_initialize() {
1.211 + _M_node._M_data._M_next = &_M_node._M_data;
1.212 + _M_node._M_data._M_prev = _M_node._M_data._M_next;
1.213 + }
1.214 +
1.215 +public:
1.216 + _AllocProxy _M_node;
1.217 +};
1.218 +
1.219 +#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
1.220 +# define list _STLP_PTR_IMPL_NAME(list)
1.221 +#elif defined (_STLP_DEBUG)
1.222 +# define list _STLP_NON_DBG_NAME(list)
1.223 +#else
1.224 +_STLP_MOVE_TO_STD_NAMESPACE
1.225 +#endif
1.226 +
1.227 +template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
1.228 +class list;
1.229 +
1.230 +#if !defined (list)
1.231 +_STLP_MOVE_TO_PRIV_NAMESPACE
1.232 +#endif
1.233 +
1.234 +// helper functions to reduce code duplication
1.235 +template <class _Tp, class _Alloc, class _Predicate>
1.236 +void _S_remove_if(list<_Tp, _Alloc>& __that, _Predicate __pred);
1.237 +
1.238 +template <class _Tp, class _Alloc, class _BinaryPredicate>
1.239 +void _S_unique(list<_Tp, _Alloc>& __that, _BinaryPredicate __binary_pred);
1.240 +
1.241 +template <class _Tp, class _Alloc, class _StrictWeakOrdering>
1.242 +void _S_merge(list<_Tp, _Alloc>& __that, list<_Tp, _Alloc>& __x,
1.243 + _StrictWeakOrdering __comp);
1.244 +
1.245 +template <class _Tp, class _Alloc, class _StrictWeakOrdering>
1.246 +void _S_sort(list<_Tp, _Alloc>& __that, _StrictWeakOrdering __comp);
1.247 +
1.248 +#if !defined (list)
1.249 +_STLP_MOVE_TO_STD_NAMESPACE
1.250 +#endif
1.251 +
1.252 +template <class _Tp, class _Alloc>
1.253 +class list : public _STLP_PRIV _List_base<_Tp, _Alloc>
1.254 +#if defined (_STLP_USE_PARTIAL_SPEC_WORKAROUND) && !defined (list)
1.255 + , public __stlport_class<list<_Tp, _Alloc> >
1.256 +#endif
1.257 +{
1.258 + typedef _STLP_PRIV _List_base<_Tp, _Alloc> _Base;
1.259 + typedef list<_Tp, _Alloc> _Self;
1.260 + typedef _STLP_PRIV _List_node<_Tp> _Node;
1.261 + typedef _STLP_PRIV _List_node_base _Node_base;
1.262 +public:
1.263 + typedef _Tp value_type;
1.264 + typedef value_type* pointer;
1.265 + typedef const value_type* const_pointer;
1.266 + typedef value_type& reference;
1.267 + typedef const value_type& const_reference;
1.268 + typedef size_t size_type;
1.269 + typedef ptrdiff_t difference_type;
1.270 + _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
1.271 + typedef typename _Base::allocator_type allocator_type;
1.272 + typedef bidirectional_iterator_tag _Iterator_category;
1.273 +
1.274 +public:
1.275 + typedef _STLP_PRIV _List_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
1.276 + typedef _STLP_PRIV _List_iterator<_Tp, _Const_traits<_Tp> > const_iterator;
1.277 + _STLP_DECLARE_BIDIRECTIONAL_REVERSE_ITERATORS;
1.278 +
1.279 +protected:
1.280 +#if !defined(_STLP_DONT_SUP_DFLT_PARAM)
1.281 + _Node_base* _M_create_node(const_reference __x = value_type()) {
1.282 +#else
1.283 + _Node_base* _M_create_node(const_reference __x) {
1.284 +#endif /*!_STLP_DONT_SUP_DFLT_PARAM*/
1.285 + _Node* __p = this->_M_node.allocate(1);
1.286 + _STLP_TRY {
1.287 + _Copy_Construct(&__p->_M_data, __x);
1.288 + }
1.289 + _STLP_UNWIND(this->_M_node.deallocate(__p, 1))
1.290 + return __p;
1.291 + }
1.292 +
1.293 +#if defined(_STLP_DONT_SUP_DFLT_PARAM)
1.294 + _Node_base* _M_create_node() {
1.295 + _Node* __p = this->_M_node.allocate(1);
1.296 + _STLP_TRY {
1.297 + _STLP_STD::_Construct(&__p->_M_data);
1.298 + }
1.299 + _STLP_UNWIND(this->_M_node.deallocate(__p, 1))
1.300 + return __p;
1.301 + }
1.302 +#endif /*_STLP_DONT_SUP_DFLT_PARAM*/
1.303 +
1.304 +public:
1.305 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
1.306 + explicit list(size_type __n, const_reference __val = _STLP_DEFAULT_CONSTRUCTED(value_type),
1.307 + const allocator_type& __a = allocator_type())
1.308 +#else
1.309 + explicit list(size_type __n)
1.310 + : _STLP_PRIV _List_base<_Tp, _Alloc>(allocator_type())
1.311 + { this->insert(begin(), __n, _STLP_DEFAULT_CONSTRUCTED(value_type)); }
1.312 + list(size_type __n, const_reference __val)
1.313 + : _STLP_PRIV _List_base<_Tp, _Alloc>(allocator_type())
1.314 + { this->insert(begin(), __n, __val); }
1.315 + list(size_type __n, const_reference __val, const allocator_type& __a)
1.316 +#endif /*_STLP_DONT_SUP_DFLT_PARAM*/
1.317 + : _STLP_PRIV _List_base<_Tp, _Alloc>(__a)
1.318 + { this->insert(begin(), __n, __val); }
1.319 +
1.320 +#if defined (_STLP_MEMBER_TEMPLATES)
1.321 + // We don't need any dispatching tricks here, because insert does all of
1.322 + // that anyway.
1.323 + template <class _InputIterator>
1.324 + list(_InputIterator __first, _InputIterator __last,
1.325 + const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL)
1.326 + : _STLP_PRIV _List_base<_Tp, _Alloc>(__a)
1.327 + { _M_insert(begin(), __first, __last); }
1.328 +
1.329 +# if defined (_STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS)
1.330 + template <class _InputIterator>
1.331 + list(_InputIterator __first, _InputIterator __last)
1.332 + : _STLP_PRIV _List_base<_Tp, _Alloc>(allocator_type())
1.333 + { _M_insert(begin(), __first, __last); }
1.334 +# endif
1.335 +#else /* _STLP_MEMBER_TEMPLATES */
1.336 + list(const value_type* __first, const value_type* __last,
1.337 + const allocator_type& __a = allocator_type())
1.338 + : _STLP_PRIV _List_base<_Tp, _Alloc>(__a)
1.339 + { _M_insert(begin(), __first, __last); }
1.340 + list(const_iterator __first, const_iterator __last,
1.341 + const allocator_type& __a = allocator_type())
1.342 + : _STLP_PRIV _List_base<_Tp, _Alloc>(__a)
1.343 + { _M_insert(begin(), __first, __last); }
1.344 +#endif /* _STLP_MEMBER_TEMPLATES */
1.345 +
1.346 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
1.347 + explicit list(const allocator_type& __a = allocator_type())
1.348 +#else
1.349 + list()
1.350 + : _STLP_PRIV _List_base<_Tp, _Alloc>(allocator_type()) {}
1.351 + list(const allocator_type& __a)
1.352 +#endif
1.353 + : _STLP_PRIV _List_base<_Tp, _Alloc>(__a) {}
1.354 +
1.355 + list(const _Self& __x) : _STLP_PRIV _List_base<_Tp, _Alloc>(__x.get_allocator())
1.356 + { _M_insert(begin(), __x.begin(), __x.end()); }
1.357 +
1.358 + list(__move_source<_Self> src)
1.359 + : _STLP_PRIV _List_base<_Tp, _Alloc>(__move_source<_Base>(src.get())) {}
1.360 +
1.361 + ~list() {}
1.362 +
1.363 + _Self& operator = (const _Self& __x);
1.364 +
1.365 + iterator begin() { return iterator(this->_M_node._M_data._M_next); }
1.366 + const_iterator begin() const { return const_iterator(this->_M_node._M_data._M_next); }
1.367 +
1.368 + iterator end() { return iterator(&this->_M_node._M_data); }
1.369 + const_iterator end() const { return const_iterator(__CONST_CAST(_Node_base*, &this->_M_node._M_data)); }
1.370 +
1.371 + reverse_iterator rbegin() { return reverse_iterator(end()); }
1.372 + const_reverse_iterator rbegin() const { return const_reverse_iterator(end()); }
1.373 +
1.374 + reverse_iterator rend() { return reverse_iterator(begin()); }
1.375 + const_reverse_iterator rend() const { return const_reverse_iterator(begin()); }
1.376 +
1.377 + size_type size() const {
1.378 + size_type __result = distance(begin(), end());
1.379 + return __result;
1.380 + }
1.381 + size_type max_size() const { return size_type(-1); }
1.382 +
1.383 + reference front() { return *begin(); }
1.384 + const_reference front() const { return *begin(); }
1.385 + reference back() { return *(--end()); }
1.386 + const_reference back() const { return *(--end()); }
1.387 +
1.388 +private:
1.389 + void _M_swap_aux(_Self& __x) {
1.390 + __x._M_node._M_swap_alloc(this->_M_node);
1.391 + __x._M_node._M_data._M_next = this->_M_node._M_data._M_next;
1.392 + __x._M_node._M_data._M_next->_M_prev = &__x._M_node._M_data;
1.393 + __x._M_node._M_data._M_prev = this->_M_node._M_data._M_prev;
1.394 + __x._M_node._M_data._M_prev->_M_next = &__x._M_node._M_data;
1.395 + this->_M_empty_initialize();
1.396 + }
1.397 +
1.398 +public:
1.399 + void swap(_Self& __x) {
1.400 + if (__x.empty()) {
1.401 + if (this->empty()) {
1.402 + return;
1.403 + }
1.404 + this->_M_swap_aux(__x);
1.405 + } else if (this->empty()) {
1.406 + __x._M_swap_aux(*this);
1.407 + } else {
1.408 + this->_M_node.swap(__x._M_node);
1.409 + _STLP_STD::swap(this->_M_node._M_data._M_prev->_M_next, __x._M_node._M_data._M_prev->_M_next);
1.410 + _STLP_STD::swap(this->_M_node._M_data._M_next->_M_prev, __x._M_node._M_data._M_next->_M_prev);
1.411 + }
1.412 + }
1.413 +
1.414 +#if !defined(_STLP_DONT_SUP_DFLT_PARAM) && !defined(_STLP_NO_ANACHRONISMS)
1.415 + iterator insert(iterator __pos, const_reference __x = value_type()) {
1.416 +#else
1.417 + iterator insert(iterator __pos, const_reference __x) {
1.418 +#endif /*!_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
1.419 + _Node_base* __tmp = _M_create_node(__x);
1.420 + _Node_base* __n = __pos._M_node;
1.421 + _Node_base* __p = __n->_M_prev;
1.422 + __tmp->_M_next = __n;
1.423 + __tmp->_M_prev = __p;
1.424 + __p->_M_next = __tmp;
1.425 + __n->_M_prev = __tmp;
1.426 + return iterator(__tmp);
1.427 + }
1.428 +
1.429 +private:
1.430 +#if defined (_STLP_MEMBER_TEMPLATES)
1.431 + template <class _InputIterator>
1.432 + void _M_insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
1.433 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.434 + _M_insert_dispatch(__pos, __first, __last, _Integral());
1.435 + }
1.436 +
1.437 + // Check whether it's an integral type. If so, it's not an iterator.
1.438 + template<class _Integer>
1.439 + void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1.440 + const __true_type& /*_IsIntegral*/) {
1.441 + _M_fill_insert(__pos, __n, __x);
1.442 + }
1.443 + template <class _InputIter>
1.444 + void _M_insert_dispatch(iterator __pos,
1.445 + _InputIter __first, _InputIter __last,
1.446 + const __false_type& /*_IsIntegral*/) {
1.447 +#else /* _STLP_MEMBER_TEMPLATES */
1.448 + void _M_insert(iterator __pos, const value_type* __first, const value_type* __last) {
1.449 + for (; __first != __last; ++__first)
1.450 + insert(__pos, *__first);
1.451 + }
1.452 + void _M_insert(iterator __pos, const_iterator __first, const_iterator __last) {
1.453 +#endif /* _STLP_MEMBER_TEMPLATES */
1.454 + //We use a temporary list to avoid the auto reference troubles (infinite loop)
1.455 + for (; __first != __last; ++__first)
1.456 + insert(__pos, *__first);
1.457 + }
1.458 +
1.459 +public:
1.460 +#if defined (_STLP_MEMBER_TEMPLATES)
1.461 + template <class _InputIterator>
1.462 + void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
1.463 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.464 + _M_splice_insert_dispatch(__pos, __first, __last, _Integral());
1.465 + }
1.466 +
1.467 +private:
1.468 + // Check whether it's an integral type. If so, it's not an iterator.
1.469 + template<class _Integer>
1.470 + void _M_splice_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1.471 + const __true_type& /*_IsIntegral*/) {
1.472 + _M_fill_insert(__pos, __n, __x);
1.473 + }
1.474 + template <class _InputIter>
1.475 + void _M_splice_insert_dispatch(iterator __pos,
1.476 + _InputIter __first, _InputIter __last,
1.477 + const __false_type& /*_IsIntegral*/) {
1.478 +#else /* _STLP_MEMBER_TEMPLATES */
1.479 + void insert(iterator __pos, const value_type* __first, const value_type* __last) {
1.480 + _Self __tmp(__first, __last, this->get_allocator());
1.481 + splice(__pos, __tmp);
1.482 + }
1.483 + void insert(iterator __pos, const_iterator __first, const_iterator __last) {
1.484 +#endif /* _STLP_MEMBER_TEMPLATES */
1.485 + //We use a temporary list to avoid the auto reference troubles (infinite loop)
1.486 + _Self __tmp(__first, __last, this->get_allocator());
1.487 + splice(__pos, __tmp);
1.488 + }
1.489 +
1.490 +public:
1.491 + void insert(iterator __pos, size_type __n, const_reference __x)
1.492 + { _M_fill_insert(__pos, __n, __x); }
1.493 +
1.494 +private:
1.495 + void _M_fill_insert(iterator __pos, size_type __n, const_reference __x) {
1.496 + for ( ; __n > 0; --__n)
1.497 + insert(__pos, __x);
1.498 + }
1.499 +
1.500 +public:
1.501 + void push_front(const_reference __x) { insert(begin(), __x); }
1.502 + void push_back (const_reference __x) { insert(end(), __x); }
1.503 +
1.504 +#if defined (_STLP_DONT_SUP_DFLT_PARAM) && !defined (_STLP_NO_ANACHRONISMS)
1.505 + iterator insert(iterator __pos)
1.506 + { return insert(__pos, _STLP_DEFAULT_CONSTRUCTED(value_type)); }
1.507 + void push_front() {insert(begin());}
1.508 + void push_back() {insert(end());}
1.509 +# endif /*_STLP_DONT_SUP_DFLT_PARAM && !_STLP_NO_ANACHRONISMS*/
1.510 +
1.511 + iterator erase(iterator __pos) {
1.512 + _Node_base* __next_node = __pos._M_node->_M_next;
1.513 + _Node_base* __prev_node = __pos._M_node->_M_prev;
1.514 + _Node* __n = __STATIC_CAST(_Node*, __pos._M_node);
1.515 + __prev_node->_M_next = __next_node;
1.516 + __next_node->_M_prev = __prev_node;
1.517 + _STLP_STD::_Destroy(&__n->_M_data);
1.518 + this->_M_node.deallocate(__n, 1);
1.519 + return iterator(__next_node);
1.520 + }
1.521 +
1.522 + iterator erase(iterator __first, iterator __last) {
1.523 + while (__first != __last)
1.524 + erase(__first++);
1.525 + return __last;
1.526 + }
1.527 +
1.528 +#if !defined (_STLP_DONT_SUP_DFLT_PARAM)
1.529 + void resize(size_type __new_size, const_reference __x = value_type());
1.530 +#else
1.531 + void resize(size_type __new_size, const_reference __x);
1.532 + void resize(size_type __new_size)
1.533 + { this->resize(__new_size, _STLP_DEFAULT_CONSTRUCTED(value_type)); }
1.534 +#endif /*!_STLP_DONT_SUP_DFLT_PARAM*/
1.535 +
1.536 + void pop_front() { erase(begin()); }
1.537 + void pop_back() {
1.538 + iterator __tmp = end();
1.539 + erase(--__tmp);
1.540 + }
1.541 +
1.542 +public:
1.543 + // assign(), a generalized assignment member function. Two
1.544 + // versions: one that takes a count, and one that takes a range.
1.545 + // The range version is a member template, so we dispatch on whether
1.546 + // or not the type is an integer.
1.547 +
1.548 + void assign(size_type __n, const_reference __val) { _M_fill_assign(__n, __val); }
1.549 +
1.550 + void _M_fill_assign(size_type __n, const_reference __val);
1.551 +
1.552 +#if defined (_STLP_MEMBER_TEMPLATES)
1.553 + template <class _InputIterator>
1.554 + void assign(_InputIterator __first, _InputIterator __last) {
1.555 + typedef typename _IsIntegral<_InputIterator>::_Ret _Integral;
1.556 + _M_assign_dispatch(__first, __last, _Integral());
1.557 + }
1.558 +
1.559 + template <class _Integer>
1.560 + void _M_assign_dispatch(_Integer __n, _Integer __val,
1.561 + const __true_type& /*_IsIntegral*/) {
1.562 + _M_fill_assign(__n, __val);
1.563 + }
1.564 +
1.565 + template <class _InputIterator>
1.566 + void _M_assign_dispatch(_InputIterator __first2, _InputIterator __last2,
1.567 + const __false_type& /*_IsIntegral*/) {
1.568 +#else
1.569 + void assign(const value_type *__first2, const value_type *__last2) {
1.570 + iterator __first1 = begin();
1.571 + iterator __last1 = end();
1.572 + for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
1.573 + *__first1 = *__first2;
1.574 + if (__first2 == __last2)
1.575 + erase(__first1, __last1);
1.576 + else
1.577 + insert(__last1, __first2, __last2);
1.578 + }
1.579 + void assign(const_iterator __first2, const_iterator __last2) {
1.580 +#endif /* _STLP_MEMBER_TEMPLATES */
1.581 + iterator __first1 = begin();
1.582 + iterator __last1 = end();
1.583 + for ( ; __first1 != __last1 && __first2 != __last2; ++__first1, ++__first2)
1.584 + *__first1 = *__first2;
1.585 + if (__first2 == __last2)
1.586 + erase(__first1, __last1);
1.587 + else
1.588 + insert(__last1, __first2, __last2);
1.589 + }
1.590 +
1.591 +public:
1.592 + void splice(iterator __pos, _Self& __x) {
1.593 + if (!__x.empty()) {
1.594 + if (this->get_allocator() == __x.get_allocator()) {
1.595 + _STLP_PRIV _List_global_inst::_Transfer(__pos._M_node, __x.begin()._M_node, __x.end()._M_node);
1.596 + }
1.597 + else {
1.598 + insert(__pos, __x.begin(), __x.end());
1.599 + __x.clear();
1.600 + }
1.601 + }
1.602 + }
1.603 + void splice(iterator __pos, _Self& __x, iterator __i) {
1.604 + iterator __j = __i;
1.605 + ++__j;
1.606 + if (__pos == __i || __pos == __j) return;
1.607 + if (this->get_allocator() == __x.get_allocator()) {
1.608 + _STLP_PRIV _List_global_inst::_Transfer(__pos._M_node, __i._M_node, __j._M_node);
1.609 + }
1.610 + else {
1.611 + insert(__pos, *__i);
1.612 + __x.erase(__i);
1.613 + }
1.614 + }
1.615 + void splice(iterator __pos, _Self& __x, iterator __first, iterator __last) {
1.616 + if (__first != __last) {
1.617 + if (this->get_allocator() == __x.get_allocator()) {
1.618 + _STLP_PRIV _List_global_inst::_Transfer(__pos._M_node, __first._M_node, __last._M_node);
1.619 + }
1.620 + else {
1.621 + insert(__pos, __first, __last);
1.622 + __x.erase(__first, __last);
1.623 + }
1.624 + }
1.625 + }
1.626 +
1.627 + void remove(const_reference __val) {
1.628 + iterator __first = begin();
1.629 + iterator __last = end();
1.630 + while (__first != __last) {
1.631 + iterator __next = __first;
1.632 + ++__next;
1.633 + if (__val == *__first) erase(__first);
1.634 + __first = __next;
1.635 + }
1.636 + }
1.637 +
1.638 + void unique()
1.639 + { _STLP_PRIV _S_unique(*this, equal_to<value_type>()); }
1.640 +
1.641 + void merge(_Self& __x)
1.642 + { _STLP_PRIV _S_merge(*this, __x, less<value_type>()); }
1.643 +
1.644 + void reverse() {
1.645 + _Node_base* __p = &this->_M_node._M_data;
1.646 + _Node_base* __tmp = __p;
1.647 + do {
1.648 + _STLP_STD::swap(__tmp->_M_next, __tmp->_M_prev);
1.649 + __tmp = __tmp->_M_prev; // Old next node is now prev.
1.650 + } while (__tmp != __p);
1.651 + }
1.652 +
1.653 + void sort()
1.654 + { _STLP_PRIV _S_sort(*this, less<value_type>()); }
1.655 +
1.656 +#if defined (_STLP_MEMBER_TEMPLATES)
1.657 + template <class _Predicate>
1.658 + void remove_if(_Predicate __pred)
1.659 + { _STLP_PRIV _S_remove_if(*this, __pred); }
1.660 + template <class _BinaryPredicate>
1.661 + void unique(_BinaryPredicate __binary_pred)
1.662 + { _STLP_PRIV _S_unique(*this, __binary_pred); }
1.663 +
1.664 + template <class _StrictWeakOrdering>
1.665 + void merge(_Self& __x,
1.666 + _StrictWeakOrdering __comp) {
1.667 + _STLP_PRIV _S_merge(*this, __x, __comp);
1.668 + }
1.669 +
1.670 + template <class _StrictWeakOrdering>
1.671 + void sort(_StrictWeakOrdering __comp)
1.672 + { _STLP_PRIV _S_sort(*this, __comp); }
1.673 +#endif /* _STLP_MEMBER_TEMPLATES */
1.674 +};
1.675 +
1.676 +#if defined (list)
1.677 +# undef list
1.678 +_STLP_MOVE_TO_STD_NAMESPACE
1.679 +#endif
1.680 +
1.681 +_STLP_END_NAMESPACE
1.682 +
1.683 +#if !defined (_STLP_LINK_TIME_INSTANTIATION)
1.684 +# include <stl/_list.c>
1.685 +#endif
1.686 +
1.687 +#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
1.688 +# include <stl/pointers/_list.h>
1.689 +#endif
1.690 +
1.691 +#if defined (_STLP_DEBUG)
1.692 +# include <stl/debug/_list.h>
1.693 +#endif
1.694 +
1.695 +_STLP_BEGIN_NAMESPACE
1.696 +
1.697 +template <class _Tp, class _Alloc>
1.698 +_STLP_INLINE_LOOP bool _STLP_CALL
1.699 +operator==(const list<_Tp,_Alloc>& __x, const list<_Tp,_Alloc>& __y) {
1.700 + typedef typename list<_Tp,_Alloc>::const_iterator const_iterator;
1.701 + const_iterator __end1 = __x.end();
1.702 + const_iterator __end2 = __y.end();
1.703 +
1.704 + const_iterator __i1 = __x.begin();
1.705 + const_iterator __i2 = __y.begin();
1.706 + while (__i1 != __end1 && __i2 != __end2 && *__i1 == *__i2) {
1.707 + ++__i1;
1.708 + ++__i2;
1.709 + }
1.710 + return __i1 == __end1 && __i2 == __end2;
1.711 +}
1.712 +
1.713 +#define _STLP_EQUAL_OPERATOR_SPECIALIZED
1.714 +#define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc>
1.715 +#define _STLP_TEMPLATE_CONTAINER list<_Tp, _Alloc>
1.716 +#include <stl/_relops_cont.h>
1.717 +#undef _STLP_TEMPLATE_CONTAINER
1.718 +#undef _STLP_TEMPLATE_HEADER
1.719 +#undef _STLP_EQUAL_OPERATOR_SPECIALIZED
1.720 +
1.721 +#if defined (_STLP_CLASS_PARTIAL_SPECIALIZATION)
1.722 +template <class _Tp, class _Alloc>
1.723 +struct __move_traits<list<_Tp, _Alloc> > {
1.724 + typedef __stlp_movable implemented;
1.725 + typedef typename __move_traits<_Alloc>::complete complete;
1.726 +};
1.727 +#endif /* _STLP_CLASS_PARTIAL_SPECIALIZATION */
1.728 +
1.729 +_STLP_END_NAMESPACE
1.730 +
1.731 +#endif /* _STLP_INTERNAL_LIST_IMPL_H */
1.732 +
1.733 +// Local Variables:
1.734 +// mode:C++
1.735 +// End: