wcvbase.mh

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

//
//  wcvbase.h    Definitions for the base classes used by
//               the WATCOM Container Vector Class
//
:keep CPP_HDR
:include crwat.sp
//
#ifndef _WCVBASE_H_INCLUDED
#define _WCVBASE_H_INCLUDED
:include readonly.sp

#ifndef __cplusplus
#error wcvbase.h is for use with C++
#endif

#ifndef _WCEXCEPT_H_INCLUDED
 #include <wcexcept.h>
#endif


// "Warning! W549: 'sizeof' operand contains compiler generated information"
#pragma warning 549 9

:include undefnew.sp

//
//  constants used by vector classes
//

//
//  The default number of elements a vector is created to store.  Specifying
//  the first parameter to the vector constructors will override this value.
//
const size_t WCDEFAULT_VECTOR_LENGTH = 10;

//
//  The default number of elements a vector will grow by when an element is
//  inserted into a full vector (the number of entries in the vector is
//  the same as the vector length).  This growth is performed using the
//  resize member function.
//  This constant applies only ordered and sorted vectors with the
//  resize_required exception disabled.
//  Specifying the second paramter to the ordered and sorted vector
//  constructors will override this value.
//
const size_t WCDEFAULT_VECTOR_RESIZE_GROW = 5;



//
//  Implementation note:
//  From the user's view, all vector elements have been constructed
//  (possibly with only the default constructor).
//
//  In order to avoid any overhead from default intializing and then
//  immediately assigning a value to a vector element, the C-array used
//  to implement arrays is uninitialized (contains raw memory with none
//  of Type's constuctors called) until it needs to be.  This means
//  more efficient copy constucters can be used, and default constuctors
//  do not get called unless they need to.  This is especially helpfull
//  for the resize member function.
//  Initializing previously allocated chunks of memory requires calling the
//  new operator with the allocated memory as a placement syntax parameter.
//  If Type defines an operator new with any parameters, then Type must
//  provide the following operator new for the vector classes:
//  void *operator new( size_t, void *ptr ) { return ptr; }
//  WCValVector and WCPtrVector are implemented so that whenever the user
//  accesses an element which has not been initialized, all uninitalized
//  elements upto and including the accessed element are initialized using
//  Type's default constructor.
//  ordered and sorted vectors do not have this "random access" issue, since
//  the index operator can only index previously initialized elements.  The
//  last element in a vector is copied in using the copy constructor on and
//  each insert, and the last element(s) in a vector is/are destructed after
//  a remove is performed, so that the number of initialized elements in a
//  vector is always equal to the number of entries in the vector.
//




//
//  This class is the base class for all vector container classes.
//  WCExcept provides common exception handling for all vectors.
//
//  It is an abstract base class to prevent objects of this class
//  from being created.
//

template<class Type>
class WCBareVectorBase : public WCExcept {
protected:
    Type *vector;
    int vector_len;
    int num_init;

    // WCValVector, WCPtrVector assignment operator base
    void base_assign( const WCBareVectorBase * );
    // WCValVector, WCPtrVector copy constructor base
    void base_construct( const WCBareVectorBase * );
    int base_index_check( int ) const;
    virtual void base_init_upto( int );
public:
    WCBareVectorBase( size_t length );
    virtual ~WCBareVectorBase() = 0;

    int operator==( const WCBareVectorBase & rhs ) const {
        return( this == &rhs );
    };

    inline void clear() {
        resize( 0 );
    };

    WCbool resize( size_t new_length );
};


template<class Type>
void WCBareVectorBase<Type>::base_assign( const WCBareVectorBase * orig ) {
    if( this != orig ) {
        resize( 0 );
        base_construct( orig );
    }
};


template<class Type>
void WCBareVectorBase<Type>::base_construct( const WCBareVectorBase * orig ) {
    WCExcept::base_construct( orig );
    num_init = orig->num_init;
    vector_len = orig->vector_len;
    if( vector_len > 0 ) {
        // get the raw memory for the vector's C-array
        vector = ( Type * )new char[ sizeof( Type ) * vector_len ];
        if( vector != 0 ) {
            for( int i = 0; i < num_init; i++ ) {
                // Copy all initialized elements from orig to vector, using
                // Type's copy constructor.  The placement parameter is used
                // so that the C-array's raw memory is initialized, instead
                // of allocating a new chunck of memory.
                new( &( vector[ i ] ) ) Type( orig->vector[ i ] );
            }
        } else {
            num_init = 0;
            vector_len = 0;
            base_throw_out_of_memory();
        }
    } else {
        vector = 0;
    }
};


