home *** CD-ROM | disk | FTP | other *** search
/ PC World Komputer 1998 May / Pcwk5b98.iso / Borland / Cplus45 / BC45 / CLASSINC.PAK / HASHIMP.H < prev    next >
C/C++ Source or Header  |  1995-08-29  |  18KB  |  594 lines
  1. /*------------------------------------------------------------------------*/
  2. /*                                                                        */
  3. /*  HASHIMP.H                                                             */
  4. /*                                                                        */
  5. /*  Copyright (c) 1991, 1994 Borland International                        */
  6. /*  All Rights Reserved                                                   */
  7. /*                                                                        */
  8. /*  Note: Hash tables can determine the hash value of an object by        */
  9. /*  calling a member function or global function named HashValue().       */
  10. /*                                                                        */
  11. /*  For member functions, the following prototype should be used:         */
  12. /*                                                                        */
  13. /*      unsigned HashValue() const;                                       */
  14. /*                                                                        */
  15. /*  For global functions, then following prototype should be used:        */
  16. /*                                                                        */
  17. /*      unsigned HashValue( const T& t );                                 */
  18. /*                                                                        */
  19. /*  If the global function is used, the member function does not need to  */
  20. /*  be defined.                                                           */
  21. /*                                                                        */
  22. /*------------------------------------------------------------------------*/
  23.  
  24. #if !defined( CLASSLIB_HASHIMP_H )
  25. #define CLASSLIB_HASHIMP_H
  26.  
  27. #if !defined( __CHECKS_H )
  28. #include <checks.h>
  29. #endif
  30.  
  31. #if !defined( CLASSLIB_DEFS_H )
  32. #include <classlib/defs.h>
  33. #endif
  34.  
  35. #if !defined( CLASSLIB_LISTIMP_H )
  36. #include <classlib/listimp.h>
  37. #endif
  38.  
  39. #if !defined( CLASSLIB_VECTIMP_H )
  40. #include <classlib/vectimp.h>
  41. #endif
  42.  
  43. #pragma option -Vo-
  44. #if defined( BI_CLASSLIB_NO_po )
  45. #pragma option -po-
  46. #endif
  47.  
  48. /*------------------------------------------------------------------------*/
  49. /*                                                                        */
  50. /*  template <class T> unsigned HashValue( T & t )                        */
  51. /*                     unsigned HashValue( void *& )                      */
  52. /*                                                                        */
  53. /*  Template function which calls the HashValue() member function for     */
  54. /*  an object of type T.  The (void *) non-template function is           */
  55. /*  defined so that indirect container templates will compile. It         */
  56. /*  should never be called.                                               */
  57. /*                                                                        */
  58. /*------------------------------------------------------------------------*/
  59.  
  60. inline unsigned HashValue( void *& t )
  61. {
  62.     return unsigned(t);
  63. }
  64.  
  65. inline unsigned HashValue( const TVoidPointer& t )
  66. {
  67.     return unsigned(STATIC_CAST(void *,t));
  68. }
  69.  
  70. template <class T> unsigned HashValue( const T& t )
  71. {
  72.     return t.HashValue();
  73. }
  74.  
  75. /*------------------------------------------------------------------------*/
  76. /*                                                                        */
  77. /*  template <class T,class Alloc,class List> class TMInternalHashImp     */
  78. /*                                                                        */
  79. /*  Used internally.                                                      */
  80. /*                                                                        */
  81. /*------------------------------------------------------------------------*/
  82.  
  83. template <class T,class Alloc,class List>
  84.     class TMInternalHashTableIteratorImp;
  85.  
  86. template <class T,class Alloc,class List> class TMInternalHashImp :
  87.     public Alloc
  88. {
  89.  
  90. public:
  91.  
  92.     friend TMInternalHashTableIteratorImp<T,Alloc,List>;
  93.  
  94.     TMInternalHashImp( unsigned size ) :
  95.         Table(size),
  96.         Size(size),
  97.         ItemsInContainer(0)
  98.         {
  99.         }
  100.  
  101.     unsigned GetItemsInContainer() const
  102.         {
  103.         return ItemsInContainer;
  104.         }
  105.  
  106.     int IsEmpty() const
  107.         {
  108.         return ItemsInContainer == 0;
  109.         }
  110.  
  111. protected:
  112.  
  113.     unsigned TableSize() const
  114.         {
  115.         return Size;
  116.         }
  117.  
  118.     unsigned ItemsInContainer;
  119.     TMIVectorImp<List,Alloc> Table;
  120.  
  121. private:
  122.  
  123.     virtual unsigned GetHashValue( const T& t ) const = 0;
  124.  
  125.     unsigned Size;
  126.  
  127. };
  128.  
  129. /*------------------------------------------------------------------------*/
  130. /*                                                                        */
  131. /*  template <class T,class Alloc,class List>                             */
  132. /*      class TMInternalHashTableIteratorImp                              */
  133. /*                                                                        */
  134. /*  Used internally.                                                      */
  135. /*                                                                        */
  136. /*------------------------------------------------------------------------*/
  137.  
  138. template <class T,class Alloc,class List>
  139. class TMInternalHashTableIteratorImp :
  140.     public Alloc
  141. {
  142.  
  143. public:
  144.  
  145.     TMInternalHashTableIteratorImp( const TMInternalHashImp<T,Alloc,List>& h ) :
  146.         HashIter(h.Table),
  147.         ListIter(0)
  148.         {
  149.         Restart();
  150.         }
  151.         
  152.     ~TMInternalHashTableIteratorImp()
  153.         {
  154.         delete ListIter;
  155.         }
  156.         
  157.     operator int()
  158.         {
  159.         return HashIter;
  160.         }
  161.         
  162.     const T& Current()
  163.         {
  164.         PRECONDITION( ListIter != 0 );
  165.         return ListIter->Current();
  166.         }
  167.         
  168.     const T& operator ++ ( int )
  169.         {
  170.         PRECONDITION( ListIter != 0 );
  171.         const T& t = ListIter->Current();
  172.         Scan();
  173.         return t;
  174.         }
  175.         
  176.     const T& operator ++ ()
  177.         {
  178.         PRECONDITION( ListIter != 0 );
  179.         Scan();
  180.         PRECONDITION( ListIter != 0 );
  181.         return ListIter->Current();
  182.         }
  183.         
  184.     void Restart();
  185.         
  186. private:
  187.  
  188.     TMIVectorIteratorImp<List,Alloc> HashIter;
  189.     TMListIteratorImp<T,Alloc> *ListIter;
  190.     
  191.     void Scan();
  192. };
  193.  
  194. template <class T,class Alloc,class List>
  195. void TMInternalHashTableIteratorImp<T,Alloc,List>::Restart()
  196. {
  197.     HashIter.Restart();
  198.         
  199.     delete ListIter;
  200.     while( HashIter && HashIter.Current() == 0 )
  201.         HashIter++;
  202.     ListIter = HashIter ?
  203.         new(*this)TMListIteratorImp<T,Alloc>( *HashIter.Current() ) : 0;
  204. }
  205.  
  206. template <class T,class Alloc,class List>
  207. void TMInternalHashTableIteratorImp<T,Alloc,List>::Scan()
  208. {
  209.     // if not at end of list, then iterate to the next item
  210.     if( *ListIter )
  211.         (*ListIter)++;
  212.  
  213.     // if now at end of list, then iterate to the next list (if any)
  214.     if( ! *ListIter )
  215.         {
  216.         HashIter++;
  217.         delete ListIter;
  218.  
  219.         while( HashIter != 0 && HashIter.Current() == 0 )
  220.             HashIter++;
  221.         if( HashIter == 0 )
  222.             ListIter = 0;
  223.         else
  224.             ListIter =
  225.                 new(*this)TMListIteratorImp<T,Alloc>( *HashIter.Current() );
  226.         }
  227. }
  228.  
  229. /*------------------------------------------------------------------------*/
  230. /*                                                                        */
  231. /*  template <class T,class Alloc> class TMHashTableImp                   */
  232. /*  template <class T,class Alloc> class TMHashTableIteratorImp           */
  233. /*                                                                        */
  234. /*  Implements a managed hash table of objects of type T, using storage   */
  235. /*  storage allocator A.  Assumes that T has meaningful copy and ==       */
  236. /*  semantics as well as a default constructor.                           */
  237. /*                                                                        */
  238. /*------------------------------------------------------------------------*/
  239.  
  240. template <class T,class Alloc> class TMHashTableIteratorImp;
  241.  
  242. template <class T,class Alloc> class TMHashTableImp :
  243.     private TMInternalHashImp< T,Alloc,TMListImp<T,Alloc> >
  244. {
  245.  
  246.     typedef TMInternalHashImp< T,Alloc,TMListImp<T,Alloc> > Parent;
  247.  
  248. public:
  249.  
  250.     friend TMHashTableIteratorImp<T,Alloc>;
  251.  
  252.     typedef void (*IterFunc)(T&, void *);
  253.  
  254.     int Add( const T& t );
  255.     int Detach( const T& t );
  256.  
  257.     TMHashTableImp( unsigned size = DEFAULT_HASH_TABLE_SIZE ) :
  258.         TMInternalHashImp< T,Alloc,TMListImp<T,Alloc> >(size)
  259.         {
  260.         }
  261.         
  262.     void ForEach( IterFunc iter, void *args );
  263.     T *Find( const T& t ) const;
  264.     void Flush();
  265.  
  266.     Parent::GetItemsInContainer;
  267.     Parent::IsEmpty;
  268.     Parent::operator delete;
  269.     Parent::operator delete [];
  270.  
  271. private:
  272.  
  273.     unsigned GetHashValue( const T& t ) const
  274.         {
  275.         return HashValue(t) % TableSize();
  276.         }
  277.  
  278. };
  279.  
  280. template <class T,class Alloc> class TMHashTableIteratorImp :
  281.     public TMInternalHashTableIteratorImp<T,Alloc,TMListImp<T,Alloc> >
  282. {
  283.  
  284. public:
  285.     TMHashTableIteratorImp( const TMHashTableImp<T,Alloc>& h ) :
  286.         TMInternalHashTableIteratorImp<T,Alloc,TMListImp<T,Alloc> >(h) {}
  287.     
  288. };
  289.  
  290. template <class T,class Alloc>
  291. int TMHashTableImp<T,Alloc>::Add( const T& t )
  292. {
  293.     unsigned index = GetHashValue(t);
  294.     TMListImp<T,Alloc> *list = Table[index];
  295.     if( list == 0 )
  296.         {
  297.         list = Table[index] = new(*this)TMListImp<T,Alloc>;
  298.         }
  299.     if( list == 0 )
  300.         return 0;
  301.     else 
  302.         {
  303.         list->Add(t);
  304.         ItemsInContainer++;
  305.         return 1;
  306.         }
  307. }
  308.  
  309. template <class T,class Alloc>
  310. int TMHashTableImp<T,Alloc>::Detach( const T& t )
  311. {
  312.     unsigned index = GetHashValue(t);
  313.     TMListImp<T,Alloc> *list = Table[index];
  314.     if( list == 0 || ! list->Detach(t) )
  315.         return 0;
  316.     else
  317.         {
  318.         if( list->IsEmpty() )
  319.             {
  320.             delete Table[index];
  321.             Table[index] = 0;
  322.             }
  323.         ItemsInContainer--;
  324.         return 1;
  325.         }
  326. }
  327.  
  328. template <class T,class Alloc>
  329. void TMHashTableImp<T,Alloc>::ForEach( IterFunc iter, void *args )
  330. {
  331.     TMIVectorIteratorImp<TMListImp<T,Alloc>,Alloc> iterator(Table);
  332.     while( iterator )
  333.         {
  334.         TMListImp<T,Alloc> *list = iterator++;
  335.         if( list != 0 )
  336.             list->ForEach(iter,args);
  337.         }
  338. }
  339.  
  340. template <class T,class Alloc>
  341. T *TMHashTableImp<T,Alloc>::Find( const T& t ) const
  342. {
  343.     TMListImp<T,Alloc> *list = Table[GetHashValue(t)];
  344.     return list ? list->Find(t) : 0;
  345. }
  346.  
  347. template <class T,class Alloc> void TMHashTableImp<T,Alloc>::Flush()
  348. {
  349.     for( unsigned i = 0; i < TableSize(); i++ )
  350.         {
  351.         if( Table[i] != 0 )
  352.             {
  353.             Table[i]->Flush();
  354.             delete Table[i];
  355.             Table[i] = 0;
  356.             }
  357.         }
  358.     ItemsInContainer = 0;
  359. }
  360.  
  361. /*------------------------------------------------------------------------*/
  362. /*                                                                        */
  363. /*  template <class T> class THashTableImp                                */
  364. /*  template <class T> class THashTableIteratorImp                        */
  365. /*                                                                        */
  366. /*  Implements a hash table of objects of type T.                         */
  367. /*                                                                        */
  368. /*------------------------------------------------------------------------*/
  369.  
  370. template <class T> class THashTableIteratorImp;
  371.  
  372. template <class T> class THashTableImp :
  373.     public TMHashTableImp<T,TStandardAllocator>
  374. {
  375. public:
  376.  
  377.     friend THashTableIteratorImp<T>;
  378.  
  379.     THashTableImp( unsigned aPrime = DEFAULT_HASH_TABLE_SIZE ) :
  380.         TMHashTableImp<T,TStandardAllocator>(aPrime)
  381.         {
  382.         }
  383. };
  384.  
  385. template <class T> class THashTableIteratorImp :
  386.     public TMHashTableIteratorImp<T,TStandardAllocator>
  387. {
  388. public:
  389.  
  390.     THashTableIteratorImp( const THashTableImp<T>& h ) :
  391.         TMHashTableIteratorImp<T,TStandardAllocator>(h)
  392.         {
  393.         }
  394. };
  395.  
  396. /*------------------------------------------------------------------------*/
  397. /*                                                                        */
  398. /*  template <class T,class Alloc> class TMIHashTableImp                  */
  399. /*  template <class T,class Alloc> class TMIHashTableIteratorImp          */
  400. /*                                                                        */
  401. /*  Implements a managed hash table of pointers to objects of type T,     */
  402. /*  using the storage storage allocator A.                                */
  403. /*                                                                        */
  404. /*------------------------------------------------------------------------*/
  405.  
  406. template <class T,class Alloc> class TMIHashTableIteratorImp;
  407.  
  408. template <class T,class Alloc> class TMIHashTableImp :
  409.     private TMInternalHashImp<TVoidPointer,Alloc,TMIListImp<T,Alloc> >
  410. {
  411.  
  412.     typedef TMInternalHashImp<TVoidPointer,Alloc,TMIListImp<T,Alloc> > Parent;
  413.  
  414. public:
  415.  
  416.     friend TMIHashTableIteratorImp<T,Alloc>;
  417.  
  418.     typedef void (*IterFunc)(T&, void *);
  419.  
  420.     TMIHashTableImp( unsigned size = DEFAULT_HASH_TABLE_SIZE ) :
  421.         TMInternalHashImp<TVoidPointer,Alloc,TMIListImp<T,Alloc> >(size)
  422.         {
  423.         }
  424.  
  425.     int Add( T *t );
  426.     int Detach( T *t, int del = 0 );
  427.  
  428.     void ForEach( IterFunc iter, void *args );
  429.     T *Find( const T *t ) const;
  430.  
  431.     void Flush( int del = 0 );
  432.  
  433.     Parent::GetItemsInContainer;
  434.     Parent::IsEmpty;
  435.     Parent::operator delete;
  436.  
  437. private:
  438.  
  439.     unsigned GetHashValue( const TVoidPointer& t ) const
  440.         {
  441.         return HashValue(*STATIC_CAST(T *,STATIC_CAST(void *,t)))%TableSize();
  442.         }
  443.  
  444. };
  445.  
  446. template <class T,class Alloc>
  447. class TMIHashTableIteratorImp :
  448.     private TMInternalHashTableIteratorImp<TVoidPointer,Alloc,TMIListImp<T,Alloc> >
  449. {
  450.  
  451.     typedef TMInternalHashTableIteratorImp<TVoidPointer,Alloc,TMIListImp<T,Alloc> > Parent;
  452.  
  453. public:
  454.  
  455.     TMIHashTableIteratorImp( const TMIHashTableImp<T,Alloc>& h ) :
  456.         TMInternalHashTableIteratorImp<TVoidPointer,Alloc,TMIListImp<T,Alloc> >(h)
  457.         {
  458.         }
  459.  
  460.     T *Current()
  461.         {
  462.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::Current()));
  463.         }
  464.         
  465.     T *operator ++ (int)
  466.         {
  467.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++(1)));
  468.         }
  469.         
  470.     T *operator ++ ()
  471.         {
  472.         return STATIC_CAST(T *,STATIC_CAST(void *,Parent::operator++()));
  473.         }
  474.  
  475.     Parent::Restart;
  476.     Parent::operator int;
  477.  
  478. };
  479.  
  480. template <class T,class Alloc>
  481. void TMIHashTableImp<T,Alloc>::ForEach( IterFunc iter, void *args )
  482. {
  483.     TMIVectorIteratorImp<TMIListImp<T,Alloc>,Alloc> iterator(Table);
  484.     while( iterator )
  485.         {
  486.         if( iterator.Current() != 0 )
  487.             iterator.Current()->ForEach(iter,args);
  488.         iterator++;
  489.         }
  490. }
  491.  
  492. template <class T,class Alloc>
  493. T *TMIHashTableImp<T,Alloc>::Find( const T *t ) const
  494. {
  495.     TMIListImp<T,Alloc> *list = Table[GetHashValue(t)];
  496.     return list ? list->Find(t) : 0;
  497. }
  498.  
  499. template <class T,class Alloc> int TMIHashTableImp<T,Alloc>::Add( T *t )
  500. {
  501.     unsigned index = GetHashValue(t);
  502.     TMIListImp<T,Alloc> *list = Table[GetHashValue(t)];
  503.     if( list == 0 )
  504.         {
  505.         list = Table[index] = new(*this)TMIListImp<T,Alloc>;
  506.         }
  507.     if( list == 0 )
  508.         return 0;
  509.     else 
  510.         {
  511.         list->Add(t);
  512.         ItemsInContainer++;
  513.         return 1;
  514.         }
  515. }
  516.  
  517. template <class T,class Alloc>
  518. int TMIHashTableImp<T,Alloc>::Detach( T *t, int del )
  519. {
  520.     unsigned index = GetHashValue(t);
  521.     TMIListImp<T,Alloc> *list = Table[GetHashValue(t)];
  522.     if( list == 0 || ! list->Detach( t, del ) )
  523.         return 0;
  524.     else
  525.         {
  526.         if( list->IsEmpty() )
  527.             {
  528.             delete Table[index];
  529.             Table[index] = 0;
  530.             }
  531.         ItemsInContainer--;
  532.         return 1;
  533.         }
  534. }
  535.  
  536. template <class T,class Alloc>
  537. void TMIHashTableImp<T,Alloc>::Flush( int del )
  538. {
  539.     for( unsigned i = 0; i < TableSize(); i++ )
  540.         {
  541.         if( Table[i] != 0 )
  542.             {
  543.             Table[i]->Flush(del);
  544.             delete Table[i];
  545.             Table[i] = 0;
  546.             }
  547.         }
  548.     ItemsInContainer = 0;
  549. }
  550.  
  551. /*------------------------------------------------------------------------*/
  552. /*                                                                        */
  553. /*  template <class T> class TIHashTableImp                               */
  554. /*  template <class T> class TIHashTableIteratorImp                       */
  555. /*                                                                        */
  556. /*  Implements a hash table of pointers to objects of type T              */
  557. /*                                                                        */
  558. /*------------------------------------------------------------------------*/
  559.  
  560. template <class T> class TIHashTableIteratorImp;
  561.  
  562. template <class T> class TIHashTableImp :
  563.     public TMIHashTableImp<T,TStandardAllocator>
  564. {
  565. public:
  566.  
  567.     friend TIHashTableIteratorImp<T>;
  568.  
  569.     TIHashTableImp( unsigned aPrime = DEFAULT_HASH_TABLE_SIZE ) :
  570.         TMIHashTableImp<T,TStandardAllocator>( aPrime)
  571.         {
  572.         }
  573. };
  574.  
  575. template <class T> class TIHashTableIteratorImp :
  576.     public TMIHashTableIteratorImp<T,TStandardAllocator>
  577. {
  578. public:
  579.  
  580.     TIHashTableIteratorImp( const TIHashTableImp<T>& h ) :
  581.         TMIHashTableIteratorImp<T,TStandardAllocator>(h)
  582.         {
  583.         }
  584. };
  585.  
  586. #if defined( BI_CLASSLIB_NO_po )
  587. #pragma option -po.
  588. #endif
  589.  
  590. #pragma option -Vo.
  591.  
  592. #endif  // CLASSLIB_HASHIMP_H
  593.  
  594.