New approach for GPU font atlas

In the previous code, each GrTextStrike had exclusive access to one or more GrPlots in the texture atlas. This led to poor packing when only a few glyphs were used. This change allows GrTextStrikes to share GrPlots, thereby getting much better utilization of the entire texture.

BUG=skia:2224
R=robertphillips@google.com, bsalomon@google.com

Author: jvanverth@google.com

Review URL: https://codereview.chromium.org/177463003

git-svn-id: http://skia.googlecode.com/svn/trunk@13636 2bbb7eff-a529-9590-31e7-b0007b416f81

6 files changed, 134 insertions, 165 deletions

diff --git a/src/gpu/GrAtlas.cpp b/src/gpu/GrAtlas.cpp
index 646c213b86..c2fcf46f68 100644
--- a/src/gpu/GrAtlas.cpp
+++ b/src/gpu/GrAtlas.cpp
@@ -35,10 +35,6 @@
 
 ///////////////////////////////////////////////////////////////////////////////
 
-#ifdef SK_DEBUG
-    static int gCounter;
-#endif
-
 // for testing
 #define FONT_CACHE_STATS 0
 #if FONT_CACHE_STATS
@@ -46,7 +42,6 @@ static int g_UploadCount = 0;
 #endif
 
 GrPlot::GrPlot() : fDrawToken(NULL, 0)
-                 , fNext(NULL)
                  , fTexture(NULL)
                  , fAtlasMgr(NULL)
                  , fBytesPerPixel(1)
@@ -94,6 +89,11 @@ bool GrPlot::addSubImage(int width, int height, const void* image,
     return true;
 }
 
