stl_deque.h

gcc-you can use this code to learn something about gcc, and inquire further into linux,

// 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.
 */

#ifndef __GLIBCPP_INTERNAL_DEQUE_H
#define __GLIBCPP_INTERNAL_DEQUE_H

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

namespace std
{ 
  /**
   *  @if maint
   *  @brief This function controls the size of memory nodes.
   *  @param  size  The size of an element.
   *  @return   The number (not byte size) 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.  The '512' is
   *  tuneable (and no other code needs to change), but no investigation has
   *  been done since inheriting the SGI code.
   *  @endif
  */
  inline size_t 
  __deque_buf_size(size_t __size) 
  { return __size < 512 ? size_t(512 / __size) : size_t(1); }
  
  
  /**
   *  @brief 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 <typename _Tp, typename _Ref, typename _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 ambiguous overload resolution when std::rel_ops operators
  // are in scope (for additional details, see libstdc++/3628)
  template <typename _Tp, typename _Ref, typename _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 <typename _Tp, typename _RefL, typename _PtrL,
                          typename _RefR, typename _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 <typename _Tp, typename _Ref, typename _Ptr>
  inline bool
  operator!=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  	   const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
  {
    return !(__x == __y);
  }
  
  template <typename _Tp, typename _RefL, typename _PtrL,
                          typename _RefR, typename _PtrR>
  inline bool
  operator!=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
  	   const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
  {
    return !(__x == __y);
  }
  
  template <typename _Tp, typename _Ref, typename _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 <typename _Tp, typename _RefL, typename _PtrL,
                          typename _RefR, typename _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 <typename _Tp, typename _Ref, typename _Ptr>
  inline bool
  operator>(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  	   const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
  {
    return __y < __x;
  }
  
  template <typename _Tp, typename _RefL, typename _PtrL,
                          typename _RefR, typename _PtrR>
  inline bool
  operator>(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
  	   const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
  {
    return __y < __x;
  }
  
  template <typename _Tp, typename _Ref, typename _Ptr>
  inline bool
  operator<=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  	   const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
  {
    return !(__y < __x);
  }
  
  template <typename _Tp, typename _RefL, typename _PtrL,
                          typename _RefR, typename _PtrR>
  inline bool
  operator<=(const _Deque_iterator<_Tp, _RefL, _PtrL>& __x,
  	   const _Deque_iterator<_Tp, _RefR, _PtrR>& __y)
  {
    return !(__y < __x);
  }
  
  template <typename _Tp, typename _Ref, typename _Ptr>
  inline bool
  operator>=(const _Deque_iterator<_Tp, _Ref, _Ptr>& __x,
  	   const _Deque_iterator<_Tp, _Ref, _Ptr>& __y)
  {
    return !(__x < __y);
  }
  
  template <typename _Tp, typename _RefL, typename _PtrL,
                          typename _RefR, typename _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 <typename _Tp, typename _Ref, typename _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.  (See stl_alloc.h for more on this topic.)  There are two
   *  versions:  this ordinary one, and the space-saving specialization for
   *  instanceless allocators.
   *  @endif
  */
  template <typename _Tp, typename _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;
  
    _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); }
  
    allocator_type       _M_node_allocator;
    _Map_allocator_type  _M_map_allocator;
    _Tp**                _M_map;
    size_t               _M_map_size;
  };
  
  /// @if maint Specialization for instanceless allocators.  @endif
  template <typename _Tp, typename _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)
    {}