_deque.c

symbian 上的stl_port进过编译的。

/*
 *
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Copyright (c) 1996,1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Copyright (c) 1997
 * Moscow Center for SPARC Technology
 *
 * Copyright (c) 1999
 * Boris Fomitchev
 *
 * This material is provided "as is", with absolutely no warranty expressed
 * or implied. Any use is at your own risk.
 *
 * Permission to use or copy this software for any purpose is hereby granted
 * without fee, provided the above notices are retained on all copies.
 * Permission to modify the code and to distribute modified code is granted,
 * provided the above notices are retained, and a notice that the code was
 * modified is included with the above copyright notice.
 *
 */
#ifndef _STLP_DEQUE_C
#define _STLP_DEQUE_C

#ifndef _STLP_INTERNAL_DEQUE_H
#  include <stl/_deque.h>
#endif

_STLP_BEGIN_NAMESPACE

_STLP_MOVE_TO_PRIV_NAMESPACE

// Non-inline member functions from _Deque_base.

template <class _Tp, class _Alloc >
_Deque_base<_Tp,_Alloc >::~_Deque_base() {
  if (_M_map._M_data) {
    _M_destroy_nodes(_M_start._M_node, this->_M_finish._M_node + 1);
    _M_map.deallocate(_M_map._M_data, _M_map_size._M_data);
  }
}

template <class _Tp, class _Alloc >
void _Deque_base<_Tp,_Alloc>::_M_initialize_map(size_t __num_elements) {
  size_t __num_nodes = __num_elements / this->buffer_size() + 1 ;

  _M_map_size._M_data = (max)((size_t) _S_initial_map_size, __num_nodes + 2);
  _M_map._M_data = _M_map.allocate(_M_map_size._M_data);

  _Tp** __nstart = _M_map._M_data + (_M_map_size._M_data - __num_nodes) / 2;
  _Tp** __nfinish = __nstart + __num_nodes;

  _STLP_TRY {
    _M_create_nodes(__nstart, __nfinish);
  }
  _STLP_UNWIND((_M_map.deallocate(_M_map._M_data, _M_map_size._M_data),
                _M_map._M_data = 0, _M_map_size._M_data = 0))
  _M_start._M_set_node(__nstart);
  this->_M_finish._M_set_node(__nfinish - 1);
  _M_start._M_cur = _M_start._M_first;
  this->_M_finish._M_cur = this->_M_finish._M_first + __num_elements % this->buffer_size();
}

template <class _Tp, class _Alloc >
void _Deque_base<_Tp,_Alloc>::_M_create_nodes(_Tp** __nstart,
                                              _Tp** __nfinish) {
  _Tp** __cur = __nstart;
  _STLP_TRY {
    for (; __cur < __nfinish; ++__cur)
      *__cur = _M_map_size.allocate(this->buffer_size());
  }
  _STLP_UNWIND(_M_destroy_nodes(__nstart, __cur))
}

template <class _Tp, class _Alloc >
void _Deque_base<_Tp,_Alloc>::_M_destroy_nodes(_Tp** __nstart,
                                               _Tp** __nfinish) {
  for (_Tp** __n = __nstart; __n < __nfinish; ++__n)
    _M_map_size.deallocate(*__n, this->buffer_size());
}

#if defined (_STLP_USE_PTR_SPECIALIZATIONS)
#  define deque _STLP_PTR_IMPL_NAME(deque)
#elif defined (_STLP_DEBUG)
#  define deque _STLP_NON_DBG_NAME(deque)
#else
_STLP_MOVE_TO_STD_NAMESPACE
#endif

#if defined (_STLP_NESTED_TYPE_PARAM_BUG)
// qualified references
#  define __iterator__   _Deque_iterator<_Tp, _Nonconst_traits<_Tp> >
#  define const_iterator _Deque_iterator<_Tp, _Const_traits<_Tp>  >
#  define iterator       __iterator__
#  define size_type      size_t
#  define value_type     _Tp
#else
#  define __iterator__   _STLP_TYPENAME_ON_RETURN_TYPE deque<_Tp, _Alloc>::iterator
#endif

template <class _Tp, class _Alloc >
deque<_Tp, _Alloc >&
deque<_Tp, _Alloc >::operator= (const deque<_Tp, _Alloc >& __x) {
  const size_type __len = size();
  if (&__x != this) {
    if (__len >= __x.size())
      erase(copy(__x.begin(), __x.end(), this->_M_start), this->_M_finish);
    else {
      const_iterator __mid = __x.begin() + difference_type(__len);
      copy(__x.begin(), __mid, this->_M_start);
      insert(this->_M_finish, __mid, __x.end());
    }
  }
  return *this;
}

template <class _Tp, class _Alloc >
void deque<_Tp, _Alloc >::_M_fill_insert(iterator __pos,
                                         size_type __n, const value_type& __x) {
  if (__pos._M_cur == this->_M_start._M_cur) {
    iterator __new_start = _M_reserve_elements_at_front(__n);
    _STLP_TRY {
      uninitialized_fill(__new_start, this->_M_start, __x);
    }
    _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
    this->_M_start = __new_start;
  }
  else if (__pos._M_cur == this->_M_finish._M_cur) {
    iterator __new_finish = _M_reserve_elements_at_back(__n);
    _STLP_TRY {
      uninitialized_fill(this->_M_finish, __new_finish, __x);
    }
    _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node+1, __new_finish._M_node+1))
    this->_M_finish = __new_finish;
  }
  else
    _M_fill_insert_aux(__pos, __n, __x, _Movable());
}

