wchash.mh

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

//
//  wchash.h    Defines for the WATCOM Container Hash Table Class
//
:keep CPP_HDR
:include crwat.sp
//
#ifndef _WCHASH_H_INCLUDED
#define _WCHASH_H_INCLUDED
:include readonly.sp

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

#ifndef _WCDEFS_H_INCLUDED
 #include <wcdefs.h>
#endif
#ifndef _WCEXCEPT_H_INCLUDED
 #include <wcexcept.h>
#endif
#ifndef _WCLIST_H_INCLUDED
 #include <wclist.h>
#endif
#ifndef _WCLISTIT_H_INCLUDED
 #include <wclistit.h>
#endif
#ifndef _WCHBASE_H_INCLUDED
 #include <wchbase.h>
#endif


:include undefnew.sp

//
// Macros to allow the user to find the size of objects which will be allocated
// and deallocated using their allocator and deallocator functions
//

#define WCValHashTableItemSize( Type )  sizeof( WCHashLink<Type> )
#define WCPtrHashTableItemSize( Type )  sizeof( WCHashLink<Type *> )
#define WCValHashSetItemSize( Type )    sizeof( WCHashLink<Type> )
#define WCPtrHashSetItemSize( Type )    sizeof( WCHashLink<Type *> )
#define WCValHashDictItemSize( Key, Value )     \
                        sizeof( WCHashLink<WCHashDictKeyVal<Key, Value> > )
#define WCPtrHashDictItemSize( Key, Value )     \
                        sizeof( WCHashLink<WCHashDictKeyVal<void *, void *> > )




//
// WCValHashTable - hash table for values, values do not need to be unique
//

template <class Type>
class WCValHashTable : public WCHashBase {
private:
    void * (* alloc_fn)( size_t );
    void (* dealloc_fn)( void *, size_t );

protected:
    typedef WCHashLink<Type> HashLink;

    // for PtrHash, hash_fn has the same prototype (ie Type is not really
    // <Type *> but just the Type which the PtrHash is templated over).  This
    // is accomplished by casting and base_get_bucket being virtual.  This
    // way the user can have an identical hash fn for both ValHash and PtrHash.
    unsigned (*hash_fn)( const Type & );

    // assignment operator base
    void base_assign( const WCValHashTable * orig );
    // copy constructor base
    void base_construct( const WCValHashTable * orig );

    // for WCHashBase::base_construct
    virtual BaseHashLink *base_copy_link( const BaseHashLink *orig ) {
        return( WCHashNew( &( (HashLink *)orig )->data ) );
    };

    // defines element equivalence, virtual, since pointer and dictionary
    // hash classes inherit from WCValHashTable, and have different
    // equivalence definitions
    // prototype is really base_equivalent(HashLink *, Type *)
    virtual int base_equivalent( BaseHashLink *elem1
                               , TTypePtr elem2 ) const {
        return( (const Type)( (HashLink *)elem1 )->data
                == *(const Type *)elem2 );
    };

    inline HashLink *base_find( const Type & elem, unsigned *bucket
                               , unsigned *index, find_type type ) const {
        return( (HashLink *)WCHashBase::base_find( &elem, bucket
                                                 , index, type ) );
    };

    // return the bucket an element hashes to
    virtual unsigned base_get_bucket_for_link( BaseHashLink *link ) const {
        return( base_get_bucket( &( (HashLink *)link )->data ) );
    };

    // parameter is really ( Type * elem )
    virtual unsigned base_get_bucket( TTypePtr elem ) const {
        return( hash_fn( *(const Type *)elem ) % num_buckets );
    }

    inline HashLink *base_remove_but_not_delete( const Type & elem ) {
        return( (HashLink *)WCHashBase::base_remove_but_not_delete( &elem ) );
    }

    inline HashLink *base_set_insert( const Type & elem ) {
        return( (HashLink *)WCHashBase::base_set_insert( &elem ) );
    };

    // similar to new and delete, but these will use user allocator and
    // deallocator functions if they were passed in
    virtual BaseHashLink * WCHashNew( TTypePtr elem );
    virtual void WCHashDelete( BaseHashLink *old_link );
public:
    inline WCValHashTable( unsigned (*fn)( const Type & )
                  , unsigned buckets = WC_DEFAULT_HASH_SIZE
                  ) : WCHashBase( buckets ), alloc_fn( 0 )
                   , dealloc_fn( 0 ), hash_fn( fn ) {};

    inline WCValHashTable( unsigned (*fn)( const Type & )
                  , unsigned buckets
                  , void * (*user_alloc)( size_t )
                  , void (*user_dealloc)( void *, size_t )
                  ) : WCHashBase( buckets ), alloc_fn( user_alloc )
                    , dealloc_fn( user_dealloc ), hash_fn( fn ) {};

