Use SkTHashMap in SkGlyphCache.

src/core/SkGlyphCache.cpp

Index: src/core/SkGlyphCache.cpp
diff --git a/src/core/SkGlyphCache.cpp b/src/core/SkGlyphCache.cpp
index 57c54bfc1ec3f7f35d3c499ba14c26abe99bcdcf..31f2485da2052e186a8346130952de6f569b7b21 100755
--- a/src/core/SkGlyphCache.cpp
+++ b/src/core/SkGlyphCache.cpp
@@ -40,24 +40,13 @@ static SkGlyphCache_Globals& getGlobals() {
 
 ///////////////////////////////////////////////////////////////////////////////
 
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
-    #define RecordHashSuccess()             fHashHitCount += 1
-    #define RecordHashCollisionIf(pred)     do { if (pred) fHashMissCount += 1; } while (0)
-#else
-    #define RecordHashSuccess()             (void)0
-    #define RecordHashCollisionIf(pred)     (void)0
-#endif
-#define RecordHashCollision() RecordHashCollisionIf(true)
-
-///////////////////////////////////////////////////////////////////////////////
-
 // so we don't grow our arrays a lot
 #define kMinGlyphCount      16
 #define kMinGlyphImageSize  (16*2)
 #define kMinAllocAmount     ((sizeof(SkGlyph) + kMinGlyphImageSize) * kMinGlyphCount)
 
 SkGlyphCache::SkGlyphCache(SkTypeface* typeface, const SkDescriptor* desc, SkScalerContext* ctx)
-        : fScalerContext(ctx), fGlyphAlloc(kMinAllocAmount) {
+        : fScalerContext(ctx), fAlloc(kMinAllocAmount) {
     SkASSERT(typeface);
     SkASSERT(desc);
     SkASSERT(ctx);
@@ -67,70 +56,20 @@ SkGlyphCache::SkGlyphCache(SkTypeface* typeface, const SkDescriptor* desc, SkSca
     fDesc = desc->copy();
     fScalerContext->getFontMetrics(&fFontMetrics);
 
-    // init to 0 so that all of the pointers will be null
-    memset(fGlyphHash, 0, sizeof(fGlyphHash));
-            
     fMemoryUsed = sizeof(*this);
 
-    fGlyphArray.setReserve(kMinGlyphCount);
-
     fAuxProcList = NULL;
-
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
-    fHashHitCount = fHashMissCount = 0;
-#endif
 }
 
-SkGlyphCache::~SkGlyphCache() {
-#if 0
-    {
-        size_t ptrMem = fGlyphArray.count() * sizeof(SkGlyph*);
-        size_t glyphAlloc = fGlyphAlloc.totalCapacity();
-        size_t glyphHashUsed = 0;
-        size_t uniHashUsed = 0;
-        for (int i = 0; i < kHashCount; ++i) {
-            glyphHashUsed += fGlyphHash[i] ? sizeof(fGlyphHash[0]) : 0;
-            uniHashUsed += fCharToGlyphHash[i].fID != 0xFFFFFFFF ? sizeof(fCharToGlyphHash[0]) : 0;
-        }
-        size_t glyphUsed = fGlyphArray.count() * sizeof(SkGlyph);
-        size_t imageUsed = 0;
-        for (int i = 0; i < fGlyphArray.count(); ++i) {
-            const SkGlyph& g = *fGlyphArray[i];
-            if (g.fImage) {
-                imageUsed += g.fHeight * g.rowBytes();
-            }
-        }
+static void delete_path(uint32_t, SkGlyph* glyph) { SkDELETE(glyph->fPath); }
 
-        SkDebugf("glyphPtrArray,%zu, Alloc,%zu, imageUsed,%zu, glyphUsed,%zu, glyphHashAlloc,%zu, glyphHashUsed,%zu, unicharHashAlloc,%zu, unicharHashUsed,%zu\n",
-                 ptrMem, glyphAlloc, imageUsed, glyphUsed, sizeof(fGlyphHash), glyphHashUsed, sizeof(CharGlyphRec) * kHashCount, uniHashUsed);
-
-    }
-#endif
-    SkGlyph**   gptr = fGlyphArray.begin();
-    SkGlyph**   stop = fGlyphArray.end();
-    while (gptr < stop) {
-        SkPath* path = (*gptr)->fPath;
-        if (path) {
-            SkDELETE(path);
-        }
-        gptr += 1;
-    }
+SkGlyphCache::~SkGlyphCache() {
+    fGlyphs.foreach(delete_path);
     SkDescriptor::Free(fDesc);
     SkDELETE(fScalerContext);
     this->invokeAndRemoveAuxProcs();
 }
 
-SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(uint32_t id) {
-    if (NULL == fCharToGlyphHash.get()) {
-        fCharToGlyphHash.reset(kHashCount);
-        // init with 0xFF so that the charCode field will be -1, which is invalid
-        memset(fCharToGlyphHash.get(), 0xFF,
-               sizeof(CharGlyphRec) * kHashCount);
-    }
-    
-    return &fCharToGlyphHash[ID2HashIndex(id)];
-}
-
 ///////////////////////////////////////////////////////////////////////////////
 
 #ifdef SK_DEBUG
@@ -141,14 +80,12 @@ SkGlyphCache::CharGlyphRec* SkGlyphCache::getCharGlyphRec(uint32_t id) {
 
 uint16_t SkGlyphCache::unicharToGlyph(SkUnichar charCode) {
     VALIDATE();
-    uint32_t id = SkGlyph::MakeID(charCode);
-    const CharGlyphRec& rec = *this->getCharGlyphRec(id);
-
-    if (rec.fID == id) {
-        return rec.fGlyph->getGlyphID();
-    } else {
-        return fScalerContext->charToGlyphID(charCode);
+    if (const uint16_t* glyphID = fCharToGlyphID.find(charCode)) {
+        return *glyphID;
     }
+    uint16_t glyphID = fScalerContext->charToGlyphID(charCode);
+    fCharToGlyphID.set(charCode, glyphID);
+    return glyphID;
 }
 
 SkUnichar SkGlyphCache::glyphToUnichar(uint16_t glyphID) {
@@ -159,179 +96,66 @@ unsigned SkGlyphCache::getGlyphCount() {
     return fScalerContext->getGlyphCount();
 }
 
-///////////////////////////////////////////////////////////////////////////////
-
 const SkGlyph& SkGlyphCache::getUnicharAdvance(SkUnichar charCode) {
-    VALIDATE();
-    uint32_t id = SkGlyph::MakeID(charCode);
-    CharGlyphRec* rec = this->getCharGlyphRec(id);
-
-    if (rec->fID != id) {
-        // this ID is based on the UniChar
-        rec->fID = id;
-        // this ID is based on the glyph index
-        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode));
-        rec->fGlyph = this->lookupMetrics(id, kJustAdvance_MetricsType);
-    }
-    return *rec->fGlyph;
+    return this->getGlyphIDAdvance(this->unicharToGlyph(charCode));
 }
-
-const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
-    VALIDATE();
-    uint32_t id = SkGlyph::MakeID(glyphID);
-    unsigned index = ID2HashIndex(id);
-    SkGlyph* glyph = fGlyphHash[index];
-
-    if (NULL == glyph || glyph->fID != id) {
-        glyph = this->lookupMetrics(glyphID, kJustAdvance_MetricsType);
-        fGlyphHash[index] = glyph;
-    }
-    return *glyph;
-}
-
-///////////////////////////////////////////////////////////////////////////////
-
 const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode) {
-    VALIDATE();
-    uint32_t id = SkGlyph::MakeID(charCode);
-    CharGlyphRec* rec = this->getCharGlyphRec(id);
-
-    if (rec->fID != id) {
-        RecordHashCollisionIf(rec->fGlyph != NULL);
-        // this ID is based on the UniChar
-        rec->fID = id;
-        // this ID is based on the glyph index
-        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode));
-        rec->fGlyph = this->lookupMetrics(id, kFull_MetricsType);
-    } else {
-        RecordHashSuccess();
-        if (rec->fGlyph->isJustAdvance()) {
-            fScalerContext->getMetrics(rec->fGlyph);
-        }
-    }
-    SkASSERT(rec->fGlyph->isFullMetrics());
-    return *rec->fGlyph;
+    return this->getGlyphIDMetrics(this->unicharToGlyph(charCode));
+}
+const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode, SkFixed x, SkFixed y) {
+    return this->getGlyphIDMetrics(this->unicharToGlyph(charCode), x, y);
 }
 
