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