glcontainer.h

00001 #ifndef GRINLIZ_CONTAINER_INCLUDED
00002 #define GRINLIZ_CONTAINER_INCLUDED
00003 
00004 #include "gldebug.h"
00005 
00006 namespace grinliz
00007 {
00008 
00009 template< typename T, typename Equal >
00010 class PtrHashTable
00011 {
00012 public:
00013         PtrHashTable( int _size = 256 ) : size( 0 ), population( 0 ), table( 0 )
00014         {
00015                 Resize( _size );
00016         }
00017 
00018         ~PtrHashTable() { delete [] table; }
00019 
00020         void Clear()
00021         {
00022                 memset( table, 0, size*sizeof(T*) );
00023                 population = 0;
00024         }
00025 
00026         void Put( T* t ) 
00027         {
00028                 if ( population > size / 2 ) {
00029                         GLOUTPUT(( "PtrHashTable resize %d to %d\n", size, size*4 ));
00030                         Resize( size*4 );
00031                 }
00032 
00033                 U32 hash = t->HashCode();
00034                 unsigned index = hash % size;
00035                 GLASSERT( index < size );
00036 
00037                 // Linear probe
00038                 while( table[index] ) {
00039                         ++index;
00040                         if ( index == size )
00041                                 index = 0;
00042                 }
00043                 table[index] = t;
00044                 ++population;
00045         }
00046 
00047         T* Contains( const T& key ) 
00048         {
00049                 U32 hash = key.HashCode();
00050                 unsigned index = hash % size;
00051                 while( table[index] ) 
00052                 {
00053                         Equal equal;
00054                         if ( equal( *(table[index]), key ) )
00055                                 return table[index];
00056 
00057                         ++index;
00058                         if ( index == size )
00059                                 index = 0;
00060                 }
00061                 return 0;
00062         }
00063 
00064         void Resize( unsigned newSize ) 
00065         {
00066                 if ( newSize < population / 4 )
00067                         newSize = population*4;
00068 
00069                 T** oldTable = table;
00070                 unsigned oldSize = size;
00071 
00072                 size = newSize;
00073                 table = new T*[size];
00074                 Clear();
00075 
00076                 for( unsigned i=0; i<oldSize; ++i ) 
00077                 {
00078                         if ( oldTable[i] )
00079                                 Put( oldTable[i] );
00080                 }
00081                 delete [] oldTable;
00082         }
00083 
00084 private:
00085         unsigned size;
00086         unsigned population;
00087         T** table;
00088 };
00089 
00090 
00091 }       // namespace grinliz
00092 #endif

Generated on Thu Jul 20 20:45:31 2006 for Kyra by  doxygen 1.4.7