//
//  wchash.h    Defines for the WATCOM Container Hash Table Class
//
// =========================================================================
//
//                          Open Watcom Project
//
//    Copyright (c) 2002-2010 Open Watcom Contributors. All Rights Reserved.
//    Portions Copyright (c) 1983-2002 Sybase, Inc. All Rights Reserved.
//
//    This file is automatically generated. Do not edit directly.
//
// =========================================================================
//
#ifndef _WCHASH_H_INCLUDED
#define _WCHASH_H_INCLUDED

#ifndef _ENABLE_AUTODEPEND
 #pragma read_only_file;
#endif

#ifndef __cplusplus
 #error This header file requires 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

#if defined( new ) && defined( _WNEW_OPERATOR )
 #undef new
#endif
#if defined( delete ) && defined( _WDELETE_OPERATOR )
 #undef delete
#endif

//
// 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 );
    };


    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( 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;


    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>
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( 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 );
    }
}

#ifdef _WNEW_OPERATOR
 #define new _WNEW_OPERATOR
#endif
#ifdef _WDELETE_OPERATOR
 #define delete _WDELETE_OPERATOR
#endif

#endif