Main Page | Namespace List | Class Hierarchy | Class List | Directories | File List | Namespace Members | Class Members | File Members | Search for 

CamCache Class Reference

#include <gcache.h>

List of all members.

Public Member Functions

 CamCache (size_t Size=0x40000, UINT32 Log2MaxEntries=12)
 ~CamCache ()
BOOL Verify ()
BOOL FindPath (UINT32 Handle, INT32 *&Points, BYTE *&Types, UINT32 &Length)
void AddPath (UINT32 Handle, INT32 *Points, BYTE *Types, UINT32 Length)
char * FindString (UINT32 Handle)
void AddString (UINT32 Handle, char *String)

Private Member Functions

void * FindEntry (UINT32 Handle)
void * AddEntry (UINT32 Handle, size_t ObjectSize)
size_t BlockSize (CacheBlock *Block)

Private Attributes

size_t HashTableSize
UINT32 HashTableMask
CacheBlock ** HashTable
CacheBlock * CacheStart
CacheBlock * CacheEnd
CacheBlock * LeastUsed
CacheBlock * MostUsed

Detailed Description

Gavin's original defaults GCache( size_t Size = 0x40000, UINT32 Log2MaxEntries = 12 ) ;

The size of the cache is 128k, average character size = 1k, We allow a maximum of 1K entries GCache( size_t Size = 0x20000, UINT32 Log2MaxEntries = 10 ) ;

Size specifies the byte size of the cache. Log2MaxEntries specifes the number of entries in the hash table. Note that the cache will still work even if there are more characters than the size of the hash table.

BOOL Verify() ; This will return TRUE if the cache is in use. Use after construction to ensure that construction succeeded.

BOOL FindPath( UINT32 Handle, INT32* &Points, BYTE* &Types, UINT32 &Length ) ;

Searches for the given handle. If found it returns TRUE and returns the associated path in Points, Types and Length, else it returns FALSE.

void AddPath( UINT32 Handle, INT32* Points, BYTE* Types, UINT32 Length ) ;

Stores the given path in the cache using the specified handle.

char* FindString( UINT32 Handle ) ;

Searches for the given handle. If found it returns the string associated with the handle, else it returns FALSE.

void AddString( UINT32 Handle, char* String ) ;

Stores the given string in the cache using the specified handle.

Definition at line 168 of file gcache.h.

Constructor & Destructor Documentation

CamCache::CamCache (  size_t  Size = 0x40000,
UINT32  Log2MaxEntries = 12
) 
 

Definition at line 113 of file gcache.cpp.

00114 {
00115     HashTableSize = 1<<Log2MaxEntries ;
00116     HashTableMask = HashTableSize-1 ;
00117     HashTable     = NULL ;
00118     CacheStart    = NULL ;
00119 
00120     HashTable   = new ( CacheBlock* [HashTableSize] ) ;
00121     CacheStart  = (CacheBlock*) new BYTE[Size+2*FreeCacheBlockSize] ;
00122 
00123     if (!HashTable || !CacheStart)
00124     {
00125         if (HashTable)
00126         {
00127             delete [] HashTable  ; HashTable  = NULL ;
00128         }
00129         if (CacheStart)
00130         {
00131             delete [] CacheStart ; CacheStart = NULL ;
00132         }
00133         return ;
00134     }
00135     for ( size_t i=0 ; i<HashTableSize ; i++ )
00136         HashTable[i] = NULL ;
00137     CacheBlock *FreeBlock ;
00138     FreeBlock   = (CacheBlock*) ((BYTE*)CacheStart+FreeCacheBlockSize) ;
00139     CacheEnd    = (CacheBlock*) ((BYTE*)CacheStart+Size-FreeCacheBlockSize) ;
00140     CacheStart->Prev        = CacheStart ;
00141                               CacheEnd->Next        = CacheEnd ;
00142     CacheStart->Next        = CacheEnd->Prev        =
00143     CacheStart->NextFree    = CacheEnd->PrevFree    = FreeBlock ;
00144     CacheStart->PrevFree    = CacheEnd->NextFree    = NULL ;
00145     CacheStart->State       = CacheEnd->State       = 0 ;
00146     FreeBlock->Prev         = FreeBlock->PrevFree   = CacheStart ;
00147     FreeBlock->Next         = FreeBlock->NextFree   = CacheEnd ;
00148     FreeBlock->State        = FREE ;
00149     LeastUsed = MostUsed = NULL ;
00150 }

CamCache::~CamCache (   ) 
 

Definition at line 163 of file gcache.cpp.

