wchash.mh

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

class WCValHashSet : public WCValHashTable<Type> {
private:
    // not necessary for a set, contains and remove can be used instead
    unsigned occurrencesOf( const Type &elem ) const;
    unsigned removeAll( const Type &elem );
public:
    inline WCValHashSet( unsigned (*fn)( const Type & )
                         , unsigned buckets = WC_DEFAULT_HASH_SIZE
                         ) : WCValHashTable( fn, buckets ) {};

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

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

    virtual ~WCValHashSet() {};

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

    inline WCbool insert( const Type & elem ) {
        return( base_set_insert( elem ) != 0 );
    };
};



//
// WCPtrHashSet - hash table for pointers values, values pointed to must
//                be unique
//

template <class Type>
class WCPtrHashSet : public WCPtrHashTable<Type> {
private:
    // not necessary for a set, contains and remove can be used instead
    unsigned occurrencesOf( const Type *elem ) const;
    unsigned removeAll( const Type *elem );

public:
    inline WCPtrHashSet( unsigned (*fn)( const Type & )
                         , unsigned buckets = WC_DEFAULT_HASH_SIZE
                         ) : WCPtrHashTable( fn, buckets ) {};

    inline WCPtrHashSet( unsigned (*fn)( const Type & )
                       , unsigned buckets
                       , void * (*user_alloc)( size_t )
                       , void (*user_dealloc)( void *, size_t )
                       ) : WCPtrHashTable( fn, buckets
                                         , user_alloc, user_dealloc ) {};

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

    virtual ~WCPtrHashSet() {};

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

    inline WCbool insert( Type * elem ) {
        return( base_set_insert( elem ) != 0 );
    };
};




//
// WCValHashDict - hash dictionary for Keys and Values.  Keys must be unique
// Lookup is done using the Key, and both the Key and Value are stored.
// The Key can be viewed as a handle to the Value.
//

template<class Key, class Value>
class WCValHashDict : public WCValHashSet<WCHashDictKeyVal<Key, Value> > {
protected:
    // the type stored by WCValHashSet
    typedef WCHashDictKeyVal<Key, Value> KeyVal;
    // the prototype of the user's hash function
    typedef unsigned (*_HashFnType)( const Key & );
    // the prototype of the hash function stored by WCValHashSet
    typedef unsigned (*_StorageHashFnType)( const KeyVal & );

    // element equivalence definition (used by base classes), two elements
    // are equivalent if their keys are equivalent
    // prototype is really base_equivalent(HashLink *, KeyVal *)
    virtual int base_equivalent( BaseHashLink *elem1, TTypePtr elem2 ) const {
        return( (const Key)( (HashLink *)elem1 )->data.key
                == ( (const KeyVal *)elem2)->key );
    };

    // equivalence definition for hash dictionaries
    virtual int base_dict_equivalent( const Key key1, const Key key2 ) const {
        return( key1 == key2 );
    };

    // find an key-value element with a matching key
    HashLink *base_dict_find( const Key &search
                            , unsigned *bucket, unsigned *index ) const;

    // return the bucket which elem hashes to (used by base classes)
    // parameter is really ( KeyVal * elem )
    virtual unsigned base_get_bucket( TTypePtr elem ) const {
        return( base_get_dict_bucket( ( (const KeyVal *)elem )->key ) );
    }

    // return the bucket which key hashes to
    inline virtual unsigned base_get_dict_bucket( const Key & key ) const {
        return( ((_HashFnType)hash_fn)( key ) % num_buckets );
    }

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

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

    inline WCValHashDict( const WCValHashDict &orig
                ) : WCValHashSet( orig ) {};

    virtual ~WCValHashDict() {};

    inline WCbool contains( const Key & key ) const {
        unsigned bucket, index;
        return( base_dict_find( key, &bucket, &index ) != 0 );
    };

    WCbool find( const Key &search, Value &return_val ) const;

    WCbool findKeyAndValue( const Key &search, Key &ret_key
                          , Value &ret_value ) const;

    void forAll( void (*)(Key, Value, void*), void * ) const;

