michael@0: 
michael@0: /*
michael@0:  * Copyright 2012 Google Inc.
michael@0:  *
michael@0:  * Use of this source code is governed by a BSD-style license that can be
michael@0:  * found in the LICENSE file.
michael@0:  */
michael@0: 
michael@0: #include "GrTextureStripAtlas.h"
michael@0: #include "SkPixelRef.h"
michael@0: #include "SkTSearch.h"
michael@0: #include "GrTexture.h"
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0:     #define VALIDATE this->validate()
michael@0: #else
michael@0:     #define VALIDATE
michael@0: #endif
michael@0: 
michael@0: int32_t GrTextureStripAtlas::gCacheCount = 0;
michael@0: 
michael@0: GrTHashTable<GrTextureStripAtlas::AtlasEntry,
michael@0:                 GrTextureStripAtlas::AtlasHashKey, 8>*
michael@0:                             GrTextureStripAtlas::gAtlasCache = NULL;
michael@0: 
michael@0: GrTHashTable<GrTextureStripAtlas::AtlasEntry, GrTextureStripAtlas::AtlasHashKey, 8>*
michael@0: GrTextureStripAtlas::GetCache() {
michael@0: 
michael@0:     if (NULL == gAtlasCache) {
michael@0:         gAtlasCache = SkNEW((GrTHashTable<AtlasEntry, AtlasHashKey, 8>));
michael@0:     }
michael@0: 
michael@0:     return gAtlasCache;
michael@0: }
michael@0: 
michael@0: // Remove the specified atlas from the cache
michael@0: void GrTextureStripAtlas::CleanUp(const GrContext*, void* info) {
michael@0:     SkASSERT(NULL != info);
michael@0: 
michael@0:     AtlasEntry* entry = static_cast<AtlasEntry*>(info);
michael@0: 
michael@0:     // remove the cache entry
michael@0:     GetCache()->remove(entry->fKey, entry);
michael@0: 
michael@0:     // remove the actual entry
michael@0:     SkDELETE(entry);
michael@0: 
michael@0:     if (0 == GetCache()->count()) {
michael@0:         SkDELETE(gAtlasCache);
michael@0:         gAtlasCache = NULL;
michael@0:     }
michael@0: }
michael@0: 
michael@0: GrTextureStripAtlas* GrTextureStripAtlas::GetAtlas(const GrTextureStripAtlas::Desc& desc) {
michael@0:     AtlasHashKey key;
michael@0:     key.setKeyData(desc.asKey());
michael@0:     AtlasEntry* entry = GetCache()->find(key);
michael@0:     if (NULL == entry) {
michael@0:         entry = SkNEW(AtlasEntry);
michael@0: 
michael@0:         entry->fAtlas = SkNEW_ARGS(GrTextureStripAtlas, (desc));
michael@0:         entry->fKey = key;
michael@0: 
michael@0:         desc.fContext->addCleanUp(CleanUp, entry);
michael@0: 
michael@0:         GetCache()->insert(key, entry);
michael@0:     }
michael@0: 
michael@0:     return entry->fAtlas;
michael@0: }
michael@0: 
michael@0: GrTextureStripAtlas::GrTextureStripAtlas(GrTextureStripAtlas::Desc desc)
michael@0:     : fCacheKey(sk_atomic_inc(&gCacheCount))
michael@0:     , fLockedRows(0)
michael@0:     , fDesc(desc)
michael@0:     , fNumRows(desc.fHeight / desc.fRowHeight)
michael@0:     , fTexture(NULL)
michael@0:     , fRows(SkNEW_ARRAY(AtlasRow, fNumRows))
michael@0:     , fLRUFront(NULL)
michael@0:     , fLRUBack(NULL) {
michael@0:     SkASSERT(fNumRows * fDesc.fRowHeight == fDesc.fHeight);
michael@0:     this->initLRU();
michael@0:     VALIDATE;
michael@0: }
michael@0: 
michael@0: GrTextureStripAtlas::~GrTextureStripAtlas() {
michael@0:     SkDELETE_ARRAY(fRows);
michael@0: }
michael@0: 
michael@0: int GrTextureStripAtlas::lockRow(const SkBitmap& data) {
michael@0:     VALIDATE;
michael@0:     if (0 == fLockedRows) {
michael@0:         this->lockTexture();
michael@0:     }
michael@0: 
michael@0:     int key = data.getGenerationID();
michael@0:     int rowNumber = -1;
michael@0:     int index = this->searchByKey(key);
michael@0: 
michael@0:     if (index >= 0) {
michael@0:         // We already have the data in a row, so we can just return that row
michael@0:         AtlasRow* row = fKeyTable[index];
michael@0:         if (0 == row->fLocks) {
michael@0:             this->removeFromLRU(row);
michael@0:         }
michael@0:         ++row->fLocks;
michael@0:         ++fLockedRows;
michael@0: 
michael@0:         // Since all the rows are always stored in a contiguous array, we can save the memory
michael@0:         // required for storing row numbers and just compute it with some pointer arithmetic
michael@0:         rowNumber = static_cast<int>(row - fRows);
michael@0:     } else {
michael@0:         // ~index is the index where we will insert the new key to keep things sorted
michael@0:         index = ~index;
michael@0: 
michael@0:         // We don't have this data cached, so pick the least recently used row to copy into
michael@0:         AtlasRow* row = this->getLRU();
michael@0: 
michael@0:         ++fLockedRows;
michael@0: 
michael@0:         if (NULL == row) {
michael@0:             // force a flush, which should unlock all the rows; then try again
michael@0:             fDesc.fContext->flush();
michael@0:             row = this->getLRU();
michael@0:             if (NULL == row) {
michael@0:                 --fLockedRows;
michael@0:                 return -1;
michael@0:             }
michael@0:         }
michael@0: 
michael@0:         this->removeFromLRU(row);
michael@0: 
michael@0:         uint32_t oldKey = row->fKey;
michael@0: 
michael@0:         // If we are writing into a row that already held bitmap data, we need to remove the
michael@0:         // reference to that genID which is stored in our sorted table of key values.
michael@0:         if (oldKey != kEmptyAtlasRowKey) {
michael@0: 
michael@0:             // Find the entry in the list; if it's before the index where we plan on adding the new
michael@0:             // entry, we decrement since it will shift elements ahead of it back by one.
michael@0:             int oldIndex = this->searchByKey(oldKey);
michael@0:             if (oldIndex < index) {
michael@0:                 --index;
michael@0:             }
michael@0: 
michael@0:             fKeyTable.remove(oldIndex);
michael@0:         }
michael@0: 
michael@0:         row->fKey = key;
michael@0:         row->fLocks = 1;
michael@0:         fKeyTable.insert(index, 1, &row);
michael@0:         rowNumber = static_cast<int>(row - fRows);
michael@0: 
michael@0:         SkAutoLockPixels lock(data);
michael@0: 
michael@0:         // Pass in the kDontFlush flag, since we know we're writing to a part of this texture
michael@0:         // that is not currently in use
michael@0:         fDesc.fContext->writeTexturePixels(fTexture,
michael@0:                                            0,  rowNumber * fDesc.fRowHeight,
michael@0:                                            fDesc.fWidth, fDesc.fRowHeight,
michael@0:                                            SkBitmapConfig2GrPixelConfig(data.config()),
michael@0:                                            data.getPixels(),
michael@0:                                            data.rowBytes(),
michael@0:                                            GrContext::kDontFlush_PixelOpsFlag);
michael@0:     }
michael@0: 
michael@0:     SkASSERT(rowNumber >= 0);
michael@0:     VALIDATE;
michael@0:     return rowNumber;
michael@0: }
michael@0: 
michael@0: void GrTextureStripAtlas::unlockRow(int row) {
michael@0:     VALIDATE;
michael@0:     --fRows[row].fLocks;
michael@0:     --fLockedRows;
michael@0:     SkASSERT(fRows[row].fLocks >= 0 && fLockedRows >= 0);
michael@0:     if (0 == fRows[row].fLocks) {
michael@0:         this->appendLRU(fRows + row);
michael@0:     }
michael@0:     if (0 == fLockedRows) {
michael@0:         this->unlockTexture();
michael@0:     }
michael@0:     VALIDATE;
michael@0: }
michael@0: 
michael@0: GrTextureStripAtlas::AtlasRow* GrTextureStripAtlas::getLRU() {
michael@0:     // Front is least-recently-used
michael@0:     AtlasRow* row = fLRUFront;
michael@0:     return row;
michael@0: }
michael@0: 
michael@0: void GrTextureStripAtlas::lockTexture() {
michael@0:     GrTextureParams params;
michael@0:     GrTextureDesc texDesc;
michael@0:     texDesc.fWidth = fDesc.fWidth;
michael@0:     texDesc.fHeight = fDesc.fHeight;
michael@0:     texDesc.fConfig = fDesc.fConfig;
michael@0: 
michael@0:     static const GrCacheID::Domain gTextureStripAtlasDomain = GrCacheID::GenerateDomain();
michael@0:     GrCacheID::Key key;
michael@0:     *key.fData32 = fCacheKey;
michael@0:     memset(key.fData32 + 1, 0, sizeof(key) - sizeof(uint32_t));
michael@0:     GrCacheID cacheID(gTextureStripAtlasDomain, key);
michael@0: 
michael@0:     fTexture = fDesc.fContext->findAndRefTexture(texDesc, cacheID, &params);
michael@0:     if (NULL == fTexture) {
michael@0:         fTexture = fDesc.fContext->createTexture(&params, texDesc, cacheID, NULL, 0);
michael@0:         // This is a new texture, so all of our cache info is now invalid
michael@0:         this->initLRU();
michael@0:         fKeyTable.rewind();
michael@0:     }
michael@0:     SkASSERT(NULL != fTexture);
michael@0: }
michael@0: 
michael@0: void GrTextureStripAtlas::unlockTexture() {
michael@0:     SkASSERT(NULL != fTexture && 0 == fLockedRows);
michael@0:     fTexture->unref();
michael@0:     fTexture = NULL;
michael@0:     fDesc.fContext->purgeCache();
michael@0: }
michael@0: 
michael@0: void GrTextureStripAtlas::initLRU() {
michael@0:     fLRUFront = NULL;
michael@0:     fLRUBack = NULL;
michael@0:     // Initially all the rows are in the LRU list
michael@0:     for (int i = 0; i < fNumRows; ++i) {
michael@0:         fRows[i].fKey = kEmptyAtlasRowKey;
michael@0:         fRows[i].fNext = NULL;
michael@0:         fRows[i].fPrev = NULL;
michael@0:         this->appendLRU(fRows + i);
michael@0:     }
michael@0:     SkASSERT(NULL == fLRUFront || NULL == fLRUFront->fPrev);
michael@0:     SkASSERT(NULL == fLRUBack || NULL == fLRUBack->fNext);
michael@0: }
michael@0: 
michael@0: void GrTextureStripAtlas::appendLRU(AtlasRow* row) {
michael@0:     SkASSERT(NULL == row->fPrev && NULL == row->fNext);
michael@0:     if (NULL == fLRUFront && NULL == fLRUBack) {
michael@0:         fLRUFront = row;
michael@0:         fLRUBack = row;
michael@0:     } else {
michael@0:         row->fPrev = fLRUBack;
michael@0:         fLRUBack->fNext = row;
michael@0:         fLRUBack = row;
michael@0:     }
michael@0: }
michael@0: 
michael@0: void GrTextureStripAtlas::removeFromLRU(AtlasRow* row) {
michael@0:     SkASSERT(NULL != row);
michael@0:     if (NULL != row->fNext && NULL != row->fPrev) {
michael@0:         row->fPrev->fNext = row->fNext;
michael@0:         row->fNext->fPrev = row->fPrev;
michael@0:     } else {
michael@0:         if (NULL == row->fNext) {
michael@0:             SkASSERT(row == fLRUBack);
michael@0:             fLRUBack = row->fPrev;
michael@0:             if (fLRUBack) {
michael@0:                 fLRUBack->fNext = NULL;
michael@0:             }
michael@0:         }
michael@0:         if (NULL == row->fPrev) {
michael@0:             SkASSERT(row == fLRUFront);
michael@0:             fLRUFront = row->fNext;
michael@0:             if (fLRUFront) {
michael@0:                 fLRUFront->fPrev = NULL;
michael@0:             }
michael@0:         }
michael@0:     }
michael@0:     row->fNext = NULL;
michael@0:     row->fPrev = NULL;
michael@0: }
michael@0: 
michael@0: int GrTextureStripAtlas::searchByKey(uint32_t key) {
michael@0:     AtlasRow target;
michael@0:     target.fKey = key;
michael@0:     return SkTSearch<const AtlasRow,
michael@0:                      GrTextureStripAtlas::KeyLess>((const AtlasRow**)fKeyTable.begin(),
michael@0:                                                    fKeyTable.count(),
michael@0:                                                    &target,
michael@0:                                                    sizeof(AtlasRow*));
michael@0: }
michael@0: 
michael@0: #ifdef SK_DEBUG
michael@0: void GrTextureStripAtlas::validate() {
michael@0: 
michael@0:     // Our key table should be sorted
michael@0:     uint32_t prev = 1 > fKeyTable.count() ? 0 : fKeyTable[0]->fKey;
michael@0:     for (int i = 1; i < fKeyTable.count(); ++i) {
michael@0:         SkASSERT(prev < fKeyTable[i]->fKey);
michael@0:         SkASSERT(fKeyTable[i]->fKey != kEmptyAtlasRowKey);
michael@0:         prev = fKeyTable[i]->fKey;
michael@0:     }
michael@0: 
michael@0:     int lruCount = 0;
michael@0:     // Validate LRU pointers, and count LRU entries
michael@0:     SkASSERT(NULL == fLRUFront || NULL == fLRUFront->fPrev);
michael@0:     SkASSERT(NULL == fLRUBack  || NULL == fLRUBack->fNext);
michael@0:     for (AtlasRow* r = fLRUFront; r != NULL; r = r->fNext) {
michael@0:         if (NULL == r->fNext) {
michael@0:             SkASSERT(r == fLRUBack);
michael@0:         } else {
michael@0:             SkASSERT(r->fNext->fPrev == r);
michael@0:         }
michael@0:         ++lruCount;
michael@0:     }
michael@0: 
michael@0:     int rowLocks = 0;
michael@0:     int freeRows = 0;
michael@0: 
michael@0:     for (int i = 0; i < fNumRows; ++i) {
michael@0:         rowLocks += fRows[i].fLocks;
michael@0:         if (0 == fRows[i].fLocks) {
michael@0:             ++freeRows;
michael@0:             bool inLRU = false;
michael@0:             // Step through the LRU and make sure it's present
michael@0:             for (AtlasRow* r = fLRUFront; r != NULL; r = r->fNext) {
michael@0:                 if (r == &fRows[i]) {
michael@0:                     inLRU = true;
michael@0:                     break;
michael@0:                 }
michael@0:             }
michael@0:             SkASSERT(inLRU);
michael@0:         } else {
michael@0:             // If we are locked, we should have a key
michael@0:             SkASSERT(kEmptyAtlasRowKey != fRows[i].fKey);
michael@0:         }
michael@0: 
michael@0:         // If we have a key != kEmptyAtlasRowKey, it should be in the key table
michael@0:         SkASSERT(fRows[i].fKey == kEmptyAtlasRowKey || this->searchByKey(fRows[i].fKey) >= 0);
michael@0:     }
michael@0: 
michael@0:     // Our count of locks should equal the sum of row locks, unless we ran out of rows and flushed,
michael@0:     // in which case we'll have one more lock than recorded in the rows (to represent the pending
michael@0:     // lock of a row; which ensures we don't unlock the texture prematurely).
michael@0:     SkASSERT(rowLocks == fLockedRows || rowLocks + 1 == fLockedRows);
michael@0: 
michael@0:     // We should have one lru entry for each free row
michael@0:     SkASSERT(freeRows == lruCount);
michael@0: 
michael@0:     // If we have locked rows, we should have a locked texture, otherwise
michael@0:     // it should be unlocked
michael@0:     if (fLockedRows == 0) {
michael@0:         SkASSERT(NULL == fTexture);
michael@0:     } else {
michael@0:         SkASSERT(NULL != fTexture);
michael@0:     }
michael@0: }
michael@0: #endif