michael@0: 
michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #include "SkBitmapHeap.h"
michael@0: 
michael@0: #include "SkBitmap.h"
michael@0: #include "SkReadBuffer.h"
michael@0: #include "SkWriteBuffer.h"
michael@0: #include "SkTSearch.h"
michael@0: 
michael@0: SkBitmapHeapEntry::SkBitmapHeapEntry()
michael@0:     : fSlot(-1)
michael@0:     , fRefCount(0)
michael@0:     , fBytesAllocated(0) {
michael@0: }
michael@0: 
michael@0: SkBitmapHeapEntry::~SkBitmapHeapEntry() {
michael@0:     SkASSERT(0 == fRefCount);
michael@0: }
michael@0: 
michael@0: void SkBitmapHeapEntry::addReferences(int count) {
michael@0:     if (0 == fRefCount) {
michael@0:         // If there are no current owners then the heap manager
michael@0:         // will be the only one able to modify it, so it does not
michael@0:         // need to be an atomic operation.
michael@0:         fRefCount = count;
michael@0:     } else {
michael@0:         sk_atomic_add(&fRefCount, count);
michael@0:     }
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: static bool operator<(const SkIPoint& a, const SkIPoint& b) {
michael@0:     return *(const int64_t*)&a < *(const int64_t*)&b;
michael@0: }
michael@0: 
michael@0: static bool operator>(const SkIPoint& a, const SkIPoint& b) {
michael@0:     return *(const int64_t*)&a > *(const int64_t*)&b;
michael@0: }
michael@0: 
michael@0: bool SkBitmapHeap::LookupEntry::Less(const SkBitmapHeap::LookupEntry& a,
michael@0:                                      const SkBitmapHeap::LookupEntry& b) {
michael@0:     if (a.fGenerationId < b.fGenerationId) {
michael@0:         return true;
michael@0:     } else if (a.fGenerationId > b.fGenerationId) {
michael@0:         return false;
michael@0:     } else if (a.fPixelOrigin < b.fPixelOrigin) {
michael@0:         return true;
michael@0:     } else if (a.fPixelOrigin > b.fPixelOrigin) {
michael@0:         return false;
michael@0:     } else if (a.fWidth < b.fWidth) {
michael@0:         return true;
michael@0:     } else if (a.fWidth > b.fWidth) {
michael@0:         return false;
michael@0:     } else if (a.fHeight < b.fHeight) {
michael@0:         return true;
michael@0:     }
michael@0:     return false;
michael@0: }
michael@0: 
michael@0: ///////////////////////////////////////////////////////////////////////////////
michael@0: 
michael@0: SkBitmapHeap::SkBitmapHeap(int32_t preferredSize, int32_t ownerCount)
michael@0:     : INHERITED()
michael@0:     , fExternalStorage(NULL)
michael@0:     , fMostRecentlyUsed(NULL)
michael@0:     , fLeastRecentlyUsed(NULL)
michael@0:     , fPreferredCount(preferredSize)
michael@0:     , fOwnerCount(ownerCount)
michael@0:     , fBytesAllocated(0)
michael@0:     , fDeferAddingOwners(false) {
michael@0: }
michael@0: 
michael@0: SkBitmapHeap::SkBitmapHeap(ExternalStorage* storage, int32_t preferredSize)
michael@0:     : INHERITED()
michael@0:     , fExternalStorage(storage)
michael@0:     , fMostRecentlyUsed(NULL)
michael@0:     , fLeastRecentlyUsed(NULL)
michael@0:     , fPreferredCount(preferredSize)
michael@0:     , fOwnerCount(IGNORE_OWNERS)
michael@0:     , fBytesAllocated(0)
michael@0:     , fDeferAddingOwners(false) {
michael@0:     SkSafeRef(storage);
michael@0: }
michael@0: 
michael@0: SkBitmapHeap::~SkBitmapHeap() {
michael@0:     SkDEBUGCODE(
michael@0:     for (int i = 0; i < fStorage.count(); i++) {
michael@0:         bool unused = false;
michael@0:         for (int j = 0; j < fUnusedSlots.count(); j++) {
michael@0:             if (fUnusedSlots[j] == fStorage[i]->fSlot) {
michael@0:                 unused = true;
michael@0:                 break;
michael@0:             }
michael@0:         }
michael@0:         if (!unused) {
michael@0:             fBytesAllocated -= fStorage[i]->fBytesAllocated;
michael@0:         }
michael@0:     }
michael@0:     fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
michael@0:     )
michael@0:     SkASSERT(0 == fBytesAllocated);
michael@0:     fStorage.deleteAll();
michael@0:     SkSafeUnref(fExternalStorage);
michael@0:     fLookupTable.deleteAll();
michael@0: }
michael@0: 
michael@0: SkTRefArray<SkBitmap>* SkBitmapHeap::extractBitmaps() const {
michael@0:     const int size = fStorage.count();
michael@0:     SkTRefArray<SkBitmap>* array = NULL;
michael@0:     if (size > 0) {
michael@0:         array = SkTRefArray<SkBitmap>::Create(size);
michael@0:         for (int i = 0; i < size; i++) {
michael@0:             // make a shallow copy of the bitmap
michael@0:             array->writableAt(i) = fStorage[i]->fBitmap;
michael@0:         }
michael@0:     }
michael@0:     return array;
michael@0: }
michael@0: 
michael@0: void SkBitmapHeap::removeFromLRU(SkBitmapHeap::LookupEntry* entry) {
michael@0:     if (fMostRecentlyUsed == entry) {
michael@0:         fMostRecentlyUsed = entry->fLessRecentlyUsed;
michael@0:         if (NULL == fMostRecentlyUsed) {
michael@0:             SkASSERT(fLeastRecentlyUsed == entry);
michael@0:             fLeastRecentlyUsed = NULL;
michael@0:         } else {
michael@0:             fMostRecentlyUsed->fMoreRecentlyUsed = NULL;
michael@0:         }
michael@0:     } else {
michael@0:         // Remove entry from its prior place, and make sure to cover the hole.
michael@0:         if (fLeastRecentlyUsed == entry) {
michael@0:             SkASSERT(entry->fMoreRecentlyUsed != NULL);
michael@0:             fLeastRecentlyUsed = entry->fMoreRecentlyUsed;
michael@0:         }
michael@0:         // Since we have already considered the case where entry is the most recently used, it must
michael@0:         // have a more recently used at this point.
michael@0:         SkASSERT(entry->fMoreRecentlyUsed != NULL);
michael@0:         entry->fMoreRecentlyUsed->fLessRecentlyUsed = entry->fLessRecentlyUsed;
michael@0: 
michael@0:         if (entry->fLessRecentlyUsed != NULL) {
michael@0:             SkASSERT(fLeastRecentlyUsed != entry);
michael@0:             entry->fLessRecentlyUsed->fMoreRecentlyUsed = entry->fMoreRecentlyUsed;
michael@0:         }
michael@0:     }
michael@0:     entry->fMoreRecentlyUsed = NULL;
michael@0: }
michael@0: 
michael@0: void SkBitmapHeap::appendToLRU(SkBitmapHeap::LookupEntry* entry) {
michael@0:     if (fMostRecentlyUsed != NULL) {
michael@0:         SkASSERT(NULL == fMostRecentlyUsed->fMoreRecentlyUsed);
michael@0:         fMostRecentlyUsed->fMoreRecentlyUsed = entry;
michael@0:         entry->fLessRecentlyUsed = fMostRecentlyUsed;
michael@0:     }
michael@0:     fMostRecentlyUsed = entry;
michael@0:     if (NULL == fLeastRecentlyUsed) {
michael@0:         fLeastRecentlyUsed = entry;
michael@0:     }
michael@0: }
michael@0: 
michael@0: // iterate through our LRU cache and try to find an entry to evict
michael@0: SkBitmapHeap::LookupEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& replacement) {
michael@0:     SkASSERT(fPreferredCount != UNLIMITED_SIZE);
michael@0:     SkASSERT(fStorage.count() >= fPreferredCount);
michael@0: 
michael@0:     SkBitmapHeap::LookupEntry* iter = fLeastRecentlyUsed;
michael@0:     while (iter != NULL) {
michael@0:         SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot];
michael@0:         if (heapEntry->fRefCount > 0) {
michael@0:             // If the least recently used bitmap has not been unreferenced
michael@0:             // by its owner, then according to our LRU specifications a more
michael@0:             // recently used one can not have used all its references yet either.
michael@0:             return NULL;
michael@0:         }
michael@0:         if (replacement.getGenerationID() == iter->fGenerationId) {
michael@0:             // Do not replace a bitmap with a new one using the same
michael@0:             // pixel ref. Instead look for a different one that will
michael@0:             // potentially free up more space.
michael@0:             iter = iter->fMoreRecentlyUsed;
michael@0:         } else {
michael@0:             return iter;
michael@0:         }
michael@0:     }
michael@0:     return NULL;
michael@0: }
michael@0: 
michael@0: size_t SkBitmapHeap::freeMemoryIfPossible(size_t bytesToFree) {
michael@0:     if (UNLIMITED_SIZE == fPreferredCount) {
michael@0:         return 0;
michael@0:     }
michael@0:     LookupEntry* iter = fLeastRecentlyUsed;
michael@0:     size_t origBytesAllocated = fBytesAllocated;
michael@0:     // Purge starting from LRU until a non-evictable bitmap is found or until
michael@0:     // everything is evicted.
michael@0:     while (iter != NULL) {
michael@0:         SkBitmapHeapEntry* heapEntry = fStorage[iter->fStorageSlot];
michael@0:         if (heapEntry->fRefCount > 0) {
michael@0:             break;
michael@0:         }
michael@0:         LookupEntry* next = iter->fMoreRecentlyUsed;
michael@0:         this->removeEntryFromLookupTable(iter);
michael@0:         // Free the pixel memory. removeEntryFromLookupTable already reduced
michael@0:         // fBytesAllocated properly.
michael@0:         heapEntry->fBitmap.reset();
michael@0:         // Add to list of unused slots which can be reused in the future.
michael@0:         fUnusedSlots.push(heapEntry->fSlot);
michael@0:         iter = next;
michael@0:         if (origBytesAllocated - fBytesAllocated >= bytesToFree) {
michael@0:             break;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     if (fLeastRecentlyUsed != iter) {
michael@0:         // There was at least one eviction.
michael@0:         fLeastRecentlyUsed = iter;
michael@0:         if (NULL == fLeastRecentlyUsed) {
michael@0:             // Everything was evicted
michael@0:             fMostRecentlyUsed = NULL;
michael@0:             fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
michael@0:             fStorage.deleteAll();
michael@0:             fUnusedSlots.reset();
michael@0:             SkASSERT(0 == fBytesAllocated);
michael@0:         } else {
michael@0:             fLeastRecentlyUsed->fLessRecentlyUsed = NULL;
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     return origBytesAllocated - fBytesAllocated;
michael@0: }
michael@0: 
michael@0: int SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapEntry** entry) {
michael@0:     int index = SkTSearch<const LookupEntry, LookupEntry::Less>(
michael@0:                                              (const LookupEntry**)fLookupTable.begin(),
michael@0:                                              fLookupTable.count(),
michael@0:                                              &indexEntry, sizeof(void*));
michael@0: 
michael@0:     if (index < 0) {
michael@0:         // insert ourselves into the bitmapIndex
michael@0:         index = ~index;
michael@0:         *fLookupTable.insert(index) = SkNEW_ARGS(LookupEntry, (indexEntry));
michael@0:     } else if (entry != NULL) {
michael@0:         // populate the entry if needed
michael@0:         *entry = fStorage[fLookupTable[index]->fStorageSlot];
michael@0:     }
michael@0: 
michael@0:     return index;
michael@0: }
michael@0: 
michael@0: bool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap) {
michael@0:     SkASSERT(!fExternalStorage);
michael@0: 
michael@0:     // If the bitmap is mutable, we need to do a deep copy, since the
michael@0:     // caller may modify it afterwards.
michael@0:     if (originalBitmap.isImmutable()) {
michael@0:         copiedBitmap = originalBitmap;
michael@0: // TODO if we have the pixel ref in the heap we could pass it here to avoid a potential deep copy
michael@0: //    else if (sharedPixelRef != NULL) {
michael@0: //        copiedBitmap = orig;
michael@0: //        copiedBitmap.setPixelRef(sharedPixelRef, originalBitmap.pixelRefOffset());
michael@0:     } else if (originalBitmap.empty()) {
michael@0:         copiedBitmap.reset();
michael@0:     } else if (!originalBitmap.deepCopyTo(&copiedBitmap)) {
michael@0:         return false;
michael@0:     }
michael@0:     copiedBitmap.setImmutable();
michael@0:     return true;
michael@0: }
michael@0: 
michael@0: int SkBitmapHeap::removeEntryFromLookupTable(LookupEntry* entry) {
michael@0:     // remove the bitmap index for the deleted entry
michael@0:     SkDEBUGCODE(int count = fLookupTable.count();)
michael@0:     int index = this->findInLookupTable(*entry, NULL);
michael@0:     // Verify that findInLookupTable found an existing entry rather than adding
michael@0:     // a new entry to the lookup table.
michael@0:     SkASSERT(count == fLookupTable.count());
michael@0:     fBytesAllocated -= fStorage[entry->fStorageSlot]->fBytesAllocated;
michael@0:     SkDELETE(fLookupTable[index]);
michael@0:     fLookupTable.remove(index);
michael@0:     return index;
michael@0: }
michael@0: 
michael@0: int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
michael@0:     SkBitmapHeapEntry* entry = NULL;
michael@0:     int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entry);
michael@0: 
michael@0:     if (entry) {
michael@0:         // Already had a copy of the bitmap in the heap.
michael@0:         if (fOwnerCount != IGNORE_OWNERS) {
michael@0:             if (fDeferAddingOwners) {
michael@0:                 *fDeferredEntries.append() = entry->fSlot;
michael@0:             } else {
michael@0:                 entry->addReferences(fOwnerCount);
michael@0:             }
michael@0:         }
michael@0:         if (fPreferredCount != UNLIMITED_SIZE) {
michael@0:             LookupEntry* lookupEntry = fLookupTable[searchIndex];
michael@0:             if (lookupEntry != fMostRecentlyUsed) {
michael@0:                 this->removeFromLRU(lookupEntry);
michael@0:                 this->appendToLRU(lookupEntry);
michael@0:             }
michael@0:         }
michael@0:         return entry->fSlot;
michael@0:     }
michael@0: 
michael@0:     // decide if we need to evict an existing heap entry or create a new one
michael@0:     if (fPreferredCount != UNLIMITED_SIZE && fStorage.count() >= fPreferredCount) {
michael@0:         // iterate through our LRU cache and try to find an entry to evict
michael@0:         LookupEntry* lookupEntry = this->findEntryToReplace(originalBitmap);
michael@0:         if (lookupEntry != NULL) {
michael@0:             // we found an entry to evict
michael@0:             entry = fStorage[lookupEntry->fStorageSlot];
michael@0:             // Remove it from the LRU. The new entry will be added to the LRU later.
michael@0:             this->removeFromLRU(lookupEntry);
michael@0:             int index = this->removeEntryFromLookupTable(lookupEntry);
michael@0: 
michael@0:             // update the current search index now that we have removed one
michael@0:             if (index < searchIndex) {
michael@0:                 searchIndex--;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // if we didn't have an entry yet we need to create one
michael@0:     if (!entry) {
michael@0:         if (fPreferredCount != UNLIMITED_SIZE && fUnusedSlots.count() > 0) {
michael@0:             int slot;
michael@0:             fUnusedSlots.pop(&slot);
michael@0:             entry = fStorage[slot];
michael@0:         } else {
michael@0:             entry = SkNEW(SkBitmapHeapEntry);
michael@0:             fStorage.append(1, &entry);
michael@0:             entry->fSlot = fStorage.count() - 1;
michael@0:             fBytesAllocated += sizeof(SkBitmapHeapEntry);
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     // create a copy of the bitmap
michael@0:     bool copySucceeded;
michael@0:     if (fExternalStorage) {
michael@0:         copySucceeded = fExternalStorage->insert(originalBitmap, entry->fSlot);
michael@0:     } else {
michael@0:         copySucceeded = copyBitmap(originalBitmap, entry->fBitmap);
michael@0:     }
michael@0: 
michael@0:     // if the copy failed then we must abort
michael@0:     if (!copySucceeded) {
michael@0:         // delete the index
michael@0:         SkDELETE(fLookupTable[searchIndex]);
michael@0:         fLookupTable.remove(searchIndex);
michael@0:         // If entry is the last slot in storage, it is safe to delete it.
michael@0:         if (fStorage.count() - 1 == entry->fSlot) {
michael@0:             // free the slot
michael@0:             fStorage.remove(entry->fSlot);
michael@0:             fBytesAllocated -= sizeof(SkBitmapHeapEntry);
michael@0:             SkDELETE(entry);
michael@0:         } else {
michael@0:             fUnusedSlots.push(entry->fSlot);
michael@0:         }
michael@0:         return INVALID_SLOT;
michael@0:     }
michael@0: 
michael@0:     // update the index with the appropriate slot in the heap
michael@0:     fLookupTable[searchIndex]->fStorageSlot = entry->fSlot;
michael@0: 
michael@0:     // compute the space taken by this entry
michael@0:     // TODO if there is a shared pixel ref don't count it
michael@0:     // If the SkBitmap does not share an SkPixelRef with an SkBitmap already
michael@0:     // in the SharedHeap, also include the size of its pixels.
michael@0:     entry->fBytesAllocated = originalBitmap.getSize();
michael@0: 
michael@0:     // add the bytes from this entry to the total count
michael@0:     fBytesAllocated += entry->fBytesAllocated;
michael@0: 
michael@0:     if (fOwnerCount != IGNORE_OWNERS) {
michael@0:         if (fDeferAddingOwners) {
michael@0:             *fDeferredEntries.append() = entry->fSlot;
michael@0:         } else {
michael@0:             entry->addReferences(fOwnerCount);
michael@0:         }
michael@0:     }
michael@0:     if (fPreferredCount != UNLIMITED_SIZE) {
michael@0:         this->appendToLRU(fLookupTable[searchIndex]);
michael@0:     }
michael@0:     return entry->fSlot;
michael@0: }
michael@0: 
michael@0: void SkBitmapHeap::deferAddingOwners() {
michael@0:     fDeferAddingOwners = true;
michael@0: }
michael@0: 
michael@0: void SkBitmapHeap::endAddingOwnersDeferral(bool add) {
michael@0:     if (add) {
michael@0:         for (int i = 0; i < fDeferredEntries.count(); i++) {
michael@0:             SkASSERT(fOwnerCount != IGNORE_OWNERS);
michael@0:             SkBitmapHeapEntry* heapEntry = this->getEntry(fDeferredEntries[i]);
michael@0:             SkASSERT(heapEntry != NULL);
michael@0:             heapEntry->addReferences(fOwnerCount);
michael@0:         }
michael@0:     }
michael@0:     fDeferAddingOwners = false;
michael@0:     fDeferredEntries.reset();
michael@0: }