    WCbool insert( const Key & key, const Value & value ) {
        KeyVal key_and_val( key, value );
        return( WCValHashSet::insert( key_and_val ) );
    }

    WCbool remove( const Key &elem );

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

    Value & operator[]( const Key & key );

    const Value & operator[]( const Key & key ) const;

    friend class WCValHashDictIter;
};


template <class Key, class Value>
WCHashLink<WCHashDictKeyVal<Key, Value> > *WCValHashDict<Key, Value>
                ::base_dict_find( const Key & elem, unsigned *bucket
                           , unsigned *ret_index ) const {
    if( num_buckets == 0 ) {
        return( 0 );
    }
    int index = 0;
    *bucket = base_get_dict_bucket( elem );
    WCIsvSListIter<BaseHashLink> iter( hash_array[ *bucket ] );
    HashLink *link;

    while( ( link = (HashLink *)++iter ) != 0 ) {
        if( base_dict_equivalent( link->data.key, elem ) ) {
            *ret_index = index;
            return( link );
        }
        index++;
    }
    return( 0 );
};


template <class Key, class Value>
WCbool WCValHashDict<Key, Value>::find( const Key &search
                                      , Value &return_val ) const {
    unsigned bucket, index;

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


template <class Key, class Value>
WCbool WCValHashDict<Key, Value>::findKeyAndValue( const Key &search
                              , Key &return_key, Value &return_val ) const {
    unsigned bucket, index;

    HashLink *link = base_dict_find( search, &bucket, &index );
    if( link ) {
        return_key = link->data.key;
        return_val = link->data.value;
        return( TRUE );
    }
    return( FALSE );
};


template <class Key, class Value>
void WCValHashDict<Key, Value>::forAll( register void (*user_fn)(Key, Value
                                                                , 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.key, link->data.value, data );
        }
    }
};


template <class Key, class Value>
WCbool WCValHashDict<Key, Value>::remove( const Key &elem ) {
    unsigned bucket, index;

    if( base_dict_find( elem, &bucket, &index ) ) {
        HashLink *link = (HashLink *)hash_array[ bucket ].get( index );
        WCHashDelete( link );
        num_entries--;
        return( TRUE );
    } else {
        return( FALSE );
    }
};


template <class Key, class Value>
Value & WCValHashDict<Key, Value>::operator[]( const Key & key ) {
    unsigned bucket, index;

    HashLink *link = base_dict_find( key, &bucket, &index );
    if( link != 0 ) {
        return( link->data.value );
    } else {
        KeyVal key_and_val( key );
        link = base_set_insert( key_and_val );
        if( link ) {
            return( link->data.value );
        } else {
            // insert failed because allocation failed and out_of_memory
            // exception disabled
            return( *(Value *)0 );
        }
    }
};



template <class Key, class Value>
const Value & WCValHashDict<Key, Value>::operator[]( const Key & key ) const {
    unsigned bucket, index;

    HashLink *link = base_dict_find( key, &bucket, &index );
    if( link != 0 ) {
        return( link->data.value );
    } else {
        base_throw_index_range();
        // key not found, and index_range is disabled
        return( *( const Value *)0 );
    }
};




//
// WCPtrHashDict - hash dictionary for Keys and Values.  Only the pointers
// to the Keys and Values are copied into the dictionary.  Keys must be unique
// Lookup is done using the Key, and both the Key and Value are stored.
// The Key can be viewed as a handle to the Value.
//
// Implementation note:
// WCPtrHashDict inherits from WCValHashDict templated over <void *, void *>.
// This saves most of the hash dictionary code being generated for pointer
// hash dictionaries templated over different types, speeding up compile time,
// and reducing code size.
//