00164 {
00165     delete [] HashTable  ; HashTable  = NULL ;
00166     delete [] CacheStart ; CacheStart = NULL ;
00167 }

Member Function Documentation

void * CamCache::AddEntry (  UINT32  Handle,
size_t  ObjectSize
)  [private]
 

Definition at line 263 of file gcache.cpp.

00264 {
00265     UINT32 HashIndex = Hash( Handle ) & HashTableMask ;
00266     CacheBlock *Ptr = HashTable[HashIndex] ;
00267     while ( Ptr )
00268         if ( Ptr->Handle == Handle )
00269             return Ptr->Object ;                    /* Entry already exists */
00270         else
00271             Ptr = Ptr->Link ;
00272     CacheBlock *FreeBlock = CacheStart->NextFree ;
00273     size_t ObjectBlockSize = (ObjectSize+UsedCacheBlockSize+3) & ~3 ;
00274     while ( ObjectBlockSize > BlockSize(FreeBlock) )
00275         if ( !(FreeBlock=FreeBlock->NextFree) )
00276         {
00277             /* Remove least recently used object from hash table */
00278             UINT32 HashIndex = Hash( LeastUsed->Handle ) & HashTableMask ;
00279             CacheBlock *Ptr = HashTable[HashIndex] ;
00280             if ( Ptr == LeastUsed )
00281                 HashTable[HashIndex] = LeastUsed->Link ;
00282             else
00283             {
00284                 while ( Ptr->Link != LeastUsed )
00285                     Ptr = Ptr->Link ;
00286                 Ptr->Link = LeastUsed->Link ;
00287             }               
00288             /* Merge least recently used object with adjacent free blocks and try again */
00289             FreeBlock = LeastUsed ;
00290             LeastUsed = LeastUsed->NextUsed ;
00291             LeastUsed->PrevUsed = NULL ;
00292             FreeBlock->State = FREE ;
00293             CacheStart->NextFree->PrevFree = FreeBlock ;
00294             FreeBlock->NextFree = CacheStart->NextFree ;
00295             FreeBlock->PrevFree = CacheStart ;
00296             CacheStart->NextFree = FreeBlock ;
00297             CacheBlock *NextBlock = FreeBlock->Next ;
00298             CacheBlock *PrevBlock = FreeBlock->Prev ;
00299             if ( NextBlock->State == FREE )
00300             {
00301                 NextBlock->PrevFree->NextFree = NextBlock->NextFree ;
00302                 NextBlock->NextFree->PrevFree = NextBlock->PrevFree ;
00303                 FreeBlock->Next = NextBlock->Next ;
00304                 NextBlock->Next->Prev = FreeBlock ;
00305             }
00306             if ( PrevBlock->State == FREE )
00307             {
00308                 FreeBlock->PrevFree->NextFree = FreeBlock->NextFree ;
00309                 FreeBlock->NextFree->PrevFree = FreeBlock->PrevFree ;
00310                 PrevBlock->Next = FreeBlock->Next ;
00311                 FreeBlock->Next->Prev = PrevBlock ;
00312                 FreeBlock = PrevBlock ;
00313             }
00314         }
00315     /* Add object */
00316     if ( ObjectBlockSize+FreeCacheBlockSize > BlockSize(FreeBlock) )
00317     {
00318         FreeBlock->PrevFree->NextFree = FreeBlock->NextFree ;
00319         FreeBlock->NextFree->PrevFree = FreeBlock->PrevFree ;
00320     }
00321     else
00322     {
00323         CacheBlock *NewBlock = (CacheBlock*) ((BYTE*)FreeBlock+ObjectBlockSize) ;
00324         NewBlock->Prev      = FreeBlock ;
00325         NewBlock->Next      = FreeBlock->Next ;
00326         NewBlock->State     = FREE ;
00327         NewBlock->NextFree  = FreeBlock->NextFree ;
00328         NewBlock->PrevFree  = FreeBlock->PrevFree ;
00329         NewBlock->NextFree->PrevFree = NewBlock->PrevFree->NextFree = NewBlock ;
00330         FreeBlock->Next     = NewBlock->Next->Prev = NewBlock ;
00331     }
00332     FreeBlock->Link     = HashTable[HashIndex] ;
00333     FreeBlock->PrevUsed = MostUsed ;
00334     FreeBlock->NextUsed = NULL ;
00335     FreeBlock->Handle   = Handle ;
00336     HashTable[HashIndex] = FreeBlock ;
00337     if ( MostUsed )
00338         MostUsed->NextUsed = FreeBlock ;
00339     MostUsed = FreeBlock ;
00340     if ( !LeastUsed )
00341         LeastUsed = FreeBlock ;
00342     return FreeBlock->Object ;
00343 }

