- Main Page
- Classes
- Files
- Directories
- Related Pages

# 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