stl_list.h

俄罗斯高人Mamaich的Pocket gcc编译器（运行在PocketPC上）的全部源代码。

// List 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) 1996,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_list.h
 *  This is an internal header file, included by other library headers.
 *  You should not attempt to use it directly.
 */

#ifndef __GLIBCPP_INTERNAL_LIST_H
#define __GLIBCPP_INTERNAL_LIST_H

#include <bits/concept_check.h>

namespace std
{
  // Supporting structures are split into common and templated types; the
  // latter publicly inherits from the former in an effort to reduce code
  // duplication.  This results in some "needless" static_cast'ing later on,
  // but it's all safe downcasting.
  
  /// @if maint Common part of a node in the %list.  @endif
  struct _List_node_base
  {
    _List_node_base* _M_next;   ///< Self-explanatory
    _List_node_base* _M_prev;   ///< Self-explanatory
  };
  
  /// @if maint An actual node in the %list.  @endif
  template<typename _Tp>
    struct _List_node : public _List_node_base
  {
    _Tp _M_data;                ///< User's data.
  };
  
  
  /**
   *  @if maint
   *  @brief Common part of a list::iterator.
   *
   *  A simple type to walk a doubly-linked list.  All operations here should
   *  be self-explanatory after taking any decent introductory data structures
   *  course.
   *  @endif
  */
  struct _List_iterator_base
  {
    typedef size_t                        size_type;
    typedef ptrdiff_t                     difference_type;
    typedef bidirectional_iterator_tag    iterator_category;
  
    /// The only member points to the %list element.
    _List_node_base* _M_node;
  
    _List_iterator_base(_List_node_base* __x)
    : _M_node(__x)
    { }
  
    _List_iterator_base()
    { }
  
    /// Walk the %list forward.
    void
    _M_incr()
    { _M_node = _M_node->_M_next; }
  
    /// Walk the %list backward.
    void
    _M_decr()
    { _M_node = _M_node->_M_prev; }
  
    bool
    operator==(const _List_iterator_base& __x) const
    { return _M_node == __x._M_node; }
  
    bool
    operator!=(const _List_iterator_base& __x) const
    { return _M_node != __x._M_node; }
  };
  
  /**
   *  @brief A list::iterator.
   *
   *  In addition to being used externally, a list holds one of these
   *  internally, pointing to the sequence of data.
   *
   *  @if maint
   *  All the functions are op overloads.
   *  @endif
  */
  template<typename _Tp, typename _Ref, typename _Ptr>
    struct _List_iterator : public _List_iterator_base
  {
    typedef _List_iterator<_Tp,_Tp&,_Tp*>             iterator;
    typedef _List_iterator<_Tp,const _Tp&,const _Tp*> const_iterator;
    typedef _List_iterator<_Tp,_Ref,_Ptr>             _Self;
  
    typedef _Tp                                       value_type;
    typedef _Ptr                                      pointer;
    typedef _Ref                                      reference;
    typedef _List_node<_Tp>                           _Node;
  
    _List_iterator(_Node* __x)
    : _List_iterator_base(__x)
    { }
  
    _List_iterator()
    { }
  
    _List_iterator(const iterator& __x)
    : _List_iterator_base(__x._M_node)
    { }
  
    reference
    operator*() const
    { return static_cast<_Node*>(_M_node)->_M_data; }
    // Must downcast from List_node_base to _List_node to get to _M_data.
  
    pointer
    operator->() const
    { return &(operator*()); }
  
    _Self&
    operator++()
    {
      this->_M_incr();
      return *this;
    }
  
    _Self
    operator++(int)
    {
      _Self __tmp = *this;
      this->_M_incr();
      return __tmp;
    }
  
    _Self&
    operator--()
    {
      this->_M_decr();
      return *this;
    }
  
    _Self
    operator--(int)
    {
      _Self __tmp = *this;
      this->_M_decr();
      return __tmp;
    }
  };
  
  
  /// @if maint Primary default version.  @endif
  /**
   *  @if maint
   *  See bits/stl_deque.h's _Deque_alloc_base for an explanation.
   *  @endif
  */
  template<typename _Tp, typename _Allocator, bool _IsStatic>
    class _List_alloc_base
  {
  public:
    typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
            allocator_type;
  
    allocator_type
    get_allocator() const { return _M_node_allocator; }
  
    _List_alloc_base(const allocator_type& __a)
    : _M_node_allocator(__a)
    { }
  
  protected:
    _List_node<_Tp>*
    _M_get_node()
    { return _M_node_allocator.allocate(1); }
  
    void
    _M_put_node(_List_node<_Tp>* __p)
    { _M_node_allocator.deallocate(__p, 1); }
  
    // NOTA BENE
    // The stored instance is not actually of "allocator_type"'s type.  Instead
    // we rebind the type to Allocator<List_node<Tp>>, which according to
    // [20.1.5]/4 should probably be the same.  List_node<Tp> is not the same
    // size as Tp (it's two pointers larger), and specializations on Tp may go
    // unused because List_node<Tp> is being bound instead.
    //
    // We put this to the test in get_allocator above; if the two types are
    // actually different, there had better be a conversion between them.
    //
    // None of the predefined allocators shipped with the library (as of 3.1)
    // use this instantiation anyhow; they're all instanceless.
    typename _Alloc_traits<_List_node<_Tp>, _Allocator>::allocator_type
             _M_node_allocator;
  
