The Tor Browser / file revision

 /*

  * Copyright 2012 Google Inc.

  *

  * Use of this source code is governed by a BSD-style license that can be

  * found in the LICENSE file.

  */

 #ifndef SkBitmapHeap_DEFINED

 #define SkBitmapHeap_DEFINED

 #include "SkBitmap.h"

 #include "SkFlattenable.h"

 #include "SkRefCnt.h"

 #include "SkTDArray.h"

 #include "SkThread.h"

 #include "SkTRefArray.h"

 /**

  * SkBitmapHeapEntry provides users of SkBitmapHeap (using internal storage) with a means to...

  *  (1) get access a bitmap in the heap

  *  (2) indicate they are done with bitmap by releasing their reference (if they were an owner).

  */

 class SkBitmapHeapEntry : SkNoncopyable {

 public:

     ~SkBitmapHeapEntry();

     int32_t getSlot() { return fSlot; }

     SkBitmap* getBitmap() { return &fBitmap; }

     void releaseRef() {

         sk_atomic_dec(&fRefCount);

     }

 private:

     SkBitmapHeapEntry();

     void addReferences(int count);

     int32_t fSlot;

     int32_t fRefCount;

     SkBitmap fBitmap;

     // Keep track of the bytes allocated for this bitmap. When replacing the

     // bitmap or removing this HeapEntry we know how much memory has been

     // reclaimed.

     size_t fBytesAllocated;

     friend class SkBitmapHeap;

     friend class SkBitmapHeapTester;

 };

 class SkBitmapHeapReader : public SkRefCnt {

 public:

     SK_DECLARE_INST_COUNT(SkBitmapHeapReader)

     SkBitmapHeapReader() : INHERITED() {}

     virtual SkBitmap* getBitmap(int32_t slot) const = 0;

     virtual void releaseRef(int32_t slot) = 0;

 private:

     typedef SkRefCnt INHERITED;

 };

 /**

  * TODO: stores immutable bitmaps into a heap

  */

 class SkBitmapHeap : public SkBitmapHeapReader {

 public:

     class ExternalStorage : public SkRefCnt {

      public:

         SK_DECLARE_INST_COUNT(ExternalStorage)

         virtual bool insert(const SkBitmap& bitmap, int32_t slot) = 0;

      private:

         typedef SkRefCnt INHERITED;

     };

     static const int32_t UNLIMITED_SIZE = -1;

     static const int32_t IGNORE_OWNERS  = -1;

     static const int32_t INVALID_SLOT   = -1;

     /**

      * Constructs a heap that is responsible for allocating and managing its own storage.  In the

      * case where we choose to allow the heap to grow indefinitely (i.e. UNLIMITED_SIZE) we

      * guarantee that once allocated in the heap a bitmap's index in the heap is immutable.

      * Otherwise we guarantee the bitmaps placement in the heap until its owner count goes to zero.

      *

      * @param preferredSize  Specifies the preferred maximum number of bitmaps to store. This is

      *   not a hard limit as it can grow larger if the number of bitmaps in the heap with active

      *   owners exceeds this limit.

      * @param ownerCount  The number of owners to assign to each inserted bitmap. NOTE: while a

      *   bitmap in the heap has a least one owner it can't be removed.

      */

     SkBitmapHeap(int32_t preferredSize = UNLIMITED_SIZE, int32_t ownerCount = IGNORE_OWNERS);

     /**

      * Constructs a heap that defers the responsibility of storing the bitmaps to an external

      * function. This is especially useful if the bitmaps will be used in a separate process as the

      * external storage can ensure the data is properly shuttled to the appropriate processes.

      *

      * Our LRU implementation assumes that inserts into the external storage are consumed in the

      * order that they are inserted (i.e. SkPipe). This ensures that we don't need to query the

      * external storage to see if a slot in the heap is eligible to be overwritten.

      *

      * @param externalStorage  The class responsible for storing the bitmaps inserted into the heap

      * @param heapSize  The maximum size of the heap. Because of the sequential limitation imposed

      *   by our LRU implementation we can guarantee that the heap will never grow beyond this size.

      */

     SkBitmapHeap(ExternalStorage* externalStorage, int32_t heapSize = UNLIMITED_SIZE);

     virtual ~SkBitmapHeap();

     /**

      * Makes a shallow copy of all bitmaps currently in the heap and returns them as an array. The

      * array indices match their position in the heap.

      *

      * @return  a ptr to an array of bitmaps or NULL if external storage is being used.

      */

     SkTRefArray<SkBitmap>* extractBitmaps() const;

     /**

      * Retrieves the bitmap from the specified slot in the heap

      *

      * @return  The bitmap located at that slot or NULL if external storage is being used.

      */

     virtual SkBitmap* getBitmap(int32_t slot) const SK_OVERRIDE {

         SkASSERT(fExternalStorage == NULL);

         SkBitmapHeapEntry* entry = getEntry(slot);

         if (entry) {

             return &entry->fBitmap;

         }

         return NULL;

     }

     /**

      * Retrieves the bitmap from the specified slot in the heap

      *

      * @return  The bitmap located at that slot or NULL if external storage is being used.

      */

     virtual void releaseRef(int32_t slot) SK_OVERRIDE {

         SkASSERT(fExternalStorage == NULL);

         if (fOwnerCount != IGNORE_OWNERS) {

             SkBitmapHeapEntry* entry = getEntry(slot);

             if (entry) {

                 entry->releaseRef();

             }

         }

     }

     /**

      * Inserts a bitmap into the heap. The stored version of bitmap is guaranteed to be immutable

      * and is not dependent on the lifecycle of the provided bitmap.

      *

      * @param bitmap  the bitmap to be inserted into the heap

      * @return  the slot in the heap where the bitmap is stored or INVALID_SLOT if the bitmap could

      *          not be added to the heap. If it was added the slot will remain valid...

      *            (1) indefinitely if no owner count has been specified.

      *            (2) until all owners have called releaseRef on the appropriate SkBitmapHeapEntry*

      */

     int32_t insert(const SkBitmap& bitmap);

     /**

      * Retrieves an entry from the heap at a given slot.

      *

      * @param slot  the slot in the heap where a bitmap was stored.

      * @return  a SkBitmapHeapEntry that wraps the bitmap or NULL if external storage is used.

      */

     SkBitmapHeapEntry* getEntry(int32_t slot) const {

         SkASSERT(slot <= fStorage.count());

         if (fExternalStorage != NULL) {

             return NULL;

         }

         return fStorage[slot];

     }

     /**

      * Returns a count of the number of items currently in the heap

      */

     int count() const {

         SkASSERT(fExternalStorage != NULL ||

                  fStorage.count() - fUnusedSlots.count() == fLookupTable.count());

         return fLookupTable.count();

     }

     /**

      * Returns the total number of bytes allocated by the bitmaps in the heap

      */

     size_t bytesAllocated() const {

         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);

     /**

      * Defer any increments of owner counts until endAddingOwnersDeferral is called. So if an

      * existing SkBitmap is inserted into the SkBitmapHeap, its corresponding SkBitmapHeapEntry will

      * not have addReferences called on it, and the client does not need to make a corresponding

      * call to releaseRef. Only meaningful if this SkBitmapHeap was created with an owner count not

      * equal to IGNORE_OWNERS.

      */

     void deferAddingOwners();

     /**

      * Resume adding references when duplicate SkBitmaps are inserted.

      * @param add If true, add references to the SkBitmapHeapEntrys whose SkBitmaps were re-inserted

      *            while deferring.

      */

     void endAddingOwnersDeferral(bool add);

 private:

     struct LookupEntry {

         LookupEntry(const SkBitmap& bm)

         : fGenerationId(bm.getGenerationID())

         , fPixelOrigin(bm.pixelRefOrigin())

         , fWidth(bm.width())

         , fHeight(bm.height())

         , fMoreRecentlyUsed(NULL)

         , fLessRecentlyUsed(NULL){}

         const uint32_t fGenerationId; // SkPixelRef GenerationID.

         const SkIPoint fPixelOrigin;

         const uint32_t fWidth;

         const uint32_t fHeight;

         // TODO: Generalize the LRU caching mechanism

         LookupEntry* fMoreRecentlyUsed;

         LookupEntry* fLessRecentlyUsed;

         uint32_t fStorageSlot; // slot of corresponding bitmap in fStorage.

         /**

          * Compare two LookupEntry pointers for sorting and searching.

          */

         static bool Less(const LookupEntry& a, const LookupEntry& b);

     };

     /**

      * Remove the entry from the lookup table. Also deletes the entry pointed

      * to by the table. Therefore, if a pointer to that one was passed in, the

      * pointer should no longer be used, since the object to which it points has

      * been deleted.

      * @return The index in the lookup table of the entry before removal.

      */

     int removeEntryFromLookupTable(LookupEntry*);

     /**

      * 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 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 LookupEntry& key, SkBitmapHeapEntry** entry);

     LookupEntry* findEntryToReplace(const SkBitmap& replacement);

     bool copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap);

     /**

      * Remove a LookupEntry from the LRU, in preparation for either deleting or appending as most

      * recent. Points the LookupEntry's old neighbors at each other, and sets fLeastRecentlyUsed

      * (if there is still an entry left). Sets LookupEntry's fMoreRecentlyUsed to NULL and leaves

      * its fLessRecentlyUsed unmodified.

      */

     void removeFromLRU(LookupEntry* entry);

     /**

      * Append a LookupEntry to the end of the LRU cache, marking it as the most

      * recently used. Assumes that the LookupEntry is already in fLookupTable,

      * but is not in the LRU cache. If it is in the cache, removeFromLRU should

      * be called first.

      */

     void appendToLRU(LookupEntry*);

     // searchable index that maps to entries in the heap

     SkTDArray<LookupEntry*> fLookupTable;

     // 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;

     LookupEntry* fMostRecentlyUsed;

     LookupEntry* fLeastRecentlyUsed;

     const int32_t fPreferredCount;

     const int32_t fOwnerCount;

     size_t fBytesAllocated;

     bool fDeferAddingOwners;

     SkTDArray<int> fDeferredEntries;

     typedef SkBitmapHeapReader INHERITED;

 };

 #endif // SkBitmapHeap_DEFINED