home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1997 May / Pcwk0597.iso / sybase / starbuck / h.z / WCHASH.H < prev    next >
C/C++ Source or Header  |  1996-07-24  |  30KB  |  923 lines
  1. //
  2. //  wchash.h    Defines for the WATCOM Container Hash Table Class
  3. //
  4. //  Copyright by WATCOM International Corp. 1988-1996.  All rights reserved.
  5. //
  6. #ifndef _WCHASH_H_INCLUDED
  7. #define _WCHASH_H_INCLUDED
  8.  
  9. #ifndef __cplusplus
  10. #error wchash.h is for use with C++
  11. #endif
  12.  
  13. #ifndef _WCDEFS_H_INCLUDED
  14.  #include <wcdefs.h>
  15. #endif
  16. #ifndef _WCEXCEPT_H_INCLUDED
  17.  #include <wcexcept.h>
  18. #endif
  19. #ifndef _WCLIST_H_INCLUDED
  20.  #include <wclist.h>
  21. #endif
  22. #ifndef _WCLISTIT_H_INCLUDED
  23.  #include <wclistit.h>
  24. #endif
  25. #ifndef _WCHBASE_H_INCLUDED
  26.  #include <wchbase.h>
  27. #endif
  28.  
  29.  
  30. #if defined( new ) && defined( _WNEW_OPERATOR )
  31. #  undef new
  32. #endif
  33. #if defined( delete ) && defined( _WDELETE_OPERATOR )
  34. #  undef delete
  35. #endif
  36.  
  37. //
  38. // Macros to allow the user to find the size of objects which will be allocated
  39. // and deallocated using their allocator and deallocator functions
  40. //
  41.  
  42. #define WCValHashTableItemSize( Type )  sizeof( WCHashLink<Type> )
  43. #define WCPtrHashTableItemSize( Type )  sizeof( WCHashLink<Type *> )
  44. #define WCValHashSetItemSize( Type )    sizeof( WCHashLink<Type> )
  45. #define WCPtrHashSetItemSize( Type )    sizeof( WCHashLink<Type *> )
  46. #define WCValHashDictItemSize( Key, Value )     \
  47.                         sizeof( WCHashLink<WCHashDictKeyVal<Key, Value> > )
  48. #define WCPtrHashDictItemSize( Key, Value )     \
  49.                         sizeof( WCHashLink<WCHashDictKeyVal<void *, void *> > )
  50.  
  51.  
  52.  
  53.  
  54. //
  55. // WCValHashTable - hash table for values, values do not need to be unique
  56. //
  57.  
  58. template <class Type>
  59. class WCValHashTable : public WCHashBase {
  60. private:
  61.     void * (* alloc_fn)( size_t );
  62.     void (* dealloc_fn)( void *, size_t );
  63.  
  64. protected:
  65.     typedef WCHashLink<Type> HashLink;
  66.  
  67.     // for PtrHash, hash_fn has the same prototype (ie Type is not really
  68.     // <Type *> but just the Type which the PtrHash is templated over).  This
  69.     // is accomplished by casting and base_get_bucket being virtual.  This
  70.     // way the user can have an identical hash fn for both ValHash and PtrHash.
  71.     unsigned (*hash_fn)( const Type & );
  72.     
  73.     // assignment operator base
  74.     void base_assign( const WCValHashTable * orig );
  75.     // copy constructor base
  76.     void base_construct( const WCValHashTable * orig );
  77.  
  78.     // for WCHashBase::base_construct
  79.     virtual BaseHashLink *base_copy_link( const BaseHashLink *orig ) {
  80.         return( WCHashNew( &( (HashLink *)orig )->data ) );
  81.     };
  82.  
  83.     // defines element equivalence, virtual, since pointer and dictionary
  84.     // hash classes inherit from WCValHashTable, and have different
  85.     // equivalence definitions
  86.     // prototype is really base_equivalent(HashLink *, Type *)
  87.     virtual int base_equivalent( BaseHashLink *elem1
  88.                                , TTypePtr elem2 ) const {
  89.         return( (const Type)( (HashLink *)elem1 )->data
  90.                 == *(const Type *)elem2 );
  91.     };
  92.  
  93.     inline HashLink *base_find( const Type & elem, unsigned *bucket
  94.                                , unsigned *index, find_type type ) const {
  95.         return( (HashLink *)WCHashBase::base_find( &elem, bucket
  96.                                                  , index, type ) );
  97.     };
  98.  
  99.     // return the bucket an element hashes to
  100.     virtual unsigned base_get_bucket_for_link( BaseHashLink *link ) const {
  101.         return( base_get_bucket( &( (HashLink *)link )->data ) );
  102.     };
  103.  
  104.     // parameter is really ( Type * elem )
  105.     virtual unsigned base_get_bucket( TTypePtr elem ) const {
  106.         return( hash_fn( *(const Type *)elem ) % num_buckets );
  107.     }
  108.  
  109.     inline HashLink *base_remove_but_not_delete( const Type & elem ) {
  110.         return( (HashLink *)WCHashBase::base_remove_but_not_delete( &elem ) );
  111.     }
  112.  
  113.     inline HashLink *base_set_insert( const Type & elem ) {
  114.         return( (HashLink *)WCHashBase::base_set_insert( &elem ) );
  115.     };
  116.  
  117.     // similar to new and delete, but these will use user allocator and
  118.     // deallocator functions if they were passed in
  119.     virtual BaseHashLink * WCHashNew( TTypePtr elem );
  120.     virtual void WCHashDelete( BaseHashLink *old_link );
  121. public:
  122.     inline WCValHashTable( unsigned (*fn)( const Type & )
  123.                   , unsigned buckets = WC_DEFAULT_HASH_SIZE 
  124.                   ) : WCHashBase( buckets ), alloc_fn( 0 )
  125.                    , dealloc_fn( 0 ), hash_fn( fn ) {};
  126.  
  127.     inline WCValHashTable( unsigned (*fn)( const Type & )
  128.                   , unsigned buckets 
  129.                   , void * (*user_alloc)( size_t )
  130.                   , void (*user_dealloc)( void *, size_t )
  131.                   ) : WCHashBase( buckets ), alloc_fn( user_alloc )
  132.                     , dealloc_fn( user_dealloc ), hash_fn( fn ) {};
  133.  
  134.     inline WCValHashTable( const WCValHashTable &orig ) {
  135.         if( orig.num_buckets > 0 ) {
  136.             hash_array = new WCIsvSList<BaseHashLink>[ orig.num_buckets ];
  137.         } else {
  138.             hash_array = 0;
  139.         }
  140.         base_construct( &orig );
  141.     };
  142.  
  143.     virtual ~WCValHashTable ();
  144.  
  145.     inline unsigned buckets () const {
  146.         return( num_buckets );
  147.     };
  148.  
  149.     inline void clear () {
  150.         WCHashBase::clear();
  151.     };
  152.  
  153.     inline WCbool contains( const Type & elem ) const {
  154.         unsigned bucket, index;
  155.         return( base_find( elem, &bucket, &index, FIND_FIRST ) != 0 );
  156.     };
  157.  
  158.     inline unsigned entries() const {
  159.         return( num_entries );
  160.     };
  161.  
  162.  
  163.     WCbool find( const Type &search, Type &return_val ) const;
  164.  
  165.     void forAll( void (*)(Type, void*), void * ) const;
  166.  
  167.     inline WCbool insert( const Type & elem ) {
  168.         return( WCHashBase::insert( &elem ) );
  169.     };
  170.  
  171.     inline WCbool isEmpty () const {
  172.         return( 0 == num_entries );
  173.     }
  174.  
  175.     inline unsigned occurrencesOf( const Type &elem ) const {
  176.         return( WCHashBase::occurrencesOf( &elem ) );
  177.     };
  178.  
  179.     WCbool remove( const Type &elem );
  180.  
  181.     inline unsigned removeAll( const Type &elem ) {
  182.         return( WCHashBase::removeAll( &elem ) );
  183.     };
  184.  
  185.     inline void resize( unsigned buckets ) {
  186.         WCHashBase::resize( buckets );
  187.     };
  188.  
  189.     inline WCValHashTable &operator=( const WCValHashTable & orig ) {
  190.         base_assign( &orig );
  191.         return( *this );
  192.     };
  193.  
  194.     inline int operator==( const WCValHashTable &rhs ) const {
  195.         return( this == &rhs );
  196.     };
  197. };
  198.     
  199.  
  200. template <class Type>
  201. void WCValHashTable<Type>::base_assign( const WCValHashTable * orig ) {
  202.     if( this != orig ) {
  203.         clear();
  204.         delete [] hash_array;
  205.         if( orig->num_buckets > 0 ) {
  206.             hash_array = new WCIsvSList<BaseHashLink>[ orig->num_buckets ];
  207.         } else {
  208.             hash_array = 0;
  209.         }
  210.         base_construct( orig );
  211.     }
  212. };
  213.  
  214.  
  215. template <class Type>
  216. void WCValHashTable<Type>::base_construct( const WCValHashTable * orig ) {
  217.     alloc_fn = orig->alloc_fn;
  218.     dealloc_fn = orig->dealloc_fn;
  219.     hash_fn = orig->hash_fn;
  220.     WCHashBase::base_construct( orig );
  221. };
  222.  
  223.  
  224. template <class Type>
  225. WCSLink *WCValHashTable<Type>::WCHashNew( TTypePtr elem ) {
  226.     HashLink *new_link;
  227.  
  228.     if( alloc_fn ) {
  229.         // call the user specified allocator function to get the memory
  230.         new_link = (HashLink *)alloc_fn( sizeof( HashLink ) );
  231.     } else {
  232.         new_link = (HashLink *)new char[ sizeof( HashLink ) ];
  233.     }
  234.     if( new_link ) {
  235.         // use the placement syntax to call WCHashLink's copy constructor
  236.         // with the memory allocated above
  237.         new( new_link ) HashLink( *(const Type *)elem );
  238.     }
  239.     return( new_link );
  240. };
  241.  
  242. template <class Type>
  243. void WCValHashTable<Type>::WCHashDelete( BaseHashLink *old_base_link ) {
  244.     HashLink *old_link = (HashLink *)old_base_link;
  245.  
  246.     if( old_link ) {
  247.         old_link->~HashLink();
  248.         if( dealloc_fn ) {
  249.             // call the user specified deallocator functor to free the memory
  250.             dealloc_fn( old_link, sizeof( HashLink ) );
  251.         } else {
  252.             delete [] (char *)old_link;
  253.         }
  254.     }
  255. };
  256.  
  257. template <class Type>
  258. WCValHashTable<Type>::~WCValHashTable () {
  259.     if( num_entries > 0 ) {
  260.         base_throw_not_empty();
  261.     }
  262.     clear();
  263.     delete [] hash_array;
  264. };
  265.  
  266.  
  267. template <class Type>
  268. WCbool WCValHashTable<Type>::find( const Type &search
  269.                                  , Type &return_val ) const {
  270.     unsigned bucket, index;
  271.     
  272.     HashLink *link = base_find( search, &bucket, &index, FIND_FIRST );
  273.     if( link ) {
  274.         return_val = link->data;
  275.         return( TRUE );
  276.     }
  277.     return( FALSE );
  278. };
  279.  
  280.  
  281. template <class Type>
  282. void WCValHashTable<Type>::forAll( register void (*user_fn)(Type, void*)
  283.                                  , void *data ) const {
  284.     WCIsvSListIter<BaseHashLink> iter;
  285.     HashLink *link;
  286.  
  287.     for( int i = 0; i < num_buckets; i++ ) {
  288.         iter.reset( hash_array[ i ] );
  289.         while( ( link = (HashLink *)++iter ) != 0 ) {
  290.             user_fn( link->data, data );
  291.         }
  292.     }
  293. };
  294.  
  295.  
  296. template <class Type>
  297. WCbool WCValHashTable<Type>::remove( const Type &elem ) {
  298.     HashLink *link = base_remove_but_not_delete( elem );
  299.     if( link ) {
  300.         WCHashDelete( link );
  301.     }
  302.     return( link != 0 );
  303. };
  304.  
  305.  
  306. //
  307. // WCPtrHashTable - hash table for pointers, values pointed to do not need
  308. // to be unique
  309. //
  310. // Implementation note:
  311. // WCPtrHashTable inherits from WCValHashTable templated over <void *>.  This
  312. // saves most of the hash table code being generated for pointer hash tables
  313. // templated over different types, speeding up compile time, and reducing
  314. // code size.
  315. //
  316.  
  317. template <class Type>
  318. class WCPtrHashTable : public WCValHashTable<void *> {
  319. protected:
  320.     // the real type of what is stored in the hash table
  321.     typedef Type * __Type_Ptr;
  322.     // all pointers are stored as pointers to void so that all pointer hashes
  323.     // inherit from WCValHashTable templated over <void *>
  324.     typedef void * __Stored_Ptr;
  325.     // the hashing function which the user passes in, and what is called
  326.     typedef unsigned (*_HashFnType)( const Type & );
  327.     // the hashing function is stored by WCValHashTable, and this type
  328.     // matches the type WCValHashTable stores
  329.     typedef unsigned (*_StorageHashFnType)( const __Stored_Ptr & );
  330.     // the user function passed to the forAll member function is passed
  331.     // to WCValHashTable< void * >::forAll using this cast type
  332.     typedef void (*_ForAllFnCast)( void *, void * );
  333.  
  334.     // equivalence definition for WCPtrHashTable, two pointers are equivalent
  335.     // if the values pointed to are equivalent
  336.     // prototype is really base_equivalent(HashLink *, Type * *)
  337.     virtual int base_equivalent( BaseHashLink *elem1
  338.                                , TTypePtr elem2 ) const {
  339.         return( *(const Type *)( (HashLink *)elem1 )->data
  340.                 == * *(const Type * *)elem2 );
  341.     };
  342.  
  343.     // determine the bucket elem hashes to
  344.     // parameter is really ( Type * * elem )
  345.     virtual unsigned base_get_bucket( TTypePtr elem ) const {
  346.         return( ( (_HashFnType)hash_fn )( * *(Type * *)elem ) % num_buckets );
  347.     }
  348.  
  349. public:
  350.     inline WCPtrHashTable( _HashFnType fn
  351.               , unsigned buckets = WC_DEFAULT_HASH_SIZE
  352.               ) : WCValHashTable( (_StorageHashFnType)fn, buckets ) {};
  353.  
  354.     inline WCPtrHashTable( _HashFnType fn
  355.                   , unsigned buckets 
  356.                   , void * (*user_alloc)( size_t )
  357.                   , void (*user_dealloc)( void *, size_t )
  358.                   ) : WCValHashTable( (_StorageHashFnType)fn, buckets
  359.                                     , user_alloc, user_dealloc ) {};
  360.  
  361.     inline WCPtrHashTable( const WCPtrHashTable &orig )
  362.                 : WCValHashTable( orig.hash_fn, orig.num_buckets ) {
  363.         base_construct( &orig );
  364.     };
  365.  
  366.     virtual ~WCPtrHashTable() {};
  367.  
  368.     void clearAndDestroy();
  369.  
  370.     inline WCbool contains( const Type *elem ) const {
  371.         return( WCValHashTable::contains( (const __Type_Ptr)elem ) );
  372.     };
  373.  
  374.     Type *find( const Type *elem ) const;
  375.  
  376.  
  377.     void forAll( void (*fn)(Type *, void*), void *data ) const {
  378.         WCValHashTable::forAll( (_ForAllFnCast)fn, data );
  379.     };
  380.  
  381.     inline WCbool insert( Type *elem ) {
  382.         return( WCValHashTable::insert( elem ) );
  383.     };
  384.  
  385.     inline unsigned occurrencesOf( const Type *elem ) const {
  386.         return( WCValHashTable::occurrencesOf( (const __Type_Ptr)elem ) );
  387.     };
  388.  
  389.     Type *remove( const Type *elem );
  390.  
  391.     inline unsigned removeAll( const Type *elem ) {
  392.         return( WCValHashTable::removeAll( (const __Type_Ptr)elem ) );
  393.     };
  394.  
  395.     inline WCPtrHashTable &operator=( const WCPtrHashTable & orig ) {
  396.         base_assign( &orig );
  397.         return( *this );
  398.     };
  399. };
  400.     
  401.     
  402. template <class Type>
  403. void WCPtrHashTable<Type>::clearAndDestroy() {
  404.     HashLink *link;
  405.     for( unsigned i = 0; i < buckets(); i++ ) {
  406.         while( ( link = (HashLink *)hash_array[ i ].get() ) != 0 ) {
  407.             delete( (Type *)link->data );
  408.             WCHashDelete( link );
  409.         }
  410.     }
  411.     num_entries = 0;
  412. }
  413.  
  414.  
  415. template <class Type>
  416. Type *WCPtrHashTable<Type>::find( const Type *elem ) const {
  417.     unsigned bucket, index;
  418.     
  419.     HashLink *link = base_find( (const __Type_Ptr)elem
  420.                               , &bucket, &index, FIND_FIRST );
  421.     if( link ) {
  422.         return( (Type *)link->data );
  423.     } else {
  424.         return( 0 );
  425.     }
  426. };
  427.  
  428.  
  429. template <class Type>
  430. Type *WCPtrHashTable<Type>::remove( const Type *elem ) {
  431.     HashLink *link = base_remove_but_not_delete(
  432.                                                 (const __Type_Ptr)elem );
  433.     if( link != 0 ) {
  434.         Type *ret_ptr = (Type *)link->data;
  435.         WCHashDelete( link );
  436.         return( ret_ptr );
  437.     } else {
  438.         return( 0 );
  439.     }
  440. }
  441.  
  442.  
  443.  
  444.  
  445. //
  446. // WCValHashSet - hash table for values, values must be unique
  447. //
  448.  
  449. template <class Type>
  450. class WCValHashSet : public WCValHashTable<Type> {
  451. private:
  452.     // not necessary for a set, contains and remove can be used instead
  453.     unsigned occurrencesOf( const Type &elem ) const;
  454.     unsigned removeAll( const Type &elem );
  455. public:
  456.     inline WCValHashSet( unsigned (*fn)( const Type & )
  457.                          , unsigned buckets = WC_DEFAULT_HASH_SIZE
  458.                          ) : WCValHashTable( fn, buckets ) {};
  459.  
  460.     inline WCValHashSet( unsigned (*fn)( const Type & )
  461.                        , unsigned buckets 
  462.                        , void * (*user_alloc)( size_t )
  463.                        , void (*user_dealloc)( void *, size_t )
  464.                        ) : WCValHashTable( fn, buckets
  465.                                          , user_alloc, user_dealloc ) {};
  466.  
  467.     inline WCValHashSet( const WCValHashSet &orig
  468.                 ) : WCValHashTable( orig.hash_fn, orig.num_buckets ) {
  469.         base_construct( &orig );
  470.     };
  471.  
  472.     virtual ~WCValHashSet() {};
  473.  
  474.     inline WCValHashSet &operator=( const WCValHashSet & orig ) {
  475.         base_assign( &orig );
  476.         return( *this );
  477.     };
  478.  
  479.     inline WCbool insert( const Type & elem ) {
  480.         return( base_set_insert( elem ) != 0 );
  481.     };
  482. };
  483.  
  484.  
  485.  
  486. //
  487. // WCPtrHashSet - hash table for pointers values, values pointed to must
  488. //                be unique
  489. //
  490.  
  491. template <class Type>
  492. class WCPtrHashSet : public WCPtrHashTable<Type> {
  493. private:
  494.     // not necessary for a set, contains and remove can be used instead
  495.     unsigned occurrencesOf( const Type *elem ) const;
  496.     unsigned removeAll( const Type *elem );
  497.     
  498. public:
  499.     inline WCPtrHashSet( unsigned (*fn)( const Type & )
  500.                          , unsigned buckets = WC_DEFAULT_HASH_SIZE
  501.                          ) : WCPtrHashTable( fn, buckets ) {};
  502.  
  503.     inline WCPtrHashSet( unsigned (*fn)( const Type & )
  504.                        , unsigned buckets
  505.                        , void * (*user_alloc)( size_t )
  506.                        , void (*user_dealloc)( void *, size_t )
  507.                        ) : WCPtrHashTable( fn, buckets
  508.                                          , user_alloc, user_dealloc ) {};
  509.  
  510.     inline WCPtrHashSet( const WCPtrHashSet &orig
  511.                 ) : WCPtrHashTable( (_HashFnType)orig.hash_fn
  512.                                   , orig.num_buckets ) {
  513.         base_construct( &orig );
  514.     };
  515.  
  516.     virtual ~WCPtrHashSet() {};
  517.  
  518.     inline WCPtrHashSet &operator=( const WCPtrHashSet & orig ) {
  519.         base_assign( &orig );
  520.         return( *this );
  521.     };
  522.  
  523.     inline WCbool insert( Type * elem ) {
  524.         return( base_set_insert( elem ) != 0 );
  525.     };
  526. };
  527.  
  528.  
  529.  
  530.  
  531. //
  532. // WCValHashDict - hash dictionary for Keys and Values.  Keys must be unique
  533. // Lookup is done using the Key, and both the Key and Value are stored.
  534. // The Key can be viewed as a handle to the Value.
  535. //
  536.  
  537. template<class Key, class Value>
  538. class WCValHashDict : public WCValHashSet<WCHashDictKeyVal<Key, Value> > {
  539. protected:
  540.     // the type stored by WCValHashSet
  541.     typedef WCHashDictKeyVal<Key, Value> KeyVal;
  542.     // the prototype of the user's hash function
  543.     typedef unsigned (*_HashFnType)( const Key & );
  544.     // the prototype of the hash function stored by WCValHashSet
  545.     typedef unsigned (*_StorageHashFnType)( const KeyVal & );
  546.  
  547.     // element equivalence definition (used by base classes), two elements
  548.     // are equivalent if their keys are equivalent
  549.     // prototype is really base_equivalent(HashLink *, KeyVal *)
  550.     virtual int base_equivalent( BaseHashLink *elem1, TTypePtr elem2 ) const {
  551.         return( (const Key)( (HashLink *)elem1 )->data.key
  552.                 == ( (const KeyVal *)elem2)->key );
  553.     };
  554.  
  555.     // equivalence definition for hash dictionaries
  556.     virtual int base_dict_equivalent( const Key key1, const Key key2 ) const {
  557.         return( key1 == key2 );
  558.     };
  559.     
  560.     // find an key-value element with a matching key
  561.     HashLink *base_dict_find( const Key &search
  562.                             , unsigned *bucket, unsigned *index ) const;
  563.                             
  564.     // return the bucket which elem hashes to (used by base classes)
  565.     // parameter is really ( KeyVal * elem )
  566.     virtual unsigned base_get_bucket( TTypePtr elem ) const {
  567.         return( base_get_dict_bucket( ( (const KeyVal *)elem )->key ) );
  568.     }
  569.  
  570.     // return the bucket which key hashes to
  571.     inline virtual unsigned base_get_dict_bucket( const Key & key ) const {
  572.         return( ((_HashFnType)hash_fn)( key ) % num_buckets );
  573.     }
  574.  
  575. public:
  576.     inline WCValHashDict( _HashFnType fn
  577.                         , unsigned buckets = WC_DEFAULT_HASH_SIZE
  578.                         ) : WCValHashSet( (_StorageHashFnType)fn, buckets ) {};
  579.  
  580.     inline WCValHashDict( _HashFnType fn
  581.                         , unsigned buckets 
  582.                         , void * (*user_alloc)( size_t )
  583.                         , void (*user_dealloc)( void *, size_t )
  584.                         ) : WCValHashSet( (_StorageHashFnType)fn, buckets
  585.                                         , user_alloc, user_dealloc ) {};
  586.  
  587.     inline WCValHashDict( const WCValHashDict &orig
  588.                 ) : WCValHashSet( orig ) {};
  589.  
  590.     virtual ~WCValHashDict() {};
  591.  
  592.     inline WCbool contains( const Key & key ) const {
  593.         unsigned bucket, index;
  594.         return( base_dict_find( key, &bucket, &index ) != 0 );
  595.     };
  596.  
  597.     WCbool find( const Key &search, Value &return_val ) const;
  598.  
  599.     WCbool findKeyAndValue( const Key &search, Key &ret_key
  600.                           , Value &ret_value ) const;
  601.  
  602.     void forAll( void (*)(Key, Value, void*), void * ) const;
  603.  
  604.     WCbool insert( const Key & key, const Value & value ) {
  605.         KeyVal key_and_val( key, value );
  606.         return( WCValHashSet::insert( key_and_val ) );
  607.     }
  608.  
  609.     WCbool remove( const Key &elem );
  610.  
  611.     inline WCValHashDict &operator=( const WCValHashDict & orig ) {
  612.         base_assign( &orig );
  613.         return( *this );
  614.     };
  615.  
  616.     Value & operator[]( const Key & key );
  617.  
  618.     const Value & operator[]( const Key & key ) const;
  619.  
  620.     friend class WCValHashDictIter;
  621. };
  622.  
  623.  
  624. template <class Key, class Value>
  625. WCHashLink<WCHashDictKeyVal<Key, Value> > *WCValHashDict<Key, Value>
  626.                 ::base_dict_find( const Key & elem, unsigned *bucket
  627.                            , unsigned *ret_index ) const {
  628.     if( num_buckets == 0 ) {
  629.         return( 0 );
  630.     }
  631.     int index = 0;
  632.     *bucket = base_get_dict_bucket( elem );
  633.     WCIsvSListIter<BaseHashLink> iter( hash_array[ *bucket ] );
  634.     HashLink *link;
  635.  
  636.     while( ( link = (HashLink *)++iter ) != 0 ) {
  637.         if( base_dict_equivalent( link->data.key, elem ) ) {
  638.             *ret_index = index;
  639.             return( link );
  640.         }
  641.         index++;
  642.     }
  643.     return( 0 );
  644. };
  645.  
  646.  
  647. template <class Key, class Value>
  648. WCbool WCValHashDict<Key, Value>::find( const Key &search
  649.                                       , Value &return_val ) const {
  650.     unsigned bucket, index;
  651.     
  652.     HashLink *link = base_dict_find( search, &bucket, &index );
  653.     if( link ) {
  654.         return_val = link->data.value;
  655.         return( TRUE );
  656.     }
  657.     return( FALSE );
  658. };
  659.  
  660.  
  661. template <class Key, class Value>
  662. WCbool WCValHashDict<Key, Value>::findKeyAndValue( const Key &search
  663.                               , Key &return_key, Value &return_val ) const {
  664.     unsigned bucket, index;
  665.     
  666.     HashLink *link = base_dict_find( search, &bucket, &index );
  667.     if( link ) {
  668.         return_key = link->data.key;
  669.         return_val = link->data.value;
  670.         return( TRUE );
  671.     }
  672.     return( FALSE );
  673. };
  674.  
  675.  
  676. template <class Key, class Value>
  677. void WCValHashDict<Key, Value>::forAll( register void (*user_fn)(Key, Value
  678.                                                                 , void*)
  679.                                       , void *data ) const {
  680.     WCIsvSListIter<BaseHashLink> iter;
  681.     HashLink *link;
  682.  
  683.     for( int i = 0; i < num_buckets; i++ ) {
  684.         iter.reset( hash_array[ i ] );
  685.         while( ( link = (HashLink *)++iter ) != 0 ) {
  686.             user_fn( link->data.key, link->data.value, data );
  687.         }
  688.     }
  689. };
  690.  
  691.  
  692. template <class Key, class Value>
  693. WCbool WCValHashDict<Key, Value>::remove( const Key &elem ) {
  694.     unsigned bucket, index;
  695.  
  696.     if( base_dict_find( elem, &bucket, &index ) ) {
  697.         HashLink *link = (HashLink *)hash_array[ bucket ].get( index );
  698.         WCHashDelete( link );
  699.         num_entries--;
  700.         return( TRUE );
  701.     } else {
  702.         return( FALSE );
  703.     }
  704. };
  705.  
  706.  
  707. template <class Key, class Value>
  708. Value & WCValHashDict<Key, Value>::operator[]( const Key & key ) {
  709.     unsigned bucket, index;
  710.     
  711.     HashLink *link = base_dict_find( key, &bucket, &index );
  712.     if( link != 0 ) {
  713.         return( link->data.value );
  714.     } else {
  715.         KeyVal key_and_val( key );
  716.         link = base_set_insert( key_and_val );
  717.         if( link ) {
  718.             return( link->data.value );
  719.         } else {
  720.             // insert failed because allocation failed and out_of_memory
  721.             // exception disabled
  722.             return( *(Value *)0 );
  723.         }
  724.     }
  725. };
  726.     
  727.  
  728.  
  729. template <class Key, class Value>
  730. const Value & WCValHashDict<Key, Value>::operator[]( const Key & key ) const {
  731.     unsigned bucket, index;
  732.  
  733.     HashLink *link = base_dict_find( key, &bucket, &index );
  734.     if( link != 0 ) {
  735.         return( link->data.value );
  736.     } else {
  737.         base_throw_index_range();
  738.         // key not found, and index_range is disabled
  739.         return( *( const Value *)0 );
  740.     }
  741. };
  742.  
  743.  
  744.  
  745.  
  746. //
  747. // WCPtrHashDict - hash dictionary for Keys and Values.  Only the pointers
  748. // to the Keys and Values are copied into the dictionary.  Keys must be unique
  749. // Lookup is done using the Key, and both the Key and Value are stored.
  750. // The Key can be viewed as a handle to the Value.
  751. //
  752. // Implementation note:
  753. // WCPtrHashDict inherits from WCValHashDict templated over <void *, void *>.
  754. // This saves most of the hash dictionary code being generated for pointer
  755. // hash dictionaries templated over different types, speeding up compile time,
  756. // and reducing code size.
  757. //
  758.  
  759. template<class Key, class Value>
  760. class WCPtrHashDict : public WCValHashDict<void *, void *> {
  761. protected:
  762.     // the real type that is stored in the hash dictionary
  763.     typedef WCHashDictKeyVal<Key *, Value *> KeyVal;
  764.     // all pointers are stored as pointers to void so that all pointer hashes
  765.     // inherit from WCValHashDict templated over <void *, void *>
  766.     typedef WCHashDictKeyVal<void *, void *> StoredKeyVal;
  767.     // the hashing function which the user passes in, and what is called
  768.     typedef unsigned (*_HashFnType)( const Key & );
  769.     // the hashing function is stored by WCValHashDict, and this type
  770.     // matches the type WCValHashDict stores
  771.     typedef unsigned (*_StorageHashFnType)( void * const & );
  772.     // the user function passed to the forAll member function is passed
  773.     // to WCValHashDict<void *, void *>::forAll using this cast
  774.     typedef void (*_ForAllFnCast)( void *, void *, void * );
  775.     typedef Key *Key_Ptr;
  776.  
  777.     // equivalence definition for pointer hash dictionaries
  778.     // prototype is really base_equivalent(HashLink *, KeyVal *)
  779.     virtual int base_equivalent( BaseHashLink *elem1
  780.                                , TTypePtr elem2 ) const {
  781.         return( *(const Key *)( (HashLink *)elem1 )->data.key
  782.                 == *(const Key *)( (KeyVal *)elem2 )->key );
  783.     };
  784.  
  785.     // find an key-value element with a matching key
  786.     virtual int base_dict_equivalent( void *const key1
  787.                                     , void *const key2 ) const {
  788.         return( *(const Key *)key1 == *(const Key *)key2 );
  789.     };
  790.  
  791.     // return the bucket which elem hashes to (used by base classes)
  792.     // parameter is really ( KeyVal * elem )
  793.     virtual unsigned base_get_bucket( TTypePtr elem ) const {
  794.         return( base_get_dict_bucket( ( (StoredKeyVal *)elem)->key ) );
  795.     }
  796.  
  797.     // return the bucket which key hashes to
  798.     inline virtual unsigned base_get_dict_bucket( void * const & key ) const {
  799.         return( ((_HashFnType)hash_fn)( *(Key *)key ) % num_buckets );
  800.     }
  801.  
  802. public:
  803.     inline WCPtrHashDict( _HashFnType fn
  804.                         , unsigned buckets = WC_DEFAULT_HASH_SIZE
  805.                         ) : WCValHashDict( (_StorageHashFnType)fn, buckets ) {};
  806.  
  807.     inline WCPtrHashDict( _HashFnType fn
  808.                         , unsigned buckets 
  809.                         , void * (*user_alloc)( size_t )
  810.                         , void (*user_dealloc)( void *, size_t )
  811.                         ) : WCValHashDict( (_StorageHashFnType)fn, buckets
  812.                                          , user_alloc, user_dealloc ) {};
  813.  
  814.     inline WCPtrHashDict( const WCPtrHashDict &orig
  815.                 ) : WCValHashDict( orig ) {};
  816.  
  817.     virtual ~WCPtrHashDict() {};
  818.  
  819.     void clearAndDestroy();
  820.  
  821.     inline WCbool contains( const Key * key ) const {
  822.         return( WCValHashDict::contains( (const Key_Ptr)key ) );
  823.     };
  824.  
  825.     Value *find( const Key * ) const;
  826.  
  827.     Value *findKeyAndValue( const Key * search, Key * &ret_key ) const;
  828.  
  829.     inline void forAll( void (*user_fn)(Key *, Value *, void*)
  830.                       , void *data ) const {
  831.         WCValHashDict::forAll( (_ForAllFnCast)user_fn, data );
  832.     };
  833.  
  834.     inline WCbool insert( Key * key, Value * value ) {
  835.         return( WCValHashDict::insert( (const Key_Ptr)key
  836.                                      , (Value * const)value ) );
  837.     };
  838.  
  839.     Value *remove( const Key * key );
  840.  
  841.     inline WCPtrHashDict &operator=( const WCPtrHashDict & orig ) {
  842.         base_assign( &orig );
  843.         return( *this );
  844.     };
  845.  
  846.     inline Value * & operator[]( const Key * key ) {
  847.         return( (Value * &)WCValHashDict::operator[]( (const Key_Ptr)key ) );
  848.     };
  849.  
  850.     inline Value * const & operator[]( const Key * key ) const {
  851.         return( (Value * const &)WCValHashDict
  852.                                         ::operator[]( (const Key_Ptr)key ) );
  853.     };
  854.  
  855. };
  856.  
  857.  
  858. template <class Key, class Value>
  859. void WCPtrHashDict<Key, Value>::clearAndDestroy() {
  860.     HashLink *link;
  861.     for( unsigned i = 0; i < buckets(); i++ ) {
  862.         while( ( link = (HashLink *)hash_array[ i ].get() ) != 0 ) {
  863.             delete( (Key *)link->data.key );
  864.             delete( (Value *)link->data.value );
  865.             WCHashDelete( link );
  866.         }
  867.     }
  868.     num_entries = 0;
  869. }
  870.  
  871.  
  872. template <class Key, class Value>
  873. Value *WCPtrHashDict<Key, Value>::find( const Key * search ) const {
  874.     unsigned bucket, index;
  875.     
  876.     HashLink *link = base_dict_find( (const Key_Ptr)search, &bucket, &index );
  877.     if( link ) {
  878.         return( (Value *)link->data.value );
  879.     } else {
  880.         return( 0 );
  881.     }
  882. };
  883.  
  884.  
  885. template <class Key, class Value>
  886. Value *WCPtrHashDict<Key, Value>::findKeyAndValue( const Key * search
  887.                                                  , Key * &ret_key ) const {
  888.     unsigned bucket, index;
  889.     
  890.     HashLink *link = base_dict_find( (const Key_Ptr)search, &bucket, &index );
  891.     if( link ) {
  892.         ret_key = (Key *)link->data.key;
  893.         return( (Value *)link->data.value );
  894.     } else {
  895.         return( 0 );
  896.     }
  897. };
  898.  
  899.  
  900. template <class Key, class Value>
  901. Value *WCPtrHashDict<Key, Value>::remove( const Key *elem ) {
  902.     unsigned bucket, index;
  903.  
  904.     if( base_dict_find( (const Key_Ptr)elem, &bucket, &index ) ) {
  905.         HashLink *link = (HashLink *)hash_array[ bucket ].get( index );
  906.         Value *ret_ptr = (Value *)link->data.value;
  907.         WCHashDelete( link );
  908.         num_entries--;
  909.         return( ret_ptr );
  910.     } else {
  911.         return( 0 );
  912.     }
  913. }
  914.  
  915. #if defined( _WNEW_OPERATOR )
  916. #  define new _WNEW_OPERATOR
  917. #endif
  918. #if defined( _WDELETE_OPERATOR )
  919. #  define delete _WDELETE_OPERATOR
  920. #endif
  921.  
  922. #endif
  923.