1.1 --- a/epoc32/include/stdapis/stlport/stl/_deque.h Tue Nov 24 13:55:44 2009 +0000
1.2 +++ b/epoc32/include/stdapis/stlport/stl/_deque.h Tue Mar 16 16:12:26 2010 +0000
1.3 @@ -1,1 +1,988 @@
1.4 -_deque.h
1.5 +/*
1.6 + * © Portions copyright (c) 2006-2007 Nokia Corporation. All rights reserved.
1.7 + *
1.8 + * Copyright (c) 1994
1.9 + * Hewlett-Packard Company
1.10 + *
1.11 + * Copyright (c) 1996,1997
1.12 + * Silicon Graphics Computer Systems, Inc.
1.13 + *
1.14 + * Copyright (c) 1997
1.15 + * Moscow Center for SPARC Technology
1.16 + *
1.17 + * Copyright (c) 1999
1.18 + * Boris Fomitchev
1.19 + *
1.20 + * This material is provided "as is", with absolutely no warranty expressed
1.21 + * or implied. Any use is at your own risk.
1.22 + *
1.23 + * Permission to use or copy this software for any purpose is hereby granted
1.24 + * without fee, provided the above notices are retained on all copies.
1.25 + * Permission to modify the code and to distribute modified code is granted,
1.26 + * provided the above notices are retained, and a notice that the code was
1.27 + * modified is included with the above copyright notice.
1.28 + *
1.29 + */
1.30 +
1.31 +/* NOTE: This is an internal header file, included by other STL headers.
1.32 + * You should not attempt to use it directly.
1.33 + */
1.34 +
1.35 +#ifndef _STLP_INTERNAL_DEQUE_H
1.36 +#define _STLP_INTERNAL_DEQUE_H
1.37 +
1.38 +# ifndef _STLP_INTERNAL_ALGOBASE_H
1.39 +# include <stl/_algobase.h>
1.40 +# endif
1.41 +
1.42 +# ifndef _STLP_INTERNAL_ALLOC_H
1.43 +# include <stl/_alloc.h>
1.44 +# endif
1.45 +
1.46 +# ifndef _STLP_INTERNAL_ITERATOR_H
1.47 +# include <stl/_iterator.h>
1.48 +# endif
1.49 +
1.50 +# ifndef _STLP_INTERNAL_UNINITIALIZED_H
1.51 +# include <stl/_uninitialized.h>
1.52 +# endif
1.53 +
1.54 +# ifndef _STLP_RANGE_ERRORS_H
1.55 +# include <stl/_range_errors.h>
1.56 +# endif
1.57 +
1.58 +/* Class invariants:
1.59 + * For any nonsingular iterator i:
1.60 + * i.node is the address of an element in the map array. The
1.61 + * contents of i.node is a pointer to the beginning of a node.
1.62 + * i.first == *(i.node)
1.63 + * i.last == i.first + node_size
1.64 + * i.cur is a pointer in the range [i.first, i.last). NOTE:
1.65 + * the implication of this is that i.cur is always a dereferenceable
1.66 + * pointer, even if i is a past-the-end iterator.
1.67 + * Start and Finish are always nonsingular iterators. NOTE: this means
1.68 + * that an empty deque must have one node, and that a deque
1.69 + * with N elements, where N is the buffer size, must have two nodes.
1.70 + * For every node other than start.node and finish.node, every element
1.71 + * in the node is an initialized object. If start.node == finish.node,
1.72 + * then [start.cur, finish.cur) are initialized objects, and
1.73 + * the elements outside that range are uninitialized storage. Otherwise,
1.74 + * [start.cur, start.last) and [finish.first, finish.cur) are initialized
1.75 + * objects, and [start.first, start.cur) and [finish.cur, finish.last)
1.76 + * are uninitialized storage.
1.77 + * [map, map + map_size) is a valid, non-empty range.
1.78 + * [start.node, finish.node] is a valid range contained within
1.79 + * [map, map + map_size).
1.80 + * A pointer in the range [map, map + map_size) points to an allocated node
1.81 + * if and only if the pointer is in the range [start.node, finish.node].
1.82 + */
1.83 +
1.84 +# undef deque
1.85 +# define deque __WORKAROUND_DBG_RENAME(deque)
1.86 +
1.87 +_STLP_BEGIN_NAMESPACE
1.88 +
1.89 +template <class _Tp>
1.90 +struct _Deque_iterator_base {
1.91 +
1.92 + enum _Constants {
1.93 + _blocksize = _MAX_BYTES,
1.94 + __buffer_size = (sizeof(_Tp) < (size_t)_blocksize ?
1.95 + ( (size_t)_blocksize / sizeof(_Tp)) : size_t(1))
1.96 + };
1.97 +
1.98 + typedef random_access_iterator_tag iterator_category;
1.99 +
1.100 + typedef _Tp value_type;
1.101 + typedef size_t size_type;
1.102 + typedef ptrdiff_t difference_type;
1.103 +
1.104 + typedef value_type** _Map_pointer;
1.105 +
1.106 + typedef _Deque_iterator_base< _Tp > _Self;
1.107 +
1.108 + value_type* _M_cur;
1.109 + value_type* _M_first;
1.110 + value_type* _M_last;
1.111 + _Map_pointer _M_node;
1.112 +
1.113 + _Deque_iterator_base(value_type* __x, _Map_pointer __y)
1.114 + : _M_cur(__x), _M_first(*__y),
1.115 + _M_last(*__y + __buffer_size), _M_node(__y) {}
1.116 + _Deque_iterator_base() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
1.117 +
1.118 + difference_type _M_subtract(const _Self& __x) const {
1.119 + return difference_type(__buffer_size) * (_M_node - __x._M_node - 1) +
1.120 + (_M_cur - _M_first) + (__x._M_last - __x._M_cur);
1.121 + }
1.122 +
1.123 + void _M_increment() {
1.124 + if (++_M_cur == _M_last) {
1.125 + _M_set_node(_M_node + 1);
1.126 + _M_cur = _M_first;
1.127 + }
1.128 + }
1.129 +
1.130 + void _M_decrement() {
1.131 + if (_M_cur == _M_first) {
1.132 + _M_set_node(_M_node - 1);
1.133 + _M_cur = _M_last;
1.134 + }
1.135 + --_M_cur;
1.136 + }
1.137 +
1.138 + void _M_advance(difference_type __n)
1.139 + {
1.140 + difference_type __offset = __n + (_M_cur - _M_first);
1.141 + if (__offset >= 0 && __offset < difference_type(__buffer_size))
1.142 + _M_cur += __n;
1.143 + else {
1.144 + difference_type __node_offset =
1.145 + __offset > 0 ? __offset / __buffer_size
1.146 + : -difference_type((-__offset - 1) / __buffer_size) - 1;
1.147 + _M_set_node(_M_node + __node_offset);
1.148 + _M_cur = _M_first +
1.149 + (__offset - __node_offset * difference_type(__buffer_size));
1.150 + }
1.151 + }
1.152 +
1.153 + void _M_set_node(_Map_pointer __new_node) {
1.154 + _M_last = (_M_first = *(_M_node = __new_node)) + difference_type(__buffer_size);
1.155 + }
1.156 +};
1.157 +
1.158 +
1.159 +
1.160 +template <class _Tp, class _Traits>
1.161 +struct _Deque_iterator : public _Deque_iterator_base< _Tp> {
1.162 +
1.163 + typedef random_access_iterator_tag iterator_category;
1.164 + typedef _Tp value_type;
1.165 + typedef typename _Traits::reference reference;
1.166 + typedef typename _Traits::pointer pointer;
1.167 + typedef size_t size_type;
1.168 + typedef ptrdiff_t difference_type;
1.169 + typedef value_type** _Map_pointer;
1.170 +
1.171 + typedef _Deque_iterator_base< _Tp > _Base;
1.172 + typedef _Deque_iterator<_Tp, _Traits> _Self;
1.173 + typedef _Deque_iterator<_Tp, _Nonconst_traits<_Tp> > _Nonconst_self;
1.174 + typedef _Deque_iterator<_Tp, _Const_traits<_Tp> > _Const_self;
1.175 +
1.176 + _Deque_iterator(value_type* __x, _Map_pointer __y) :
1.177 + _Deque_iterator_base<value_type>(__x,__y) {}
1.178 +
1.179 + _Deque_iterator() {}
1.180 + _Deque_iterator(const _Nonconst_self& __x) :
1.181 + _Deque_iterator_base<value_type>(__x) {}
1.182 +
1.183 + reference operator*() const {
1.184 + return *this->_M_cur;
1.185 + }
1.186 +
1.187 + _STLP_DEFINE_ARROW_OPERATOR
1.188 +
1.189 + difference_type operator-(const _Self& __x) const { return this->_M_subtract(__x); }
1.190 +
1.191 + _Self& operator++() { this->_M_increment(); return *this; }
1.192 + _Self operator++(int) {
1.193 + _Self __tmp = *this;
1.194 + ++*this;
1.195 + return __tmp;
1.196 + }
1.197 +
1.198 + _Self& operator--() { this->_M_decrement(); return *this; }
1.199 + _Self operator--(int) {
1.200 + _Self __tmp = *this;
1.201 + --*this;
1.202 + return __tmp;
1.203 + }
1.204 +
1.205 + _Self& operator+=(difference_type __n) { this->_M_advance(__n); return *this; }
1.206 + _Self operator+(difference_type __n) const
1.207 + {
1.208 + _Self __tmp = *this;
1.209 + return __tmp += __n;
1.210 + }
1.211 +
1.212 + _Self& operator-=(difference_type __n) { return *this += -__n; }
1.213 + _Self operator-(difference_type __n) const {
1.214 + _Self __tmp = *this;
1.215 + return __tmp -= __n;
1.216 + }
1.217 +
1.218 + reference operator[](difference_type __n) const { return *(*this + __n); }
1.219 +};
1.220 +
1.221 +template <class _Tp, class _Traits>
1.222 +inline _Deque_iterator<_Tp, _Traits> _STLP_CALL
1.223 +operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Traits>& __x)
1.224 +{
1.225 + return __x + __n;
1.226 +}
1.227 +
1.228 +
1.229 +#ifdef _STLP_USE_SEPARATE_RELOPS_NAMESPACE
1.230 +
1.231 +template <class _Tp>
1.232 +inline bool _STLP_CALL
1.233 +operator==(const _Deque_iterator_base<_Tp >& __x,
1.234 + const _Deque_iterator_base<_Tp >& __y) {
1.235 + return __x._M_cur == __y._M_cur;
1.236 +}
1.237 +
1.238 +template <class _Tp>
1.239 +inline bool _STLP_CALL
1.240 +operator < (const _Deque_iterator_base<_Tp >& __x,
1.241 + const _Deque_iterator_base<_Tp >& __y) {
1.242 + return (__x._M_node == __y._M_node) ?
1.243 + (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
1.244 +}
1.245 +
1.246 +template <class _Tp>
1.247 +inline bool _STLP_CALL
1.248 +operator!=(const _Deque_iterator_base<_Tp >& __x,
1.249 + const _Deque_iterator_base<_Tp >& __y) {
1.250 + return __x._M_cur != __y._M_cur;
1.251 +}
1.252 +template <class _Tp>
1.253 +inline bool _STLP_CALL
1.254 +operator>(const _Deque_iterator_base<_Tp >& __x,
1.255 + const _Deque_iterator_base<_Tp >& __y) {
1.256 + return __y < __x;
1.257 +}
1.258 +template <class _Tp>
1.259 +inline bool _STLP_CALL operator>=(const _Deque_iterator_base<_Tp >& __x,
1.260 + const _Deque_iterator_base<_Tp >& __y) {
1.261 + return !(__x < __y);
1.262 +}
1.263 +template <class _Tp>
1.264 +inline bool _STLP_CALL operator<=(const _Deque_iterator_base<_Tp >& __x,
1.265 + const _Deque_iterator_base<_Tp >& __y) {
1.266 + return !(__y < __x);
1.267 +}
1.268 +
1.269 +# else
1.270 +
1.271 +template <class _Tp, class _Traits1, class _Traits2>
1.272 +inline bool _STLP_CALL
1.273 +operator==(const _Deque_iterator<_Tp, _Traits1 >& __x,
1.274 + const _Deque_iterator<_Tp, _Traits2 >& __y) {
1.275 + return __x._M_cur == __y._M_cur;
1.276 +}
1.277 +
1.278 +template <class _Tp, class _Traits1, class _Traits2>
1.279 +inline bool _STLP_CALL
1.280 +operator < (const _Deque_iterator<_Tp, _Traits1 >& __x,
1.281 + const _Deque_iterator<_Tp, _Traits2 >& __y) {
1.282 + return (__x._M_node == __y._M_node) ?
1.283 + (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
1.284 +}
1.285 +
1.286 +template <class _Tp>
1.287 +inline bool _STLP_CALL
1.288 +operator!=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
1.289 + const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y) {
1.290 + return __x._M_cur != __y._M_cur;
1.291 +}
1.292 +template <class _Tp>
1.293 +inline bool _STLP_CALL
1.294 +operator>(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
1.295 + const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y) {
1.296 + return __y < __x;
1.297 +}
1.298 +template <class _Tp>
1.299 +inline bool _STLP_CALL
1.300 +operator>=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
1.301 + const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y) {
1.302 + return !(__x < __y);
1.303 +}
1.304 +template <class _Tp>
1.305 +inline bool _STLP_CALL
1.306 +operator<=(const _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >& __x,
1.307 + const _Deque_iterator<_Tp, _Const_traits<_Tp> >& __y) {
1.308 + return !(__y < __x);
1.309 +}
1.310 +# endif
1.311 +
1.312 +# ifdef _STLP_USE_OLD_HP_ITERATOR_QUERIES
1.313 +template <class _Tp, class _Traits> inline _Tp* _STLP_CALL value_type(const _Deque_iterator<_Tp, _Traits >&) { return (_Tp*)0; }
1.314 +template <class _Tp, class _Traits> inline random_access_iterator_tag _STLP_CALL
1.315 +iterator_category(const _Deque_iterator<_Tp, _Traits >&) { return random_access_iterator_tag(); }
1.316 +template <class _Tp, class _Traits> inline ptrdiff_t* _STLP_CALL
1.317 +distance_type(const _Deque_iterator<_Tp, _Traits >&) { return 0; }
1.318 +#endif
1.319 +
1.320 +// Deque base class. It has two purposes. First, its constructor
1.321 +// and destructor allocate (but don't initialize) storage. This makes
1.322 +// exception safety easier. Second, the base class encapsulates all of
1.323 +// the differences between SGI-style allocators and standard-conforming
1.324 +// allocators.
1.325 +
1.326 +template <class _Tp, class _Alloc>
1.327 +class _Deque_base
1.328 +{
1.329 +public:
1.330 + typedef _Tp value_type;
1.331 + _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
1.332 + typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
1.333 + typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type _Map_alloc_type;
1.334 +
1.335 + typedef _Deque_iterator<_Tp, _Nonconst_traits<_Tp> > iterator;
1.336 + typedef _Deque_iterator<_Tp, _Const_traits<_Tp> > const_iterator;
1.337 +
1.338 + typedef _Deque_base<_Tp, _Alloc> _Base;
1.339 +
1.340 + static size_t _STLP_CALL buffer_size() { return (size_t)_Deque_iterator_base<_Tp>::__buffer_size; }
1.341 +
1.342 + _Deque_base(const allocator_type& __a, size_t __num_elements)
1.343 + : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
1.344 + _M_map_size(__a, (size_t)0) {
1.345 + _STLP_PUSH_CLEANUP_ITEM(_Base, this)
1.346 + _M_initialize_map(__num_elements);
1.347 + }
1.348 + _Deque_base(const allocator_type& __a)
1.349 + : _M_start(), _M_finish(), _M_map(_STLP_CONVERT_ALLOCATOR(__a, _Tp*), 0),
1.350 + _M_map_size(__a, (size_t)0) {
1.351 + _STLP_PUSH_CLEANUP_ITEM(_Base, this)
1.352 + }
1.353 + ~_Deque_base();
1.354 +
1.355 +protected:
1.356 + void _M_initialize_map(size_t);
1.357 + void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
1.358 + void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
1.359 + enum { _S_initial_map_size = 8 };
1.360 +
1.361 +protected:
1.362 + iterator _M_start;
1.363 + iterator _M_finish;
1.364 + _STLP_alloc_proxy<value_type**, value_type*, _Map_alloc_type> _M_map;
1.365 + _STLP_alloc_proxy<size_t, value_type, allocator_type> _M_map_size;
1.366 +};
1.367 +
1.368 +
1.369 +template <class _Tp, _STLP_DEFAULT_ALLOCATOR_SELECT(_Tp) >
1.370 +class deque : public _Deque_base<_Tp, _Alloc> {
1.371 + typedef _Deque_base<_Tp, _Alloc> _Base;
1.372 + typedef deque<_Tp, _Alloc> _Self;
1.373 +public: // Basic types
1.374 + typedef _Tp value_type;
1.375 + typedef value_type* pointer;
1.376 + typedef const value_type* const_pointer;
1.377 + typedef value_type& reference;
1.378 + typedef const value_type& const_reference;
1.379 + typedef size_t size_type;
1.380 + typedef ptrdiff_t difference_type;
1.381 + typedef random_access_iterator_tag _Iterator_category;
1.382 + _STLP_FORCE_ALLOCATORS(_Tp, _Alloc)
1.383 + typedef typename _Base::allocator_type allocator_type;
1.384 +
1.385 +public: // Iterators
1.386 + typedef typename _Base::iterator iterator;
1.387 + typedef typename _Base::const_iterator const_iterator;
1.388 +
1.389 + _STLP_DECLARE_RANDOM_ACCESS_REVERSE_ITERATORS;
1.390 +
1.391 +protected: // Internal typedefs
1.392 + typedef pointer* _Map_pointer;
1.393 + typedef typename __type_traits<_Tp>::has_trivial_assignment_operator _TrivialAss;
1.394 + typedef typename __type_traits<_Tp>::has_trivial_assignment_operator _IsPODType;
1.395 +
1.396 +public: // Basic accessors
1.397 + iterator begin() { return this->_M_start; }
1.398 + iterator end() { return this->_M_finish; }
1.399 + const_iterator begin() const { return const_iterator(this->_M_start); }
1.400 + const_iterator end() const { return const_iterator(this->_M_finish); }
1.401 +
1.402 + reverse_iterator rbegin() { return reverse_iterator(this->_M_finish); }
1.403 + reverse_iterator rend() { return reverse_iterator(this->_M_start); }
1.404 + const_reverse_iterator rbegin() const
1.405 + { return const_reverse_iterator(this->_M_finish); }
1.406 + const_reverse_iterator rend() const
1.407 + { return const_reverse_iterator(this->_M_start); }
1.408 +
1.409 + reference operator[](size_type __n)
1.410 + { return this->_M_start[difference_type(__n)]; }
1.411 + const_reference operator[](size_type __n) const
1.412 + { return this->_M_start[difference_type(__n)]; }
1.413 +
1.414 + void _M_range_check(size_type __n) const {
1.415 + if (__n >= this->size())
1.416 + __stl_throw_out_of_range("deque");
1.417 + }
1.418 + reference at(size_type __n)
1.419 + { _M_range_check(__n); return (*this)[__n]; }
1.420 + const_reference at(size_type __n) const
1.421 + { _M_range_check(__n); return (*this)[__n]; }
1.422 +
1.423 + reference front() { return *this->_M_start; }
1.424 + reference back() {
1.425 + iterator __tmp = this->_M_finish;
1.426 + --__tmp;
1.427 + return *__tmp;
1.428 + }
1.429 + const_reference front() const { return *this->_M_start; }
1.430 + const_reference back() const {
1.431 + const_iterator __tmp = this->_M_finish;
1.432 + --__tmp;
1.433 + return *__tmp;
1.434 + }
1.435 +
1.436 + size_type size() const { return this->_M_finish - this->_M_start; }
1.437 + size_type max_size() const { return size_type(-1); }
1.438 + bool empty() const { return this->_M_finish == this->_M_start; }
1.439 + allocator_type get_allocator() const { return this->_M_map_size; }
1.440 +
1.441 +public: // Constructor, destructor.
1.442 + explicit deque(const allocator_type& __a = allocator_type())
1.443 + : _Deque_base<_Tp, _Alloc>(__a, 0) {
1.444 + _STLP_POP_CLEANUP_ITEM
1.445 + }
1.446 +
1.447 + deque(const _Self& __x) :
1.448 + _Deque_base<_Tp, _Alloc>(__x.get_allocator(), __x.size()) {
1.449 + uninitialized_copy(__x.begin(), __x.end(), this->_M_start);
1.450 + _STLP_POP_CLEANUP_ITEM
1.451 + }
1.452 +
1.453 + deque(size_type __n, const value_type& __val,
1.454 + const allocator_type& __a = allocator_type()) :
1.455 + _Deque_base<_Tp, _Alloc>(__a, __n)
1.456 + {
1.457 + _M_fill_initialize(__val);
1.458 + _STLP_POP_CLEANUP_ITEM
1.459 + }
1.460 + // int,long variants may be needed
1.461 + explicit deque(size_type __n) : _Deque_base<_Tp, _Alloc>(allocator_type(), __n)
1.462 + {
1.463 +#ifdef __SYMBIAN32__
1.464 +// Though the below code is for Symbian
1.465 +// we are not using cleanup stack with this version.
1.466 + _M_fill_initialize(value_type());
1.467 +#else
1.468 + value_type __p;
1.469 + _STLP_PUSH_CLEANUP_ITEM(_Tp, &__p)
1.470 + _M_fill_initialize(__p);
1.471 + // unconditional for __p
1.472 +// CleanupStack::Pop();
1.473 + _STLP_POP_CLEANUP_ITEM
1.474 +#endif // __SYMBIAN32__
1.475 + }
1.476 +
1.477 +#ifdef _STLP_MEMBER_TEMPLATES
1.478 +
1.479 + template <class _Integer>
1.480 + void _M_initialize_dispatch(_Integer __n, _Integer __x, const __true_type&) {
1.481 + this->_M_initialize_map(__n);
1.482 + _M_fill_initialize(__x);
1.483 + }
1.484 +
1.485 + template <class _InputIter>
1.486 + void _M_initialize_dispatch(_InputIter __first, _InputIter __last,
1.487 + const __false_type&) {
1.488 + _M_range_initialize(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIter));
1.489 + }
1.490 +
1.491 +# ifdef _STLP_NEEDS_EXTRA_TEMPLATE_CONSTRUCTORS
1.492 + // VC++ needs this
1.493 + template <class _InputIterator>
1.494 + deque(_InputIterator __first, _InputIterator __last) :
1.495 + _Deque_base<_Tp, _Alloc>(allocator_type()) {
1.496 + typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
1.497 + _M_initialize_dispatch(__first, __last, _Integral());
1.498 + _STLP_POP_CLEANUP_ITEM
1.499 + }
1.500 +# endif
1.501 +
1.502 + // Check whether it's an integral type. If so, it's not an iterator.
1.503 + template <class _InputIterator>
1.504 + deque(_InputIterator __first, _InputIterator __last,
1.505 + const allocator_type& __a _STLP_ALLOCATOR_TYPE_DFL) :
1.506 + _Deque_base<_Tp, _Alloc>(__a) {
1.507 + typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
1.508 + _M_initialize_dispatch(__first, __last, _Integral());
1.509 + _STLP_POP_CLEANUP_ITEM
1.510 + }
1.511 +
1.512 +# else
1.513 + deque(const value_type* __first, const value_type* __last,
1.514 + const allocator_type& __a = allocator_type() )
1.515 + : _Deque_base<_Tp, _Alloc>(__a, __last - __first) {
1.516 + __uninitialized_copy(__first, __last, this->_M_start, _IsPODType());
1.517 + _STLP_POP_CLEANUP_ITEM
1.518 + }
1.519 +
1.520 + deque(const_iterator __first, const_iterator __last,
1.521 + const allocator_type& __a = allocator_type() )
1.522 + : _Deque_base<_Tp, _Alloc>(__a, __last - __first) {
1.523 + __uninitialized_copy(__first, __last, this->_M_start, _IsPODType());
1.524 + _STLP_POP_CLEANUP_ITEM
1.525 + }
1.526 +#endif /* _STLP_MEMBER_TEMPLATES */
1.527 +
1.528 + ~deque() {
1.529 + _STLP_STD::_Destroy(this->_M_start, this->_M_finish);
1.530 + }
1.531 +
1.532 + _Self& operator= (const _Self& __x);
1.533 +
1.534 + void swap(_Self& __x) {
1.535 + _STLP_STD::swap(this->_M_start, __x._M_start);
1.536 + _STLP_STD::swap(this->_M_finish, __x._M_finish);
1.537 + _STLP_STD::swap(this->_M_map, __x._M_map);
1.538 + _STLP_STD::swap(this->_M_map_size, __x._M_map_size);
1.539 + }
1.540 +
1.541 +#ifdef _STLP_USE_TRAP_LEAVE
1.542 +public:
1.543 + static void* operator new (size_t __n, TLeave) { return _STLP_StackHelper<bool>::_NewLC(__n); }
1.544 + static void* operator new (size_t __n) { return _STLP_StackHelper<bool>::_NewLC(__n); }
1.545 +#endif
1.546 +
1.547 +public:
1.548 + // assign(), a generalized assignment member function. Two
1.549 + // versions: one that takes a count, and one that takes a range.
1.550 + // The range version is a member template, so we dispatch on whether
1.551 + // or not the type is an integer.
1.552 +
1.553 + void _M_fill_assign(size_type __n, const _Tp& __val) {
1.554 + if (__n > size()) {
1.555 + _STLP_STD::fill(begin(), end(), __val);
1.556 + insert(end(), __n - size(), __val);
1.557 + }
1.558 + else {
1.559 + erase(begin() + __n, end());
1.560 + _STLP_STD::fill(begin(), end(), __val);
1.561 + }
1.562 + }
1.563 +
1.564 + void assign(size_type __n, const _Tp& __val) {
1.565 + _M_fill_assign(__n, __val);
1.566 + }
1.567 +
1.568 +#ifdef _STLP_MEMBER_TEMPLATES
1.569 +
1.570 + template <class _InputIterator>
1.571 + void assign(_InputIterator __first, _InputIterator __last) {
1.572 + typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
1.573 + _M_assign_dispatch(__first, __last, _Integral());
1.574 + }
1.575 +
1.576 +private: // helper functions for assign()
1.577 +
1.578 + template <class _Integer>
1.579 + void _M_assign_dispatch(_Integer __n, _Integer __val, const __true_type&)
1.580 + { _M_fill_assign((size_type) __n, (_Tp) __val); }
1.581 +
1.582 + template <class _InputIterator>
1.583 + void _M_assign_dispatch(_InputIterator __first, _InputIterator __last,
1.584 + const __false_type&) {
1.585 + _M_assign_aux(__first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
1.586 + }
1.587 +
1.588 + template <class _InputIter>
1.589 + void _M_assign_aux(_InputIter __first, _InputIter __last, const input_iterator_tag &) {
1.590 + iterator __cur = begin();
1.591 + for ( ; __first != __last && __cur != end(); ++__cur, ++__first)
1.592 + *__cur = *__first;
1.593 + if (__first == __last)
1.594 + erase(__cur, end());
1.595 + else
1.596 + insert(end(), __first, __last);
1.597 + }
1.598 +
1.599 + template <class _ForwardIterator>
1.600 + void _M_assign_aux(_ForwardIterator __first, _ForwardIterator __last,
1.601 + const forward_iterator_tag &) {
1.602 + size_type __len = distance(__first, __last);
1.603 + if (__len > size()) {
1.604 + _ForwardIterator __mid = __first;
1.605 + advance(__mid, size());
1.606 + copy(__first, __mid, begin());
1.607 + insert(end(), __mid, __last);
1.608 + }
1.609 + else
1.610 + erase(copy(__first, __last, begin()), end());
1.611 + }
1.612 +
1.613 +#endif /* _STLP_MEMBER_TEMPLATES */
1.614 +
1.615 +public: // push_* and pop_*
1.616 +
1.617 + void push_back(const value_type& __t) {
1.618 + if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
1.619 + _Construct(this->_M_finish._M_cur, __t);
1.620 + ++this->_M_finish._M_cur;
1.621 + }
1.622 + else
1.623 + _M_push_back_aux_v(__t);
1.624 + }
1.625 + void push_front(const value_type& __t) {
1.626 + if (this->_M_start._M_cur != this->_M_start._M_first) {
1.627 + _Construct(this->_M_start._M_cur - 1, __t);
1.628 + --this->_M_start._M_cur;
1.629 + }
1.630 + else
1.631 + _M_push_front_aux_v(__t);
1.632 + }
1.633 +
1.634 +# ifndef _STLP_NO_ANACHRONISMS
1.635 + void push_back() {
1.636 + if (this->_M_finish._M_cur != this->_M_finish._M_last - 1) {
1.637 + _Construct(this->_M_finish._M_cur);
1.638 + ++this->_M_finish._M_cur;
1.639 + }
1.640 + else
1.641 + _M_push_back_aux();
1.642 + }
1.643 + void push_front() {
1.644 + if (this->_M_start._M_cur != this->_M_start._M_first) {
1.645 + _Construct(this->_M_start._M_cur - 1);
1.646 + --this->_M_start._M_cur;
1.647 + }
1.648 + else
1.649 + _M_push_front_aux();
1.650 + }
1.651 +# endif
1.652 +
1.653 + void pop_back() {
1.654 + if (this->_M_finish._M_cur != this->_M_finish._M_first) {
1.655 + --this->_M_finish._M_cur;
1.656 + _STLP_STD::_Destroy(this->_M_finish._M_cur);
1.657 + }
1.658 + else
1.659 + _M_pop_back_aux();
1.660 + }
1.661 +
1.662 + void pop_front() {
1.663 + if (this->_M_start._M_cur != this->_M_start._M_last - 1) {
1.664 + _STLP_STD::_Destroy(this->_M_start._M_cur);
1.665 + ++this->_M_start._M_cur;
1.666 + }
1.667 + else
1.668 + _M_pop_front_aux();
1.669 + }
1.670 +
1.671 +public: // Insert
1.672 +
1.673 + iterator insert(iterator __position, const value_type& __x) {
1.674 + if (__position._M_cur == this->_M_start._M_cur) {
1.675 + push_front(__x);
1.676 + return this->_M_start;
1.677 + }
1.678 + else if (__position._M_cur == this->_M_finish._M_cur) {
1.679 + push_back(__x);
1.680 + iterator __tmp = this->_M_finish;
1.681 + --__tmp;
1.682 + return __tmp;
1.683 + }
1.684 + else {
1.685 + return _M_insert_aux(__position, __x);
1.686 + }
1.687 + }
1.688 +
1.689 + iterator insert(iterator __position)
1.690 + { return insert(__position, value_type()); }
1.691 +
1.692 + void insert(iterator __pos, size_type __n, const value_type& __x) {
1.693 + _M_fill_insert(__pos, __n, __x);
1.694 + }
1.695 +
1.696 + void _M_fill_insert(iterator __pos, size_type __n, const value_type& __x);
1.697 +
1.698 +#ifdef _STLP_MEMBER_TEMPLATES
1.699 +
1.700 + // Check whether it's an integral type. If so, it's not an iterator.
1.701 + template <class _InputIterator>
1.702 + void insert(iterator __pos, _InputIterator __first, _InputIterator __last) {
1.703 + typedef typename _Is_integer<_InputIterator>::_Integral _Integral;
1.704 + _M_insert_dispatch(__pos, __first, __last, _Integral());
1.705 + }
1.706 +
1.707 + template <class _Integer>
1.708 + void _M_insert_dispatch(iterator __pos, _Integer __n, _Integer __x,
1.709 + const __true_type&) {
1.710 + _M_fill_insert(__pos, (size_type) __n, (value_type) __x);
1.711 + }
1.712 +
1.713 + template <class _InputIterator>
1.714 + void _M_insert_dispatch(iterator __pos,
1.715 + _InputIterator __first, _InputIterator __last,
1.716 + const __false_type&) {
1.717 + insert(__pos, __first, __last, _STLP_ITERATOR_CATEGORY(__first, _InputIterator));
1.718 + }
1.719 +
1.720 +#else /* _STLP_MEMBER_TEMPLATES */
1.721 +
1.722 + void insert(iterator __pos,
1.723 + const value_type* __first, const value_type* __last);
1.724 + void insert(iterator __pos,
1.725 + const_iterator __first, const_iterator __last);
1.726 +
1.727 +#endif /* _STLP_MEMBER_TEMPLATES */
1.728 +
1.729 + void resize(size_type __new_size, value_type __x) {
1.730 + const size_type __len = size();
1.731 + if (__new_size < __len)
1.732 + erase(this->_M_start + __new_size, this->_M_finish);
1.733 + else
1.734 + insert(this->_M_finish, __new_size - __len, __x);
1.735 + }
1.736 +
1.737 + void resize(size_type new_size) { resize(new_size, value_type()); }
1.738 +
1.739 +public: // Erase
1.740 + iterator erase(iterator __pos) {
1.741 + iterator __next = __pos;
1.742 + ++__next;
1.743 + difference_type __index = __pos - this->_M_start;
1.744 + if (size_type(__index) < this->size() >> 1) {
1.745 + copy_backward(this->_M_start, __pos, __next);
1.746 + pop_front();
1.747 + }
1.748 + else {
1.749 + copy(__next, this->_M_finish, __pos);
1.750 + pop_back();
1.751 + }
1.752 + return this->_M_start + __index;
1.753 + }
1.754 +
1.755 + iterator erase(iterator __first, iterator __last);
1.756 + void clear();
1.757 +
1.758 +protected: // Internal construction/destruction
1.759 +
1.760 + void _M_fill_initialize(const value_type& __val);
1.761 +
1.762 +#ifdef _STLP_MEMBER_TEMPLATES
1.763 +
1.764 + template <class _InputIterator>
1.765 + void _M_range_initialize(_InputIterator __first,
1.766 + _InputIterator __last,
1.767 + const input_iterator_tag &) {
1.768 + this->_M_initialize_map(0);
1.769 + _STLP_TRY {
1.770 + for ( ; __first != __last; ++__first)
1.771 + push_back(*__first);
1.772 + }
1.773 + _STLP_UNWIND(clear());
1.774 + }
1.775 + template <class _ForwardIterator>
1.776 + void _M_range_initialize(_ForwardIterator __first,
1.777 + _ForwardIterator __last,
1.778 + const forward_iterator_tag &) {
1.779 + size_type __n = distance(__first, __last);
1.780 + this->_M_initialize_map(__n);
1.781 + _STLP_LEAVE_VOLATILE _Map_pointer __cur_node = 0 ;
1.782 + _STLP_TRY {
1.783 + for (__cur_node = this->_M_start._M_node;
1.784 + __cur_node < this->_M_finish._M_node;
1.785 + ++__cur_node) {
1.786 + _ForwardIterator __mid = __first;
1.787 + advance(__mid, this->buffer_size());
1.788 + uninitialized_copy(__first, __mid, *__cur_node);
1.789 + __first = __mid;
1.790 + }
1.791 + uninitialized_copy(__first, __last, this->_M_finish._M_first);
1.792 + }
1.793 + _STLP_UNWIND(_STLP_STD::_Destroy(this->_M_start, iterator(*__cur_node, __cur_node)));
1.794 + }
1.795 +#endif /* _STLP_MEMBER_TEMPLATES */
1.796 +
1.797 +protected: // Internal push_* and pop_*
1.798 +
1.799 + void _M_push_back_aux_v(const value_type&);
1.800 + void _M_push_front_aux_v(const value_type&);
1.801 +# ifndef _STLP_NO_ANACHRONISMS
1.802 + void _M_push_back_aux();
1.803 + void _M_push_front_aux();
1.804 +# endif
1.805 + void _M_pop_back_aux();
1.806 + void _M_pop_front_aux();
1.807 +
1.808 +protected: // Internal insert functions
1.809 +
1.810 +#ifdef _STLP_MEMBER_TEMPLATES
1.811 +
1.812 +template <class _InputIterator>
1.813 +void
1.814 +insert(iterator __pos,
1.815 + _InputIterator __first,
1.816 + _InputIterator __last,
1.817 + const input_iterator_tag &)
1.818 +{
1.819 + copy(__first, __last, inserter(*this, __pos));
1.820 +}
1.821 +
1.822 +template <class _ForwardIterator>
1.823 +void insert(iterator __pos,
1.824 + _ForwardIterator __first,
1.825 + _ForwardIterator __last,
1.826 + const forward_iterator_tag &)
1.827 + {
1.828 + size_type __n = distance(__first, __last);
1.829 + if (__pos._M_cur == this->_M_start._M_cur) {
1.830 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.831 + _STLP_TRY {
1.832 + uninitialized_copy(__first, __last, __new_start);
1.833 + this->_M_start = __new_start;
1.834 + }
1.835 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
1.836 + }
1.837 + else if (__pos._M_cur == this->_M_finish._M_cur) {
1.838 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.839 + _STLP_TRY {
1.840 + uninitialized_copy(__first, __last, this->_M_finish);
1.841 + this->_M_finish = __new_finish;
1.842 + }
1.843 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1));
1.844 + }
1.845 + else
1.846 + _M_insert_aux(__pos, __first, __last, __n);
1.847 +}
1.848 +#endif /* _STLP_MEMBER_TEMPLATES */
1.849 +
1.850 + iterator _M_insert_aux(iterator __pos, const value_type& __x);
1.851 + iterator _M_insert_aux(iterator __pos);
1.852 + iterator _M_insert_aux_prepare(iterator __pos);
1.853 +
1.854 + void _M_insert_aux(iterator __pos, size_type __n, const value_type& __x);
1.855 +
1.856 +#ifdef _STLP_MEMBER_TEMPLATES
1.857 + template <class _ForwardIterator>
1.858 + void _M_insert_aux(iterator __pos,
1.859 + _ForwardIterator __first,
1.860 + _ForwardIterator __last,
1.861 + size_type __n) {
1.862 +
1.863 + const difference_type __elemsbefore = __pos - this->_M_start;
1.864 + size_type __length = size();
1.865 + if (__elemsbefore < difference_type(__length / 2)) {
1.866 + iterator __new_start = _M_reserve_elements_at_front(__n);
1.867 + iterator __old_start = this->_M_start;
1.868 + __pos = this->_M_start + __elemsbefore;
1.869 + _STLP_TRY {
1.870 + if (__elemsbefore >= difference_type(__n)) {
1.871 + iterator __start_n = this->_M_start + difference_type(__n);
1.872 + uninitialized_copy(this->_M_start, __start_n, __new_start);
1.873 + this->_M_start = __new_start;
1.874 + copy(__start_n, __pos, __old_start);
1.875 + copy(__first, __last, __pos - difference_type(__n));
1.876 + }
1.877 + else {
1.878 + _ForwardIterator __mid = __first;
1.879 + advance(__mid, difference_type(__n) - __elemsbefore);
1.880 + __uninitialized_copy_copy(this->_M_start, __pos, __first, __mid,
1.881 + __new_start, _IsPODType());
1.882 + this->_M_start = __new_start;
1.883 + copy(__mid, __last, __old_start);
1.884 + }
1.885 + }
1.886 + _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node));
1.887 + }
1.888 + else {
1.889 + iterator __new_finish = _M_reserve_elements_at_back(__n);
1.890 + iterator __old_finish = this->_M_finish;
1.891 + const difference_type __elemsafter =
1.892 + difference_type(__length) - __elemsbefore;
1.893 + __pos = this->_M_finish - __elemsafter;
1.894 + _STLP_TRY {
1.895 + if (__elemsafter > difference_type(__n)) {
1.896 + iterator __finish_n = this->_M_finish - difference_type(__n);
1.897 + uninitialized_copy(__finish_n, this->_M_finish, this->_M_finish);
1.898 + this->_M_finish = __new_finish;
1.899 + copy_backward(__pos, __finish_n, __old_finish);
1.900 + copy(__first, __last, __pos);
1.901 + }
1.902 + else {
1.903 + _ForwardIterator __mid = __first;
1.904 + advance(__mid, __elemsafter);
1.905 + __uninitialized_copy_copy(__mid, __last, __pos, this->_M_finish, this->_M_finish, _IsPODType());
1.906 + this->_M_finish = __new_finish;
1.907 + copy(__first, __mid, __pos);
1.908 + }
1.909 + }
1.910 + _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1, __new_finish._M_node + 1));
1.911 + }
1.912 + }
1.913 +#else /* _STLP_MEMBER_TEMPLATES */
1.914 +
1.915 + void _M_insert_aux(iterator __pos,
1.916 + const value_type* __first, const value_type* __last,
1.917 + size_type __n);
1.918 +
1.919 + void _M_insert_aux(iterator __pos,
1.920 + const_iterator __first, const_iterator __last,
1.921 + size_type __n);
1.922 +
1.923 +#endif /* _STLP_MEMBER_TEMPLATES */
1.924 +
1.925 + iterator _M_reserve_elements_at_front(size_type __n) {
1.926 + size_type __vacancies = this->_M_start._M_cur - this->_M_start._M_first;
1.927 + if (__n > __vacancies)
1.928 + _M_new_elements_at_front(__n - __vacancies);
1.929 + return this->_M_start - difference_type(__n);
1.930 + }
1.931 +
1.932 + iterator _M_reserve_elements_at_back(size_type __n) {
1.933 + size_type __vacancies = (this->_M_finish._M_last - this->_M_finish._M_cur) - 1;
1.934 + if (__n > __vacancies)
1.935 + _M_new_elements_at_back(__n - __vacancies);
1.936 + return this->_M_finish + difference_type(__n);
1.937 + }
1.938 +
1.939 + void _M_new_elements_at_front(size_type __new_elements);
1.940 + void _M_new_elements_at_back(size_type __new_elements);
1.941 +
1.942 +protected: // Allocation of _M_map and nodes
1.943 +
1.944 + // Makes sure the _M_map has space for new nodes. Does not actually
1.945 + // add the nodes. Can invalidate _M_map pointers. (And consequently,
1.946 + // deque iterators.)
1.947 +
1.948 + void _M_reserve_map_at_back (size_type __nodes_to_add = 1) {
1.949 + if (__nodes_to_add + 1 > this->_M_map_size._M_data - (this->_M_finish._M_node - this->_M_map._M_data))
1.950 + _M_reallocate_map(__nodes_to_add, false);
1.951 + }
1.952 +
1.953 + void _M_reserve_map_at_front (size_type __nodes_to_add = 1) {
1.954 + if (__nodes_to_add > size_type(this->_M_start._M_node - this->_M_map._M_data))
1.955 + _M_reallocate_map(__nodes_to_add, true);
1.956 + }
1.957 +
1.958 + void _M_reallocate_map(size_type __nodes_to_add, bool __add_at_front);
1.959 +
1.960 +};
1.961 +
1.962 +# define _STLP_TEMPLATE_CONTAINER deque<_Tp, _Alloc>
1.963 +# define _STLP_TEMPLATE_HEADER template <class _Tp, class _Alloc>
1.964 +# include <stl/_relops_cont.h>
1.965 +# undef _STLP_TEMPLATE_CONTAINER
1.966 +# undef _STLP_TEMPLATE_HEADER
1.967 +
1.968 +_STLP_END_NAMESPACE
1.969 +
1.970 +// do a cleanup
1.971 +# undef deque
1.972 +# undef __deque__
1.973 +# define __deque__ __WORKAROUND_DBG_RENAME(deque)
1.974 +
1.975 +# if !defined (_STLP_LINK_TIME_INSTANTIATION)
1.976 +# include <stl/_deque.c>
1.977 +# endif
1.978 +
1.979 +#if defined (_STLP_DEBUG)
1.980 +# include <stl/debug/_deque.h>
1.981 +#endif
1.982 +
1.983 +# if defined (_STLP_USE_WRAPPER_FOR_ALLOC_PARAM)
1.984 +# include <stl/wrappers/_deque.h>
1.985 +# endif
1.986 +
1.987 +#endif /* _STLP_INTERNAL_DEQUE_H */
1.988 +
1.989 +// Local Variables:
1.990 +// mode:C++
1.991 +// End:
1.992 +