template<class Type>
int WCBareVectorBase<Type>::base_index_check( int index ) const {
    int entry_index = vector_len - 1;
    if( index < 0 || index > entry_index ) {
        base_throw_index_range();
        if( index < 0 ) {
            index = 0;
        } else {
            if( entry_index <= 0 ) {
                index = 0;
            } else {
                index = entry_index;
            }
        }
    }
    return( index );
};


//
//  Initialize all unintialized elements upto and including the index'th
//  element using Type's default constructor.
//

template<class Type>
void WCBareVectorBase<Type>::base_init_upto( int index ) {
    if( index >= num_init ){
        for( int i = num_init; i <= index; i++ ){
            // initialize elements using Type's default constructor.  The
            // placement parameter is used so that the C-array's raw memory
            // is initialized, instead of allocating a new chunck of memory.
            new( &( vector[ i ] ) ) Type();
        }
        num_init = index + 1;
    }
}


template<class Type>
WCBareVectorBase<Type>::WCBareVectorBase( size_t length ){
    vector_len = length;
    num_init = 0;
    if( length > 0 ){
        // get the raw memory for the vector's C-array
        vector = ( Type * )new char[ sizeof( Type ) * length ];
        if( vector == 0 ) {
            vector_len = 0;
        }
    } else {
        vector = 0;
    }
};


template<class Type>
virtual WCBareVectorBase<Type>::~WCBareVectorBase() {
    if( vector ) {
        base_throw_not_empty();
        // call destructors for any initialized elements
        for( int i = 0; i < num_init; i++ ){
            vector[ i ].~Type();
        }
        // delete the C-array (now just raw memory)
        delete [] (char *)vector;
    }
};


template<class Type>
WCbool WCBareVectorBase<Type>::resize( size_t new_length ) {
    Type *new_vector;
    int max_index = num_init < new_length ? num_init : new_length;

    if( new_length > 0 ) {
        // get the raw memory for the vector's C-array
        new_vector = ( Type * )new char[ sizeof( Type ) * new_length ];
        if( new_vector == 0 ){
            base_throw_out_of_memory();
            return( FALSE );
        }
        // Copy all initialized elements from vector (the old C-array) to
        // new_vector (the new C-array), using Type's copy constructor.
        // The placement parameter is used so that the C-array's raw memory
        // is initialized, instead of allocating a new chunck of memory.
        for( int i = 0; i < max_index; i++ ){
            new( &( new_vector[ i ] ) ) Type( vector[ i ] );
        }
    } else {
        new_vector = 0;
    }
    // call destructors for any initialized elements in the old vector
    for( int i = 0; i < num_init; i++ ){
        vector[ i ].~Type();
    }
    // delete the old C-array (now just raw memory)
    delete [] (char *) vector;
    num_init = max_index;
    vector = new_vector;
    vector_len = new_length;
    return( TRUE );
};


//
//  This class is the base class for Ptr and Val OrderedVector and SortedVector
//  container classes.
//
//  It is an abstract base class to prevent objects of this class
//  from being created.
//

template<class Type>
class WCVectorBase : public WCBareVectorBase<Type> {
protected:
    unsigned num_entries;
    unsigned resize_grow;       // the number of elements to grow a vector
                                // when inserting into a full vector

    enum find_type {            // for the base_find function
        find_any,               // find any matching element in the vector
        find_first,             // find first matching element in vector
        next_mult_find,         // find next matching element in vector
        find_for_insert };      // find index to insert element in sorted vector

    // the assignment operator base
    void base_assign( const WCVectorBase * );
    // the copy constructor base
    void base_construct( const WCVectorBase * );
    virtual int base_equivalent( const Type &elem1
                               , const Type &elem2 ) const = 0;
    // find first parm in vector, with specified find_type.  index passes
    // in where to start the search, and returns the index where first param
    // found if returns true
    virtual WCbool base_find( const Type &, find_type, int * index ) const = 0;
    int base_index_check( int ) const;
    WCbool base_insert_at( int, const Type& );
    void base_remove_at( int );

public:
    inline WCVectorBase( size_t length, unsigned grow )
                        : num_entries( 0 ), resize_grow( grow ),
                                WCBareVectorBase<Type>( length ) {};
    inline virtual ~WCVectorBase() = 0;