-const SkGlyph& SkGlyphCache::getUnicharMetrics(SkUnichar charCode,
-                                               SkFixed x, SkFixed y) {
+const SkGlyph& SkGlyphCache::getGlyphIDAdvance(uint16_t glyphID) {
     VALIDATE();
-    uint32_t id = SkGlyph::MakeID(charCode, x, y);
-    CharGlyphRec* rec = this->getCharGlyphRec(id);
-
-    if (rec->fID != id) {
-        RecordHashCollisionIf(rec->fGlyph != NULL);
-        // this ID is based on the UniChar
-        rec->fID = id;
-        // this ID is based on the glyph index
-        id = SkGlyph::MakeID(fScalerContext->charToGlyphID(charCode), x, y);
-        rec->fGlyph = this->lookupMetrics(id, kFull_MetricsType);
-    } else {
-        RecordHashSuccess();
-        if (rec->fGlyph->isJustAdvance()) {
-            fScalerContext->getMetrics(rec->fGlyph);
-        }
-    }
-    SkASSERT(rec->fGlyph->isFullMetrics());
-    return *rec->fGlyph;
+    const SkGlyph* glyph =
+        this->lookupMetrics(SkGlyph::MakeID(glyphID), kJustAdvance_MetricsType);
+    SkASSERT(glyph);
+    return *glyph;
 }
 
 const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID) {
     VALIDATE();
-    uint32_t id = SkGlyph::MakeID(glyphID);
-    unsigned index = ID2HashIndex(id);
-    SkGlyph* glyph = fGlyphHash[index];
-
-    if (NULL == glyph || glyph->fID != id) {
-        RecordHashCollisionIf(glyph != NULL);
-        glyph = this->lookupMetrics(glyphID, kFull_MetricsType);
-        fGlyphHash[index] = glyph;
-    } else {
-        RecordHashSuccess();
-        if (glyph->isJustAdvance()) {
-            fScalerContext->getMetrics(glyph);
-        }
-    }
+    const SkGlyph* glyph =
+        this->lookupMetrics(SkGlyph::MakeID(glyphID), kFull_MetricsType);
+    SkASSERT(glyph);
     SkASSERT(glyph->isFullMetrics());
     return *glyph;
 }
 
 const SkGlyph& SkGlyphCache::getGlyphIDMetrics(uint16_t glyphID, SkFixed x, SkFixed y) {
     VALIDATE();
-    uint32_t id = SkGlyph::MakeID(glyphID, x, y);
-    unsigned index = ID2HashIndex(id);
-    SkGlyph* glyph = fGlyphHash[index];
-
-    if (NULL == glyph || glyph->fID != id) {
-        RecordHashCollisionIf(glyph != NULL);
-        glyph = this->lookupMetrics(id, kFull_MetricsType);
-        fGlyphHash[index] = glyph;
-    } else {
-        RecordHashSuccess();
-        if (glyph->isJustAdvance()) {
-            fScalerContext->getMetrics(glyph);
-        }
-    }
+    const SkGlyph* glyph =
+        this->lookupMetrics(SkGlyph::MakeID(glyphID, x, y), kFull_MetricsType);
+    SkASSERT(glyph);
     SkASSERT(glyph->isFullMetrics());
     return *glyph;
 }
 
 SkGlyph* SkGlyphCache::lookupMetrics(uint32_t id, MetricsType mtype) {
-    SkGlyph* glyph;
-
-    int     hi = 0;
-    int     count = fGlyphArray.count();
-
-    if (count) {
-        SkGlyph**   gptr = fGlyphArray.begin();
-        int     lo = 0;
-
-        hi = count - 1;
-        while (lo < hi) {
-            int mid = (hi + lo) >> 1;
-            if (gptr[mid]->fID < id) {
-                lo = mid + 1;
-            } else {
-                hi = mid;
-            }
-        }
-        glyph = gptr[hi];
-        if (glyph->fID == id) {
-            if (kFull_MetricsType == mtype && glyph->isJustAdvance()) {
-                fScalerContext->getMetrics(glyph);
-            }
-            return glyph;
-        }
-
-        // check if we need to bump hi before falling though to the allocator
-        if (glyph->fID < id) {
-            hi += 1;
+    if (SkGlyph* glyph = fGlyphs.find(id)) {
+        if (kFull_MetricsType == mtype && glyph->isJustAdvance()) {
+            fScalerContext->getMetrics(glyph);
         }
+        return glyph;
     }
 
-    // not found, but hi tells us where to inser the new glyph
-    fMemoryUsed += sizeof(SkGlyph);
-
-    glyph = (SkGlyph*)fGlyphAlloc.alloc(sizeof(SkGlyph),
-                                        SkChunkAlloc::kThrow_AllocFailType);
-    glyph->init(id);
-    *fGlyphArray.insert(hi) = glyph;
-
+    SkGlyph glyph;
+    glyph.init(id);
     if (kJustAdvance_MetricsType == mtype) {
-        fScalerContext->getAdvance(glyph);
+        fScalerContext->getAdvance(&glyph);
     } else {
         SkASSERT(kFull_MetricsType == mtype);
-        fScalerContext->getMetrics(glyph);
+        fScalerContext->getMetrics(&glyph);
     }
-
-    return glyph;
+    return fGlyphs.set(id, glyph);
 }
 
 const void* SkGlyphCache::findImage(const SkGlyph& glyph) {
     if (glyph.fWidth > 0 && glyph.fWidth < kMaxGlyphWidth) {
         if (NULL == glyph.fImage) {
             size_t  size = glyph.computeImageSize();
-            const_cast<SkGlyph&>(glyph).fImage = fGlyphAlloc.alloc(size,
+            const_cast<SkGlyph&>(glyph).fImage = fAlloc.alloc(size,
                                         SkChunkAlloc::kReturnNil_AllocFailType);
             // check that alloc() actually succeeded
             if (glyph.fImage) {
@@ -374,11 +198,7 @@ void SkGlyphCache::dump() const {
                matrix[SkMatrix::kMScaleX], matrix[SkMatrix::kMSkewX],
                matrix[SkMatrix::kMSkewY], matrix[SkMatrix::kMScaleY],
                rec.fLumBits & 0xFF, rec.fDeviceGamma, rec.fPaintGamma, rec.fContrast,
-               fGlyphArray.count());
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
-    const int sum = SkTMax(fHashHitCount + fHashMissCount, 1);   // avoid divide-by-zero
-    msg.appendf(" hash:%2d\n", 100 * fHashHitCount / sum);
-#endif
+               fGlyphs.count());
     SkDebugf("%s\n", msg.c_str());
 }
 
@@ -548,21 +368,9 @@ void SkGlyphCache::Dump() {
     SkDebugf("SkGlyphCache strikes:%d memory:%d\n",
              globals.getCacheCountUsed(), (int)globals.getTotalMemoryUsed());
 
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
-    int hitCount = 0;
-    int missCount = 0;
-#endif
-
     for (cache = globals.internalGetHead(); cache != NULL; cache = cache->fNext) {
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
-        hitCount += cache->fHashHitCount;
-        missCount += cache->fHashMissCount;
-#endif
         cache->dump();
     }
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
-    SkDebugf("Hash hit percent:%2d\n", 100 * hitCount / (hitCount + missCount));
-#endif
 }
 
 ///////////////////////////////////////////////////////////////////////////////
@@ -674,20 +482,6 @@ void SkGlyphCache_Globals::internalDetachCache(SkGlyphCache* cache) {
 #ifdef SK_DEBUG
 
 void SkGlyphCache::validate() const {
-#ifdef SK_DEBUG_GLYPH_CACHE
-    int count = fGlyphArray.count();
-    for (int i = 0; i < count; i++) {
-        const SkGlyph* glyph = fGlyphArray[i];
-        SkASSERT(glyph);
-        SkASSERT(fGlyphAlloc.contains(glyph));
-        if (glyph->fImage) {
-            SkASSERT(fGlyphAlloc.contains(glyph->fImage));
-        }
-        if (glyph->fDistanceField) {
-            SkASSERT(fGlyphAlloc.contains(glyph->fDistanceField));
-        }
-    }
-#endif
 }
 
 void SkGlyphCache_Globals::validate() const {