gemrb/core/Cache.cpp

   1 /* GemRB - Infinity Engine Emulator
   2  * Copyright (C) 2003 The GemRB Project
   3  *
   4  * This program is free software; you can redistribute it and/or
   5  * modify it under the terms of the GNU General Public License
   6  * as published by the Free Software Foundation; either version 2
   7  * of the License, or (at your option) any later version.
   8  *
   9  * This program is distributed in the hope that it will be useful,
  10  * but WITHOUT ANY WARRANTY; without even the implied warranty of
  11  * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
  12  * GNU General Public License for more details.
  13  *
  14  * You should have received a copy of the GNU General Public License
  15  * along with this program; if not, write to the Free Software
  16  * Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301, USA.
  17  *
  18  *
  19  */
  20
  21 #include "Cache.h"
  22
  23 #include <ctype.h>
  24
  25 // private inlines
  26 inline unsigned int Cache::MyHashKey(const char* key) const
  27 {
  28         int nHash = tolower(key[0]);
  29         for (int i=1;(i<KEYSIZE) && key[i];i++) {
  30                 nHash = (nHash << 5) ^ tolower(key[i]);
  31         }
  32         return nHash % m_nHashTableSize;
  33 }
  34
  35 Cache::Cache(int nBlockSize, int nHashTableSize)
  36 {
  37         assert( nBlockSize > 0 );
  38         assert( nHashTableSize > 16 );
  39
  40         m_pHashTable = NULL;
  41         m_nHashTableSize = nHashTableSize; // default size
  42         m_nCount = 0;
  43         m_pFreeList = NULL;
  44         m_pBlocks = NULL;
  45         m_nBlockSize = nBlockSize;
  46 }
  47
  48 void Cache::InitHashTable(unsigned int nHashSize, bool bAllocNow)
  49         //Used to force allocation of a hash table or to override the default
  50         //hash table size of (which is fairly small)
  51 {
  52         assert( m_nCount == 0 );
  53         assert( nHashSize > 16 );
  54
  55         if (m_pHashTable != NULL) {
  56                 // free hash table
  57                 free( m_pHashTable);
  58                 m_pHashTable = NULL;
  59         }
  60
  61         if (bAllocNow) {
  62                 m_pHashTable = (Cache::MyAssoc **) malloc( sizeof( Cache::MyAssoc * ) * nHashSize );
  63                 memset( m_pHashTable, 0, sizeof( Cache::MyAssoc * ) * nHashSize );
  64         }
  65         m_nHashTableSize = nHashSize;
  66 }
  67
  68 void Cache::RemoveAll(ReleaseFun fun)
  69 {
  70         if (m_pHashTable) {
  71                 for (unsigned int nHash = 0; nHash < m_nHashTableSize; nHash++)
  72                 {
  73                         MyAssoc* pAssoc;
  74                         for (pAssoc = m_pHashTable[nHash]; pAssoc != NULL;
  75                                 pAssoc = pAssoc->pNext)
  76                         {
  77                                 if (fun)
  78                                         fun(pAssoc->data);
  79                                 pAssoc->MyAssoc::~MyAssoc();
  80                         }
  81                 }
  82                 // free hash table
  83                 free( m_pHashTable );
  84                 m_pHashTable = NULL;
  85         }
  86
  87         m_nCount = 0;
  88         m_pFreeList = NULL;
  89
  90         // free memory blocks
  91         MemBlock* p = m_pBlocks;
  92         while (p != NULL) {
  93                 MemBlock* pNext = p->pNext;
  94                 free( p );
  95                 p = pNext;
  96         }
  97
  98         m_pBlocks = NULL;
  99 }
 100
 101 Cache::~Cache()
 102 {
 103         RemoveAll(NULL);
 104 }
 105
 106 Cache::MyAssoc* Cache::NewAssoc()
 107 {
 108         if (m_pFreeList == NULL) {
 109                 // add another block
 110                 Cache::MemBlock* newBlock = ( Cache::MemBlock* ) malloc(m_nBlockSize * sizeof( Cache::MyAssoc ) + sizeof( Cache::MemBlock ));
 111                 assert( newBlock != NULL ); // we must have something
 112
 113                 newBlock->pNext = m_pBlocks;
 114                 m_pBlocks = newBlock;
 115
 116                 // chain them into free list
 117                 Cache::MyAssoc* pAssoc = ( Cache::MyAssoc* )
 118                         ( newBlock + 1 );
 119                 for (int i = 0; i < m_nBlockSize; i++) {
 120                         pAssoc->pNext = m_pFreeList;
 121                         m_pFreeList = pAssoc++;
 122                 }
 123         }
 124
 125         Cache::MyAssoc* pAssoc = m_pFreeList;
 126         m_pFreeList = m_pFreeList->pNext;
 127         m_nCount++;
 128         assert( m_nCount > 0 ); // make sure we don't overflow
 129 #ifdef _DEBUG
 130         pAssoc->key[0] = 0;
 131         pAssoc->data = 0;
 132 #endif
 133         pAssoc->nRefCount=1;
 134         return pAssoc;
 135 }
 136
 137 void Cache::FreeAssoc(Cache::MyAssoc* pAssoc)
 138 {
 139         if(pAssoc->pNext) {
 140                 pAssoc->pNext->pPrev=pAssoc->pPrev;
 141         }
 142         *pAssoc->pPrev = pAssoc->pNext;
 143         pAssoc->pNext = m_pFreeList;
 144         m_pFreeList = pAssoc;
 145         m_nCount--;
 146         assert( m_nCount >= 0 ); // make sure we don't underflow
 147
 148         // if no more elements, cleanup completely
 149         if (m_nCount == 0) {
 150                 RemoveAll(NULL);
 151         }
 152 }
 153
 154 Cache::MyAssoc *Cache::GetNextAssoc(Cache::MyAssoc *Position) const
 155 {
 156         if (m_pHashTable == NULL || m_nCount==0) {
 157                 return NULL;
 158         }
 159
 160         Cache::MyAssoc* pAssocRet = (Cache::MyAssoc*)Position;
 161
 162         if (pAssocRet == NULL)
 163         {
 164                 // find the first association
 165                 for (unsigned int nBucket = 0; nBucket < m_nHashTableSize; nBucket++)
 166                         if ((pAssocRet = m_pHashTable[nBucket]) != NULL)
 167                                 break;
 168                 return pAssocRet;
 169         }
 170         Cache::MyAssoc* pAssocNext = pAssocRet->pNext;
 171         if (pAssocNext == NULL)
 172         {
 173                 // go to next bucket
 174                 for (unsigned int nBucket = MyHashKey(pAssocRet->key) + 1;
 175                         nBucket < m_nHashTableSize; nBucket++)
 176                         if ((pAssocNext = m_pHashTable[nBucket]) != NULL)
 177                                 break;
 178         }
 179
 180         return pAssocNext;
 181 }
 182
 183 Cache::MyAssoc* Cache::GetAssocAt(const ieResRef key) const
 184         // find association (or return NULL)
 185 {
 186         if (m_pHashTable == NULL) {
 187                 return NULL;
 188         }
 189
 190         unsigned int nHash = MyHashKey( key );
 191
 192         // see if it exists
 193         Cache::MyAssoc* pAssoc;
 194         for (pAssoc = m_pHashTable[nHash];
 195                 pAssoc != NULL;
 196                 pAssoc = pAssoc->pNext) {
 197                 if (!strnicmp( pAssoc->key, key, KEYSIZE )) {
 198                         return pAssoc;
 199                 }
 200         }
 201         return NULL;
 202 }
 203
 204 void *Cache::GetResource(const ieResRef key) const
 205 {
 206         Cache::MyAssoc* pAssoc = GetAssocAt( key );
 207         if (pAssoc == NULL) {
 208                 return NULL;
 209         } // not in map
 210
 211         pAssoc->nRefCount++;
 212         return pAssoc->data;
 213 }
 214
 215 //returns true if it was successful
 216 bool Cache::SetAt(const ieResRef key, void *rValue)
 217 {
 218         int i;
 219
 220         if (m_pHashTable == NULL) {
 221                 InitHashTable( m_nHashTableSize );
 222         }
 223
 224         Cache::MyAssoc* pAssoc=GetAssocAt( key );
 225
 226         if (pAssoc) {
 227                 //already exists, but we return true if it is the same
 228                 return (pAssoc->data==rValue);
 229         }
 230
 231         // it doesn't exist, add a new Association
 232         pAssoc = NewAssoc();
 233         for (i=0;i<KEYSIZE && key[i];i++) {
 234                 pAssoc->key[i]=tolower(key[i]);
 235         }
 236         for (;i<KEYSIZE;i++) {
 237                 pAssoc->key[i]=0;
 238         }
 239         pAssoc->data=rValue;
 240         // put into hash table
 241         unsigned int nHash = MyHashKey(pAssoc->key);
 242         pAssoc->pNext = m_pHashTable[nHash];
 243         pAssoc->pPrev = &m_pHashTable[nHash];
 244         if (pAssoc->pNext) {
 245                 pAssoc->pNext->pPrev = &pAssoc->pNext;
 246         }
 247         m_pHashTable[nHash] = pAssoc;
 248         return true;
 249 }
 250
 251 int Cache::RefCount(const ieResRef key) const
 252 {
 253         Cache::MyAssoc* pAssoc=GetAssocAt( key );
 254         if (pAssoc) {
 255                 return pAssoc->nRefCount;
 256         }
 257         return -1;
 258 }
 259
 260 int Cache::DecRef(void *data, const ieResRef key, bool remove)
 261 {
 262         Cache::MyAssoc* pAssoc;
 263
 264         if (key) {
 265                 pAssoc=GetAssocAt( key );
 266                 if (pAssoc && (pAssoc->data==data) ) {
 267                         if (!pAssoc->nRefCount) {
 268                                 return -1;
 269                         }
 270                         --pAssoc->nRefCount;
 271                         if (remove && !pAssoc->nRefCount) {
 272                                 FreeAssoc(pAssoc);
 273                                 return 0;
 274                         }
 275                         return pAssoc->nRefCount;
 276                 }
 277                 return -1;
 278         }
 279
 280         pAssoc=(Cache::MyAssoc *) GetNextAssoc(NULL);
 281
 282         while (pAssoc) {
 283                 if (pAssoc->data == data) {
 284                         if (!pAssoc->nRefCount) {
 285                                 return -1;
 286                         }
 287                         --pAssoc->nRefCount;
 288                         if (remove && !pAssoc->nRefCount) {
 289                                 FreeAssoc(pAssoc);
 290                                 return 0;
 291                         }
 292                         return pAssoc->nRefCount;
 293                 }
 294                 pAssoc=GetNextAssoc(pAssoc);
 295         }
 296         return -1;
 297 }
 298
 299 void Cache::Cleanup()
 300 {
 301         Cache::MyAssoc* pAssoc=(Cache::MyAssoc *) GetNextAssoc(NULL);
 302
 303         while (pAssoc)
 304         {
 305                 Cache::MyAssoc* nextAssoc = GetNextAssoc(pAssoc);
 306                 if (pAssoc->nRefCount == 0) {
 307                         FreeAssoc(pAssoc);
 308                 }
 309                 pAssoc=nextAssoc;
 310         }
 311 }