+void GrPlot::resetRects() { 
+    SkASSERT(NULL != fRects); 
+    fRects->reset(); 
+}
+
 ///////////////////////////////////////////////////////////////////////////////
 
 GrAtlasMgr::GrAtlasMgr(GrGpu* gpu, GrPixelConfig config) {
@@ -104,19 +104,17 @@ GrAtlasMgr::GrAtlasMgr(GrGpu* gpu, GrPixelConfig config) {
 
     // set up allocated plots
     size_t bpp = GrBytesPerPixel(fPixelConfig);
-    fPlots = SkNEW_ARRAY(GrPlot, (GR_PLOT_WIDTH*GR_PLOT_HEIGHT));
-    fFreePlots = NULL;
-    GrPlot* currPlot = fPlots;
+    fPlotArray = SkNEW_ARRAY(GrPlot, (GR_PLOT_WIDTH*GR_PLOT_HEIGHT));
+
+    GrPlot* currPlot = fPlotArray;
     for (int y = GR_PLOT_HEIGHT-1; y >= 0; --y) {
         for (int x = GR_PLOT_WIDTH-1; x >= 0; --x) {
             currPlot->fAtlasMgr = this;
             currPlot->fOffset.set(x, y);
             currPlot->fBytesPerPixel = bpp;
 
-            // add to free list
-            currPlot->fNext = fFreePlots;
-            fFreePlots = currPlot;
-
+            // build LRU list
+            fPlotList.addToHead(currPlot);
             ++currPlot;
         }
     }
@@ -124,7 +122,7 @@ GrAtlasMgr::GrAtlasMgr(GrGpu* gpu, GrPixelConfig config) {
 
 GrAtlasMgr::~GrAtlasMgr() {
     SkSafeUnref(fTexture);
-    SkDELETE_ARRAY(fPlots);
+    SkDELETE_ARRAY(fPlotArray);
 
     fGpu->unref();
 #if FONT_CACHE_STATS
@@ -132,25 +130,29 @@ GrAtlasMgr::~GrAtlasMgr() {
 #endif
 }
 
+void GrAtlasMgr::moveToHead(GrPlot* plot) {
+    if (fPlotList.head() == plot) {
+        return;
+    }
+  
+    fPlotList.remove(plot);
+    fPlotList.addToHead(plot);
+};
+
 GrPlot* GrAtlasMgr::addToAtlas(GrAtlas* atlas,
                                int width, int height, const void* image,
                                GrIPoint16* loc) {
-    // iterate through entire plot list, see if we can find a hole
-    GrPlot* plotIter = atlas->fPlots;
-    while (plotIter) {
-        if (plotIter->addSubImage(width, height, image, loc)) {
-            return plotIter;
+    // iterate through entire plot list for this atlas, see if we can find a hole
+    // last one was most recently added and probably most empty
+    for (int i = atlas->fPlots.count()-1; i >= 0; --i) {
+        GrPlot* plot = atlas->fPlots[i];
+        if (plot->addSubImage(width, height, image, loc)) {
+            this->moveToHead(plot);
+            return plot;
         }
-        plotIter = plotIter->fNext;
-    }
-
-    // If the above fails, then either we have no starting plot, or the current
-    // plot list is full. Either way we need to allocate a new plot
-    GrPlot* newPlot = this->allocPlot();
-    if (NULL == newPlot) {
-        return NULL;
     }
 
+    // before we get a new plot, make sure we have a backing texture
     if (NULL == fTexture) {
         // TODO: Update this to use the cache rather than directly creating a texture.
         GrTextureDesc desc;
@@ -164,77 +166,53 @@ GrPlot* GrAtlasMgr::addToAtlas(GrAtlas* atlas,
             return NULL;
         }
     }
-    // be sure to set texture for fast lookup
-    newPlot->fTexture = fTexture;
 
-    if (!newPlot->addSubImage(width, height, image, loc)) {
-        this->freePlot(newPlot);
-        return NULL;
+    // now look through all allocated plots for one we can share, in MRU order
+    GrPlotList::Iter plotIter;
+    plotIter.init(fPlotList, GrPlotList::Iter::kHead_IterStart);
+    GrPlot* plot;
+    while (NULL != (plot = plotIter.get())) {
+        // make sure texture is set for quick lookup
+        plot->fTexture = fTexture;
+        if (plot->addSubImage(width, height, image, loc)) {
+            this->moveToHead(plot);
+            // new plot for atlas, put at end of array
+            *(atlas->fPlots.append()) = plot;
+            return plot;
+        }
+        plotIter.next();
     }
 
-    // new plot, put at head
-    newPlot->fNext = atlas->fPlots;
-    atlas->fPlots = newPlot;
-
-    return newPlot;
+    // If the above fails, then the current plot list has no room
+    return NULL;
 }
 
-bool GrAtlasMgr::removeUnusedPlots(GrAtlas* atlas) {
-
-    // GrPlot** is used so that the head element can be easily
-    // modified when the first element is deleted
-    GrPlot** plotRef = &atlas->fPlots;
-    GrPlot* plot = atlas->fPlots;
-    bool removed = false;
-    while (NULL != plot) {
-        if (plot->drawToken().isIssued()) {
-            *plotRef = plot->fNext;
-            this->freePlot(plot);
-            plot = *plotRef;
-            removed = true;
-        } else {
-            plotRef = &plot->fNext;
-            plot = plot->fNext;
+bool GrAtlasMgr::removePlot(GrAtlas* atlas, const GrPlot* plot) {
+    // iterate through plot list for this atlas
+    int count = atlas->fPlots.count();
+    for (int i = 0; i < count; ++i) {
+        if (plot == atlas->fPlots[i]) {
+            atlas->fPlots.remove(i);
+            return true;
         }
     }
 
-    return removed;
-}
-
-void GrAtlasMgr::deletePlotList(GrPlot* plot) {
-    while (NULL != plot) {
-        GrPlot* next = plot->fNext;
-        this->freePlot(plot);
-        plot = next;
-    }
+    return false;
 }
 
-GrPlot* GrAtlasMgr::allocPlot() {
-    if (NULL == fFreePlots) {
-        return NULL;
-    } else {
-        GrPlot* alloc = fFreePlots;
-        fFreePlots = alloc->fNext;
-#ifdef SK_DEBUG
-//        GrPrintf(" GrPlot %p [%d %d] %d\n", this, alloc->fOffset.fX, alloc->fOffset.fY, gCounter);
-        gCounter += 1;
-#endif
-        return alloc;
+// get a plot that's not being used by the current draw
+GrPlot* GrAtlasMgr::getUnusedPlot() {
+    GrPlotList::Iter plotIter;
+    plotIter.init(fPlotList, GrPlotList::Iter::kTail_IterStart);
+    GrPlot* plot;
+    while (NULL != (plot = plotIter.get())) {
+        if (plot->drawToken().isIssued()) {
+            return plot;
+        }
+        plotIter.prev();
     }
 
-}
-
-void GrAtlasMgr::freePlot(GrPlot* plot) {
-    SkASSERT(this == plot->fAtlasMgr);
-
-    plot->fRects->reset();
-    plot->fNext = fFreePlots;
-    fFreePlots = plot;
-
-#ifdef SK_DEBUG
-    --gCounter;
-//    GrPrintf("~GrPlot %p [%d %d] %d\n", this, plot->fOffset.fX, plot->fOffset.fY, gCounter);
-#endif
+    return NULL;
 }
 
 SkISize GrAtlas::getSize() const {
diff --git a/src/gpu/GrAtlas.h b/src/gpu/GrAtlas.h
index e290822fe1..ee4ead92a0 100644
--- a/src/gpu/GrAtlas.h
+++ b/src/gpu/GrAtlas.h
@@ -31,6 +31,8 @@ class GrAtlas;
 
 class GrPlot {
 public:
+    SK_DECLARE_INTERNAL_LLIST_INTERFACE(GrPlot);
+    
     int getOffsetX() const { return fOffset.fX; }
     int getOffsetY() const { return fOffset.fY; }
 
@@ -41,6 +43,8 @@ public:
     GrDrawTarget::DrawToken drawToken() const { return fDrawToken; }
     void setDrawToken(GrDrawTarget::DrawToken draw) { fDrawToken = draw; }
 
+    void resetRects();
+
 private:
     GrPlot();
     ~GrPlot(); // does not try to delete the fNext field
@@ -48,8 +52,6 @@ private:
     // for recycling
     GrDrawTarget::DrawToken fDrawToken;
 
-    GrPlot*                 fNext;
-
     GrTexture*              fTexture;
     GrRectanizer*           fRects;
     GrAtlasMgr*             fAtlasMgr;
@@ -59,6 +61,8 @@ private:
     friend class GrAtlasMgr;
 };
 
+typedef SkTInternalLList<GrPlot> GrPlotList;
+
 class GrAtlasMgr {
 public:
     GrAtlasMgr(GrGpu*, GrPixelConfig);
@@ -68,42 +72,41 @@ public:
     // returns the containing GrPlot and location relative to the backing texture
     GrPlot* addToAtlas(GrAtlas*, int width, int height, const void*, GrIPoint16*);
 
-    // free up any plots that are not waiting on a draw call
-    bool removeUnusedPlots(GrAtlas* atlas);
+    // remove reference to this plot
+    bool removePlot(GrAtlas* atlas, const GrPlot* plot);
 
-    // to be called by ~GrAtlas()
-    void deletePlotList(GrPlot* plot);
+    // get a plot that's not being used by the current draw
+    // this allows us to overwrite this plot without flushing
+    GrPlot* getUnusedPlot();
 
     GrTexture* getTexture() const {
         return fTexture;
     }
 
 private:
-    GrPlot* allocPlot();
-    void freePlot(GrPlot* plot);
+    void moveToHead(GrPlot* plot);
 
     GrGpu*        fGpu;
     GrPixelConfig fPixelConfig;
     GrTexture*    fTexture;
 
     // allocated array of GrPlots
-    GrPlot*       fPlots;
-    // linked list of free GrPlots
-    GrPlot*       fFreePlots;
+    GrPlot*       fPlotArray;
+    // LRU list of GrPlots
+    GrPlotList    fPlotList;
 };
 
 class GrAtlas {
 public:
-    GrAtlas(GrAtlasMgr* mgr) : fPlots(NULL), fAtlasMgr(mgr) { }
-    ~GrAtlas() { fAtlasMgr->deletePlotList(fPlots); }
+    GrAtlas() { }
+    ~GrAtlas() { }
 
-    bool isEmpty() { return NULL == fPlots; }
+    bool isEmpty() { return 0 == fPlots.count(); }
 
     SkISize getSize() const;
 
 private:
-    GrPlot*     fPlots;
-    GrAtlasMgr* fAtlasMgr;
+    SkTDArray<GrPlot*> fPlots;
 
     friend class GrAtlasMgr;
 };
diff --git a/src/gpu/GrBitmapTextContext.cpp b/src/gpu/GrBitmapTextContext.cpp
index 4f43c75899..f2a6d95cb8 100755
--- a/src/gpu/GrBitmapTextContext.cpp
+++ b/src/gpu/GrBitmapTextContext.cpp
@@ -518,13 +518,13 @@ void GrBitmapTextContext::drawPackedGlyph(GrGlyph::PackedID packed,
     }
 
     if (NULL == glyph->fPlot) {
-        if (fStrike->getGlyphAtlas(glyph, scaler)) {
+        if (fStrike->addGlyphToAtlas(glyph, scaler)) {
             goto HAS_ATLAS;
         }
 
         // try to clear out an unused plot before we flush
-        fContext->getFontCache()->freePlotExceptFor(fStrike);
-        if (fStrike->getGlyphAtlas(glyph, scaler)) {
+        if (fContext->getFontCache()->freeUnusedPlot(fStrike) &&
+            fStrike->addGlyphToAtlas(glyph, scaler)) {
             goto HAS_ATLAS;
         }
 
@@ -534,14 +534,13 @@ void GrBitmapTextContext::drawPackedGlyph(GrGlyph::PackedID packed,
 #endif
         }
 
-        // before we purge the cache, we must flush any accumulated draws
+        // flush any accumulated draws to allow us to free up a plot
         this->flushGlyphs();
         fContext->flush();
 
-        // try to purge
-        fContext->getFontCache()->purgeExceptFor(fStrike);
-        // need to use new flush count here
-        if (fStrike->getGlyphAtlas(glyph, scaler)) {
+        // we should have an unused plot now
+        if (fContext->getFontCache()->freeUnusedPlot(fStrike) &&
+            fStrike->addGlyphToAtlas(glyph, scaler)) {
             goto HAS_ATLAS;
         }
 
diff --git a/src/gpu/GrDistanceFieldTextContext.cpp b/src/gpu/GrDistanceFieldTextContext.cpp
index c22807d396..e372b6cb1b 100755
--- a/src/gpu/GrDistanceFieldTextContext.cpp
+++ b/src/gpu/GrDistanceFieldTextContext.cpp
@@ -161,13 +161,13 @@ void GrDistanceFieldTextContext::drawPackedGlyph(GrGlyph::PackedID packed,
     }
 */
     if (NULL == glyph->fPlot) {
-        if (fStrike->getGlyphAtlas(glyph, scaler)) {
+        if (fStrike->addGlyphToAtlas(glyph, scaler)) {
             goto HAS_ATLAS;
         }
 
         // try to clear out an unused plot before we flush
-        fContext->getFontCache()->freePlotExceptFor(fStrike);
-        if (fStrike->getGlyphAtlas(glyph, scaler)) {
+        if (fContext->getFontCache()->freeUnusedPlot(fStrike) &&
+            fStrike->addGlyphToAtlas(glyph, scaler)) {
             goto HAS_ATLAS;
         }
 
@@ -181,10 +181,9 @@ void GrDistanceFieldTextContext::drawPackedGlyph(GrGlyph::PackedID packed,
         this->flushGlyphs();
         fContext->flush();
 
-        // try to purge
-        fContext->getFontCache()->purgeExceptFor(fStrike);
-        // need to use new flush count here
-        if (fStrike->getGlyphAtlas(glyph, scaler)) {
+        // we should have an unused plot now
+        if (fContext->getFontCache()->freeUnusedPlot(fStrike) &&
+            fStrike->addGlyphToAtlas(glyph, scaler)) {
             goto HAS_ATLAS;
         }
 
diff --git a/src/gpu/GrTextStrike.cpp b/src/gpu/GrTextStrike.cpp
index c70e822cd9..e303a23df8 100644
--- a/src/gpu/GrTextStrike.cpp
+++ b/src/gpu/GrTextStrike.cpp
@@ -110,47 +110,39 @@ void GrFontCache::purgeStrike(GrTextStrike* strike) {
     delete strike;
 }
 
-void GrFontCache::purgeExceptFor(GrTextStrike* preserveStrike) {
+bool GrFontCache::freeUnusedPlot(GrTextStrike* preserveStrike) {
     SkASSERT(NULL != preserveStrike);
-    GrTextStrike* strike = fTail;
-    bool purge = true;
+
+    GrAtlasMgr* atlasMgr = preserveStrike->fAtlasMgr;
+    GrPlot* plot = atlasMgr->getUnusedPlot();
+    if (NULL == plot) {
+        return false;
+    }
+    plot->resetRects();
+
+    GrTextStrike* strike = fHead;
     GrMaskFormat maskFormat = preserveStrike->fMaskFormat;
     while (strike) {
-        if (strike == preserveStrike || maskFormat != strike->fMaskFormat) {
-            strike = strike->fPrev;
+        if (maskFormat != strike->fMaskFormat) {
+            strike = strike->fNext;
             continue;
         }
+
         GrTextStrike* strikeToPurge = strike;
-        strike = strikeToPurge->fPrev;
-        if (purge) {
-            // keep purging if we won't free up any atlases with this strike.
-            purge = strikeToPurge->fAtlas.isEmpty();
+        strike = strikeToPurge->fNext;
+        strikeToPurge->removePlot(plot);
+
+        // clear out any empty strikes (except this one)
+        if (strikeToPurge != preserveStrike && strikeToPurge->fAtlas.isEmpty()) {
             this->purgeStrike(strikeToPurge);
         }
     }
+
 #if FONT_CACHE_STATS
     ++g_PurgeCount;
 #endif
-}
 
-void GrFontCache::freePlotExceptFor(GrTextStrike* preserveStrike) {
-    SkASSERT(NULL != preserveStrike);
-    GrTextStrike* strike = fTail;
-    GrMaskFormat maskFormat = preserveStrike->fMaskFormat;
-    while (strike) {
-        if (strike == preserveStrike || maskFormat != strike->fMaskFormat) {
-            strike = strike->fPrev;
-            continue;
-        }
-        GrTextStrike* strikeToPurge = strike;
-        strike = strikeToPurge->fPrev;
-        if (strikeToPurge->removeUnusedPlots()) {
-            if (strikeToPurge->fAtlas.isEmpty()) {
-                this->purgeStrike(strikeToPurge);
-            }
-            break;
-        }
-    }
+    return true;
 }
 
 #ifdef SK_DEBUG
@@ -221,7 +213,7 @@ void GrFontCache::dump() const {
 
 GrTextStrike::GrTextStrike(GrFontCache* cache, const GrKey* key,
                            GrMaskFormat format,
-                           GrAtlasMgr* atlasMgr) : fPool(64), fAtlas(atlasMgr) {
+                           GrAtlasMgr* atlasMgr) : fPool(64) {
     fFontScalerKey = key;
     fFontScalerKey->ref();
 
@@ -236,16 +228,10 @@ GrTextStrike::GrTextStrike(GrFontCache* cache, const GrKey* key,
 #endif
 }
 
-// these signatures are needed because they're used with
-// SkTDArray::visitAll() (see destructor & removeUnusedAtlases())
+// this signature is needed because it's used with
+// SkTDArray::visitAll() (see destructor)
 static void free_glyph(GrGlyph*& glyph) { glyph->free(); }
 
-static void invalidate_glyph(GrGlyph*& glyph) {
-    if (glyph->fPlot && glyph->fPlot->drawToken().isIssued()) {
-        glyph->fPlot = NULL;
-    }
-}
-
 GrTextStrike::~GrTextStrike() {
     fFontScalerKey->unref();
     fCache.getArray().visitAll(free_glyph);
@@ -278,13 +264,19 @@ GrGlyph* GrTextStrike::generateGlyph(GrGlyph::PackedID packed,
     return glyph;
 }
 
-bool GrTextStrike::removeUnusedPlots() {
-    fCache.getArray().visitAll(invalidate_glyph);
-    return fAtlasMgr->removeUnusedPlots(&fAtlas);
+void GrTextStrike::removePlot(const GrPlot* plot) {
+    SkTDArray<GrGlyph*>& glyphArray = fCache.getArray();
+    for (int i = 0; i < glyphArray.count(); ++i) {
+        if (plot == glyphArray[i]->fPlot) {
+            glyphArray[i]->fPlot = NULL;
+        }
+    }
+
+    fAtlasMgr->removePlot(&fAtlas, plot);
 }
 
 
-bool GrTextStrike::getGlyphAtlas(GrGlyph* glyph, GrFontScaler* scaler) {
+bool GrTextStrike::addGlyphToAtlas(GrGlyph* glyph, GrFontScaler* scaler) {
 #if 0   // testing hack to force us to flush our cache often
     static int gCounter;
     if ((++gCounter % 10) == 0) return false;
diff --git a/src/gpu/GrTextStrike.h b/src/gpu/GrTextStrike.h
index 17dcec618c..784ea91544 100644
--- a/src/gpu/GrTextStrike.h
+++ b/src/gpu/GrTextStrike.h
@@ -37,7 +37,7 @@ public:
     GrMaskFormat getMaskFormat() const { return fMaskFormat; }
 
     inline GrGlyph* getGlyph(GrGlyph::PackedID, GrFontScaler*);
-    bool getGlyphAtlas(GrGlyph*, GrFontScaler*);
+    bool addGlyphToAtlas(GrGlyph*, GrFontScaler*);
 
     SkISize getAtlasSize() const { return fAtlas.getSize(); }
 
@@ -47,11 +47,11 @@ public:
         return fCache.getArray()[index];
     }
 
-    // returns true if a plot was removed
-    bool removeUnusedPlots();
+    // remove any references to this plot
+    void removePlot(const GrPlot* plot);
 
 public:
-    // for LRU
+    // for easy removal from list
     GrTextStrike*   fPrev;
     GrTextStrike*   fNext;
 
@@ -88,10 +88,8 @@ public:
 
     void freeAll();
 
-    void purgeExceptFor(GrTextStrike*);
-
-    // remove an unused plot and its strike (if necessary)
-    void freePlotExceptFor(GrTextStrike*);
+    // make an unused plot available
+    bool freeUnusedPlot(GrTextStrike* preserveStrike);
 
     // testing
     int countStrikes() const { return fCache.getArray().count(); }