deque.mh

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

        other.buffer + other.head_index,
        other.buffer + other.head_index + part1_size,
        buffer
      );
      part1_done = true;
      if( other.tail_index < other.head_index ) {
        uninitialized_copy(
          other.buffer, other.buffer + other.tail_index, bookmark );
      }
    }
    catch( ... ) {
      if( part1_done ) {
        for( size_type i = 0; i < part1_size; ++i ) {
          mem.destroy( &buffer[i] );
        }
      }
      mem.deallocate( buffer, buf_length );
      throw;
    }
    deq_length = other.deq_length;
    head_index = 0;
    tail_index = other.deq_length;
  }

  // ~deque( )
  // **********
  template< class Type, class Allocator >
  deque< Type, Allocator >::~deque( )
  {
    // Delete objects actually in use and deallocate the buffer.
    pointer p = &buffer[head_index];
    for( size_type i = 0; i < deq_length; ++i ) {
      mem.destroy( p );
      ++p;
      if( p == buffer + buf_length ) p = buffer;
    }
    mem.deallocate( buffer, buf_length );
  }

  // begin( )
  // ********
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::iterator
    deque< Type, Allocator >::begin( )
  {
    return( iterator( this, head_index ) );
  }

  // begin( ) const
  // **************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::const_iterator
    deque< Type, Allocator >::begin( ) const
  {
    return( const_iterator( this, head_index ) );
  }

  // end( )
  // ******
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::iterator
    deque< Type, Allocator >::end( )
  {
    return( iterator( this, tail_index ) );
  }

  // end( ) const
  // ************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::const_iterator
    deque< Type, Allocator >::end( ) const
  {
    return( const_iterator( this, tail_index ) );
  }

  // rbegin( )
  // *********
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::reverse_iterator
    deque< Type, Allocator >::rbegin( )
  {
    return( reverse_iterator( iterator( this, tail_index ) ) );
  }

  // rbegin( ) const
  // ***************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::const_reverse_iterator
    deque< Type, Allocator >::rbegin( ) const
  {
    return( const_reverse_iterator( const_iterator( this, tail_index ) ) );
  }

  // rend( )
  // *******
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::reverse_iterator
    deque< Type, Allocator >::rend( )
  {
    return( reverse_iterator( iterator( this, head_index ) ) );
  }

  // rend( ) const
  // *************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::const_reverse_iterator
    deque< Type, Allocator >::rend( ) const
  {
    return( const_reverse_iterator( const_iterator( this, tail_index ) ) );
  }

  // size( ) const
  // *************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::size_type
    deque< Type, Allocator >::size( ) const
  {
    return( deq_length );
  }

  // max_size( ) const
  // *****************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator>::size_type
    deque< Type, Allocator >::max_size( ) const
  {
    return( std::numeric_limits< size_type >::max( ) / sizeof( Type ) );
  }

  // capacity( ) const
  // *****************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::size_type
    deque< Type, Allocator >::capacity( ) const
  {
    return( buf_length );
  }

  // empty( ) const
  // **************
  template< class Type, class Allocator >
  inline
  bool deque< Type, Allocator >::empty( ) const
  {
    return( deq_length == 0 );
  }

  // reserve( size_type )
  // ********************
  template< class Type, class Allocator >
  void deque< Type, Allocator >::reserve( size_type new_capacity )
  {
    if( new_capacity <= buf_length ) return;
    if( new_capacity > max_size( ) )
      throw length_error( "deque::reserve" );

    size_type temp_length;
    pointer   temp_buffer = alloc( new_capacity, temp_length );
    bool      part1_done  = false;
    size_type part1_size  =
      ( ( tail_index >= head_index ) ? tail_index : buf_length ) - head_index;
    try {
      pointer bookmark = uninitialized_copy(
        buffer + head_index,
        buffer + head_index + part1_size,
        temp_buffer
      );
      part1_done = true;
      if( tail_index < head_index ) {
        uninitialized_copy( buffer, buffer + tail_index, bookmark );
      }
    }
    catch( ... ) {
      if( part1_done ) {
        for( size_type i = 0; i < part1_size; ++i ) {
          mem.destroy( &temp_buffer[i] );
        }
      }
      mem.deallocate( temp_buffer, temp_length );
      throw;
    }

    // New allocation was successful.
    for( size_type i = 0; i < deq_length; ++i ) {
      mem.destroy( &buffer[head_index] );
      ++head_index;
      if( head_index == buf_length ) head_index = 0;
    }
    mem.deallocate( buffer, buf_length );

    buffer     = temp_buffer;
    buf_length = temp_length;
    head_index = 0;
    tail_index = deq_length;
  }

  // operator[]( size_type )
  // ***********************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::reference
    deque< Type, Allocator >::operator[]( size_type n )
  {
    size_type first_length = buf_length - head_index;

    if( n < first_length )
      return( buffer[head_index + n] );
    else
      return( buffer[n - first_length] );
  }

  // operator[]( size_type ) const
  // *****************************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::const_reference
    deque< Type, Allocator >::operator[]( size_type n ) const
  {
    size_type first_length = buf_length - head_index;

    if( n < first_length )
      return( buffer[head_index + n] );
    else
      return( buffer[n - first_length] );
  }

  // at( size_type )
  // ***************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::reference
    deque< Type, Allocator >::at( size_type n )
  {
    if( n >= deq_length )
      throw out_of_range( "deque::at" );
    return( ( *this )[n] );
  }

  // at( size_type ) const
  // *********************
  template< class Type, class Allocator >
  typename deque< Type, Allocator >::const_reference
    deque< Type, Allocator >::at( size_type n ) const
  {
    if( n >= deq_length )
      throw out_of_range( "deque::at" );
    return( ( *this )[n] );
  }

  // front( )
  // ********
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::reference
    deque< Type, Allocator >::front( )
  {
    return( buffer[head_index] );
  }

  // front( ) const
  // **************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::const_reference
    deque< Type, Allocator >::front( ) const
  {
    return( buffer[head_index] );
  }

  // back( )
  // *******
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::reference
    deque< Type, Allocator >::back( )
  {
    if( tail_index == 0 )
      return( buffer[buf_length - 1] );
    else
      return( buffer[tail_index - 1] );
  }

  // back( ) const
  // *************
  template< class Type, class Allocator >
  inline
  typename deque< Type, Allocator >::const_reference
    deque< Type, Allocator >::back( ) const
  {
    if( tail_index == 0 )
      return( buffer[buf_length - 1] );
    else
      return( buffer[tail_index - 1] );
  }

  // push_front( )
  // *************
  template< class Type, class Allocator >
  void deque< Type, Allocator >::push_front( const Type &item )
  {
    if( deq_length + 2 > buf_length ) {
      reserve( buf_length + 1 );
    }
    size_type temp_index =   // For exception safety.
      (head_index == 0) ? buf_length - 1 : head_index - 1;
    new ( static_cast<void *>( buffer + temp_index ) ) Type( item );
    head_index = temp_index;
    ++deq_length;
  }

  // push_back( )
  template< class Type, class Allocator >
  void deque< Type, Allocator >::push_back( const Type &item )
  {
    if( deq_length + 2 > buf_length ) {
      reserve( buf_length + 1 );
    }
    new ( static_cast<void *>( buffer + tail_index ) ) Type( item );
    tail_index =
      ( tail_index == buf_length - 1 ) ? tail_index = 0 : tail_index + 1;
    ++deq_length;
  }

  // pop_front( )
  // ************
  template< class Type, class Allocator >
  inline
  void deque< Type, Allocator >::pop_front( )
  {
    mem.destroy( &buffer[head_index] );
    ++head_index;
    if( head_index == buf_length ) head_index = 0;
    --deq_length;
  }

  // pop_back( )
  // ***********
  template< class Type, class Allocator >
  void deque< Type, Allocator >::pop_back( )
  {
    if( tail_index == 0 ) {
      mem.destroy( &buffer[buf_length - 1] );
      tail_index = buf_length - 1;
    }
    else {
      mem.destroy( &buffer[tail_index - 1] );
      --tail_index;
    }
    --deq_length;
  }

  // _Sane( ) const
  // **************
  template< class Type, class Allocator >
  bool deque< Type, Allocator >::_Sane( ) const
  {
    if( buf_length == 0 ) return( false );
    if( buf_length <= deq_length ) return( false );

    // Is buf_length a power of 2?
    size_type temp = buf_length;
    while( temp != 1 ) {
      if( temp & 0x1 ) return( false );
      temp >>= 1; 
    }

    // Check the head and tail indicies.
    if( head_index >= buf_length || tail_index >= buf_length ) return( false );
    if( head_index == tail_index &&
        !( deq_length == 0 || deq_length == buf_length ) ) return( false );
    if( tail_index > head_index &&
        deq_length != ( tail_index - head_index ) ) return( false );
    if( tail_index < head_index &&
        deq_length != ( tail_index + ( buf_length - head_index ) ) ) return( false );
    return( true );
  }

  // ==============================
  // Ordinary functions using deque
  // ==============================

  // NOTE: The implementation of operator== and operator< is probably
  // the same for all three sequence containers. Should this be a helper
  // template parameterized by container type? (Probably)

  // operator==( const deque &, const deque & )
  // ******************************************
  template< class Type, class Allocator >
  bool operator==( const deque< Type, Allocator > &x,
                   const deque< Type, Allocator > &y )
  {
    if( x.size( ) != y.size( ) ) return( false );

    deque< Type, Allocator>::size_type index = 0;
    while( index < x.size( ) ) {
      if( x[index] != y[index] ) return( false );
      ++index;
    }
    return( true );
  }

  // operator<( const deque &, const deque & )
  // *****************************************
  template< class Type, class Allocator >
  bool operator< ( const deque< Type, Allocator > &x,
                   const deque< Type, Allocator > &y )
  {
    deque< Type, Allocator>::size_type index = 0;
    while( index != x.size( ) && index != y.size( ) ) {
      if( x[index] < y[index] ) return( true );
      if( y[index] < x[index] ) return( false );
      ++index;
    }
    return( index == x.size( ) && index != y.size( ) );
  }

  // operator!=( const deque &, const deque & )
  // ******************************************
  template< class Type, class Allocator >
  inline
  bool operator!=( const deque< Type, Allocator > &x,
                   const deque< Type, Allocator > &y )
  {
    return( !( x == y ) );
  }

  // operator>( const deque &, const deque & )
  // *****************************************
  template< class Type, class Allocator >
  inline
  bool operator> ( const deque< Type, Allocator > &x,
                   const deque< Type, Allocator > &y )
  {
    return( y < x );
  }

  // operator>=( const deque &, const deque & )
  // ******************************************
  template< class Type, class Allocator >
  inline
  bool operator>=( const deque< Type, Allocator > &x,
                   const deque< Type, Allocator > &y )
  {
    return( !( x < y ) );
  }

  // operator<=( const deque &, const deque & )
  // ******************************************
  template< class Type, class Allocator >
  inline
  bool operator<=( const deque< Type, Allocator > &x,
                   const deque< Type, Allocator > &y )
  {
    return( !( x > y ) );
  }

:: Deque swap ambiguous if general swap (in algorithm) visible.
:: Need partial ordering of function templates for this to work.
  #ifdef __NEVER
  // swap( deque &, deque & )
  // **************************
  template< class Type, class Allocator >
  inline
  void swap( deque< Type, Allocator > &x, deque< Type, Allocator > &y )
  {
    x.swap( y );
  }
  #endif

} // End of namespace std.

#endif