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
9#include "GrTextureStripAtlas.h"
10#include "SkPixelRef.h"
11#include "SkTSearch.h"
12#include "GrTexture.h"
13
14#ifdef SK_DEBUG
15    #define VALIDATE this->validate()
16#else
17    #define VALIDATE
18#endif
19
20int32_t GrTextureStripAtlas::gCacheCount = 0;
21
22GrTHashTable<GrTextureStripAtlas::AtlasEntry,
23                GrTextureStripAtlas::AtlasHashKey, 8>*
24                            GrTextureStripAtlas::gAtlasCache = NULL;
25
26GrTHashTable<GrTextureStripAtlas::AtlasEntry, GrTextureStripAtlas::AtlasHashKey, 8>*
27GrTextureStripAtlas::GetCache() {
28
29    if (NULL == gAtlasCache) {
30        gAtlasCache = SkNEW((GrTHashTable<AtlasEntry, AtlasHashKey, 8>));
31    }
32
33    return gAtlasCache;
34}
35
36// Remove the specified atlas from the cache
37void GrTextureStripAtlas::CleanUp(const GrContext*, void* info) {
38    GrAssert(NULL != info);
39
40    AtlasEntry* entry = static_cast<AtlasEntry*>(info);
41
42    // remove the cache entry
43    GetCache()->remove(entry->fKey, entry);
44
45    // remove the actual entry
46    SkDELETE(entry);
47
48    if (0 == GetCache()->count()) {
49        SkDELETE(gAtlasCache);
50        gAtlasCache = NULL;
51    }
52}
53
54GrTextureStripAtlas* GrTextureStripAtlas::GetAtlas(const GrTextureStripAtlas::Desc& desc) {
55    AtlasHashKey key;
56    key.setKeyData(desc.asKey());
57    AtlasEntry* entry = GetCache()->find(key);
58    if (NULL == entry) {
59        entry = SkNEW(AtlasEntry);
60
61        entry->fAtlas = SkNEW_ARGS(GrTextureStripAtlas, (desc));
62        entry->fKey = key;
63
64        desc.fContext->addCleanUp(CleanUp, entry);
65
66        GetCache()->insert(key, entry);
67    }
68
69    return entry->fAtlas;
70}
71
72GrTextureStripAtlas::GrTextureStripAtlas(GrTextureStripAtlas::Desc desc)
73    : fCacheKey(sk_atomic_inc(&gCacheCount))
74    , fLockedRows(0)
75    , fDesc(desc)
76    , fNumRows(desc.fHeight / desc.fRowHeight)
77    , fTexture(NULL)
78    , fRows(SkNEW_ARRAY(AtlasRow, fNumRows))
79    , fLRUFront(NULL)
80    , fLRUBack(NULL) {
81    GrAssert(fNumRows * fDesc.fRowHeight == fDesc.fHeight);
82    this->initLRU();
83    VALIDATE;
84}
85
86GrTextureStripAtlas::~GrTextureStripAtlas() {
87    SkDELETE_ARRAY(fRows);
88}
89
90int GrTextureStripAtlas::lockRow(const SkBitmap& data) {
91    VALIDATE;
92    if (0 == fLockedRows) {
93        this->lockTexture();
94    }
95
96    int key = data.getGenerationID();
97    int rowNumber = -1;
98    int index = this->searchByKey(key);
99
100    if (index >= 0) {
101        // We already have the data in a row, so we can just return that row
102        AtlasRow* row = fKeyTable[index];
103        if (0 == row->fLocks) {
104            this->removeFromLRU(row);
105        }
106        ++row->fLocks;
107        ++fLockedRows;
108
109        // Since all the rows are always stored in a contiguous array, we can save the memory
110        // required for storing row numbers and just compute it with some pointer arithmetic
111        rowNumber = static_cast<int>(row - fRows);
112    } else {
113        // ~index is the index where we will insert the new key to keep things sorted
114        index = ~index;
115
116        // We don't have this data cached, so pick the least recently used row to copy into
117        AtlasRow* row = this->getLRU();
118
119        ++fLockedRows;
120
121        if (NULL == row) {
122            // force a flush, which should unlock all the rows; then try again
123            fDesc.fContext->flush();
124            row = this->getLRU();
125            if (NULL == row) {
126                --fLockedRows;
127                return -1;
128            }
129        }
130
131        this->removeFromLRU(row);
132
133        uint32_t oldKey = row->fKey;
134
135        // If we are writing into a row that already held bitmap data, we need to remove the
136        // reference to that genID which is stored in our sorted table of key values.
137        if (oldKey != kEmptyAtlasRowKey) {
138
139            // Find the entry in the list; if it's before the index where we plan on adding the new
140            // entry, we decrement since it will shift elements ahead of it back by one.
141            int oldIndex = this->searchByKey(oldKey);
142            if (oldIndex < index) {
143                --index;
144            }
145
146            fKeyTable.remove(oldIndex);
147        }
148
149        row->fKey = key;
150        row->fLocks = 1;
151        fKeyTable.insert(index, 1, &row);
152        rowNumber = static_cast<int>(row - fRows);
153
154        SkAutoLockPixels lock(data);
155
156        // Pass in the kDontFlush flag, since we know we're writing to a part of this texture
157        // that is not currently in use
158        fDesc.fContext->writeTexturePixels(fTexture,
159                                           0,  rowNumber * fDesc.fRowHeight,
160                                           fDesc.fWidth, fDesc.fRowHeight,
161                                           SkBitmapConfig2GrPixelConfig(data.config()),
162                                           data.getPixels(),
163                                           data.rowBytes(),
164                                           GrContext::kDontFlush_PixelOpsFlag);
165    }
166
167    GrAssert(rowNumber >= 0);
168    VALIDATE;
169    return rowNumber;
170}
171
172void GrTextureStripAtlas::unlockRow(int row) {
173    VALIDATE;
174    --fRows[row].fLocks;
175    --fLockedRows;
176    GrAssert(fRows[row].fLocks >= 0 && fLockedRows >= 0);
177    if (0 == fRows[row].fLocks) {
178        this->appendLRU(fRows + row);
179    }
180    if (0 == fLockedRows) {
181        this->unlockTexture();
182    }
183    VALIDATE;
184}
185
186GrTextureStripAtlas::AtlasRow* GrTextureStripAtlas::getLRU() {
187    // Front is least-recently-used
188    AtlasRow* row = fLRUFront;
189    return row;
190}
191
192void GrTextureStripAtlas::lockTexture() {
193    GrTextureParams params;
194    GrTextureDesc texDesc;
195    texDesc.fWidth = fDesc.fWidth;
196    texDesc.fHeight = fDesc.fHeight;
197    texDesc.fConfig = fDesc.fConfig;
198
199    static const GrCacheID::Domain gTextureStripAtlasDomain = GrCacheID::GenerateDomain();
200    GrCacheID::Key key;
201    *key.fData32 = fCacheKey;
202    memset(key.fData32 + 1, 0, sizeof(key) - sizeof(uint32_t));
203    GrCacheID cacheID(gTextureStripAtlasDomain, key);
204
205    fTexture = fDesc.fContext->findAndRefTexture(texDesc, cacheID, &params);
206    if (NULL == fTexture) {
207        fTexture = fDesc.fContext->createTexture(&params, texDesc, cacheID, NULL, 0);
208        // This is a new texture, so all of our cache info is now invalid
209        this->initLRU();
210        fKeyTable.rewind();
211    }
212    GrAssert(NULL != fTexture);
213}
214
215void GrTextureStripAtlas::unlockTexture() {
216    GrAssert(NULL != fTexture && 0 == fLockedRows);
217    fTexture->unref();
218    fTexture = NULL;
219    fDesc.fContext->purgeCache();
220}
221
222void GrTextureStripAtlas::initLRU() {
223    fLRUFront = NULL;
224    fLRUBack = NULL;
225    // Initially all the rows are in the LRU list
226    for (int i = 0; i < fNumRows; ++i) {
227        fRows[i].fKey = kEmptyAtlasRowKey;
228        fRows[i].fNext = NULL;
229        fRows[i].fPrev = NULL;
230        this->appendLRU(fRows + i);
231    }
232    GrAssert(NULL == fLRUFront || NULL == fLRUFront->fPrev);
233    GrAssert(NULL == fLRUBack || NULL == fLRUBack->fNext);
234}
235
236void GrTextureStripAtlas::appendLRU(AtlasRow* row) {
237    GrAssert(NULL == row->fPrev && NULL == row->fNext);
238    if (NULL == fLRUFront && NULL == fLRUBack) {
239        fLRUFront = row;
240        fLRUBack = row;
241    } else {
242        row->fPrev = fLRUBack;
243        fLRUBack->fNext = row;
244        fLRUBack = row;
245    }
246}
247
248void GrTextureStripAtlas::removeFromLRU(AtlasRow* row) {
249    GrAssert(NULL != row);
250    if (NULL != row->fNext && NULL != row->fPrev) {
251        row->fPrev->fNext = row->fNext;
252        row->fNext->fPrev = row->fPrev;
253    } else {
254        if (NULL == row->fNext) {
255            GrAssert(row == fLRUBack);
256            fLRUBack = row->fPrev;
257            if (fLRUBack) {
258                fLRUBack->fNext = NULL;
259            }
260        }
261        if (NULL == row->fPrev) {
262            GrAssert(row == fLRUFront);
263            fLRUFront = row->fNext;
264            if (fLRUFront) {
265                fLRUFront->fPrev = NULL;
266            }
267        }
268    }
269    row->fNext = NULL;
270    row->fPrev = NULL;
271}
272
273int GrTextureStripAtlas::searchByKey(uint32_t key) {
274    AtlasRow target;
275    target.fKey = key;
276    return SkTSearch<const AtlasRow,
277                     GrTextureStripAtlas::KeyLess>((const AtlasRow**)fKeyTable.begin(),
278                                                   fKeyTable.count(),
279                                                   &target,
280                                                   sizeof(AtlasRow*));
281}
282
283#ifdef SK_DEBUG
284void GrTextureStripAtlas::validate() {
285
286    // Our key table should be sorted
287    uint32_t prev = 1 > fKeyTable.count() ? 0 : fKeyTable[0]->fKey;
288    for (int i = 1; i < fKeyTable.count(); ++i) {
289        GrAssert(prev < fKeyTable[i]->fKey);
290        GrAssert(fKeyTable[i]->fKey != kEmptyAtlasRowKey);
291        prev = fKeyTable[i]->fKey;
292    }
293
294    int lruCount = 0;
295    // Validate LRU pointers, and count LRU entries
296    GrAssert(NULL == fLRUFront || NULL == fLRUFront->fPrev);
297    GrAssert(NULL == fLRUBack  || NULL == fLRUBack->fNext);
298    for (AtlasRow* r = fLRUFront; r != NULL; r = r->fNext) {
299        if (NULL == r->fNext) {
300            GrAssert(r == fLRUBack);
301        } else {
302            GrAssert(r->fNext->fPrev == r);
303        }
304        ++lruCount;
305    }
306
307    int rowLocks = 0;
308    int freeRows = 0;
309
310    for (int i = 0; i < fNumRows; ++i) {
311        rowLocks += fRows[i].fLocks;
312        if (0 == fRows[i].fLocks) {
313            ++freeRows;
314            bool inLRU = false;
315            // Step through the LRU and make sure it's present
316            for (AtlasRow* r = fLRUFront; r != NULL; r = r->fNext) {
317                if (r == &fRows[i]) {
318                    inLRU = true;
319                    break;
320                }
321            }
322            GrAssert(inLRU);
323        } else {
324            // If we are locked, we should have a key
325            GrAssert(kEmptyAtlasRowKey != fRows[i].fKey);
326        }
327
328        // If we have a key != kEmptyAtlasRowKey, it should be in the key table
329        GrAssert(fRows[i].fKey == kEmptyAtlasRowKey || this->searchByKey(fRows[i].fKey) >= 0);
330    }
331
332    // Our count of locks should equal the sum of row locks, unless we ran out of rows and flushed,
333    // in which case we'll have one more lock than recorded in the rows (to represent the pending
334    // lock of a row; which ensures we don't unlock the texture prematurely).
335    GrAssert(rowLocks == fLockedRows || rowLocks + 1 == fLockedRows);
336
337    // We should have one lru entry for each free row
338    GrAssert(freeRows == lruCount);
339
340    // If we have locked rows, we should have a locked texture, otherwise
341    // it should be unlocked
342    if (fLockedRows == 0) {
343        GrAssert(NULL == fTexture);
344    } else {
345        GrAssert(NULL != fTexture);
346    }
347}
348#endif
349