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: #ifndef SkBitmapHeap_DEFINED
michael@0: #define SkBitmapHeap_DEFINED
michael@0: 
michael@0: #include "SkBitmap.h"
michael@0: #include "SkFlattenable.h"
michael@0: #include "SkRefCnt.h"
michael@0: #include "SkTDArray.h"
michael@0: #include "SkThread.h"
michael@0: #include "SkTRefArray.h"
michael@0: 
michael@0: /**
michael@0:  * SkBitmapHeapEntry provides users of SkBitmapHeap (using internal storage) with a means to...
michael@0:  *  (1) get access a bitmap in the heap
michael@0:  *  (2) indicate they are done with bitmap by releasing their reference (if they were an owner).
michael@0:  */
michael@0: class SkBitmapHeapEntry : SkNoncopyable {
michael@0: public:
michael@0:     ~SkBitmapHeapEntry();
michael@0: 
michael@0:     int32_t getSlot() { return fSlot; }
michael@0: 
michael@0:     SkBitmap* getBitmap() { return &fBitmap; }
michael@0: 
michael@0:     void releaseRef() {
michael@0:         sk_atomic_dec(&fRefCount);
michael@0:     }
michael@0: 
michael@0: private:
michael@0:     SkBitmapHeapEntry();
michael@0: 
michael@0:     void addReferences(int count);
michael@0: 
michael@0:     int32_t fSlot;
michael@0:     int32_t fRefCount;
michael@0: 
michael@0:     SkBitmap fBitmap;
michael@0:     // Keep track of the bytes allocated for this bitmap. When replacing the
michael@0:     // bitmap or removing this HeapEntry we know how much memory has been
michael@0:     // reclaimed.
michael@0:     size_t fBytesAllocated;
michael@0: 
michael@0:     friend class SkBitmapHeap;
michael@0:     friend class SkBitmapHeapTester;
michael@0: };
michael@0: 
michael@0: 
michael@0: class SkBitmapHeapReader : public SkRefCnt {
michael@0: public:
michael@0:     SK_DECLARE_INST_COUNT(SkBitmapHeapReader)
michael@0: 
michael@0:     SkBitmapHeapReader() : INHERITED() {}
michael@0:     virtual SkBitmap* getBitmap(int32_t slot) const = 0;
michael@0:     virtual void releaseRef(int32_t slot) = 0;
michael@0: private:
michael@0:     typedef SkRefCnt INHERITED;
michael@0: };
michael@0: 
michael@0: 
michael@0: /**
michael@0:  * TODO: stores immutable bitmaps into a heap
michael@0:  */
michael@0: class SkBitmapHeap : public SkBitmapHeapReader {
michael@0: public:
michael@0:     class ExternalStorage : public SkRefCnt {
michael@0:      public:
michael@0:         SK_DECLARE_INST_COUNT(ExternalStorage)
michael@0: 
michael@0:         virtual bool insert(const SkBitmap& bitmap, int32_t slot) = 0;
michael@0: 
michael@0:      private:
michael@0:         typedef SkRefCnt INHERITED;
michael@0:     };
michael@0: 
michael@0:     static const int32_t UNLIMITED_SIZE = -1;
michael@0:     static const int32_t IGNORE_OWNERS  = -1;
michael@0:     static const int32_t INVALID_SLOT   = -1;
michael@0: 
michael@0:     /**
michael@0:      * Constructs a heap that is responsible for allocating and managing its own storage.  In the
michael@0:      * case where we choose to allow the heap to grow indefinitely (i.e. UNLIMITED_SIZE) we
michael@0:      * guarantee that once allocated in the heap a bitmap's index in the heap is immutable.
michael@0:      * Otherwise we guarantee the bitmaps placement in the heap until its owner count goes to zero.
michael@0:      *
michael@0:      * @param preferredSize  Specifies the preferred maximum number of bitmaps to store. This is
michael@0:      *   not a hard limit as it can grow larger if the number of bitmaps in the heap with active
michael@0:      *   owners exceeds this limit.
michael@0:      * @param ownerCount  The number of owners to assign to each inserted bitmap. NOTE: while a
michael@0:      *   bitmap in the heap has a least one owner it can't be removed.
michael@0:      */
michael@0:     SkBitmapHeap(int32_t preferredSize = UNLIMITED_SIZE, int32_t ownerCount = IGNORE_OWNERS);
michael@0: 
michael@0:     /**
michael@0:      * Constructs a heap that defers the responsibility of storing the bitmaps to an external
michael@0:      * function. This is especially useful if the bitmaps will be used in a separate process as the
michael@0:      * external storage can ensure the data is properly shuttled to the appropriate processes.
michael@0:      *
michael@0:      * Our LRU implementation assumes that inserts into the external storage are consumed in the
michael@0:      * order that they are inserted (i.e. SkPipe). This ensures that we don't need to query the
michael@0:      * external storage to see if a slot in the heap is eligible to be overwritten.
michael@0:      *
michael@0:      * @param externalStorage  The class responsible for storing the bitmaps inserted into the heap
michael@0:      * @param heapSize  The maximum size of the heap. Because of the sequential limitation imposed
michael@0:      *   by our LRU implementation we can guarantee that the heap will never grow beyond this size.
michael@0:      */
michael@0:     SkBitmapHeap(ExternalStorage* externalStorage, int32_t heapSize = UNLIMITED_SIZE);
michael@0: 
michael@0:     virtual ~SkBitmapHeap();
michael@0: 
michael@0:     /**
michael@0:      * Makes a shallow copy of all bitmaps currently in the heap and returns them as an array. The
michael@0:      * array indices match their position in the heap.
michael@0:      *
michael@0:      * @return  a ptr to an array of bitmaps or NULL if external storage is being used.
michael@0:      */
michael@0:     SkTRefArray<SkBitmap>* extractBitmaps() const;
michael@0: 
michael@0:     /**
michael@0:      * Retrieves the bitmap from the specified slot in the heap
michael@0:      *
michael@0:      * @return  The bitmap located at that slot or NULL if external storage is being used.
michael@0:      */
michael@0:     virtual SkBitmap* getBitmap(int32_t slot) const SK_OVERRIDE {
michael@0:         SkASSERT(fExternalStorage == NULL);
michael@0:         SkBitmapHeapEntry* entry = getEntry(slot);
michael@0:         if (entry) {
michael@0:             return &entry->fBitmap;
michael@0:         }
michael@0:         return NULL;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Retrieves the bitmap from the specified slot in the heap
michael@0:      *
michael@0:      * @return  The bitmap located at that slot or NULL if external storage is being used.
michael@0:      */
michael@0:     virtual void releaseRef(int32_t slot) SK_OVERRIDE {
michael@0:         SkASSERT(fExternalStorage == NULL);
michael@0:         if (fOwnerCount != IGNORE_OWNERS) {
michael@0:             SkBitmapHeapEntry* entry = getEntry(slot);
michael@0:             if (entry) {
michael@0:                 entry->releaseRef();
michael@0:             }
michael@0:         }
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Inserts a bitmap into the heap. The stored version of bitmap is guaranteed to be immutable
michael@0:      * and is not dependent on the lifecycle of the provided bitmap.
michael@0:      *
michael@0:      * @param bitmap  the bitmap to be inserted into the heap
michael@0:      * @return  the slot in the heap where the bitmap is stored or INVALID_SLOT if the bitmap could
michael@0:      *          not be added to the heap. If it was added the slot will remain valid...
michael@0:      *            (1) indefinitely if no owner count has been specified.
michael@0:      *            (2) until all owners have called releaseRef on the appropriate SkBitmapHeapEntry*
michael@0:      */
michael@0:     int32_t insert(const SkBitmap& bitmap);
michael@0: 
michael@0:     /**
michael@0:      * Retrieves an entry from the heap at a given slot.
michael@0:      *
michael@0:      * @param slot  the slot in the heap where a bitmap was stored.
michael@0:      * @return  a SkBitmapHeapEntry that wraps the bitmap or NULL if external storage is used.
michael@0:      */
michael@0:     SkBitmapHeapEntry* getEntry(int32_t slot) const {
michael@0:         SkASSERT(slot <= fStorage.count());
michael@0:         if (fExternalStorage != NULL) {
michael@0:             return NULL;
michael@0:         }
michael@0:         return fStorage[slot];
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Returns a count of the number of items currently in the heap
michael@0:      */
michael@0:     int count() const {
michael@0:         SkASSERT(fExternalStorage != NULL ||
michael@0:                  fStorage.count() - fUnusedSlots.count() == fLookupTable.count());
michael@0:         return fLookupTable.count();
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Returns the total number of bytes allocated by the bitmaps in the heap
michael@0:      */
michael@0:     size_t bytesAllocated() const {
michael@0:         return fBytesAllocated;
michael@0:     }
michael@0: 
michael@0:     /**
michael@0:      * Attempt to reduce the storage allocated.
michael@0:      * @param bytesToFree minimum number of bytes that should be attempted to
michael@0:      *   be freed.
michael@0:      * @return number of bytes actually freed.
michael@0:      */
michael@0:     size_t freeMemoryIfPossible(size_t bytesToFree);
michael@0: 
michael@0:     /**
michael@0:      * Defer any increments of owner counts until endAddingOwnersDeferral is called. So if an
michael@0:      * existing SkBitmap is inserted into the SkBitmapHeap, its corresponding SkBitmapHeapEntry will
michael@0:      * not have addReferences called on it, and the client does not need to make a corresponding
michael@0:      * call to releaseRef. Only meaningful if this SkBitmapHeap was created with an owner count not
michael@0:      * equal to IGNORE_OWNERS.
michael@0:      */
michael@0:     void deferAddingOwners();
michael@0: 
michael@0:     /**
michael@0:      * Resume adding references when duplicate SkBitmaps are inserted.
michael@0:      * @param add If true, add references to the SkBitmapHeapEntrys whose SkBitmaps were re-inserted
michael@0:      *            while deferring.
michael@0:      */
michael@0:     void endAddingOwnersDeferral(bool add);
michael@0: 
michael@0: private:
michael@0:     struct LookupEntry {
michael@0:         LookupEntry(const SkBitmap& bm)
michael@0:         : fGenerationId(bm.getGenerationID())
michael@0:         , fPixelOrigin(bm.pixelRefOrigin())
michael@0:         , fWidth(bm.width())
michael@0:         , fHeight(bm.height())
michael@0:         , fMoreRecentlyUsed(NULL)
michael@0:         , fLessRecentlyUsed(NULL){}
michael@0: 
michael@0:         const uint32_t fGenerationId; // SkPixelRef GenerationID.
michael@0:         const SkIPoint fPixelOrigin;
michael@0:         const uint32_t fWidth;
michael@0:         const uint32_t fHeight;
michael@0: 
michael@0:         // TODO: Generalize the LRU caching mechanism
michael@0:         LookupEntry* fMoreRecentlyUsed;
michael@0:         LookupEntry* fLessRecentlyUsed;
michael@0: 
michael@0:         uint32_t fStorageSlot; // slot of corresponding bitmap in fStorage.
michael@0: 
michael@0:         /**
michael@0:          * Compare two LookupEntry pointers for sorting and searching.
michael@0:          */
michael@0:         static bool Less(const LookupEntry& a, const LookupEntry& b);
michael@0:     };
michael@0: 
michael@0:     /**
michael@0:      * Remove the entry from the lookup table. Also deletes the entry pointed
michael@0:      * to by the table. Therefore, if a pointer to that one was passed in, the
michael@0:      * pointer should no longer be used, since the object to which it points has
michael@0:      * been deleted.
michael@0:      * @return The index in the lookup table of the entry before removal.
michael@0:      */
michael@0:     int removeEntryFromLookupTable(LookupEntry*);
michael@0: 
michael@0:     /**
michael@0:      * Searches for the bitmap in the lookup table and returns the bitmaps index within the table.
michael@0:      * If the bitmap was not already in the table it is added.
michael@0:      *
michael@0:      * @param key    The key to search the lookup table, created from a bitmap.
michael@0:      * @param entry  A pointer to a SkBitmapHeapEntry* that if non-null AND the bitmap is found
michael@0:      *               in the lookup table is populated with the entry from the heap storage.
michael@0:      */
michael@0:     int findInLookupTable(const LookupEntry& key, SkBitmapHeapEntry** entry);
michael@0: 
michael@0:     LookupEntry* findEntryToReplace(const SkBitmap& replacement);
michael@0:     bool copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap);
michael@0: 
michael@0:     /**
michael@0:      * Remove a LookupEntry from the LRU, in preparation for either deleting or appending as most
michael@0:      * recent. Points the LookupEntry's old neighbors at each other, and sets fLeastRecentlyUsed
michael@0:      * (if there is still an entry left). Sets LookupEntry's fMoreRecentlyUsed to NULL and leaves
michael@0:      * its fLessRecentlyUsed unmodified.
michael@0:      */
michael@0:     void removeFromLRU(LookupEntry* entry);
michael@0: 
michael@0:     /**
michael@0:      * Append a LookupEntry to the end of the LRU cache, marking it as the most
michael@0:      * recently used. Assumes that the LookupEntry is already in fLookupTable,
michael@0:      * but is not in the LRU cache. If it is in the cache, removeFromLRU should
michael@0:      * be called first.
michael@0:      */
michael@0:     void appendToLRU(LookupEntry*);
michael@0: 
michael@0:     // searchable index that maps to entries in the heap
michael@0:     SkTDArray<LookupEntry*> fLookupTable;
michael@0: 
michael@0:     // heap storage
michael@0:     SkTDArray<SkBitmapHeapEntry*> fStorage;
michael@0:     // Used to mark slots in fStorage as deleted without actually deleting
michael@0:     // the slot so as not to mess up the numbering.
michael@0:     SkTDArray<int> fUnusedSlots;
michael@0:     ExternalStorage* fExternalStorage;
michael@0: 
michael@0:     LookupEntry* fMostRecentlyUsed;
michael@0:     LookupEntry* fLeastRecentlyUsed;
michael@0: 
michael@0:     const int32_t fPreferredCount;
michael@0:     const int32_t fOwnerCount;
michael@0:     size_t fBytesAllocated;
michael@0: 
michael@0:     bool fDeferAddingOwners;
michael@0:     SkTDArray<int> fDeferredEntries;
michael@0: 
michael@0:     typedef SkBitmapHeapReader INHERITED;
michael@0: };
michael@0: 
michael@0: #endif // SkBitmapHeap_DEFINED