src/core/SkBitmapHeap.h

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