1 2 /* 3 * Copyright 2012 Google Inc. 4 * 5 * Use of this source code is governed by a BSD-style license that can be 6 * found in the LICENSE file. 7 */ 8 9 #include "SkBitmapHeap.h" 10 11 #include "SkBitmap.h" 12 #include "SkReadBuffer.h" 13 #include "SkWriteBuffer.h" 14 #include "SkTSearch.h" 15 16 SkBitmapHeapEntry::SkBitmapHeapEntry() 17 : fSlot(-1) 18 , fRefCount(0) 19 , fBytesAllocated(0) { 20 } 21 22 SkBitmapHeapEntry::~SkBitmapHeapEntry() { 23 SkASSERT(0 == fRefCount); 24 } 25 26 void SkBitmapHeapEntry::addReferences(int count) { 27 if (0 == fRefCount) { 28 // If there are no current owners then the heap manager 29 // will be the only one able to modify it, so it does not 30 // need to be an atomic operation. 31 fRefCount = count; 32 } else { 33 sk_atomic_add(&fRefCount, count); 34 } 35 } 36 37 /////////////////////////////////////////////////////////////////////////////// 38 39 static bool operator<(const SkIPoint& a, const SkIPoint& b) { 40 return *(const int64_t*)&a < *(const int64_t*)&b; 41 } 42 43 static bool operator>(const SkIPoint& a, const SkIPoint& b) { 44 return *(const int64_t*)&a > *(const int64_t*)&b; 45 } 46 47 bool SkBitmapHeap::LookupEntry::Less(const SkBitmapHeap::LookupEntry& a, 48 const SkBitmapHeap::LookupEntry& b) { 49 if (a.fGenerationId < b.fGenerationId) { 50 return true; 51 } else if (a.fGenerationId > b.fGenerationId) { 52 return false; 53 } else if (a.fPixelOrigin < b.fPixelOrigin) { 54 return true; 55 } else if (a.fPixelOrigin > b.fPixelOrigin) { 56 return false; 57 } else if (a.fWidth < b.fWidth) { 58 return true; 59 } else if (a.fWidth > b.fWidth) { 60 return false; 61 } else if (a.fHeight < b.fHeight) { 62 return true; 63 } 64 return false; 65 } 66 67 /////////////////////////////////////////////////////////////////////////////// 68 69 SkBitmapHeap::SkBitmapHeap(int32_t preferredSize, int32_t ownerCount) 70 : INHERITED() 71 , fExternalStorage(NULL) 72 , fMostRecentlyUsed(NULL) 73 , fLeastRecentlyUsed(NULL) 74 , fPreferredCount(preferredSize) 75 , fOwnerCount(ownerCount) 76 , fBytesAllocated(0) 77 , fDeferAddingOwners(false) { 78 } 79 80 SkBitmapHeap::SkBitmapHeap(ExternalStorage* storage, int32_t preferredSize) 81 : INHERITED() 82 , fExternalStorage(storage) 83 , fMostRecentlyUsed(NULL) 84 , fLeastRecentlyUsed(NULL) 85 , fPreferredCount(preferredSize) 86 , fOwnerCount(IGNORE_OWNERS) 87 , fBytesAllocated(0) 88 , fDeferAddingOwners(false) { 89 SkSafeRef(storage); 90 } 91 92 SkBitmapHeap::~SkBitmapHeap() { 93 SkDEBUGCODE( 94 for (int i = 0; i < fStorage.count(); i++) { 95 bool unused = false; 96 for (int j = 0; j < fUnusedSlots.count(); j++) { 97 if (fUnusedSlots[j] == fStorage[i]->fSlot) { 98 unused = true; 99 break; 100 } 101 } 102 if (!unused) { 103 fBytesAllocated -= fStorage[i]->fBytesAllocated; 104 } 105 } 106 fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry)); 107 ) 108 SkASSERT(0 == fBytesAllocated); 109 fStorage.deleteAll(); 110 SkSafeUnref(fExternalStorage); 111 fLookupTable.deleteAll(); 112 } 113 114 SkTRefArray<SkBitmap>* SkBitmapHeap::extractBitmaps() const { 115 const int size = fStorage.count(); 116 SkTRefArray<SkBitmap>* array = NULL; 117 if (size > 0) { 118 array = SkTRefArray<SkBitmap>::Create(size); 119 for (int i = 0; i < size; i++) { 120 // make a shallow copy of the bitmap 121 array->writableAt(i) = fStorage[i]->fBitmap; 122 } 123 } 124 return array; 125 } 126 127 void SkBitmapHeap::removeFromLRU(SkBitmapHeap::LookupEntry* entry) { 128 if (fMostRecentlyUsed == entry) { 129 fMostRecentlyUsed = entry->fLessRecentlyUsed; 130 if (NULL == fMostRecentlyUsed) { 131 SkASSERT(fLeastRecentlyUsed == entry); 132 fLeastRecentlyUsed = NULL; 133 } else { 134 fMostRecentlyUsed->fMoreRecentlyUsed = NULL; 135 } 136 } else { 137 // Remove entry from its prior place, and make sure to cover the hole. 138 if (fLeastRecentlyUsed == entry) { 139 SkASSERT(entry->fMoreRecentlyUsed != NULL); 140 fLeastRecentlyUsed = entry->fMoreRecentlyUsed; 141 } 142 // Since we have already considered the case where entry is the most recently used, it must 143 // have a more recently used at this point. 144 SkASSERT(entry->fMoreRecentlyUsed != NULL); 145 entry->fMoreRecentlyUsed->fLessRecentlyUsed = entry->fLessRecentlyUsed; 146 147 if (entry->fLessRecentlyUsed != NULL) { 148 SkASSERT(fLeastRecentlyUsed != entry); 149 entry->fLessRecentlyUsed->fMoreRecentlyUsed = entry->fMoreRecentlyUsed; 150 } 151 } 152 entry->fMoreRecentlyUsed = NULL; 153 } 154 155 void SkBitmapHeap::appendToLRU(SkBitmapHeap::LookupEntry* entry) { 156 if (fMostRecentlyUsed != NULL) { 157 SkASSERT(NULL == fMostRecentlyUsed->fMoreRecentlyUsed); 158 fMostRecentlyUsed->fMoreRecentlyUsed = entry; 159 entry->fLessRecentlyUsed = fMostRecentlyUsed; 160 } 161 fMostRecentlyUsed = entry; 162 if (NULL == fLeastRecentlyUsed) { 163 fLeastRecentlyUsed = entry; 164 } 165 } 166 167 // iterate through our LRU cache and try to find an entry to evict 168 SkBitmapHeap::LookupEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& replacement) { 169 SkASSERT(fPreferredCount != UNLIMITED_SIZE); 170 SkASSERT(fStorage.count() >= fPreferredCount); 171 172 SkBitmapHeap::LookupEntry* iter = fLeastRecentlyUsed; 173 while (iter != NULL) { 174 SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot]; 175 if (heapEntry->fRefCount > 0) { 176 // If the least recently used bitmap has not been unreferenced 177 // by its owner, then according to our LRU specifications a more 178 // recently used one can not have used all its references yet either. 179 return NULL; 180 } 181 if (replacement.getGenerationID() == iter->fGenerationId) { 182 // Do not replace a bitmap with a new one using the same 183 // pixel ref. Instead look for a different one that will 184 // potentially free up more space. 185 iter = iter->fMoreRecentlyUsed; 186 } else { 187 return iter; 188 } 189 } 190 return NULL; 191 } 192 193 size_t SkBitmapHeap::freeMemoryIfPossible(size_t bytesToFree) { 194 if (UNLIMITED_SIZE == fPreferredCount) { 195 return 0; 196 } 197 LookupEntry* iter = fLeastRecentlyUsed; 198 size_t origBytesAllocated = fBytesAllocated; 199 // Purge starting from LRU until a non-evictable bitmap is found or until 200 // everything is evicted. 201 while (iter != NULL) { 202 SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot]; 203 if (heapEntry->fRefCount > 0) { 204 break; 205 } 206 LookupEntry* next = iter->fMoreRecentlyUsed; 207 this->removeEntryFromLookupTable(iter); 208 // Free the pixel memory. removeEntryFromLookupTable already reduced 209 // fBytesAllocated properly. 210 heapEntry->fBitmap.reset(); 211 // Add to list of unused slots which can be reused in the future. 212 fUnusedSlots.push(heapEntry->fSlot); 213 iter = next; 214 if (origBytesAllocated - fBytesAllocated >= bytesToFree) { 215 break; 216 } 217 } 218 219 if (fLeastRecentlyUsed != iter) { 220 // There was at least one eviction. 221 fLeastRecentlyUsed = iter; 222 if (NULL == fLeastRecentlyUsed) { 223 // Everything was evicted 224 fMostRecentlyUsed = NULL; 225 fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry)); 226 fStorage.deleteAll(); 227 fUnusedSlots.reset(); 228 SkASSERT(0 == fBytesAllocated); 229 } else { 230 fLeastRecentlyUsed->fLessRecentlyUsed = NULL; 231 } 232 } 233 234 return origBytesAllocated - fBytesAllocated; 235 } 236 237 int SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapEntry** entry) { 238 int index = SkTSearch<const LookupEntry, LookupEntry::Less>( 239 (const LookupEntry**)fLookupTable.begin(), 240 fLookupTable.count(), 241 &indexEntry, sizeof(void*)); 242 243 if (index < 0) { 244 // insert ourselves into the bitmapIndex 245 index = ~index; 246 *fLookupTable.insert(index) = SkNEW_ARGS(LookupEntry, (indexEntry)); 247 } else if (entry != NULL) { 248 // populate the entry if needed 249 *entry = fStorage[fLookupTable[index]->fStorageSlot]; 250 } 251 252 return index; 253 } 254 255 bool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap) { 256 SkASSERT(!fExternalStorage); 257 258 // If the bitmap is mutable, we need to do a deep copy, since the 259 // caller may modify it afterwards. 260 if (originalBitmap.isImmutable()) { 261 copiedBitmap = originalBitmap; 262 // TODO if we have the pixel ref in the heap we could pass it here to avoid a potential deep copy 263 // else if (sharedPixelRef != NULL) { 264 // copiedBitmap = orig; 265 // copiedBitmap.setPixelRef(sharedPixelRef, originalBitmap.pixelRefOffset()); 266 } else if (originalBitmap.empty()) { 267 copiedBitmap.reset(); 268 } else if (!originalBitmap.deepCopyTo(&copiedBitmap)) { 269 return false; 270 } 271 copiedBitmap.setImmutable(); 272 return true; 273 } 274 275 int SkBitmapHeap::removeEntryFromLookupTable(LookupEntry* entry) { 276 // remove the bitmap index for the deleted entry 277 SkDEBUGCODE(int count = fLookupTable.count();) 278 int index = this->findInLookupTable(*entry, NULL); 279 // Verify that findInLookupTable found an existing entry rather than adding 280 // a new entry to the lookup table. 281 SkASSERT(count == fLookupTable.count()); 282 fBytesAllocated -= fStorage[entry->fStorageSlot]->fBytesAllocated; 283 SkDELETE(fLookupTable[index]); 284 fLookupTable.remove(index); 285 return index; 286 } 287 288 int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) { 289 SkBitmapHeapEntry* entry = NULL; 290 int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entry); 291 292 if (entry) { 293 // Already had a copy of the bitmap in the heap. 294 if (fOwnerCount != IGNORE_OWNERS) { 295 if (fDeferAddingOwners) { 296 *fDeferredEntries.append() = entry->fSlot; 297 } else { 298 entry->addReferences(fOwnerCount); 299 } 300 } 301 if (fPreferredCount != UNLIMITED_SIZE) { 302 LookupEntry* lookupEntry = fLookupTable[searchIndex]; 303 if (lookupEntry != fMostRecentlyUsed) { 304 this->removeFromLRU(lookupEntry); 305 this->appendToLRU(lookupEntry); 306 } 307 } 308 return entry->fSlot; 309 } 310 311 // decide if we need to evict an existing heap entry or create a new one 312 if (fPreferredCount != UNLIMITED_SIZE && fStorage.count() >= fPreferredCount) { 313 // iterate through our LRU cache and try to find an entry to evict 314 LookupEntry* lookupEntry = this->findEntryToReplace(originalBitmap); 315 if (lookupEntry != NULL) { 316 // we found an entry to evict 317 entry = fStorage[lookupEntry->fStorageSlot]; 318 // Remove it from the LRU. The new entry will be added to the LRU later. 319 this->removeFromLRU(lookupEntry); 320 int index = this->removeEntryFromLookupTable(lookupEntry); 321 322 // update the current search index now that we have removed one 323 if (index < searchIndex) { 324 searchIndex--; 325 } 326 } 327 } 328 329 // if we didn't have an entry yet we need to create one 330 if (!entry) { 331 if (fPreferredCount != UNLIMITED_SIZE && fUnusedSlots.count() > 0) { 332 int slot; 333 fUnusedSlots.pop(&slot); 334 entry = fStorage[slot]; 335 } else { 336 entry = SkNEW(SkBitmapHeapEntry); 337 fStorage.append(1, &entry); 338 entry->fSlot = fStorage.count() - 1; 339 fBytesAllocated += sizeof(SkBitmapHeapEntry); 340 } 341 } 342 343 // create a copy of the bitmap 344 bool copySucceeded; 345 if (fExternalStorage) { 346 copySucceeded = fExternalStorage->insert(originalBitmap, entry->fSlot); 347 } else { 348 copySucceeded = copyBitmap(originalBitmap, entry->fBitmap); 349 } 350 351 // if the copy failed then we must abort 352 if (!copySucceeded) { 353 // delete the index 354 SkDELETE(fLookupTable[searchIndex]); 355 fLookupTable.remove(searchIndex); 356 // If entry is the last slot in storage, it is safe to delete it. 357 if (fStorage.count() - 1 == entry->fSlot) { 358 // free the slot 359 fStorage.remove(entry->fSlot); 360 fBytesAllocated -= sizeof(SkBitmapHeapEntry); 361 SkDELETE(entry); 362 } else { 363 fUnusedSlots.push(entry->fSlot); 364 } 365 return INVALID_SLOT; 366 } 367 368 // update the index with the appropriate slot in the heap 369 fLookupTable[searchIndex]->fStorageSlot = entry->fSlot; 370 371 // compute the space taken by this entry 372 // TODO if there is a shared pixel ref don't count it 373 // If the SkBitmap does not share an SkPixelRef with an SkBitmap already 374 // in the SharedHeap, also include the size of its pixels. 375 entry->fBytesAllocated = originalBitmap.getSize(); 376 377 // add the bytes from this entry to the total count 378 fBytesAllocated += entry->fBytesAllocated; 379 380 if (fOwnerCount != IGNORE_OWNERS) { 381 if (fDeferAddingOwners) { 382 *fDeferredEntries.append() = entry->fSlot; 383 } else { 384 entry->addReferences(fOwnerCount); 385 } 386 } 387 if (fPreferredCount != UNLIMITED_SIZE) { 388 this->appendToLRU(fLookupTable[searchIndex]); 389 } 390 return entry->fSlot; 391 } 392 393 void SkBitmapHeap::deferAddingOwners() { 394 fDeferAddingOwners = true; 395 } 396 397 void SkBitmapHeap::endAddingOwnersDeferral(bool add) { 398 if (add) { 399 for (int i = 0; i < fDeferredEntries.count(); i++) { 400 SkASSERT(fOwnerCount != IGNORE_OWNERS); 401 SkBitmapHeapEntry* heapEntry = this->getEntry(fDeferredEntries[i]); 402 SkASSERT(heapEntry != NULL); 403 heapEntry->addReferences(fOwnerCount); 404 } 405 } 406 fDeferAddingOwners = false; 407 fDeferredEntries.reset(); 408 } 409
