SkGlyphCache.cpp revision 7c5a806bf67e1818b0272a2ae8d854ae1fd72e82 
1/*
2 * Copyright 2006 The Android Open Source Project
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "SkGlyphCache.h"
9#include "SkGlyphCache_Globals.h"
10#include "SkGraphics.h"
11#include "SkOnce.h"
12#include "SkPath.h"
13#include "SkTemplates.h"
14#include "SkTraceMemoryDump.h"
15#include "SkTypeface.h"
16
17#include <cctype>
18
19//#define SPEW_PURGE_STATUS
20
21namespace {
22const char gGlyphCacheDumpName[] = "skia/sk_glyph_cache";
23}  // namespace
24
25// Returns the shared globals
26static SkGlyphCache_Globals& get_globals() {
27    static SkOnce once;
28    static SkGlyphCache_Globals* globals;
29
30    once([]{ globals = new SkGlyphCache_Globals; });
31    return *globals;
32}
33
34///////////////////////////////////////////////////////////////////////////////
35
36SkGlyphCache::SkGlyphCache(const SkDescriptor* desc, std::unique_ptr<SkScalerContext> ctx)
37    : fDesc(desc->copy())
38    , fScalerContext(std::move(ctx)) {
39    SkASSERT(desc);
40    SkASSERT(fScalerContext);
41
42    fPrev = fNext = nullptr;
43
44    fScalerContext->getFontMetrics(&fFontMetrics);
45
46    fMemoryUsed = sizeof(*this);
47}
48
49SkGlyphCache::~SkGlyphCache() {
50    fGlyphMap.foreach([](SkGlyph* g) {
51        if (g->fPathData) {
52            delete g->fPathData->fPath;
53        }
54    });
55}
56
57SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(SkPackedUnicharID packedUnicharID) {
58    if (!fPackedUnicharIDToPackedGlyphID) {
59        fPackedUnicharIDToPackedGlyphID.reset(new CharGlyphRec[kHashCount]);
60    }
61
62    return &fPackedUnicharIDToPackedGlyphID[packedUnicharID.hash() & kHashMask];
63}
64
65///////////////////////////////////////////////////////////////////////////////
66
67#ifdef SK_DEBUG
68#define VALIDATE()  AutoValidate av(this)
69#else
70#define VALIDATE()
71#endif
72
73SkGlyphID SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
74    VALIDATE();
75    SkPackedUnicharID packedUnicharID(charCode);
76    CharGlyphRec* rec = this->getCharGlyphRec(packedUnicharID);
77
78    if (rec->fPackedUnicharID == packedUnicharID) {
79        // The glyph exists in the unichar to glyph mapping cache. Return it.
80        return rec->fPackedGlyphID.code();
81    } else {
82        // The glyph is not in the unichar to glyph mapping cache. Insert it.
83        rec->fPackedUnicharID = packedUnicharID;
84        SkGlyphID glyphID = fScalerContext->charToGlyphID(charCode);
85        rec->fPackedGlyphID = SkPackedGlyphID(glyphID);
86        return glyphID;
87    }
88}
89
90SkUnichar SkGlyphCache::glyphToUnichar(SkGlyphID glyphID) {
91    return fScalerContext->glyphIDToChar(glyphID);
92}
93
94unsigned SkGlyphCache::getGlyphCount() const {
95    return fScalerContext->getGlyphCount();
96}
97
98int SkGlyphCache::countCachedGlyphs() const {
99    return fGlyphMap.count();
100}
101
102///////////////////////////////////////////////////////////////////////////////
103
104const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) {
105    VALIDATE();
106    return *this->lookupByChar(charCode, kJustAdvance_MetricsType);
107}
108
109const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
110    VALIDATE();
111    SkPackedGlyphID packedGlyphID(glyphID);
112    return *this->lookupByPackedGlyphID(packedGlyphID, kJustAdvance_MetricsType);
113}
114
115///////////////////////////////////////////////////////////////////////////////
116
117const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode) {
118    VALIDATE();
119    return *this->lookupByChar(charCode, kFull_MetricsType);
120}
121
122const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode, SkFixed x, SkFixed y) {
123    VALIDATE();
124    return *this->lookupByChar(charCode, kFull_MetricsType, x, y);
125}
126
127const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
128    VALIDATE();
129    SkPackedGlyphID packedGlyphID(glyphID);
130    return *this->lookupByPackedGlyphID(packedGlyphID, kFull_MetricsType);
131}
132
133const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) {
134    VALIDATE();
135    SkPackedGlyphID packedGlyphID(glyphID, x, y);
136    return *this->lookupByPackedGlyphID(packedGlyphID, kFull_MetricsType);
137}
138
139SkGlyph* SkGlyphCache::lookupByChar(SkUnichar charCode, MetricsType type, SkFixed x, SkFixed y) {
140    SkPackedUnicharID id(charCode, x, y);
141    CharGlyphRec* rec = this->getCharGlyphRec(id);
142    if (rec->fPackedUnicharID != id) {
143        rec->fPackedUnicharID = id;
144        rec->fPackedGlyphID = SkPackedGlyphID(fScalerContext->charToGlyphID(charCode), x, y);
145    }
146    return this->lookupByPackedGlyphID(rec->fPackedGlyphID, type);
147}
148
149SkGlyph* SkGlyphCache::lookupByPackedGlyphID(SkPackedGlyphID packedGlyphID, MetricsType type) {
150    SkGlyph* glyph = fGlyphMap.find(packedGlyphID);
151
152    if (nullptr == glyph) {
153        glyph = this->allocateNewGlyph(packedGlyphID, type);
154    } else {
155        if (type == kFull_MetricsType && glyph->isJustAdvance()) {
156           fScalerContext->getMetrics(glyph);
157        }
158    }
159    return glyph;
160}
161
162SkGlyph* SkGlyphCache::allocateNewGlyph(SkPackedGlyphID packedGlyphID, MetricsType mtype) {
163    fMemoryUsed += sizeof(SkGlyph);
164
165    SkGlyph* glyphPtr;
166    {
167        SkGlyph glyph;
168        glyph.initWithGlyphID(packedGlyphID);
169        glyphPtr = fGlyphMap.set(glyph);
170    }
171
172    if (kJustAdvance_MetricsType == mtype) {
173        fScalerContext->getAdvance(glyphPtr);
174    } else {
175        SkASSERT(kFull_MetricsType == mtype);
176        fScalerContext->getMetrics(glyphPtr);
177    }
178
179    SkASSERT(glyphPtr->fID != SkPackedGlyphID());
180    return glyphPtr;
181}
182
183const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
184    if (glyph.fWidth > 0 && glyph.fWidth < kMaxGlyphWidth) {
185        if (nullptr == glyph.fImage) {
186            size_t  size = const_cast<SkGlyph&>(glyph).allocImage(&fAlloc);
187            // check that alloc() actually succeeded
188            if (glyph.fImage) {
189                fScalerContext->getImage(glyph);
190                // TODO: the scaler may have changed the maskformat during
191                // getImage (e.g. from AA or LCD to BW) which means we may have
192                // overallocated the buffer. Check if the new computedImageSize
193                // is smaller, and if so, strink the alloc size in fImageAlloc.
194                fMemoryUsed += size;
195            }
196        }
197    }
198    return glyph.fImage;
199}
200
201const SkPath* SkGlyphCache::findPath(const SkGlyph& glyph) {
202    if (glyph.fWidth) {
203        if (glyph.fPathData == nullptr) {
204            SkGlyph::PathData* pathData = fAlloc.make<SkGlyph::PathData>();
205            const_cast<SkGlyph&>(glyph).fPathData = pathData;
206            pathData->fIntercept = nullptr;
207            SkPath* path = pathData->fPath = new SkPath;
208            fScalerContext->getPath(glyph.getPackedID(), path);
209            fMemoryUsed += sizeof(SkPath) + path->countPoints() * sizeof(SkPoint);
210        }
211    }
212    return glyph.fPathData ? glyph.fPathData->fPath : nullptr;
213}
214
215#include "../pathops/SkPathOpsCubic.h"
216#include "../pathops/SkPathOpsQuad.h"
217
218static bool quad_in_bounds(const SkScalar* pts, const SkScalar bounds[2]) {
219    SkScalar min = SkTMin(SkTMin(pts[0], pts[2]), pts[4]);
220    if (bounds[1] < min) {
221        return false;
222    }
223    SkScalar max = SkTMax(SkTMax(pts[0], pts[2]), pts[4]);
224    return bounds[0] < max;
225}
226
227static bool cubic_in_bounds(const SkScalar* pts, const SkScalar bounds[2]) {
228    SkScalar min = SkTMin(SkTMin(SkTMin(pts[0], pts[2]), pts[4]), pts[6]);
229    if (bounds[1] < min) {
230        return false;
231    }
232    SkScalar max = SkTMax(SkTMax(SkTMax(pts[0], pts[2]), pts[4]), pts[6]);
233    return bounds[0] < max;
234}
235
236void SkGlyphCache::OffsetResults(const SkGlyph::Intercept* intercept, SkScalar scale,
237                                 SkScalar xPos, SkScalar* array, int* count) {
238    if (array) {
239        array += *count;
240        for (int index = 0; index < 2; index++) {
241            *array++ = intercept->fInterval[index] * scale + xPos;
242        }
243    }
244    *count += 2;
245}
246
247void SkGlyphCache::AddInterval(SkScalar val, SkGlyph::Intercept* intercept) {
248    intercept->fInterval[0] = SkTMin(intercept->fInterval[0], val);
249    intercept->fInterval[1] = SkTMax(intercept->fInterval[1], val);
250}
251
252void SkGlyphCache::AddPoints(const SkPoint* pts, int ptCount, const SkScalar bounds[2],
253        bool yAxis, SkGlyph::Intercept* intercept) {
254    for (int i = 0; i < ptCount; ++i) {
255        SkScalar val = *(&pts[i].fY - yAxis);
256        if (bounds[0] < val && val < bounds[1]) {
257            AddInterval(*(&pts[i].fX + yAxis), intercept);
258        }
259    }
260}
261
262void SkGlyphCache::AddLine(const SkPoint pts[2], SkScalar axis, bool yAxis,
263                     SkGlyph::Intercept* intercept) {
264    SkScalar t = yAxis ? (axis - pts[0].fX) / (pts[1].fX - pts[0].fX)
265            : (axis - pts[0].fY) / (pts[1].fY - pts[0].fY);
266    if (0 <= t && t < 1) {   // this handles divide by zero above
267        AddInterval(yAxis ? pts[0].fY + t * (pts[1].fY - pts[0].fY)
268            : pts[0].fX + t * (pts[1].fX - pts[0].fX), intercept);
269    }
270}
271
272void SkGlyphCache::AddQuad(const SkPoint pts[2], SkScalar axis, bool yAxis,
273                     SkGlyph::Intercept* intercept) {
274    SkDQuad quad;
275    quad.set(pts);
276    double roots[2];
277    int count = yAxis ? quad.verticalIntersect(axis, roots)
278            : quad.horizontalIntersect(axis, roots);
279    while (--count >= 0) {
280        SkPoint pt = quad.ptAtT(roots[count]).asSkPoint();
281        AddInterval(*(&pt.fX + yAxis), intercept);
282    }
283}
284
285void SkGlyphCache::AddCubic(const SkPoint pts[3], SkScalar axis, bool yAxis,
286                      SkGlyph::Intercept* intercept) {
287    SkDCubic cubic;
288    cubic.set(pts);
289    double roots[3];
290    int count = yAxis ? cubic.verticalIntersect(axis, roots)
291            : cubic.horizontalIntersect(axis, roots);
292    while (--count >= 0) {
293        SkPoint pt = cubic.ptAtT(roots[count]).asSkPoint();
294        AddInterval(*(&pt.fX + yAxis), intercept);
295    }
296}
297
298const SkGlyph::Intercept* SkGlyphCache::MatchBounds(const SkGlyph* glyph,
299                                                    const SkScalar bounds[2]) {
300    if (!glyph->fPathData) {
301        return nullptr;
302    }
303    const SkGlyph::Intercept* intercept = glyph->fPathData->fIntercept;
304    while (intercept) {
305        if (bounds[0] == intercept->fBounds[0] && bounds[1] == intercept->fBounds[1]) {
306            return intercept;
307        }
308        intercept = intercept->fNext;
309    }
310    return nullptr;
311}
312
313void SkGlyphCache::findIntercepts(const SkScalar bounds[2], SkScalar scale, SkScalar xPos,
314        bool yAxis, SkGlyph* glyph, SkScalar* array, int* count) {
315    const SkGlyph::Intercept* match = MatchBounds(glyph, bounds);
316
317    if (match) {
318        if (match->fInterval[0] < match->fInterval[1]) {
319            OffsetResults(match, scale, xPos, array, count);
320        }
321        return;
322    }
323
324    SkGlyph::Intercept* intercept = fAlloc.make<SkGlyph::Intercept>();
325    intercept->fNext = glyph->fPathData->fIntercept;
326    intercept->fBounds[0] = bounds[0];
327    intercept->fBounds[1] = bounds[1];
328    intercept->fInterval[0] = SK_ScalarMax;
329    intercept->fInterval[1] = SK_ScalarMin;
330    glyph->fPathData->fIntercept = intercept;
331    const SkPath* path = glyph->fPathData->fPath;
332    const SkRect& pathBounds = path->getBounds();
333    if (*(&pathBounds.fBottom - yAxis) < bounds[0] || bounds[1] < *(&pathBounds.fTop - yAxis)) {
334        return;
335    }
336    SkPath::Iter iter(*path, false);
337    SkPoint pts[4];
338    SkPath::Verb verb;
339    while (SkPath::kDone_Verb != (verb = iter.next(pts))) {
340        switch (verb) {
341            case SkPath::kMove_Verb:
342                break;
343            case SkPath::kLine_Verb:
344                AddLine(pts, bounds[0], yAxis, intercept);
345                AddLine(pts, bounds[1], yAxis, intercept);
346                AddPoints(pts, 2, bounds, yAxis, intercept);
347                break;
348            case SkPath::kQuad_Verb:
349                if (!quad_in_bounds(&pts[0].fY - yAxis, bounds)) {
350                    break;
351                }
352                AddQuad(pts, bounds[0], yAxis, intercept);
353                AddQuad(pts, bounds[1], yAxis, intercept);
354                AddPoints(pts, 3, bounds, yAxis, intercept);
355                break;
356            case SkPath::kConic_Verb:
357                SkASSERT(0);  // no support for text composed of conics
358                break;
359            case SkPath::kCubic_Verb:
360                if (!cubic_in_bounds(&pts[0].fY - yAxis, bounds)) {
361                    break;
362                }
363                AddCubic(pts, bounds[0], yAxis, intercept);
364                AddCubic(pts, bounds[1], yAxis, intercept);
365                AddPoints(pts, 4, bounds, yAxis, intercept);
366                break;
367            case SkPath::kClose_Verb:
368                break;
369            default:
370                SkASSERT(0);
371                break;
372        }
373    }
374    if (intercept->fInterval[0] >= intercept->fInterval[1]) {
375        intercept->fInterval[0] = SK_ScalarMax;
376        intercept->fInterval[1] = SK_ScalarMin;
377        return;
378    }
379    OffsetResults(intercept, scale, xPos, array, count);
380}
381
382void SkGlyphCache::dump() const {
383    const SkTypeface* face = fScalerContext->getTypeface();
384    const SkScalerContextRec& rec = fScalerContext->getRec();
385    SkMatrix matrix;
386    rec.getSingleMatrix(&matrix);
387    matrix.preScale(SkScalarInvert(rec.fTextSize), SkScalarInvert(rec.fTextSize));
388    SkString name;
389    face->getFamilyName(&name);
390
391    SkString msg;
392    msg.printf("cache typeface:%x %25s:%d size:%2g [%g %g %g %g] lum:%02X devG:%d pntG:%d cntr:%d glyphs:%3d",
393               face->uniqueID(), name.c_str(), face->style(), rec.fTextSize,
394               matrix[SkMatrix::kMScaleX], matrix[SkMatrix::kMSkewX],
395               matrix[SkMatrix::kMSkewY], matrix[SkMatrix::kMScaleY],
396               rec.fLumBits & 0xFF, rec.fDeviceGamma, rec.fPaintGamma, rec.fContrast,
397               fGlyphMap.count());
398    SkDebugf("%s\n", msg.c_str());
399}
400
401///////////////////////////////////////////////////////////////////////////////
402///////////////////////////////////////////////////////////////////////////////
403
404size_t SkGlyphCache_Globals::getTotalMemoryUsed() const {
405    SkAutoExclusive ac(fLock);
406    return fTotalMemoryUsed;
407}
408
409int SkGlyphCache_Globals::getCacheCountUsed() const {
410    SkAutoExclusive ac(fLock);
411    return fCacheCount;
412}
413
414int SkGlyphCache_Globals::getCacheCountLimit() const {
415    SkAutoExclusive ac(fLock);
416    return fCacheCountLimit;
417}
418
419size_t SkGlyphCache_Globals::setCacheSizeLimit(size_t newLimit) {
420    static const size_t minLimit = 256 * 1024;
421    if (newLimit < minLimit) {
422        newLimit = minLimit;
423    }
424
425    SkAutoExclusive ac(fLock);
426
427    size_t prevLimit = fCacheSizeLimit;
428    fCacheSizeLimit = newLimit;
429    this->internalPurge();
430    return prevLimit;
431}
432
433size_t  SkGlyphCache_Globals::getCacheSizeLimit() const {
434    SkAutoExclusive ac(fLock);
435    return fCacheSizeLimit;
436}
437
438int SkGlyphCache_Globals::setCacheCountLimit(int newCount) {
439    if (newCount < 0) {
440        newCount = 0;
441    }
442
443    SkAutoExclusive ac(fLock);
444
445    int prevCount = fCacheCountLimit;
446    fCacheCountLimit = newCount;
447    this->internalPurge();
448    return prevCount;
449}
450
451void SkGlyphCache_Globals::purgeAll() {
452    SkAutoExclusive ac(fLock);
453    this->internalPurge(fTotalMemoryUsed);
454}
455
456/*  This guy calls the visitor from within the mutext lock, so the visitor
457    cannot:
458    - take too much time
459    - try to acquire the mutext again
460    - call a fontscaler (which might call into the cache)
461*/
462SkGlyphCache* SkGlyphCache::VisitCache(SkTypeface* typeface,
463                                       const SkScalerContextEffects& effects,
464                                       const SkDescriptor* desc,
465                                       bool (*proc)(const SkGlyphCache*, void*),
466                                       void* context) {
467    if (!typeface) {
468        typeface = SkTypeface::GetDefaultTypeface();
469    }
470    SkASSERT(desc);
471
472    // Precondition: the typeface id must be the fFontID in the descriptor
473    SkDEBUGCODE(
474        uint32_t length = 0;
475        const SkScalerContext::Rec* rec = static_cast<const SkScalerContext::Rec*>(
476            desc->findEntry(kRec_SkDescriptorTag, &length));
477        SkASSERT(rec);
478        SkASSERT(length == sizeof(*rec));
479        SkASSERT(typeface->uniqueID() == rec->fFontID);
480    )
481
482    SkGlyphCache_Globals& globals = get_globals();
483    SkGlyphCache*         cache;
484
485    {
486        SkAutoExclusive ac(globals.fLock);
487
488        globals.validate();
489
490        for (cache = globals.internalGetHead(); cache != nullptr; cache = cache->fNext) {
491            if (*cache->fDesc == *desc) {
492                globals.internalDetachCache(cache);
493                if (!proc(cache, context)) {
494                    globals.internalAttachCacheToHead(cache);
495                    cache = nullptr;
496                }
497                return cache;
498            }
499        }
500    }
501
502    // Check if we can create a scaler-context before creating the glyphcache.
503    // If not, we may have exhausted OS/font resources, so try purging the
504    // cache once and try again.
505    {
506        // pass true the first time, to notice if the scalercontext failed,
507        // so we can try the purge.
508        std::unique_ptr<SkScalerContext> ctx = typeface->createScalerContext(effects, desc, true);
509        if (!ctx) {
510            get_globals().purgeAll();
511            ctx = typeface->createScalerContext(effects, desc, false);
512            SkASSERT(ctx);
513        }
514        cache = new SkGlyphCache(desc, std::move(ctx));
515    }
516
517    AutoValidate av(cache);
518
519    if (!proc(cache, context)) {   // need to reattach
520        globals.attachCacheToHead(cache);
521        cache = nullptr;
522    }
523    return cache;
524}
525
526void SkGlyphCache::AttachCache(SkGlyphCache* cache) {
527    SkASSERT(cache);
528    SkASSERT(cache->fNext == nullptr);
529
530    get_globals().attachCacheToHead(cache);
531}
532
533static void dump_visitor(const SkGlyphCache& cache, void* context) {
534    int* counter = (int*)context;
535    int index = *counter;
536    *counter += 1;
537
538    const SkScalerContextRec& rec = cache.getScalerContext()->getRec();
539
540    SkDebugf("[%3d] ID %3d, glyphs %3d, size %g, scale %g, skew %g, [%g %g %g %g]\n",
541             index, rec.fFontID, cache.countCachedGlyphs(),
542             rec.fTextSize, rec.fPreScaleX, rec.fPreSkewX,
543             rec.fPost2x2[0][0], rec.fPost2x2[0][1], rec.fPost2x2[1][0], rec.fPost2x2[1][1]);
544}
545
546void SkGlyphCache::Dump() {
547    SkDebugf("GlyphCache [     used    budget ]\n");
548    SkDebugf("    bytes  [ %8zu  %8zu ]\n",
549             SkGraphics::GetFontCacheUsed(), SkGraphics::GetFontCacheLimit());
550    SkDebugf("    count  [ %8zu  %8zu ]\n",
551             SkGraphics::GetFontCacheCountUsed(), SkGraphics::GetFontCacheCountLimit());
552
553    int counter = 0;
554    SkGlyphCache::VisitAll(dump_visitor, &counter);
555}
556
557static void sk_trace_dump_visitor(const SkGlyphCache& cache, void* context) {
558    SkTraceMemoryDump* dump = static_cast<SkTraceMemoryDump*>(context);
559
560    const SkTypeface* face = cache.getScalerContext()->getTypeface();
561    const SkScalerContextRec& rec = cache.getScalerContext()->getRec();
562
563    SkString fontName;
564    face->getFamilyName(&fontName);
565    // Replace all special characters with '_'.
566    for (size_t index = 0; index < fontName.size(); ++index) {
567        if (!std::isalnum(fontName[index])) {
568            fontName[index] = '_';
569        }
570    }
571
572    SkString dumpName = SkStringPrintf("%s/%s_%d/%p",
573                                       gGlyphCacheDumpName, fontName.c_str(), rec.fFontID, &cache);
574
575    dump->dumpNumericValue(dumpName.c_str(), "size", "bytes", cache.getMemoryUsed());
576    dump->dumpNumericValue(dumpName.c_str(), "glyph_count", "objects", cache.countCachedGlyphs());
577    dump->setMemoryBacking(dumpName.c_str(), "malloc", nullptr);
578}
579
580void SkGlyphCache::DumpMemoryStatistics(SkTraceMemoryDump* dump) {
581    dump->dumpNumericValue(gGlyphCacheDumpName, "size", "bytes", SkGraphics::GetFontCacheUsed());
582    dump->dumpNumericValue(gGlyphCacheDumpName, "budget_size", "bytes",
583                           SkGraphics::GetFontCacheLimit());
584    dump->dumpNumericValue(gGlyphCacheDumpName, "glyph_count", "objects",
585                           SkGraphics::GetFontCacheCountUsed());
586    dump->dumpNumericValue(gGlyphCacheDumpName, "budget_glyph_count", "objects",
587                           SkGraphics::GetFontCacheCountLimit());
588
589    if (dump->getRequestedDetails() == SkTraceMemoryDump::kLight_LevelOfDetail) {
590        dump->setMemoryBacking(gGlyphCacheDumpName, "malloc", nullptr);
591        return;
592    }
593
594    SkGlyphCache::VisitAll(sk_trace_dump_visitor, dump);
595}
596
597void SkGlyphCache::VisitAll(Visitor visitor, void* context) {
598    SkGlyphCache_Globals& globals = get_globals();
599    SkAutoExclusive ac(globals.fLock);
600    SkGlyphCache*         cache;
601
602    globals.validate();
603
604    for (cache = globals.internalGetHead(); cache != nullptr; cache = cache->fNext) {
605        visitor(*cache, context);
606    }
607}
608
609///////////////////////////////////////////////////////////////////////////////
610
611void SkGlyphCache_Globals::attachCacheToHead(SkGlyphCache* cache) {
612    SkAutoExclusive ac(fLock);
613
614    this->validate();
615    cache->validate();
616
617    this->internalAttachCacheToHead(cache);
618    this->internalPurge();
619}
620
621SkGlyphCache* SkGlyphCache_Globals::internalGetTail() const {
622    SkGlyphCache* cache = fHead;
623    if (cache) {
624        while (cache->fNext) {
625            cache = cache->fNext;
626        }
627    }
628    return cache;
629}
630
631size_t SkGlyphCache_Globals::internalPurge(size_t minBytesNeeded) {
632    this->validate();
633
634    size_t bytesNeeded = 0;
635    if (fTotalMemoryUsed > fCacheSizeLimit) {
636        bytesNeeded = fTotalMemoryUsed - fCacheSizeLimit;
637    }
638    bytesNeeded = SkTMax(bytesNeeded, minBytesNeeded);
639    if (bytesNeeded) {
640        // no small purges!
641        bytesNeeded = SkTMax(bytesNeeded, fTotalMemoryUsed >> 2);
642    }
643
644    int countNeeded = 0;
645    if (fCacheCount > fCacheCountLimit) {
646        countNeeded = fCacheCount - fCacheCountLimit;
647        // no small purges!
648        countNeeded = SkMax32(countNeeded, fCacheCount >> 2);
649    }
650
651    // early exit
652    if (!countNeeded && !bytesNeeded) {
653        return 0;
654    }
655
656    size_t  bytesFreed = 0;
657    int     countFreed = 0;
658
659    // we start at the tail and proceed backwards, as the linklist is in LRU
660    // order, with unimportant entries at the tail.
661    SkGlyphCache* cache = this->internalGetTail();
662    while (cache != nullptr &&
663           (bytesFreed < bytesNeeded || countFreed < countNeeded)) {
664        SkGlyphCache* prev = cache->fPrev;
665        bytesFreed += cache->fMemoryUsed;
666        countFreed += 1;
667
668        this->internalDetachCache(cache);
669        delete cache;
670        cache = prev;
671    }
672
673    this->validate();
674
675#ifdef SPEW_PURGE_STATUS
676    if (countFreed) {
677        SkDebugf("purging %dK from font cache [%d entries]\n",
678                 (int)(bytesFreed >> 10), countFreed);
679    }
680#endif
681
682    return bytesFreed;
683}
684
685void SkGlyphCache_Globals::internalAttachCacheToHead(SkGlyphCache* cache) {
686    SkASSERT(nullptr == cache->fPrev && nullptr == cache->fNext);
687    if (fHead) {
688        fHead->fPrev = cache;
689        cache->fNext = fHead;
690    }
691    fHead = cache;
692
693    fCacheCount += 1;
694    fTotalMemoryUsed += cache->fMemoryUsed;
695}
696
697void SkGlyphCache_Globals::internalDetachCache(SkGlyphCache* cache) {
698    SkASSERT(fCacheCount > 0);
699    fCacheCount -= 1;
700    fTotalMemoryUsed -= cache->fMemoryUsed;
701
702    if (cache->fPrev) {
703        cache->fPrev->fNext = cache->fNext;
704    } else {
705        fHead = cache->fNext;
706    }
707    if (cache->fNext) {
708        cache->fNext->fPrev = cache->fPrev;
709    }
710    cache->fPrev = cache->fNext = nullptr;
711}
712
713///////////////////////////////////////////////////////////////////////////////
714
715#ifdef SK_DEBUG
716
717void SkGlyphCache::validate() const {
718#ifdef SK_DEBUG_GLYPH_CACHE
719    int count = fGlyphArray.count();
720    for (int i = 0; i < count; i++) {
721        const SkGlyph* glyph = &fGlyphArray[i];
722        SkASSERT(glyph);
723        if (glyph->fImage) {
724            SkASSERT(fGlyphAlloc.contains(glyph->fImage));
725        }
726    }
727#endif
728}
729
730void SkGlyphCache_Globals::validate() const {
731    size_t computedBytes = 0;
732    int computedCount = 0;
733
734    const SkGlyphCache* head = fHead;
735    while (head != nullptr) {
736        computedBytes += head->fMemoryUsed;
737        computedCount += 1;
738        head = head->fNext;
739    }
740
741    SkASSERTF(fCacheCount == computedCount, "fCacheCount: %d, computedCount: %d", fCacheCount,
742              computedCount);
743    SkASSERTF(fTotalMemoryUsed == computedBytes, "fTotalMemoryUsed: %d, computedBytes: %d",
744              fTotalMemoryUsed, computedBytes);
745}
746
747#endif
748
749///////////////////////////////////////////////////////////////////////////////
750///////////////////////////////////////////////////////////////////////////////
751
752#include "SkTypefaceCache.h"
753
754size_t SkGraphics::GetFontCacheLimit() {
755    return get_globals().getCacheSizeLimit();
756}
757
758size_t SkGraphics::SetFontCacheLimit(size_t bytes) {
759    return get_globals().setCacheSizeLimit(bytes);
760}
761
762size_t SkGraphics::GetFontCacheUsed() {
763    return get_globals().getTotalMemoryUsed();
764}
765
766int SkGraphics::GetFontCacheCountLimit() {
767    return get_globals().getCacheCountLimit();
768}
769
770int SkGraphics::SetFontCacheCountLimit(int count) {
771    return get_globals().setCacheCountLimit(count);
772}
773
774int SkGraphics::GetFontCacheCountUsed() {
775    return get_globals().getCacheCountUsed();
776}
777
778void SkGraphics::PurgeFontCache() {
779    get_globals().purgeAll();
780    SkTypefaceCache::PurgeAll();
781}
782
783// TODO(herb): clean up TLS apis.
784size_t SkGraphics::GetTLSFontCacheLimit() { return 0; }
785void SkGraphics::SetTLSFontCacheLimit(size_t bytes) { }
786