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