    inline WCValHashTable( const WCValHashTable &orig ) {
        if( orig.num_buckets > 0 ) {
            hash_array = new WCIsvSList<BaseHashLink>[ orig.num_buckets ];
        } else {
            hash_array = 0;
        }
        base_construct( &orig );
    };

    virtual ~WCValHashTable ();

    inline unsigned buckets () const {
        return( num_buckets );
    };

    inline void clear () {
        WCHashBase::clear();
    };

    inline WCbool contains( const Type & elem ) const {
        unsigned bucket, index;
        return( base_find( elem, &bucket, &index, FIND_FIRST ) != 0 );
    };

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

:segment CONT_CL_TEST
#if 1
// ******************************** for testing only!!
    void forAllPrintingBucket( void (*fn)(Type, void*), void *d ) {
        WCIsvSListIter<BaseHashLink> iter;
        for( int i = 0; i < num_buckets; i++ ) {
            cout << "\n***Bucket " << i << ": ";
            iter.reset( hash_array[ i ] );
            HashLink *link;
            while( ( link = (HashLink *)++iter ) != 0 ) {
                fn( link->data, d );
            }
        }
    };
#endif
:endsegment

    WCbool find( const Type &search, Type &return_val ) const;

    void forAll( void (*)(Type, void*), void * ) const;

    inline WCbool insert( const Type & elem ) {
        return( WCHashBase::insert( &elem ) );
    };

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

    inline unsigned occurrencesOf( const Type &elem ) const {
        return( WCHashBase::occurrencesOf( &elem ) );
    };

    WCbool remove( const Type &elem );

    inline unsigned removeAll( const Type &elem ) {
        return( WCHashBase::removeAll( &elem ) );
    };

    inline void resize( unsigned buckets ) {
        WCHashBase::resize( buckets );
    };

    inline WCValHashTable &operator=( const WCValHashTable & orig ) {
        base_assign( &orig );
        return( *this );
    };

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


template <class Type>
void WCValHashTable<Type>::base_assign( const WCValHashTable * orig ) {
    if( this != orig ) {
        clear();
        delete [] hash_array;
        if( orig->num_buckets > 0 ) {
            hash_array = new WCIsvSList<BaseHashLink>[ orig->num_buckets ];
        } else {
            hash_array = 0;
        }
        base_construct( orig );
    }
};


template <class Type>
void WCValHashTable<Type>::base_construct( const WCValHashTable * orig ) {
    alloc_fn = orig->alloc_fn;
    dealloc_fn = orig->dealloc_fn;
    hash_fn = orig->hash_fn;
    WCHashBase::base_construct( orig );
};


template <class Type>
WCSLink *WCValHashTable<Type>::WCHashNew( TTypePtr elem ) {
    HashLink *new_link;

    if( alloc_fn ) {
        // call the user specified allocator function to get the memory
        new_link = (HashLink *)alloc_fn( sizeof( HashLink ) );
    } else {
        new_link = (HashLink *)new char[ sizeof( HashLink ) ];
    }
    if( new_link ) {
        // use the placement syntax to call WCHashLink's copy constructor
        // with the memory allocated above
        new( new_link ) HashLink( *(const Type *)elem );
    }
    return( new_link );
};

template <class Type>
void WCValHashTable<Type>::WCHashDelete( BaseHashLink *old_base_link ) {
    HashLink *old_link = (HashLink *)old_base_link;

    if( old_link ) {
        old_link->~HashLink();
        if( dealloc_fn ) {
            // call the user specified deallocator functor to free the memory
            dealloc_fn( old_link, sizeof( HashLink ) );
        } else {
            delete [] (char *)old_link;
        }
    }
};

template <class Type>
WCValHashTable<Type>::~WCValHashTable () {
    if( num_entries > 0 ) {
        base_throw_not_empty();
    }
    clear();
    delete [] hash_array;
};


template <class Type>
WCbool WCValHashTable<Type>::find( const Type &search
                                 , Type &return_val ) const {
    unsigned bucket, index;

    HashLink *link = base_find( search, &bucket, &index, FIND_FIRST );
    if( link ) {
        return_val = link->data;
        return( TRUE );
    }
    return( FALSE );
};


template <class Type>
void WCValHashTable<Type>::forAll( register void (*user_fn)(Type, void*)
                                 , void *data ) const {
    WCIsvSListIter<BaseHashLink> iter;
    HashLink *link;

    for( int i = 0; i < num_buckets; i++ ) {
        iter.reset( hash_array[ i ] );
        while( ( link = (HashLink *)++iter ) != 0 ) {
            user_fn( link->data, data );
        }
    }
};


template <class Type>
WCbool WCValHashTable<Type>::remove( const Type &elem ) {
    HashLink *link = base_remove_but_not_delete( elem );
    if( link ) {
        WCHashDelete( link );
    }
    return( link != 0 );
};


//
// WCPtrHashTable - hash table for pointers, values pointed to do not need
// to be unique
//
// Implementation note:
// WCPtrHashTable inherits from WCValHashTable templated over <void *>.  This
// saves most of the hash table code being generated for pointer hash tables
// templated over different types, speeding up compile time, and reducing
// code size.
//

template <class Type>
class WCPtrHashTable : public WCValHashTable<void *> {
protected:
    // the real type of what is stored in the hash table
    typedef Type * __Type_Ptr;
    // all pointers are stored as pointers to void so that all pointer hashes
    // inherit from WCValHashTable templated over <void *>
    typedef void * __Stored_Ptr;
    // the hashing function which the user passes in, and what is called
    typedef unsigned (*_HashFnType)( const Type & );
    // the hashing function is stored by WCValHashTable, and this type
    // matches the type WCValHashTable stores
    typedef unsigned (*_StorageHashFnType)( const __Stored_Ptr & );
    // the user function passed to the forAll member function is passed
    // to WCValHashTable< void * >::forAll using this cast type
    typedef void (*_ForAllFnCast)( void *, void * );

