list.mh

来自「开放源码的编译器open watcom 1.6.0版的源代码」· MH 代码 · 共 750 行 · 第 1/2 页

///////////////////////////////////////////////////////////////////////////
// FILE: list (Definition of std::list)
//
:keep CPP_HDR
:include crwatcnt.sp
//
// Description: This header is part of the C++ standard library. It
//              provides the list sequence container.
///////////////////////////////////////////////////////////////////////////
#ifndef _LIST_INCLUDED
#define _LIST_INCLUDED

:include readonly.sp

#ifndef __cplusplus
#error The header list requires C++
#endif

#ifndef _ITERATOR_INCLUDED
    #include <iterator>
#endif

#ifndef _MEMORY_INCLUDED
    #include <memory>
#endif

#ifndef _TYPE_TRAITS_INCLUDED
    #include <type_tra>
#endif

//#line 32 "list.mh"

namespace std {

/* ==================================================================
 * list class template
 */
template< class Type, class Allocator = allocator< Type > >
class list {
public:
    typedef Type                                value_type;
    typedef unsigned int                        size_type;
    typedef int                                 difference_type;
    typedef Allocator                           allocator_type;
    typedef typename Allocator::reference       reference;
    typedef typename Allocator::const_reference const_reference;
    typedef typename Allocator::pointer         pointer;
    typedef typename Allocator::const_pointer   const_pointer;

private:
    struct DoubleLink{
        DoubleLink* fwd;
        DoubleLink* bwd;
    };
    struct Node : public DoubleLink{
        value_type value;
        Node( value_type const & v ) : value(v) {}
    };
    DoubleLink *sentinel;   //sentinel->fwd = first element in list
                            //sentinel->bwd = last element in list
    Allocator::rebind< Node >::other mMem; //needs to be up here to stop crash
    Allocator::rebind< DoubleLink >::other dlMem;
    
public:
    explicit list( Allocator const & a = Allocator( ) )
        : mSize(0), mMem(a), dlMem(a)
    {
        sentinel = dlMem.allocate( 1 );
        sentinel->fwd = sentinel->bwd = sentinel;
    }
    explicit list( size_type, Type const &, Allocator const & = Allocator() );
    // note compiler feature missing 
    // function templates can't have default params
    // also has to be inline as doesn't understand syntax otherwise
    template< class InputIt >
    list( InputIt f, InputIt l, Allocator const & a )// = Allocator() )
        : mSize(0), mMem(a), dlMem(a)
    {
        sentinel = dlMem.allocate( 1 );
        sentinel->fwd = sentinel->bwd = sentinel;
        helper_assign( f, l, tr1::is_integral<InputIt>::type() );
    }
    
    list( list const& );
   ~list( );
    list &operator=( list const & );
    
    template< class InputIterator >
    void assign( InputIterator f, InputIterator l )
    {
        clear();
        helper_assign( f, l, tr1::is_integral<InputIterator>::type() );
    }

    void assign( size_type, value_type const & );

    allocator_type get_allocator() const 
        { allocator_type a( mMem ); return( mMem ); }

    
    /* ------------------------------------------------------------------
     * iterators
     */
    class iterator_base {
    public:
        iterator_base( ) { }
        iterator_base( DoubleLink *d ) : self( d ) { }
        bool operator==( iterator_base it )
            { return( it.self == self ); }
        bool operator!=( iterator_base it )
            { return( it.self != self ); }
    protected:
        DoubleLink *self;
    };

    class iterator :
        public iterator_base,
        public std::iterator< std::bidirectional_iterator_tag, value_type >{
        friend class list;
    public:
        iterator( )
            : iterator_base( ) { }
        iterator( DoubleLink* d )
            : iterator_base( d ) { }
        value_type& operator*( )
            { return( static_cast< Node *>( self )->value ); }
        value_type* operator->( )
            { return( &( static_cast< Node * >( self )->value ) ); }
        iterator& operator++( )
            { self = self->fwd; return( *this ); }
        iterator& operator--( )
            { self = self->bwd; return( *this ); }
        iterator  operator++( int )
            { iterator it( *this ); operator++( ); return( it ); };
        iterator  operator--( int )
            { iterator it( *this ); operator--( ); return( it ); };
    };

