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
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 }
00092 #endif