    _List_node<_Tp>* _M_node;
  };
  
  /// @if maint Specialization for instanceless allocators.  @endif
  template<typename _Tp, typename _Allocator>
    class _List_alloc_base<_Tp, _Allocator, true>
  {
  public:
    typedef typename _Alloc_traits<_Tp, _Allocator>::allocator_type
            allocator_type;
  
    allocator_type
    get_allocator() const { return allocator_type(); }
  
    _List_alloc_base(const allocator_type&)
    { }
  
  protected:
    // See comment in primary template class about why this is safe for the
    // standard predefined classes.
    typedef typename _Alloc_traits<_List_node<_Tp>, _Allocator>::_Alloc_type
            _Alloc_type;
  
    _List_node<_Tp>*
    _M_get_node()
    { return _Alloc_type::allocate(1); }
  
    void
    _M_put_node(_List_node<_Tp>* __p)
    { _Alloc_type::deallocate(__p, 1); }
  
    _List_node<_Tp>* _M_node;
  };
  
  
  /**
   *  @if maint
   *  See bits/stl_deque.h's _Deque_base for an explanation.
   *  @endif
  */
  template <typename _Tp, typename _Alloc>
    class _List_base
    : public _List_alloc_base<_Tp, _Alloc,
                              _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
  {
  public:
    typedef _List_alloc_base<_Tp, _Alloc,
                             _Alloc_traits<_Tp, _Alloc>::_S_instanceless>
            _Base;
    typedef typename _Base::allocator_type allocator_type;
  
    _List_base(const allocator_type& __a)
    : _Base(__a)
    {
      _M_node = _M_get_node();
      _M_node->_M_next = _M_node;
      _M_node->_M_prev = _M_node;
    }
  
    // This is what actually destroys the list.
    ~_List_base()
    {
      __clear();
      _M_put_node(_M_node);
    }
  
    void
    __clear();
  };
  
  
  /**
   *  @brief  A standard container with linear time access to elements, and
   *  fixed time insertion/deletion at any point in the sequence.
   *
   *  @ingroup Containers
   *  @ingroup Sequences
   *
   *  Meets the requirements of a <a href="tables.html#65">container</a>, a
   *  <a href="tables.html#66">reversible container</a>, and a
   *  <a href="tables.html#67">sequence</a>, including the
   *  <a href="tables.html#68">optional sequence requirements</a> with the
   *  %exception of @c at and @c operator[].
   *
   *  This is a @e doubly @e linked %list.  Traversal up and down the %list
   *  requires linear time, but adding and removing elements (or @e nodes) is
   *  done in constant time, regardless of where the change takes place.
   *  Unlike std::vector and std::deque, random-access iterators are not
   *  provided, so subscripting ( @c [] ) access is not allowed.  For algorithms
   *  which only need sequential access, this lack makes no difference.
   *
   *  Also unlike the other standard containers, std::list provides specialized 
   *  algorithms %unique to linked lists, such as splicing, sorting, and
   *  in-place reversal.
   *
   *  @if maint
   *  A couple points on memory allocation for list<Tp>:
   *
   *  First, we never actually allocate a Tp, we allocate List_node<Tp>'s
   *  and trust [20.1.5]/4 to DTRT.  This is to ensure that after elements from
   *  %list<X,Alloc1> are spliced into %list<X,Alloc2>, destroying the memory of
   *  the second %list is a valid operation, i.e., Alloc1 giveth and Alloc2
   *  taketh away.
   *
   *  Second, a %list conceptually represented as
   *  @code
   *    A <---> B <---> C <---> D
   *  @endcode
   *  is actually circular; a link exists between A and D.  The %list class
   *  holds (as its only data member) a private list::iterator pointing to
   *  @e D, not to @e A!  To get to the head of the %list, we start at the tail
   *  and move forward by one.  When this member iterator's next/previous
   *  pointers refer to itself, the %list is %empty.
   *  @endif
  */
  template<typename _Tp, typename _Alloc = allocator<_Tp> >
    class list : protected _List_base<_Tp, _Alloc>
  {
    // concept requirements
    __glibcpp_class_requires(_Tp, _SGIAssignableConcept)
  
    typedef _List_base<_Tp, _Alloc>                       _Base;
  
  public:
    typedef _Tp                                           value_type;
    typedef value_type*                                   pointer;
    typedef const value_type*                             const_pointer;
    typedef _List_iterator<_Tp,_Tp&,_Tp*>                 iterator;
    typedef _List_iterator<_Tp,const _Tp&,const _Tp*>     const_iterator;
    typedef std::reverse_iterator<const_iterator>     const_reverse_iterator;
    typedef std::reverse_iterator<iterator>                 reverse_iterator;
    typedef value_type&                                   reference;
    typedef const value_type&                             const_reference;
    typedef size_t                                        size_type;
    typedef ptrdiff_t                                     difference_type;
    typedef typename _Base::allocator_type                allocator_type;
  
  protected:
    // Note that pointers-to-_Node's can be ctor-converted to iterator types.
    typedef _List_node<_Tp>                               _Node;