    inline void clear() {
        WCBareVectorBase::clear();
        num_entries = 0;
    };

    WCbool contains( const Type & ) const;

    inline unsigned entries() const {
        return( num_entries );
    };

    WCbool find( const Type &elem, Type &ret_val ) const;

    inline Type first() const {
        return( vector[ base_index_check( 0 ) ] );
    }

    int index( const Type & ) const;

    inline WCbool isEmpty() const {
        return( num_entries == 0 );
    };

    inline Type last() const {
        return( vector[ base_index_check( num_entries - 1 ) ] );
    }

    int occurrencesOf( const Type & elem ) const;

    WCbool remove( const Type & elem );

    unsigned removeAll( const Type & elem );

    WCbool removeAt( int );

    inline WCbool removeFirst() {
        return( removeAt( 0 ) );
    };

    inline WCbool removeLast() {
        return( removeAt( num_entries - 1 ) );
    };

    WCbool resize( size_t );

    inline Type& operator[] ( int index ) {
        return( vector[ base_index_check( index ) ] );
    };

    inline const Type& operator[] ( int index ) const {
        return( vector[ base_index_check( index ) ] );
    };
};


template<class Type>
void WCVectorBase<Type>::base_assign( const WCVectorBase * orig ) {
    if( this != orig ) {
        resize( 0 );
        base_construct( orig );
    }
};


template<class Type>
void WCVectorBase<Type>::base_construct( const WCVectorBase * orig ) {
    WCBareVectorBase<Type>::base_construct( orig );
    resize_grow = orig->resize_grow;
    if( vector != 0 ) {
        num_entries = orig->num_entries;
    } else {
        num_entries = 0;
    }
}


//
//  Check to see if index is valid, and return the closest valid index.
//  If index is invalid then exceptions are thrown if enabled, and if
//  exceptions are disabled and the vector has no entries, then the first
//  element is default initialized, effectively inserting a first element
//  (this is done for the index operators and first and last member
//  functions)
//
template<class Type>
int WCVectorBase<Type>::base_index_check( int index ) const {
    int entry_index = num_entries - 1;
    if( index < 0 || index > entry_index ) {
        if( num_entries == 0 ) {
            base_throw_empty_container();
            base_throw_index_range();
            // insert the first element as a default intialized element
            WCVectorBase<Type> * const non_const_this
                    = ( WCVectorBase<Type> * )this;
            if( vector_len == 0 ) {
                if( !non_const_this->resize( 1 ) ) {
                    // An invalid operation on an empty vector, and out memory.
                    // return the first element of a NULL C-array.
                    return( 0 );
                }
            }
            non_const_this->base_init_upto( 0 );
            non_const_this->num_entries = 1;
            index = 0;
        } else if( index < 0 ) {
            index = 0;
            base_throw_index_range();
        } else {
            index = entry_index;
            base_throw_index_range();
        }
    }
    return( index );
};


//
//  insert new_entry before the element currently at index.  If index is the
//  number of entries, insert new_entry as the last element.
//

template<class Type>
WCbool WCVectorBase<Type>::base_insert_at( int index, const Type& new_entry ) {
    if( index > (int)num_entries ) {
        base_throw_index_range();
        index = num_entries;
    } else if( index < 0 ) {
        base_throw_index_range();
        index = 0;
    }
    if( num_entries == vector_len ){
        base_throw_resize_required();
        // automatically grow the vector if it was full, the resize_required
        // exception is disabled, and the amount to grow the vector is greater
        // than zero.
        if( ( resize_grow == 0 )
          ||( !resize( vector_len + resize_grow ) ) ) {
            return( FALSE );
        }
    }
    // the last entry in the vector must be copied in, since it was previously
    // unused, and unused elements are unitialized.
    if( index == num_entries ){
        new( &( vector[ index ] ) ) Type( new_entry );
    } else {
        new( &( vector[ num_entries ] ) ) Type( vector[ num_entries - 1 ] );
        for( int i = num_entries - 2; i >= index; i-- ) {
            vector[ i + 1 ] = vector[ i ];
        }
        vector[ index ] = new_entry;
    }
    num_entries++;
    num_init++;
    return( TRUE );
}