Make SkGPipe use SkBitmapHeap.

In the single process (or hypothetical cross process/shared address
space) mode, SkGPipe now uses SkBitmapHeap instead of SharedHeap.

Still need to use the shared heap for shaders as well as for cross
process.

TEST=PipeTest

Review URL: https://codereview.appspot.com/6461059

git-svn-id: http://skia.googlecode.com/svn/trunk@5008 2bbb7eff-a529-9590-31e7-b0007b416f81

2 files changed, 126 insertions, 25 deletions

diff --git a/src/core/SkBitmapHeap.cpp b/src/core/SkBitmapHeap.cpp
index 7cff8eaace..924264bf5c 100644
--- a/src/core/SkBitmapHeap.cpp
+++ b/src/core/SkBitmapHeap.cpp
@@ -55,9 +55,26 @@ SkBitmapHeap::SkBitmapHeap(ExternalStorage* storage, int32_t preferredSize)
     , fPreferredCount(preferredSize)
     , fOwnerCount(IGNORE_OWNERS)
     , fBytesAllocated(0) {
+    SkSafeRef(storage);
 }
 
 SkBitmapHeap::~SkBitmapHeap() {
+    SkDEBUGCODE(
+    for (int i = 0; i < fStorage.count(); i++) {
+        bool unused = false;
+        for (int j = 0; j < fUnusedSlots.count(); j++) {
+            if (fUnusedSlots[j] == fStorage[i]->fSlot) {
+                unused = true;
+                break;
+            }
+        }
+        if (!unused) {
+            fBytesAllocated -= fStorage[i]->fBytesAllocated;
+        }
+    }
+    fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
+    )
+    SkASSERT(0 == fBytesAllocated);
     fStorage.deleteAll();
     SkSafeUnref(fExternalStorage);
 }
@@ -132,15 +149,53 @@ SkBitmapHeapEntry* SkBitmapHeap::findEntryToReplace(const SkBitmap& replacement)
     return NULL;
 }
 
