aboutsummaryrefslogtreecommitdiffhomepage
path: root/src/core/SkBitmapHeap.h
blob: 22c31a0b0b188500995848009ed8ec34f95edd9f (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
/*
 * 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 "SkAtomics.h"
#include "SkBitmap.h"
#include "SkPoint.h"
#include "SkRefCnt.h"
#include "SkTDArray.h"
#include "SkTypes.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:


    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:


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

    /**
     * Retrieves the bitmap from the specified slot in the heap
     *
     * @return  The bitmap located at that slot or nullptr if external storage is being used.
     */
    SkBitmap* getBitmap(int32_t slot) const override {
        SkASSERT(fExternalStorage == nullptr);
        SkBitmapHeapEntry* entry = getEntry(slot);
        if (entry) {
            return &entry->fBitmap;
        }
        return nullptr;
    }

    /**
     * Retrieves the bitmap from the specified slot in the heap
     *
     * @return  The bitmap located at that slot or nullptr if external storage is being used.
     */
    void releaseRef(int32_t slot) override {
        SkASSERT(fExternalStorage == nullptr);
        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 nullptr if external storage is used.
     */
    SkBitmapHeapEntry* getEntry(int32_t slot) const {
        SkASSERT(slot <= fStorage.count());
        if (fExternalStorage != nullptr) {
            return nullptr;
        }
        return fStorage[slot];
    }

    /**
     * Returns a count of the number of items currently in the heap
     */
    int count() const {
        SkASSERT(fExternalStorage != nullptr ||
                 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(nullptr)
        , fLessRecentlyUsed(nullptr){}

        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 nullptr 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