-/**
- * @if maint
- * @brief This function controls the size of memory nodes.
- * @param size The size of an element.
- * @return The number (not bytesize) of elements per node.
- *
- * This function started off as a compiler kludge from SGI, but seems to
- * be a useful wrapper around a repeated constant expression.
- * @endif
-*/
-inline size_t
-__deque_buf_size(size_t __size)
-{ return __size < 512 ? size_t(512 / __size) : size_t(1); }
-
-
-/// A deque::iterator.
-/**
- * Quite a bit of intelligence here. Much of the functionality of deque is
- * actually passed off to this class. A deque holds two of these internally,
- * marking its valid range. Access to elements is done as offsets of either
- * of those two, relying on operator overloading in this class.
- *
- * @if maint
- * All the functions are op overloads except for _M_set_node.
- * @endif
-*/
-template <class _Tp, class _Ref, class _Ptr>
-struct _Deque_iterator
-{
- typedef _Deque_iterator<_Tp, _Tp&, _Tp*> iterator;
- typedef _Deque_iterator<_Tp, const _Tp&, const _Tp*> const_iterator;
- static size_t _S_buffer_size() { return __deque_buf_size(sizeof(_Tp)); }
-
- typedef random_access_iterator_tag iterator_category;
- typedef _Tp value_type;
- typedef _Ptr pointer;
- typedef _Ref reference;
- typedef size_t size_type;
- typedef ptrdiff_t difference_type;
- typedef _Tp** _Map_pointer;
- typedef _Deque_iterator _Self;
-
- _Tp* _M_cur;
- _Tp* _M_first;
- _Tp* _M_last;
- _Map_pointer _M_node;
-
- _Deque_iterator(_Tp* __x, _Map_pointer __y)
- : _M_cur(__x), _M_first(*__y),
- _M_last(*__y + _S_buffer_size()), _M_node(__y) {}
- _Deque_iterator() : _M_cur(0), _M_first(0), _M_last(0), _M_node(0) {}
- _Deque_iterator(const iterator& __x)
- : _M_cur(__x._M_cur), _M_first(__x._M_first),
- _M_last(__x._M_last), _M_node(__x._M_node) {}
-
- reference operator*() const { return *_M_cur; }
- pointer operator->() const { return _M_cur; }
-
- _Self& operator++() {
- ++_M_cur;
- if (_M_cur == _M_last) {
- _M_set_node(_M_node + 1);
- _M_cur = _M_first;
- }
- return *this;
- }
- _Self operator++(int) {
- _Self __tmp = *this;
- ++*this;
- return __tmp;
- }
-
- _Self& operator--() {
- if (_M_cur == _M_first) {
- _M_set_node(_M_node - 1);
- _M_cur = _M_last;
- }
- --_M_cur;
- return *this;
- }
- _Self operator--(int) {
- _Self __tmp = *this;
- --*this;
- return __tmp;
- }
-
- _Self& operator+=(difference_type __n)
- {
- difference_type __offset = __n + (_M_cur - _M_first);
- if (__offset >= 0 && __offset < difference_type(_S_buffer_size()))
- _M_cur += __n;
- else {
- difference_type __node_offset =
- __offset > 0 ? __offset / difference_type(_S_buffer_size())
- : -difference_type((-__offset - 1) / _S_buffer_size()) - 1;
- _M_set_node(_M_node + __node_offset);
- _M_cur = _M_first +
- (__offset - __node_offset * difference_type(_S_buffer_size()));
- }
- return *this;
- }
-
- _Self operator+(difference_type __n) const
- {
- _Self __tmp = *this;
- return __tmp += __n;
- }
-
- _Self& operator-=(difference_type __n) { return *this += -__n; }
-
- _Self operator-(difference_type __n) const {
- _Self __tmp = *this;
- return __tmp -= __n;
- }
-
- reference operator[](difference_type __n) const { return *(*this + __n); }
-
- /** @if maint
- * Prepares to traverse new_node. Sets everything except _M_cur, which
- * should therefore be set by the caller immediately afterwards, based on
- * _M_first and _M_last.
- * @endif
- */
- void _M_set_node(_Map_pointer __new_node) {
- _M_node = __new_node;
- _M_first = *__new_node;
- _M_last = _M_first + difference_type(_S_buffer_size());
- }
-};
-
-// Note: we also provide overloads whose operands are of the same type in
-// order to avoid ambiguos overload resolution when std::rel_ops operators
-// are in scope (for additional details, see libstdc++/3628)
-template <class _Tp, class _Ref, class _Ptr>
-inline bool
-operator==(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
- const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
-{
- return __x._M_cur == __y._M_cur;
-}
-
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
-inline bool
-operator==(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
- const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
-{
- return __x._M_cur == __y._M_cur;
-}
-
-template <class _Tp, class _Ref, class _Ptr>
-inline bool
-operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
- const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
-{
- return !(__x == __y);
-}
-
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
-inline bool
-operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
- const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
-{
- return !(__x == __y);
-}
-
-template <class _Tp, class _Ref, class _Ptr>
-inline bool
-operator<(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
- const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
-{
- return (__x._M_node == __y._M_node) ?
- (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
-}
-
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
-inline bool
-operator<(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
- const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
-{
- return (__x._M_node == __y._M_node) ?
- (__x._M_cur < __y._M_cur) : (__x._M_node < __y._M_node);
-}
-
-template <class _Tp, class _Ref, class _Ptr>
-inline bool
-operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
- const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
-{
- return __y < __x;
-}
-
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
-inline bool
-operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
- const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
-{
- return __y < __x;
-}
-
-template <class _Tp, class _Ref, class _Ptr>
-inline bool
-operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
- const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
-{
- return !(__y < __x);
-}
-
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
-inline bool
-operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
- const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
-{
- return !(__y < __x);
-}
-
-template <class _Tp, class _Ref, class _Ptr>
-inline bool
-operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
- const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
-{
- return !(__x < __y);
-}
-
-template <class _Tp, class _RefL, class _PtrL, class _RefR, class _PtrR>
-inline bool
-operator>=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
- const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
-{
- return !(__x < __y);
-}
-
-// _GLIBCPP_RESOLVE_LIB_DEFECTS
-// According to the resolution of DR179 not only the various comparison
-// operators but also operator- must accept mixed iterator/const_iterator
-// parameters.
-template <typename _Tp, typename _RefL, typename _PtrL,
- typename _RefR, typename _PtrR>
-inline typename _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
-operator-(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
- const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
-{
- return _Deque_iterator<_Tp, _RefL, _PtrL>::difference_type
- (_Deque_iterator<_Tp, _RefL, _PtrL>::_S_buffer_size()) *
- (__x._M_node - __y._M_node - 1) + (__x._M_cur - __x._M_first) +
- (__y._M_last - __y._M_cur);
-}
-
-template <class _Tp, class _Ref, class _Ptr>
-inline _Deque_iterator<_Tp, _Ref, _Ptr>
-operator+(ptrdiff_t __n, const _Deque_iterator<_Tp, _Ref, _Ptr>& __x)
-{
- return __x + __n;
-}
-
-
-/// @if maint Primary default version. @endif
-/**
- * @if maint
- * Deque base class. It has two purposes. First, its constructor
- * and destructor allocate (but don't initialize) storage. This makes
- * exception safety easier. Second, the base class encapsulates all of
- * the differences between SGI-style allocators and standard-conforming
- * allocators. There are two versions: this ordinary one, and the
- * space-saving specialization for instanceless allocators.
- * @endif
-*/
-template <class _Tp, class _Alloc, bool __is_static>
-class _Deque_alloc_base
-{
-public:
- typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
- allocator_type get_allocator() const { return _M_node_allocator; }
-
- _Deque_alloc_base(const allocator_type& __a)
- : _M_node_allocator(__a), _M_map_allocator(__a),
- _M_map(0), _M_map_size(0)
- {}
-
-protected:
- typedef typename _Alloc_traits<_Tp*, _Alloc>::allocator_type
- _Map_allocator_type;
-
- allocator_type _M_node_allocator;
- _Map_allocator_type _M_map_allocator;
-
- _Tp* _M_allocate_node() {
- return _M_node_allocator.allocate(__deque_buf_size(sizeof(_Tp)));
- }
- void _M_deallocate_node(_Tp* __p) {
- _M_node_allocator.deallocate(__p, __deque_buf_size(sizeof(_Tp)));
- }
- _Tp** _M_allocate_map(size_t __n)
- { return _M_map_allocator.allocate(__n); }
- void _M_deallocate_map(_Tp** __p, size_t __n)
- { _M_map_allocator.deallocate(__p, __n); }
-
- _Tp** _M_map;
- size_t _M_map_size;
-};
-
-/// @if maint Specialization for instanceless allocators. @endif
-template <class _Tp, class _Alloc>
-class _Deque_alloc_base<_Tp, _Alloc, true>
-{
-public:
- typedef typename _Alloc_traits<_Tp,_Alloc>::allocator_type allocator_type;
- allocator_type get_allocator() const { return allocator_type(); }
-
- _Deque_alloc_base(const allocator_type&) : _M_map(0), _M_map_size(0) {}
-
-protected:
- typedef typename _Alloc_traits<_Tp, _Alloc>::_Alloc_type _Node_alloc_type;
- typedef typename _Alloc_traits<_Tp*, _Alloc>::_Alloc_type _Map_alloc_type;
-
- _Tp* _M_allocate_node() {
- return _Node_alloc_type::allocate(__deque_buf_size(sizeof(_Tp)));
- }
- void _M_deallocate_node(_Tp* __p) {
- _Node_alloc_type::deallocate(__p, __deque_buf_size(sizeof(_Tp)));
- }
- _Tp** _M_allocate_map(size_t __n)
- { return _Map_alloc_type::allocate(__n); }
- void _M_deallocate_map(_Tp** __p, size_t __n)
- { _Map_alloc_type::deallocate(__p, __n); }
-
- _Tp** _M_map;
- size_t _M_map_size;
-};
-
-
-/**
- * @if maint
- * Deque base class. Using _Alloc_traits in the instantiation of the parent
- * class provides the compile-time dispatching mentioned in the parent's docs.
- * This class provides the unified face for deque's allocation.
- *
- * Nothing in this class ever constructs or destroys an actual Tp element.
- * (Deque handles that itself.) Only/All memory management is performed here.
- * @endif
-*/
-template <class _Tp, class _Alloc>
-class _Deque_base
- : public _Deque_alloc_base<_Tp,_Alloc,
- _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
-{
-public:
- typedef _Deque_alloc_base<_Tp,_Alloc,
- _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
- _Base;
- typedef typename _Base::allocator_type allocator_type;
- typedef _Deque_iterator<_Tp,_Tp&,_Tp*> iterator;
- typedef _Deque_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
-
- _Deque_base(const allocator_type& __a, size_t __num_elements)
- : _Base(__a), _M_start(), _M_finish()
- { _M_initialize_map(__num_elements); }
- _Deque_base(const allocator_type& __a)
- : _Base(__a), _M_start(), _M_finish() {}
- ~_Deque_base();
-
-protected:
- void _M_initialize_map(size_t);
- void _M_create_nodes(_Tp** __nstart, _Tp** __nfinish);
- void _M_destroy_nodes(_Tp** __nstart, _Tp** __nfinish);
- enum { _S_initial_map_size = 8 };
-
-protected:
- iterator _M_start;
- iterator _M_finish;
-};
-
-
-template <class _Tp, class _Alloc>
-_Deque_base<_Tp,_Alloc>::~_Deque_base()
-{
- if (_M_map) {
- _M_destroy_nodes(_M_start._M_node, _M_finish._M_node + 1);
- _M_deallocate_map(_M_map, _M_map_size);
- }
-}
-
-/**
- * @if maint
- * @brief Layout storage.
- * @param num_elements The count of T's for which to allocate space at first.
- * @return Nothing.
- *
- * The initial underlying memory layout is a bit complicated...
- * @endif
-*/
-template <class _Tp, class _Alloc>
-void
-_Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements)
-{
- size_t __num_nodes =
- __num_elements / __deque_buf_size(sizeof(_Tp)) + 1;
-
- _M_map_size = max((size_t) _S_initial_map_size, __num_nodes + 2);
- _M_map = _M_allocate_map(_M_map_size);
-
- _Tp** __nstart = _M_map + (_M_map_size - __num_nodes) / 2;
- _Tp** __nfinish = __nstart + __num_nodes;
-
- try
- { _M_create_nodes(__nstart, __nfinish); }
- catch(...)
- {
- _M_deallocate_map(_M_map, _M_map_size);
- _M_map = 0;
- _M_map_size = 0;
- __throw_exception_again;
- }
-
- _M_start._M_set_node(__nstart);
- _M_finish._M_set_node(__nfinish - 1);
- _M_start._M_cur = _M_start._M_first;
- _M_finish._M_cur = _M_finish._M_first +
- __num_elements % __deque_buf_size(sizeof(_Tp));
-}
-
-template <class _Tp, class _Alloc>
-void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart, _Tp** __nfinish)
-{
- _Tp** __cur;
- try {
- for (__cur = __nstart; __cur < __nfinish; ++__cur)
- *__cur = _M_allocate_node();
- }
- catch(...)
- {
- _M_destroy_nodes(__nstart, __cur);
- __throw_exception_again;
- }
-}