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