1#include "SkTextureCache.h" 2 3//#define TRACE_HASH_HITS 4//#define TRACE_TEXTURE_CACHE_PURGE 5 6SkTextureCache::Entry::Entry(const SkBitmap& bitmap) 7 : fName(0), fKey(bitmap), fPrev(NULL), fNext(NULL) { 8 9 fMemSize = SkGL::ComputeTextureMemorySize(bitmap); 10 fLockCount = 0; 11} 12 13SkTextureCache::Entry::~Entry() { 14 if (fName != 0) { 15 glDeleteTextures(1, &fName); 16 } 17} 18 19/////////////////////////////////////////////////////////////////////////////// 20 21SkTextureCache::SkTextureCache(size_t countMax, size_t sizeMax) 22 : fHead(NULL), fTail(NULL), 23 fTexCountMax(countMax), fTexSizeMax(sizeMax), 24 fTexCount(0), fTexSize(0) { 25 26 sk_bzero(fHash, sizeof(fHash)); 27 this->validate(); 28} 29 30SkTextureCache::~SkTextureCache() { 31#ifdef SK_DEBUG 32 Entry* entry = fHead; 33 while (entry) { 34 SkASSERT(entry->lockCount() == 0); 35 entry = entry->fNext; 36 } 37#endif 38 this->validate(); 39} 40 41void SkTextureCache::deleteAllCaches(bool texturesAreValid) { 42 this->validate(); 43 44 Entry* entry = fHead; 45 while (entry) { 46 Entry* next = entry->fNext; 47 if (!texturesAreValid) { 48 entry->abandonTexture(); 49 } 50 SkDELETE(entry); 51 entry = next; 52 } 53 54 fSorted.reset(); 55 sk_bzero(fHash, sizeof(fHash)); 56 57 fTexCount = 0; 58 fTexSize = 0; 59 60 fTail = fHead = NULL; 61 62 this->validate(); 63} 64 65/////////////////////////////////////////////////////////////////////////////// 66 67int SkTextureCache::findInSorted(const Key& key) const { 68 int count = fSorted.count(); 69 if (count == 0) { 70 return ~0; 71 } 72 73 Entry** sorted = fSorted.begin(); 74 int lo = 0; 75 int hi = count - 1; 76 while (lo < hi) { 77 int mid = (hi + lo) >> 1; 78 if (sorted[mid]->getKey() < key) { 79 lo = mid + 1; 80 } else { 81 hi = mid; 82 } 83 } 84 85 // hi is now our best guess 86 const Entry* entry = sorted[hi]; 87 if (entry->getKey() == key) { 88 return hi; 89 } 90 91 // return where to insert it 92 if (entry->getKey() < key) { 93 hi += 1; 94 } 95 return ~hi; // we twiddle to indicate not-found 96} 97 98#ifdef TRACE_HASH_HITS 99static int gHashHits; 100static int gSortedHits; 101#endif 102 103SkTextureCache::Entry* SkTextureCache::find(const Key& key, int* insert) const { 104 int count = fSorted.count(); 105 if (count == 0) { 106 *insert = 0; 107 return NULL; 108 } 109 110 // check the hash first 111 int hashIndex = key.getHashIndex(); 112 Entry* entry = fHash[hashIndex]; 113 if (NULL != entry && entry->getKey() == key) { 114#ifdef TRACE_HASH_HITS 115 gHashHits += 1; 116#endif 117 return entry; 118 } 119 120 int index = this->findInSorted(key); 121 if (index >= 0) { 122#ifdef TRACE_HASH_HITS 123 gSortedHits += 1; 124#endif 125 entry = fSorted[index]; 126 fHash[hashIndex] = entry; 127 return entry; 128 } 129 130 // ~index is where to insert the entry 131 *insert = ~index; 132 return NULL; 133} 134 135SkTextureCache::Entry* SkTextureCache::lock(const SkBitmap& bitmap) { 136 this->validate(); 137 138 // call this before we call find(), so we don't reorder after find() and 139 // invalidate our index 140 this->purgeIfNecessary(SkGL::ComputeTextureMemorySize(bitmap)); 141 142 Key key(bitmap); 143 int index; 144 Entry* entry = this->find(key, &index); 145 146 if (NULL == entry) { 147 entry = SkNEW_ARGS(Entry, (bitmap)); 148 149 entry->fName = SkGL::BindNewTexture(bitmap, &entry->fTexSize); 150 if (0 == entry->fName) { 151 SkDELETE(entry); 152 return NULL; 153 } 154 fHash[key.getHashIndex()] = entry; 155 *fSorted.insert(index) = entry; 156 157 fTexCount += 1; 158 fTexSize += entry->memSize(); 159 } else { 160 // detach from our llist 161 Entry* prev = entry->fPrev; 162 Entry* next = entry->fNext; 163 if (prev) { 164 prev->fNext = next; 165 } else { 166 SkASSERT(fHead == entry); 167 fHead = next; 168 } 169 if (next) { 170 next->fPrev = prev; 171 } else { 172 SkASSERT(fTail == entry); 173 fTail = prev; 174 } 175 // now bind the texture 176 glBindTexture(GL_TEXTURE_2D, entry->fName); 177 } 178 179 // add to head of llist for LRU 180 entry->fPrev = NULL; 181 entry->fNext = fHead; 182 if (NULL != fHead) { 183 SkASSERT(NULL == fHead->fPrev); 184 fHead->fPrev = entry; 185 } 186 fHead = entry; 187 if (NULL == fTail) { 188 fTail = entry; 189 } 190 191 this->validate(); 192 entry->lock(); 193 194#ifdef TRACE_HASH_HITS 195 SkDebugf("---- texture cache hash=%d sorted=%d\n", gHashHits, gSortedHits); 196#endif 197 return entry; 198} 199 200void SkTextureCache::unlock(Entry* entry) { 201 this->validate(); 202 203#ifdef SK_DEBUG 204 SkASSERT(entry); 205 int index = this->findInSorted(entry->getKey()); 206 SkASSERT(fSorted[index] == entry); 207#endif 208 209 SkASSERT(entry->fLockCount > 0); 210 entry->unlock(); 211} 212 213void SkTextureCache::purgeIfNecessary(size_t extraSize) { 214 this->validate(); 215 216 size_t countMax = fTexCountMax; 217 size_t sizeMax = fTexSizeMax; 218 219 // take extraSize into account, but watch for underflow of size_t 220 if (extraSize > sizeMax) { 221 sizeMax = 0; 222 } else { 223 sizeMax -= extraSize; 224 } 225 226 Entry* entry = fTail; 227 while (entry) { 228 if (fTexCount <= countMax && fTexSize <= sizeMax) { 229 break; 230 } 231 232 Entry* prev = entry->fPrev; 233 // don't purge an entry that is locked 234 if (entry->isLocked()) { 235 entry = prev; 236 continue; 237 } 238 239 fTexCount -= 1; 240 fTexSize -= entry->memSize(); 241 242 // remove from our sorted and hash arrays 243 int index = this->findInSorted(entry->getKey()); 244 SkASSERT(index >= 0); 245 fSorted.remove(index); 246 index = entry->getKey().getHashIndex(); 247 if (entry == fHash[index]) { 248 fHash[index] = NULL; 249 } 250 251 // now detach it from our llist 252 Entry* next = entry->fNext; 253 if (prev) { 254 prev->fNext = next; 255 } else { 256 fHead = next; 257 } 258 if (next) { 259 next->fPrev = prev; 260 } else { 261 fTail = prev; 262 } 263 264 // now delete it 265#ifdef TRACE_TEXTURE_CACHE_PURGE 266 SkDebugf("---- purge texture cache %d size=%d\n", 267 entry->name(), entry->memSize()); 268#endif 269 SkDELETE(entry); 270 271 // keep going 272 entry = prev; 273 } 274 275 this->validate(); 276} 277 278void SkTextureCache::setMaxCount(size_t count) { 279 if (fTexCountMax != count) { 280 fTexCountMax = count; 281 this->purgeIfNecessary(0); 282 } 283} 284 285void SkTextureCache::setMaxSize(size_t size) { 286 if (fTexSizeMax != size) { 287 fTexSizeMax = size; 288 this->purgeIfNecessary(0); 289 } 290} 291 292/////////////////////////////////////////////////////////////////////////////// 293 294#ifdef SK_DEBUG 295void SkTextureCache::validate() const { 296 if (0 == fTexCount) { 297 SkASSERT(0 == fTexSize); 298 SkASSERT(NULL == fHead); 299 SkASSERT(NULL == fTail); 300 return; 301 } 302 303 SkASSERT(fTexSize); // do we allow a zero-sized texture? 304 SkASSERT(fHead); 305 SkASSERT(fTail); 306 307 SkASSERT(NULL == fHead->fPrev); 308 SkASSERT(NULL == fTail->fNext); 309 if (1 == fTexCount) { 310 SkASSERT(fHead == fTail); 311 } 312 313 const Entry* entry = fHead; 314 size_t count = 0; 315 size_t size = 0; 316 size_t i; 317 318 while (entry != NULL) { 319 SkASSERT(count < fTexCount); 320 SkASSERT(size < fTexSize); 321 size += entry->memSize(); 322 count += 1; 323 if (NULL == entry->fNext) { 324 SkASSERT(fTail == entry); 325 } 326 entry = entry->fNext; 327 } 328 SkASSERT(count == fTexCount); 329 SkASSERT(size == fTexSize); 330 331 count = 0; 332 size = 0; 333 entry = fTail; 334 while (entry != NULL) { 335 SkASSERT(count < fTexCount); 336 SkASSERT(size < fTexSize); 337 size += entry->memSize(); 338 count += 1; 339 if (NULL == entry->fPrev) { 340 SkASSERT(fHead == entry); 341 } 342 entry = entry->fPrev; 343 } 344 SkASSERT(count == fTexCount); 345 SkASSERT(size == fTexSize); 346 347 SkASSERT(count == (size_t)fSorted.count()); 348 for (i = 1; i < count; i++) { 349 SkASSERT(fSorted[i-1]->getKey() < fSorted[i]->getKey()); 350 } 351 352 for (i = 0; i < kHashCount; i++) { 353 if (fHash[i]) { 354 size_t index = fHash[i]->getKey().getHashIndex(); 355 SkASSERT(index == i); 356 index = fSorted.find(fHash[i]); 357 SkASSERT((size_t)index < count); 358 } 359 } 360} 361#endif 362 363 364