template<class Key, class Value>
class WCPtrHashDict : public WCValHashDict<void *, void *> {
protected:
    // the real type that is stored in the hash dictionary
    typedef WCHashDictKeyVal<Key *, Value *> KeyVal;
    // all pointers are stored as pointers to void so that all pointer hashes
    // inherit from WCValHashDict templated over <void *, void *>
    typedef WCHashDictKeyVal<void *, void *> StoredKeyVal;
    // the hashing function which the user passes in, and what is called
    typedef unsigned (*_HashFnType)( const Key & );
    // the hashing function is stored by WCValHashDict, and this type
    // matches the type WCValHashDict stores
    typedef unsigned (*_StorageHashFnType)( void * const & );
    // the user function passed to the forAll member function is passed
    // to WCValHashDict<void *, void *>::forAll using this cast
    typedef void (*_ForAllFnCast)( void *, void *, void * );
    typedef Key *Key_Ptr;

    // equivalence definition for pointer hash dictionaries
    // prototype is really base_equivalent(HashLink *, KeyVal *)
    virtual int base_equivalent( BaseHashLink *elem1
                               , TTypePtr elem2 ) const {
        return( *(const Key *)( (HashLink *)elem1 )->data.key
                == *(const Key *)( (KeyVal *)elem2 )->key );
    };

    // find an key-value element with a matching key
    virtual int base_dict_equivalent( void *const key1
                                    , void *const key2 ) const {
        return( *(const Key *)key1 == *(const Key *)key2 );
    };

    // return the bucket which elem hashes to (used by base classes)
    // parameter is really ( KeyVal * elem )
    virtual unsigned base_get_bucket( TTypePtr elem ) const {
        return( base_get_dict_bucket( ( (StoredKeyVal *)elem)->key ) );
    }

    // return the bucket which key hashes to
    inline virtual unsigned base_get_dict_bucket( void * const & key ) const {
        return( ((_HashFnType)hash_fn)( *(Key *)key ) % num_buckets );
    }

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

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

    inline WCPtrHashDict( const WCPtrHashDict &orig
                ) : WCValHashDict( orig ) {};

    virtual ~WCPtrHashDict() {};

    void clearAndDestroy();

    inline WCbool contains( const Key * key ) const {
        return( WCValHashDict::contains( (const Key_Ptr)key ) );
    };

    Value *find( const Key * ) const;

    Value *findKeyAndValue( const Key * search, Key * &ret_key ) const;

    inline void forAll( void (*user_fn)(Key *, Value *, void*)
                      , void *data ) const {
        WCValHashDict::forAll( (_ForAllFnCast)user_fn, data );
    };

    inline WCbool insert( Key * key, Value * value ) {
        return( WCValHashDict::insert( (const Key_Ptr)key
                                     , (Value * const)value ) );
    };

    Value *remove( const Key * key );

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

    inline Value * & operator[]( const Key * key ) {
        return( (Value * &)WCValHashDict::operator[]( (const Key_Ptr)key ) );
    };

    inline Value * const & operator[]( const Key * key ) const {
        return( (Value * const &)WCValHashDict
                                        ::operator[]( (const Key_Ptr)key ) );
    };

};


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


template <class Key, class Value>
Value *WCPtrHashDict<Key, Value>::find( const Key * search ) const {
    unsigned bucket, index;

    HashLink *link = base_dict_find( (const Key_Ptr)search, &bucket, &index );
    if( link ) {
        return( (Value *)link->data.value );
    } else {
        return( 0 );
    }
};


template <class Key, class Value>
Value *WCPtrHashDict<Key, Value>::findKeyAndValue( const Key * search
                                                 , Key * &ret_key ) const {
    unsigned bucket, index;

    HashLink *link = base_dict_find( (const Key_Ptr)search, &bucket, &index );
    if( link ) {
        ret_key = (Key *)link->data.key;
        return( (Value *)link->data.value );
    } else {
        return( 0 );
    }
};


template <class Key, class Value>
Value *WCPtrHashDict<Key, Value>::remove( const Key *elem ) {
    unsigned bucket, index;

    if( base_dict_find( (const Key_Ptr)elem, &bucket, &index ) ) {
        HashLink *link = (HashLink *)hash_array[ bucket ].get( index );
        Value *ret_ptr = (Value *)link->data.value;
        WCHashDelete( link );
        num_entries--;
        return( ret_ptr );
    } else {
        return( 0 );
    }
}

:include redefnew.sp

#endif