    // equivalence definition for WCPtrHashTable, two pointers are equivalent
    // if the values pointed to are equivalent
    // prototype is really base_equivalent(HashLink *, Type * *)
    virtual int base_equivalent( BaseHashLink *elem1
                               , TTypePtr elem2 ) const {
        return( *(const Type *)( (HashLink *)elem1 )->data
                == * *(const Type * *)elem2 );
    };

    // determine the bucket elem hashes to
    // parameter is really ( Type * * elem )
    virtual unsigned base_get_bucket( TTypePtr elem ) const {
        return( ( (_HashFnType)hash_fn )( * *(Type * *)elem ) % num_buckets );
    }

public:
    inline WCPtrHashTable( _HashFnType fn
              , unsigned buckets = WC_DEFAULT_HASH_SIZE
              ) : WCValHashTable( (_StorageHashFnType)fn, buckets ) {};

    inline WCPtrHashTable( _HashFnType fn
                  , unsigned buckets
                  , void * (*user_alloc)( size_t )
                  , void (*user_dealloc)( void *, size_t )
                  ) : WCValHashTable( (_StorageHashFnType)fn, buckets
                                    , user_alloc, user_dealloc ) {};

    inline WCPtrHashTable( const WCPtrHashTable &orig )
                : WCValHashTable( orig.hash_fn, orig.num_buckets ) {
        base_construct( &orig );
    };

    virtual ~WCPtrHashTable() {};

    void clearAndDestroy();

    inline WCbool contains( const Type *elem ) const {
        return( WCValHashTable::contains( (const __Type_Ptr)elem ) );
    };

    Type *find( const Type *elem ) const;

:segment CONT_CL_TEST
#if 1
// ******************************** for testing only!!
    void forAllPrintingBucket( void (*fn)(Type *, void*), void *d ) {
        WCValHashTable::forAllPrintingBucket( (_ForAllFnCast)fn, d );
    };
#endif
:endsegment

    void forAll( void (*fn)(Type *, void*), void *data ) const {
        WCValHashTable::forAll( (_ForAllFnCast)fn, data );
    };

    inline WCbool insert( Type *elem ) {
        return( WCValHashTable::insert( elem ) );
    };

    inline unsigned occurrencesOf( const Type *elem ) const {
        return( WCValHashTable::occurrencesOf( (const __Type_Ptr)elem ) );
    };

    Type *remove( const Type *elem );

    inline unsigned removeAll( const Type *elem ) {
        return( WCValHashTable::removeAll( (const __Type_Ptr)elem ) );
    };

    inline WCPtrHashTable &operator=( const WCPtrHashTable & orig ) {
        base_assign( &orig );
        return( *this );
    };
};


template <class Type>
void WCPtrHashTable<Type>::clearAndDestroy() {
    HashLink *link;
    for( unsigned i = 0; i < buckets(); i++ ) {
        while( ( link = (HashLink *)hash_array[ i ].get() ) != 0 ) {
            delete( (Type *)link->data );
            WCHashDelete( link );
        }
    }
    num_entries = 0;
}


template <class Type>
Type *WCPtrHashTable<Type>::find( const Type *elem ) const {
    unsigned bucket, index;

    HashLink *link = base_find( (const __Type_Ptr)elem
                              , &bucket, &index, FIND_FIRST );
    if( link ) {
        return( (Type *)link->data );
    } else {
        return( 0 );
    }
};


template <class Type>
Type *WCPtrHashTable<Type>::remove( const Type *elem ) {
    HashLink *link = base_remove_but_not_delete(
                                                (const __Type_Ptr)elem );
    if( link != 0 ) {
        Type *ret_ptr = (Type *)link->data;
        WCHashDelete( link );
        return( ret_ptr );
    } else {
        return( 0 );
    }
}




//
// WCValHashSet - hash table for values, values must be unique
//

template <class Type>