-int SkBitmapHeap::findInLookupTable(const SkBitmap& bitmap, SkBitmapHeapEntry** entry) {
-    LookupEntry indexEntry;
-    indexEntry.fGenerationId = bitmap.getGenerationID();
-    indexEntry.fPixelOffset = bitmap.pixelRefOffset();
-    indexEntry.fWidth = bitmap.width();
-    indexEntry.fHeight = bitmap.height();
+size_t SkBitmapHeap::freeMemoryIfPossible(size_t bytesToFree) {
+    if (UNLIMITED_SIZE == fPreferredCount) {
+        return 0;
+    }
+    SkBitmapHeapEntry* iter = fLeastRecentlyUsed;
+    size_t origBytesAllocated = fBytesAllocated;
+    // Purge starting from LRU until a non-evictable bitmap is found or until
+    // everything is evicted.
+    while (iter && 0 == iter->fRefCount) {
+        SkBitmapHeapEntry* next = iter->fMoreRecentlyUsed;
+        this->removeEntryFromLookupTable(*iter);
+        // Free the pixel memory. removeEntryFromLookupTable already reduced
+        // fBytesAllocated properly.
+        iter->fBitmap.reset();
+        // Add to list of unused slots which can be reused in the future.
+        fUnusedSlots.push(iter->fSlot);
+        // Remove its LRU pointers, so that it does not pretend it is already in
+        // the list the next time it is used.
+        iter->fMoreRecentlyUsed = iter->fLessRecentlyUsed = NULL;
+        iter = next;
+        if (origBytesAllocated - fBytesAllocated >= bytesToFree) {
+            break;
+        }
+    }
+
+    if (fLeastRecentlyUsed != iter) {
+        // There was at least one eviction.
+        fLeastRecentlyUsed = iter;
+        if (NULL == fLeastRecentlyUsed) {
+            // Everything was evicted
+            fMostRecentlyUsed = NULL;
+            fBytesAllocated -= (fStorage.count() * sizeof(SkBitmapHeapEntry));
+            fStorage.deleteAll();
+            fUnusedSlots.reset();
+            SkASSERT(0 == fBytesAllocated);
+        } else {
+            fLeastRecentlyUsed->fLessRecentlyUsed = NULL;
+        }
+    }
+    
+    return origBytesAllocated - fBytesAllocated;
+}
+
+int SkBitmapHeap::findInLookupTable(const LookupEntry& indexEntry, SkBitmapHeapEntry** entry) {
     int index = SkTSearch<const LookupEntry>(fLookupTable.begin(),
-                                                  fLookupTable.count(),
-                                                  indexEntry, sizeof(indexEntry));
+                                             fLookupTable.count(),
+                                             indexEntry, sizeof(indexEntry));
 
     if (index < 0) {
         // insert ourselves into the bitmapIndex
@@ -174,9 +229,25 @@ bool SkBitmapHeap::copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBi
     return true;
 }
 
+int SkBitmapHeap::removeEntryFromLookupTable(const SkBitmapHeapEntry& entry) {
+    // remove the bitmap index for the deleted entry
+    SkDEBUGCODE(int count = fLookupTable.count();)
+    // FIXME: If copying bitmaps retained the generation ID, we could
+    // just grab the generation ID from entry.fBitmap
+    LookupEntry key(entry.fBitmap, entry.fGenerationID);
+    int index = this->findInLookupTable(key, NULL);
+    // Verify that findInLookupTable found an existing entry rather than adding
+    // a new entry to the lookup table.
+    SkASSERT(count == fLookupTable.count());
+    
+    fLookupTable.remove(index);
+    fBytesAllocated -= entry.fBytesAllocated;
+    return index;
+}
+
 int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
     SkBitmapHeapEntry* entry = NULL;
-    int searchIndex = this->findInLookupTable(originalBitmap, &entry);
+    int searchIndex = this->findInLookupTable(LookupEntry(originalBitmap), &entry);
 
     // check to see if we already had a copy of the bitmap in the heap
     if (entry) {
@@ -195,13 +266,7 @@ int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
         entry = this->findEntryToReplace(originalBitmap);
         // we found an entry to evict
         if (entry) {
-            // remove the bitmap index for the deleted entry
-            SkDEBUGCODE(int count = fLookupTable.count();)
-            int index = findInLookupTable(entry->fBitmap, NULL);
-            SkASSERT(count == fLookupTable.count());
-
-            fLookupTable.remove(index);
-            fBytesAllocated -= entry->fBytesAllocated;
+            int index = this->removeEntryFromLookupTable(*entry);
 
             // update the current search index now that we have removed one
             if (index < searchIndex) {
@@ -212,10 +277,16 @@ int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
 
     // if we didn't have an entry yet we need to create one
     if (!entry) {
-        entry = SkNEW(SkBitmapHeapEntry);
-        fStorage.append(1, &entry);
-        entry->fSlot = fStorage.count() - 1;
-        fBytesAllocated += sizeof(SkBitmapHeapEntry);
+        if (fPreferredCount != UNLIMITED_SIZE && fUnusedSlots.count() > 0) {
+            int slot;
+            fUnusedSlots.pop(&slot);
+            entry = fStorage[slot];
+        } else {
+            entry = SkNEW(SkBitmapHeapEntry);
+            fStorage.append(1, &entry);
+            entry->fSlot = fStorage.count() - 1;
+            fBytesAllocated += sizeof(SkBitmapHeapEntry);
+        }
     }
 
     // create a copy of the bitmap
@@ -230,9 +301,13 @@ int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
     if (!copySucceeded) {
         // delete the index
         fLookupTable.remove(searchIndex);
-        // free the slot
-        fStorage.remove(entry->fSlot);
-        SkDELETE(entry);
+        // If entry is the last slot in storage, it is safe to delete it.
+        if (fStorage.count() - 1 == entry->fSlot) {
+            // free the slot
+            fStorage.remove(entry->fSlot);
+            fBytesAllocated -= sizeof(SkBitmapHeapEntry);
+            SkDELETE(entry);
+        }
         return INVALID_SLOT;
     }
 
@@ -248,6 +323,8 @@ int32_t SkBitmapHeap::insert(const SkBitmap& originalBitmap) {
     // add the bytes from this entry to the total count
     fBytesAllocated += entry->fBytesAllocated;
 
+    entry->fGenerationID = originalBitmap.getGenerationID();
+
     if (fOwnerCount != IGNORE_OWNERS) {
         entry->addReferences(fOwnerCount);
     }
diff --git a/src/core/SkBitmapHeap.h b/src/core/SkBitmapHeap.h
index bcfd0393c6..3c00b5211b 100644
--- a/src/core/SkBitmapHeap.h
+++ b/src/core/SkBitmapHeap.h
@@ -39,6 +39,7 @@ private:
 
     int32_t fSlot;
     int32_t fRefCount;
+    uint32_t fGenerationID;
 
     SkBitmap fBitmap;
     // Keep track of the bytes allocated for this bitmap. When replacing the
@@ -186,8 +187,22 @@ public:
         return fBytesAllocated;
     }
 
+    /**
+     * Attempt to reduce the storage allocated.
+     * @param bytesToFree minimum number of bytes that should be attempted to
+     *   be freed.
+     * @return number of bytes actually freed.
+     */
+    size_t freeMemoryIfPossible(size_t bytesToFree);
+
 private:
     struct LookupEntry {
+        LookupEntry(const SkBitmap& bm, uint32_t genId = 0) {
+            fGenerationId = 0 == genId ? bm.getGenerationID() : genId;
+            fPixelOffset = bm.pixelRefOffset();
+            fWidth = bm.width();
+            fHeight = bm.height();
+        }
         uint32_t fGenerationId; // SkPixelRef GenerationID.
         size_t fPixelOffset;
         uint32_t fWidth;
@@ -215,14 +230,20 @@ private:
     };
 
     /**
+     * Remove the entry from the lookup table.
+     * @return The index in the lookup table of the entry before removal.
+     */
+    int removeEntryFromLookupTable(const SkBitmapHeapEntry&);
+
+    /**
      * Searches for the bitmap in the lookup table and returns the bitmaps index within the table.
      * If the bitmap was not already in the table it is added.
      *
-     * @param bitmap  The bitmap we using as a key to search the lookup table
+     * @param key    The key to search the lookup table, created from a bitmap.
      * @param entry  A pointer to a SkBitmapHeapEntry* that if non-null AND the bitmap is found
      *               in the lookup table is populated with the entry from the heap storage.
      */
-    int findInLookupTable(const SkBitmap& bitmap, SkBitmapHeapEntry** entry);
+    int findInLookupTable(const LookupEntry& key, SkBitmapHeapEntry** entry);
 
     SkBitmapHeapEntry* findEntryToReplace(const SkBitmap& replacement);
     bool copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap);
@@ -233,6 +254,9 @@ private:
 
     // heap storage
     SkTDArray<SkBitmapHeapEntry*> fStorage;
+    // Used to mark slots in fStorage as deleted without actually deleting
+    // the slot so as not to mess up the numbering.
+    SkTDArray<int> fUnusedSlots;
     ExternalStorage* fExternalStorage;
 
     SkBitmapHeapEntry* fMostRecentlyUsed;