stl_deque.h

gcc3.2.1源代码

// deque implementation -*- C++ -*-

// Copyright (C) 2001, 2002 Free Software Foundation, Inc.
//
// This file is part of the GNU ISO C++ Library.  This library is free
// software; you can redistribute it and/or modify it under the
// terms of the GNU General Public License as published by the
// Free Software Foundation; either version 2, or (at your option)
// any later version.

// This library is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU General Public License for more details.

// You should have received a copy of the GNU General Public License along
// with this library; see the file COPYING.  If not, write to the Free
// Software Foundation, 59 Temple Place - Suite 330, Boston, MA 02111-1307,
// USA.

// As a special exception, you may use this file as part of a free software
// library without restriction.  Specifically, if other files instantiate
// templates or use macros or inline functions from this file, or you compile
// this file and link it with other files to produce an executable, this
// file does not by itself cause the resulting executable to be covered by
// the GNU General Public License.  This exception does not however
// invalidate any other reasons why the executable file might be covered by
// the GNU General Public License.

/*
 *
 * Copyright (c) 1994
 * Hewlett-Packard Company
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Hewlett-Packard Company makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 *
 *
 * Copyright (c) 1997
 * Silicon Graphics Computer Systems, Inc.
 *
 * Permission to use, copy, modify, distribute and sell this software
 * and its documentation for any purpose is hereby granted without fee,
 * provided that the above copyright notice appear in all copies and
 * that both that copyright notice and this permission notice appear
 * in supporting documentation.  Silicon Graphics makes no
 * representations about the suitability of this software for any
 * purpose.  It is provided "as is" without express or implied warranty.
 */

/** @file stl_deque.h
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#include <bits/concept_check.h>
#include <bits/stl_iterator_base_types.h>
#include <bits/stl_iterator_base_funcs.h>

#ifndef __GLIBCPP_INTERNAL_DEQUE_H
#define __GLIBCPP_INTERNAL_DEQUE_H


// Since this entire file is within namespace std, there's no reason to
// waste two spaces along the left column.  Thus the leading indentation is
// slightly violated from here on.
namespace std
{ 

/**
 *  @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,