    class const_iterator :
        public iterator_base,
        public std::iterator< std::bidirectional_iterator_tag, const value_type >{
        friend class list;
    public:
        const_iterator( iterator_base it )
            : iterator_base( it ) { }

        const_iterator( )
            : iterator_base( ) { }
        const_iterator( DoubleLink const* d )
            : iterator_base( const_cast< DoubleLink *>( d ) ) { }
        value_type& operator*( )
            { return( static_cast< Node const *>( self )->value ); }
        value_type* operator->( )
            { return( &( static_cast< Node const * >( self )->value ) ); }
        const_iterator& operator++( )
            { self = self->fwd; return( *this ); }
        const_iterator& operator--( )
            { self = self->bwd; return( *this ); }
        const_iterator  operator++( int )
            { const_iterator it( *this ); operator++( ); return( it ); };
        const_iterator  operator--( int )
            { const_iterator it( *this ); operator--( ); return( it ); };
    };

    typedef std::reverse_iterator< iterator >       reverse_iterator;
    typedef std::reverse_iterator< const_iterator > const_reverse_iterator;
    /*
     * end of iterators
     * ------------------------------------------------------------------ */
    
    iterator begin( )
        { return( iterator( sentinel->fwd ) ); }
    iterator end( )
        { return( iterator( sentinel ) ); }
    const_iterator begin( ) const
        { return( const_iterator( sentinel->fwd ) ); }
    const_iterator end( ) const
        { return( const_iterator( sentinel ) ); }

    reverse_iterator rbegin( )
        { return( reverse_iterator( iterator( sentinel ) ) ); }
    reverse_iterator rend( )
        { return( reverse_iterator( iterator( sentinel->fwd ) ) ); }
    const_reverse_iterator rbegin( ) const
        { return( const_reverse_iterator( const_iterator( sentinel ) ) ); }
    const_reverse_iterator rend ( ) const
        { return( const_reverse_iterator( const_iterator( sentinel->fwd ) ) ); }
    
    //capacity
    size_type  size( )  { return( mSize );      }
    bool       empty( ) { return( mSize == 0 ); }

    //element access
    reference  front( )
        { return( static_cast< Node* >( sentinel->fwd )->value ); }
    reference  back( )
        { return( static_cast< Node* >( sentinel->bwd )->value ); }

    //modifiers
    void push_front( value_type const & x )
        { push( static_cast< Node* >( sentinel->fwd ), x ); }
    void pop_front( )
        { pop( static_cast< Node* >( sentinel->fwd ) ); }
    void push_back( value_type const & x )
        { push( static_cast< Node* >( sentinel ), x ); }
    void pop_back( )
        { pop( static_cast< Node* >( sentinel->bwd ) ); }

    iterator insert( iterator, value_type const & );
    void insert( iterator, size_type, value_type const & );
    template< class InputIt >
    void insert( iterator p, InputIt f, InputIt l )
    {
        helper_insert( p, f, l, tr1::is_integral<InputIt>::type() );
    }
    
    iterator erase( iterator it );
    iterator erase( iterator first, iterator last );
    void swap( list & );
    void clear( );
    void remove( value_type const & );

    void splice( iterator it, list &other );
    void splice( iterator it, list &other, iterator other_it );
    void splice( iterator it, list &other, iterator first, iterator last );

    void reverse( );
    void merge( list &other );

    //ow extentions
    bool _Sane( );

private:
    inline void  pop( Node* );
    inline Node* push( Node*, value_type const & );

