Home | History | Annotate | Download | only in core 
      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 #ifndef SkBitmapHeap_DEFINED
      9 #define SkBitmapHeap_DEFINED
     10 
     11 #include "SkBitmap.h"
     12 #include "SkFlattenable.h"
     13 #include "SkRefCnt.h"
     14 #include "SkTDArray.h"
     15 #include "SkThread.h"
     16 
     17 /**
     18  * SkBitmapHeapEntry provides users of SkBitmapHeap (using internal storage) with a means to...
     19  *  (1) get access a bitmap in the heap
     20  *  (2) indicate they are done with bitmap by releasing their reference (if they were an owner).
     21  */
     22 class SkBitmapHeapEntry : SkNoncopyable {
     23 public:
     24     ~SkBitmapHeapEntry();
     25 
     26     int32_t getSlot() { return fSlot; }
     27 
     28     SkBitmap* getBitmap() { return &fBitmap; }
     29 
     30     void releaseRef() {
     31         sk_atomic_dec(&fRefCount);
     32     }
     33 
     34 private:
     35     SkBitmapHeapEntry();
     36 
     37     void addReferences(int count);
     38 
     39     int32_t fSlot;
     40     int32_t fRefCount;
     41 
     42     SkBitmap fBitmap;
     43     // Keep track of the bytes allocated for this bitmap. When replacing the
     44     // bitmap or removing this HeapEntry we know how much memory has been
     45     // reclaimed.
     46     size_t fBytesAllocated;
     47 
     48     friend class SkBitmapHeap;
     49     friend class SkBitmapHeapTester;
     50 };
     51 
     52 
     53 class SkBitmapHeapReader : public SkRefCnt {
     54 public:
     55     SK_DECLARE_INST_COUNT(SkBitmapHeapReader)
     56 
     57     SkBitmapHeapReader() : INHERITED() {}
     58     virtual SkBitmap* getBitmap(int32_t slot) const = 0;
     59     virtual void releaseRef(int32_t slot) = 0;
     60 private:
     61     typedef SkRefCnt INHERITED;
     62 };
     63 
     64 
     65 /**
     66  * TODO: stores immutable bitmaps into a heap
     67  */
     68 class SkBitmapHeap : public SkBitmapHeapReader {
     69 public:
     70     class ExternalStorage : public SkRefCnt {
     71      public:
     72         SK_DECLARE_INST_COUNT(ExternalStorage)
     73 
     74         virtual bool insert(const SkBitmap& bitmap, int32_t slot) = 0;
     75 
     76      private:
     77         typedef SkRefCnt INHERITED;
     78     };
     79 
     80     static const int32_t UNLIMITED_SIZE = -1;
     81     static const int32_t IGNORE_OWNERS  = -1;
     82     static const int32_t INVALID_SLOT   = -1;
     83 
     84     /**
     85      * Constructs a heap that is responsible for allocating and managing its own storage.  In the
     86      * case where we choose to allow the heap to grow indefinitely (i.e. UNLIMITED_SIZE) we
     87      * guarantee that once allocated in the heap a bitmap's index in the heap is immutable.
     88      * Otherwise we guarantee the bitmaps placement in the heap until its owner count goes to zero.
     89      *
     90      * @param preferredSize  Specifies the preferred maximum number of bitmaps to store. This is
     91      *   not a hard limit as it can grow larger if the number of bitmaps in the heap with active
     92      *   owners exceeds this limit.
     93      * @param ownerCount  The number of owners to assign to each inserted bitmap. NOTE: while a
     94      *   bitmap in the heap has a least one owner it can't be removed.
     95      */
     96     SkBitmapHeap(int32_t preferredSize = UNLIMITED_SIZE, int32_t ownerCount = IGNORE_OWNERS);
     97 
     98     /**
     99      * Constructs a heap that defers the responsibility of storing the bitmaps to an external
    100      * function. This is especially useful if the bitmaps will be used in a separate process as the
    101      * external storage can ensure the data is properly shuttled to the appropriate processes.
    102      *
    103      * Our LRU implementation assumes that inserts into the external storage are consumed in the
    104      * order that they are inserted (i.e. SkPipe). This ensures that we don't need to query the
    105      * external storage to see if a slot in the heap is eligible to be overwritten.
    106      *
    107      * @param externalStorage  The class responsible for storing the bitmaps inserted into the heap
    108      * @param heapSize  The maximum size of the heap. Because of the sequential limitation imposed
    109      *   by our LRU implementation we can guarantee that the heap will never grow beyond this size.
    110      */
    111     SkBitmapHeap(ExternalStorage* externalStorage, int32_t heapSize = UNLIMITED_SIZE);
    112 
    113     virtual ~SkBitmapHeap();
    114 
    115     /**
    116      * Retrieves the bitmap from the specified slot in the heap
    117      *
    118      * @return  The bitmap located at that slot or NULL if external storage is being used.
    119      */
    120     SkBitmap* getBitmap(int32_t slot) const override {
    121         SkASSERT(fExternalStorage == NULL);
    122         SkBitmapHeapEntry* entry = getEntry(slot);
    123         if (entry) {
    124             return &entry->fBitmap;
    125         }
    126         return NULL;
    127     }
    128 
    129     /**
    130      * Retrieves the bitmap from the specified slot in the heap
    131      *
    132      * @return  The bitmap located at that slot or NULL if external storage is being used.
    133      */
    134     void releaseRef(int32_t slot) override {
    135         SkASSERT(fExternalStorage == NULL);
    136         if (fOwnerCount != IGNORE_OWNERS) {
    137             SkBitmapHeapEntry* entry = getEntry(slot);
    138             if (entry) {
    139                 entry->releaseRef();
    140             }
    141         }
    142     }
    143 
    144     /**
    145      * Inserts a bitmap into the heap. The stored version of bitmap is guaranteed to be immutable
    146      * and is not dependent on the lifecycle of the provided bitmap.
    147      *
    148      * @param bitmap  the bitmap to be inserted into the heap
    149      * @return  the slot in the heap where the bitmap is stored or INVALID_SLOT if the bitmap could
    150      *          not be added to the heap. If it was added the slot will remain valid...
    151      *            (1) indefinitely if no owner count has been specified.
    152      *            (2) until all owners have called releaseRef on the appropriate SkBitmapHeapEntry*
    153      */
    154     int32_t insert(const SkBitmap& bitmap);
    155 
    156     /**
    157      * Retrieves an entry from the heap at a given slot.
    158      *
    159      * @param slot  the slot in the heap where a bitmap was stored.
    160      * @return  a SkBitmapHeapEntry that wraps the bitmap or NULL if external storage is used.
    161      */
    162     SkBitmapHeapEntry* getEntry(int32_t slot) const {
    163         SkASSERT(slot <= fStorage.count());
    164         if (fExternalStorage != NULL) {
    165             return NULL;
    166         }
    167         return fStorage[slot];
    168     }
    169 
    170     /**
    171      * Returns a count of the number of items currently in the heap
    172      */
    173     int count() const {
    174         SkASSERT(fExternalStorage != NULL ||
    175                  fStorage.count() - fUnusedSlots.count() == fLookupTable.count());
    176         return fLookupTable.count();
    177     }
    178 
    179     /**
    180      * Returns the total number of bytes allocated by the bitmaps in the heap
    181      */
    182     size_t bytesAllocated() const {
    183         return fBytesAllocated;
    184     }
    185 
    186     /**
    187      * Attempt to reduce the storage allocated.
    188      * @param bytesToFree minimum number of bytes that should be attempted to
    189      *   be freed.
    190      * @return number of bytes actually freed.
    191      */
    192     size_t freeMemoryIfPossible(size_t bytesToFree);
    193 
    194     /**
    195      * Defer any increments of owner counts until endAddingOwnersDeferral is called. So if an
    196      * existing SkBitmap is inserted into the SkBitmapHeap, its corresponding SkBitmapHeapEntry will
    197      * not have addReferences called on it, and the client does not need to make a corresponding
    198      * call to releaseRef. Only meaningful if this SkBitmapHeap was created with an owner count not
    199      * equal to IGNORE_OWNERS.
    200      */
    201     void deferAddingOwners();
    202 
    203     /**
    204      * Resume adding references when duplicate SkBitmaps are inserted.
    205      * @param add If true, add references to the SkBitmapHeapEntrys whose SkBitmaps were re-inserted
    206      *            while deferring.
    207      */
    208     void endAddingOwnersDeferral(bool add);
    209 
    210 private:
    211     struct LookupEntry {
    212         LookupEntry(const SkBitmap& bm)
    213         : fGenerationId(bm.getGenerationID())
    214         , fPixelOrigin(bm.pixelRefOrigin())
    215         , fWidth(bm.width())
    216         , fHeight(bm.height())
    217         , fMoreRecentlyUsed(NULL)
    218         , fLessRecentlyUsed(NULL){}
    219 
    220         const uint32_t fGenerationId; // SkPixelRef GenerationID.
    221         const SkIPoint fPixelOrigin;
    222         const uint32_t fWidth;
    223         const uint32_t fHeight;
    224 
    225         // TODO: Generalize the LRU caching mechanism
    226         LookupEntry* fMoreRecentlyUsed;
    227         LookupEntry* fLessRecentlyUsed;
    228 
    229         uint32_t fStorageSlot; // slot of corresponding bitmap in fStorage.
    230 
    231         /**
    232          * Compare two LookupEntry pointers for sorting and searching.
    233          */
    234         static bool Less(const LookupEntry& a, const LookupEntry& b);
    235     };
    236 
    237     /**
    238      * Remove the entry from the lookup table. Also deletes the entry pointed
    239      * to by the table. Therefore, if a pointer to that one was passed in, the
    240      * pointer should no longer be used, since the object to which it points has
    241      * been deleted.
    242      * @return The index in the lookup table of the entry before removal.
    243      */
    244     int removeEntryFromLookupTable(LookupEntry*);
    245 
    246     /**
    247      * Searches for the bitmap in the lookup table and returns the bitmaps index within the table.
    248      * If the bitmap was not already in the table it is added.
    249      *
    250      * @param key    The key to search the lookup table, created from a bitmap.
    251      * @param entry  A pointer to a SkBitmapHeapEntry* that if non-null AND the bitmap is found
    252      *               in the lookup table is populated with the entry from the heap storage.
    253      */
    254     int findInLookupTable(const LookupEntry& key, SkBitmapHeapEntry** entry);
    255 
    256     LookupEntry* findEntryToReplace(const SkBitmap& replacement);
    257     bool copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap);
    258 
    259     /**
    260      * Remove a LookupEntry from the LRU, in preparation for either deleting or appending as most
    261      * recent. Points the LookupEntry's old neighbors at each other, and sets fLeastRecentlyUsed
    262      * (if there is still an entry left). Sets LookupEntry's fMoreRecentlyUsed to NULL and leaves
    263      * its fLessRecentlyUsed unmodified.
    264      */
    265     void removeFromLRU(LookupEntry* entry);
    266 
    267     /**
    268      * Append a LookupEntry to the end of the LRU cache, marking it as the most
    269      * recently used. Assumes that the LookupEntry is already in fLookupTable,
    270      * but is not in the LRU cache. If it is in the cache, removeFromLRU should
    271      * be called first.
    272      */
    273     void appendToLRU(LookupEntry*);
    274 
    275     // searchable index that maps to entries in the heap
    276     SkTDArray<LookupEntry*> fLookupTable;
    277 
    278     // heap storage
    279     SkTDArray<SkBitmapHeapEntry*> fStorage;
    280     // Used to mark slots in fStorage as deleted without actually deleting
    281     // the slot so as not to mess up the numbering.
    282     SkTDArray<int> fUnusedSlots;
    283     ExternalStorage* fExternalStorage;
    284 
    285     LookupEntry* fMostRecentlyUsed;
    286     LookupEntry* fLeastRecentlyUsed;
    287 
    288     const int32_t fPreferredCount;
    289     const int32_t fOwnerCount;
    290     size_t fBytesAllocated;
    291 
    292     bool fDeferAddingOwners;
    293     SkTDArray<int> fDeferredEntries;
    294 
    295     typedef SkBitmapHeapReader INHERITED;
    296 };
    297 
    298 #endif // SkBitmapHeap_DEFINED
    299