#if !defined (_STLP_MEMBER_TEMPLATES)

template <class _Tp, class _Alloc >
void deque<_Tp, _Alloc>::insert(iterator __pos,
                                const value_type* __first, const value_type* __last) {
  size_type __n = __last - __first;
  if (__pos._M_cur == this->_M_start._M_cur) {
    iterator __new_start = _M_reserve_elements_at_front(__n);
    _STLP_TRY {
      _STLP_PRIV __ucopy(__first, __last, __new_start);
    }
    _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
    this->_M_start = __new_start;
  }
  else if (__pos._M_cur == this->_M_finish._M_cur) {
    iterator __new_finish = _M_reserve_elements_at_back(__n);
    _STLP_TRY {
      _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
    }
    _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
                                        __new_finish._M_node + 1))
    this->_M_finish = __new_finish;
  }
  else
    _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
}

template <class _Tp, class _Alloc >
void deque<_Tp,_Alloc>::insert(iterator __pos,
                               const_iterator __first, const_iterator __last) {
  size_type __n = __last - __first;
  if (__pos._M_cur == this->_M_start._M_cur) {
    iterator __new_start = _M_reserve_elements_at_front(__n);
    _STLP_TRY {
      _STLP_PRIV __ucopy(__first, __last, __new_start);
    }
    _STLP_UNWIND(this->_M_destroy_nodes(__new_start._M_node, this->_M_start._M_node))
    this->_M_start = __new_start;
  }
  else if (__pos._M_cur == this->_M_finish._M_cur) {
    iterator __new_finish = _M_reserve_elements_at_back(__n);
    _STLP_TRY {
      _STLP_PRIV __ucopy(__first, __last, this->_M_finish);
    }
    _STLP_UNWIND(this->_M_destroy_nodes(this->_M_finish._M_node + 1,
                                        __new_finish._M_node + 1))
    this->_M_finish = __new_finish;
  }
  else
    _M_insert_range_aux(__pos, __first, __last, __n, _Movable());
}

#endif /* _STLP_MEMBER_TEMPLATES */

template <class _Tp, class _Alloc >
__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
                                         const __true_type& /*_Movable*/) {
  difference_type __index = __pos - this->_M_start;
  if (size_type(__index) < this->size() >> 1) {
    //We move the start of the deque one position to the right
    //starting from the rightmost element to move.
    iterator __src = __pos, __dst = __pos;
    _STLP_STD::_Destroy(&(*__dst));
    if (__src != this->_M_start) {
      for (--__src; __dst != this->_M_start; --__src, --__dst) {
        _STLP_STD::_Move_Construct(&(*__dst), *__src);
        _STLP_STD::_Destroy_Moved(&(*__src));
      }
    }
    _M_pop_front_aux();
  }
  else {
    iterator __src = __pos, __dst = __pos;
    _STLP_STD::_Destroy(&(*__dst));
    for (++__src; __src != this->_M_finish; ++__src, ++__dst) {
      _STLP_STD::_Move_Construct(&(*__dst), *__src);
      _STLP_STD::_Destroy_Moved(&(*__src));
    }
    //Duplication of the pop_back code without the destroy which has already been done:
    if (this->_M_finish._M_cur != this->_M_finish._M_first) {
      --this->_M_finish._M_cur;
    }
    else {
      _M_pop_back_aux();
    }
  }
  return this->_M_start + __index;
}

template <class _Tp, class _Alloc >
__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __pos,
                                         const __false_type& /*_Movable*/) {
  iterator __next = __pos;
  ++__next;
  difference_type __index = __pos - this->_M_start;
  if (size_type(__index) < this->size() >> 1) {
    copy_backward(this->_M_start, __pos, __next);
    pop_front();
  }
  else {
    copy(__next, this->_M_finish, __pos);
    pop_back();
  }
  return this->_M_start + __index;
}

template <class _Tp, class _Alloc >
__iterator__ deque<_Tp,_Alloc>::_M_erase(iterator __first, iterator __last,
                                         const __true_type& /*_Movable*/) {
  difference_type __n = __last - __first;
  difference_type __elems_before = __first - this->_M_start;
  if (__elems_before <= difference_type(this->size() - __n) / 2) {
    iterator __src = __first, __dst = __last;
    if (__src != this->_M_start) {
      for (--__src, --__dst; (__src >= this->_M_start) && (__dst >= __first); --__src, --__dst) {
        _STLP_STD::_Destroy(&(*__dst));
        _STLP_STD::_Move_Construct(&(*__dst), *__src);
      }
      if (__dst >= __first) {
        //There are more elements to erase than elements to move
        _STLP_STD::_Destroy_Range(__first, ++__dst);
        _STLP_STD::_Destroy_Moved_Range(this->_M_start, __first);
      }
      else {
        //There are more elements to move than elements to erase
        for (; __src >= this->_M_start; --__src, --__dst) {
          _STLP_STD::_Destroy_Moved(&(*__dst));
          _STLP_STD::_Move_Construct(&(*__dst), *__src);
        }