    /* --------------------------------------------------------------
     * these ones are called when InputIt isn't an integer type
     */
    template< class InputIt >
    void helper_assign( InputIt f, InputIt l, tr1::true_type )
    {
        for( int i = 0; i < static_cast< size_type >( f ); i++ ){
            push_back( static_cast< value_type >( l ) );
        }
    }
    template< class InputIt >
    void helper_insert( iterator i, InputIt f, InputIt l, tr1::true_type )
    { 
        for( size_type n = static_cast< size_type >(f); n > 0; n-- ){
            push( static_cast< Node* >( i.self ),
                  static_cast< value_type >(l) );
        }
    }
    /* --------------------------------------------------------------
     * these ones are called when InputIt is not an integer type 
     */
    template< class InputIt >
    void helper_assign( InputIt f, InputIt l, tr1::false_type )
    {
        for( ; f != l; ++f ) push_back( *f );
    }
    template< class InputIt >
    void helper_insert( iterator p, InputIt f, InputIt l, tr1::false_type )
    {
        // this could probably be optimised to remove
        // unnecessary link rewriting when inserting lots of things
        for( ; f != l; ++f, ++p ) p = insert( p, *f );
    }

    
    //Allocator::rebind< Node >::other mMem;
        //moved above constructors for the time being
        //as this seems to stop compiler crashing.
    size_type mSize;
};

/* ------------------------------------------------------------------
 * ctor( Allocator )
 * construct empty list
 */
/*err, this only seems to work inlined, whats going on?
template< class Type, class Allocator >
explicit list< Type, Allocator >::list( Allocator const & a )
    : mSize(0), mMem(a), dlMem(a)
{
    sentinel = dlMem.allocate( 1 );
    sentinel->fwd = sentinel->bwd = sentinel;
}
*/
/* ------------------------------------------------------------------
 * ctor( size_type, Type, Allocator )
 * construct with n copies of t
 */
template< class Type, class Allocator > 
explicit list< Type, Allocator >::list( size_type n, Type const & t,
                                        Allocator const & a )
    : mSize(0), mMem(a), dlMem(a)
{
    sentinel = dlMem.allocate( 1 );
    sentinel->fwd = sentinel->bwd = sentinel;
    for( int i = 0; i < n; i++ ){
        push_back( t );
    }
}

/* ------------------------------------------------------------------
 * copy ctor
 */
template< class Type, class Allocator > 
list< Type, Allocator >::list( list const& that )
  : mMem(that.mMem), dlMem(that.dlMem)
{
    sentinel = dlMem.allocate( 1 );

    DoubleLink const * o = that.sentinel;
    DoubleLink* n = sentinel;
    mSize = 0;
    while( o->fwd != that.sentinel ){
        try{
            n->fwd = mMem.allocate( 1 );
            try{
                mMem.construct( static_cast< Node* >( n->fwd ),
                                Node(static_cast< Node* >( o->fwd )->value ));
            }catch(...){
                mMem.deallocate( static_cast<Node*>( n->fwd ), 1 );
                throw;
            }
        }catch(...){
            //unwind - can't finish copy construction so remove all elements
            DoubleLink* delme;
            while( n != sentinel ){
                delme = n;
                n = n->bwd;
                mMem.destroy( static_cast< Node* >( delme ) );
                mMem.deallocate( static_cast< Node* >( delme ), 1 );
            };
            dlMem.deallocate( sentinel, 1 );
            throw;
        }
        n->fwd->bwd = n;
        n = n->fwd;
        o = o->fwd;
    };
    n->fwd = sentinel;
    sentinel->bwd = n;
    mSize = that.mSize;
}

/* ------------------------------------------------------------------
 * ~dtor
 */
template< class Type, class Allocator >
list< Type, Allocator >::~list()
{
    clear();
    dlMem.deallocate( sentinel, 1 );
}

/* ------------------------------------------------------------------
 * operator=( lst )
 * assign incoming list to this list
 */
template< class Type, class Allocator >
list< Type, Allocator > &
list< Type, Allocator >::operator=( list const & other )
{
    if( &other == this ) return( *this );

    clear( );
    const_iterator it = other.begin( );
    while( it != other.end( ) ) {
      push_back( *it );
      ++it;
    }