DXR is a code search and navigation tool aimed at making sense of large projects. It supports full-text and regex searches as well as structural queries.

Implementation

Mercurial (d8847129d134)

VCS Links

Line Code
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 300 301 302 303 304 305 306 307

/*
 * 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 "SkBitmap.h"
#include "SkFlattenable.h"
#include "SkRefCnt.h"
#include "SkTDArray.h"
#include "SkThread.h"
#include "SkTRefArray.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:
    SK_DECLARE_INST_COUNT(SkBitmapHeapReader)

    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:
        SK_DECLARE_INST_COUNT(ExternalStorage)

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

    /**
     * Makes a shallow copy of all bitmaps currently in the heap and returns them as an array. The
     * array indices match their position in the heap.
     *
     * @return  a ptr to an array of bitmaps or NULL if external storage is being used.
     */
    SkTRefArray<SkBitmap>* extractBitmaps() const;

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

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

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

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