void CamCache::AddPath (  UINT32  Handle,
INT32 *  Points,
BYTE *  Types,
UINT32  Length
) 
 

Definition at line 184 of file gcache.cpp.

00185 {
00186     INT32 *DPtr = (INT32*) AddEntry( Handle,Length*9+4 ) ;
00187     *DPtr++ = Length ;
00188     INT32 *SPtr = Points ;
00189     size_t i;
00190     for ( i=0 ; i<2*Length ; i++ )
00191         *DPtr++ = *SPtr++ ;
00192     SPtr = (INT32*) Types ;
00193     Length = (Length+3)>>2 ;                    /* Word length */
00194     for ( i=0 ; i<Length ; i++ )
00195         *DPtr++ = *SPtr++ ;
00196 }

void CamCache::AddString (  UINT32  Handle,
char *  String
) 
 

Definition at line 209 of file gcache.cpp.

00210 {
00211     size_t StringLength = cc_strlenBytes(String)+1 ;    /* Byte length */
00212     INT32 *SPtr = (INT32*) String ;
00213     INT32 *DPtr = (INT32*) AddEntry( Handle,StringLength ) ;
00214     StringLength = (StringLength+3)>>2 ;        /* Word length */
00215     for ( size_t i=0 ; i<StringLength ; i++ )
00216         *DPtr++ = *SPtr++ ;
00217 }

size_t CamCache::BlockSize (  CacheBlock *  Block  )  [inline, private]
 

Definition at line 199 of file gcache.h.

00200     {
00201         return (size_t)((BYTE*)Block->Next-(BYTE*)Block) ;
00202     } ;

void * CamCache::FindEntry (  UINT32  Handle  )  [private]
 

Definition at line 233 of file gcache.cpp.

00234 {
00235     UINT32 HashIndex = Hash( Handle ) & HashTableMask ;
00236     CacheBlock *Ptr = HashTable[HashIndex] ;
00237     while ( Ptr )
00238         if ( Ptr->Handle == Handle )
00239         {
00240             if ( Ptr != MostUsed )
00241             {
00242                 /* Make this the most recently used object */
00243                 if ( Ptr==LeastUsed )
00244                     LeastUsed = Ptr->NextUsed ;
00245                 else
00246                     Ptr->PrevUsed->NextUsed = Ptr->NextUsed ;
00247                 Ptr->NextUsed->PrevUsed = Ptr->PrevUsed ;
00248                 Ptr->NextUsed = NULL ;
00249                 Ptr->PrevUsed = MostUsed ;
00250                 MostUsed->NextUsed = Ptr ;
00251                 MostUsed = Ptr ;
00252             }
00253             return Ptr->Object ;
00254         }
00255         else
00256             Ptr = Ptr->Link ;
00257 
00258     return NULL ;
00259 }

BOOL CamCache::FindPath (  UINT32  Handle,
INT32 *&  Points,
BYTE *&  Types,
UINT32 &  Length
) 
 

Definition at line 172 of file gcache.cpp.

00173 {
00174     INT32 *Object = (INT32*) FindEntry( Handle ) ;
00175     if ( Object )
00176     {
00177         Length = *Object ;
00178         Points = ++Object ;
00179         Types = (BYTE*) (Object+2*Length) ;
00180     }
00181     return Object!=NULL ;
00182 }

char * CamCache::FindString (  UINT32  Handle  ) 
 

Definition at line 204 of file gcache.cpp.

00205 {
00206     return (char*) FindEntry( Handle ) ;
00207 }

BOOL CamCache::Verify (   ) 
 

Definition at line 156 of file gcache.cpp.

00157 {
00158     return HashTable && CacheStart ;
00159 }

Member Data Documentation

CacheBlock* CamCache::CacheEnd [private]
 

Definition at line 191 of file gcache.h.

CacheBlock* CamCache::CacheStart [private]
 

Definition at line 190 of file gcache.h.

CacheBlock** CamCache::HashTable [private]
 

Definition at line 188 of file gcache.h.

UINT32 CamCache::HashTableMask [private]
 

Definition at line 187 of file gcache.h.

size_t CamCache::HashTableSize [private]
 

Definition at line 186 of file gcache.h.

CacheBlock* CamCache::LeastUsed [private]
 

Definition at line 193 of file gcache.h.

CacheBlock* CamCache::MostUsed [private]
 

Definition at line 194 of file gcache.h.

The documentation for this class was generated from the following files:
Generated on Sat Nov 10 03:51:44 2007 for Camelot by  doxygen 1.4.4