SkBitmapHeap.h revision 21830d90096d2dccc4168d99a427e78035ce942a 
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#include "SkTRefArray.h"
17
18/**
19 * SkBitmapHeapEntry provides users of SkBitmapHeap (using internal storage) with a means to...
20 *  (1) get access a bitmap in the heap
21 *  (2) indicate they are done with bitmap by releasing their reference (if they were an owner).
22 */
23class SkBitmapHeapEntry : SkNoncopyable {
24public:
25    ~SkBitmapHeapEntry();
26
27    int32_t getSlot() { return fSlot; }
28
29    SkBitmap* getBitmap() { return &fBitmap; }
30
31    void releaseRef() {
32        sk_atomic_dec(&fRefCount);
33    }
34
35private:
36    SkBitmapHeapEntry();
37
38    void addReferences(int count);
39
40    int32_t fSlot;
41    int32_t fRefCount;
42
43    SkBitmap fBitmap;
44    // Keep track of the bytes allocated for this bitmap. When replacing the
45    // bitmap or removing this HeapEntry we know how much memory has been
46    // reclaimed.
47    size_t fBytesAllocated;
48    // TODO: Generalize the LRU caching mechanism
49    SkBitmapHeapEntry* fMoreRecentlyUsed;
50    SkBitmapHeapEntry* fLessRecentlyUsed;
51
52    friend class SkBitmapHeap;
53};
54
55
56class SkBitmapHeapReader : public SkRefCnt {
57public:
58    SkBitmapHeapReader() : INHERITED() {}
59    virtual SkBitmap* getBitmap(int32_t slot) const = 0;
60    virtual void releaseRef(int32_t slot) = 0;
61private:
62    typedef SkRefCnt INHERITED;
63};
64
65
66/**
67 * TODO: stores immutable bitmaps into a heap
68 */
69class SkBitmapHeap : public SkBitmapHeapReader {
70public:
71    class ExternalStorage : public SkRefCnt {
72     public:
73        virtual bool insert(const SkBitmap& bitmap, int32_t slot) = 0;
74    };
75
76    static const int32_t UNLIMITED_SIZE = -1;
77    static const int32_t IGNORE_OWNERS  = -1;
78    static const int32_t INVALID_SLOT   = -1;
79
80    /**
81     * Constructs a heap that is responsible for allocating and managing its own storage.  In the
82     * case where we choose to allow the heap to grow indefinitely (i.e. UNLIMITED_SIZE) we
83     * guarantee that once allocated in the heap a bitmap's index in the heap is immutable.
84     * Otherwise we guarantee the bitmaps placement in the heap until its owner count goes to zero.
85     *
86     * @param preferredSize  Specifies the preferred maximum number of bitmaps to store. This is
87     *   not a hard limit as it can grow larger if the number of bitmaps in the heap with active
88     *   owners exceeds this limit.
89     * @param ownerCount  The number of owners to assign to each inserted bitmap. NOTE: while a
90     *   bitmap in the heap has a least one owner it can't be removed.
91     */
92    SkBitmapHeap(int32_t preferredSize = UNLIMITED_SIZE, int32_t ownerCount = IGNORE_OWNERS);
93
94    /**
95     * Constructs a heap that defers the responsibility of storing the bitmaps to an external
96     * function. This is especially useful if the bitmaps will be used in a separate process as the
97     * external storage can ensure the data is properly shuttled to the appropriate processes.
98     *
99     * Our LRU implementation assumes that inserts into the external storage are consumed in the
100     * order that they are inserted (i.e. SkPipe). This ensures that we don't need to query the
101     * external storage to see if a slot in the heap is eligible to be overwritten.
102     *
103     * @param externalStorage  The class responsible for storing the bitmaps inserted into the heap
104     * @param heapSize  The maximum size of the heap. Because of the sequential limitation imposed
105     *   by our LRU implementation we can guarantee that the heap will never grow beyond this size.
106     */
107    SkBitmapHeap(ExternalStorage* externalStorage, int32_t heapSize = UNLIMITED_SIZE);
108
109    ~SkBitmapHeap();
110
111    /**
112     * Makes a shallow copy of all bitmaps currently in the heap and returns them as an array. The
113     * array indices match their position in the heap.
114     *
115     * @return  a ptr to an array of bitmaps or NULL if external storage is being used.
116     */
117    SkTRefArray<SkBitmap>* extractBitmaps() const;
118
119    /**
120     * Retrieves the bitmap from the specified slot in the heap
121     *
122     * @return  The bitmap located at that slot or NULL if external storage is being used.
123     */
124    virtual SkBitmap* getBitmap(int32_t slot) const SK_OVERRIDE {
125        SkASSERT(fExternalStorage == NULL);
126        SkBitmapHeapEntry* entry = getEntry(slot);
127        if (entry) {
128            return &entry->fBitmap;
129        }
130        return NULL;
131    }
132
133    /**
134     * Retrieves the bitmap from the specified slot in the heap
135     *
136     * @return  The bitmap located at that slot or NULL if external storage is being used.
137     */
138    virtual void releaseRef(int32_t slot) SK_OVERRIDE {
139        SkASSERT(fExternalStorage == NULL);
140        if (fOwnerCount != IGNORE_OWNERS) {
141            SkBitmapHeapEntry* entry = getEntry(slot);
142            if (entry) {
143                entry->releaseRef();
144            }
145        }
146    }
147
148    /**
149     * Inserts a bitmap into the heap. The stored version of bitmap is guaranteed to be immutable
150     * and is not dependent on the lifecycle of the provided bitmap.
151     *
152     * @param bitmap  the bitmap to be inserted into the heap
153     * @return  the slot in the heap where the bitmap is stored or INVALID_SLOT if the bitmap could
154     *          not be added to the heap. If it was added the slot will remain valid...
155     *            (1) indefinitely if no owner count has been specified.
156     *            (2) until all owners have called releaseRef on the appropriate SkBitmapHeapEntry*
157     */
158    int32_t insert(const SkBitmap& bitmap);
159
160    /**
161     * Retrieves an entry from the heap at a given slot.
162     *
163     * @param slot  the slot in the heap where a bitmap was stored.
164     * @return  a SkBitmapHeapEntry that wraps the bitmap or NULL if external storage is used.
165     */
166    SkBitmapHeapEntry* getEntry(int32_t slot) const {
167        SkASSERT(slot <= fStorage.count());
168        if (fExternalStorage != NULL) {
169            return NULL;
170        }
171        return fStorage[slot];
172    }
173
174    /**
175     * Returns a count of the number of items currently in the heap
176     */
177    int count() const {
178        SkASSERT(fExternalStorage != NULL || fStorage.count() == fLookupTable.count());
179        return fLookupTable.count();
180    }
181
182    /**
183     * Returns the total number of bytes allocated by the bitmaps in the heap
184     */
185    size_t bytesAllocated() const {
186        return fBytesAllocated;
187    }
188
189private:
190    struct LookupEntry {
191        uint32_t fGenerationId; // SkPixelRef GenerationID.
192        size_t fPixelOffset;
193        uint32_t fWidth;
194        uint32_t fHeight;
195
196        uint32_t fStorageSlot; // slot of corresponding bitmap in fStorage.
197
198        bool operator < (const LookupEntry& other) const {
199            if (this->fGenerationId != other.fGenerationId) {
200                return this->fGenerationId < other.fGenerationId;
201            } else if(this->fPixelOffset != other.fPixelOffset) {
202                return this->fPixelOffset < other.fPixelOffset;
203            } else if(this->fWidth != other.fWidth) {
204                return this->fWidth < other.fWidth;
205            } else {
206                return this->fHeight < other.fHeight;
207            }
208        }
209        bool operator != (const LookupEntry& other) const {
210            return this->fGenerationId != other.fGenerationId
211                || this->fPixelOffset != other.fPixelOffset
212                || this->fWidth != other.fWidth
213                || this->fHeight != other.fHeight;
214        }
215    };
216
217    /**
218     * Searches for the bitmap in the lookup table and returns the bitmaps index within the table.
219     * If the bitmap was not already in the table it is added.
220     *
221     * @param bitmap  The bitmap we using as a key to search the lookup table
222     * @param entry  A pointer to a SkBitmapHeapEntry* that if non-null AND the bitmap is found
223     *               in the lookup table is populated with the entry from the heap storage.
224     */
225    int findInLookupTable(const SkBitmap& bitmap, SkBitmapHeapEntry** entry);
226
227    SkBitmapHeapEntry* findEntryToReplace(const SkBitmap& replacement);
228    bool copyBitmap(const SkBitmap& originalBitmap, SkBitmap& copiedBitmap);
229    void setMostRecentlyUsed(SkBitmapHeapEntry* entry);
230
231    // searchable index that maps to entries in the heap
232    SkTDArray<LookupEntry> fLookupTable;
233
234    // heap storage
235    SkTDArray<SkBitmapHeapEntry*> fStorage;
236    ExternalStorage* fExternalStorage;
237
238    SkBitmapHeapEntry* fMostRecentlyUsed;
239    SkBitmapHeapEntry* fLeastRecentlyUsed;
240
241    const int32_t fPreferredCount;
242    const int32_t fOwnerCount;
243    size_t fBytesAllocated;
244
245    typedef SkBitmapHeapReader INHERITED;
246};
247
248#endif // SkBitmapHeap_DEFINED
249