Move the GlyphCache to use a hash table instead of doing its own ad-hoc

src/core/SkGlyphCache.h

Index: src/core/SkGlyphCache.h
diff --git a/src/core/SkGlyphCache.h b/src/core/SkGlyphCache.h
index f3a946c7d3e0470811074557a572cab18ebba62e..13d47cf953793a29a2aaecd63aa0bcc172199869 100644
--- a/src/core/SkGlyphCache.h
+++ b/src/core/SkGlyphCache.h
@@ -8,10 +8,10 @@
 #define SkGlyphCache_DEFINED
 
 #include "SkBitmap.h"
-#include "SkChecksum.h"
 #include "SkChunkAlloc.h"
 #include "SkDescriptor.h"
 #include "SkGlyph.h"
+#include "SkTHash.h"
 #include "SkScalerContext.h"
 #include "SkTemplates.h"
 #include "SkTDArray.h"
@@ -20,10 +20,6 @@ class SkPaint;
 
 class SkGlyphCache_Globals;
 
-// Enable this locally to add stats for hash-table hit rates. It also extends the dump() output
-// to show those stats.
-//#define SK_GLYPHCACHE_TRACK_HASH_STATS
-
 /** \class SkGlyphCache
 
     This class represents a strike: a specific combination of typeface, size, matrix, etc., and
@@ -181,9 +177,12 @@ private:
         kHashMask           = kHashCount - 1
     };
 
+    typedef uint32_t PackedGlyphID;    // glyph-index + subpixel-pos
+    typedef uint32_t PackedUnicharID;  // unichar + subpixel-pos
+
     struct CharGlyphRec {
-        uint32_t    fID;    // unichar + subpixel
-        uint16_t    fGlyphIndex;
+        PackedUnicharID    fPackedUnicharID;
+        PackedGlyphID      fPackedGlyphID;
     };
 
     struct AuxProcRec {
@@ -199,56 +198,41 @@ private:
     // Return the SkGlyph* associated with MakeID. The id parameter is the
     // combined glyph/x/y id generated by MakeID. If it is just a glyph id
     // then x and y are assumed to be zero.
-    SkGlyph* lookupByCombinedID(uint32_t id, MetricsType type);
+    SkGlyph* lookupByPackedGlyphID(PackedGlyphID packedGlyphID, MetricsType type);
 
     // Return a SkGlyph* associated with unicode id and position x and y.
     SkGlyph* lookupByChar(SkUnichar id, MetricsType type, SkFixed x = 0, SkFixed y = 0);
 
-    // Return the index of id in the fGlyphArray. If it does not exist,
-    // create a new one using MetricsType.
-    uint16_t lookupMetrics(uint32_t id, MetricsType type);
+    // Return a new SkGlyph for the glyph ID and subpixel position id. Limit the amount
+    // of work
+    // using type.
+    SkGlyph* allocateNewGlyph(PackedGlyphID packedGlyphID, MetricsType type);
+
     static bool DetachProc(const SkGlyphCache*, void*) { return true; }
 
     // The id arg is a combined id generated by MakeID.
-    CharGlyphRec* getCharGlyphRec(uint32_t id);
-    void adjustCaches(int insertion_index);
-
-    static inline unsigned ID2HashIndex(uint32_t h) {
-        return SkChecksum::CheapMix(h) & kHashMask;
-    }
+    CharGlyphRec* getCharGlyphRec(PackedUnicharID id);
 
     void invokeAndRemoveAuxProcs();
 
     inline static SkGlyphCache* FindTail(SkGlyphCache* head);
 
-    SkGlyphCache*        fNext, *fPrev;
-    SkDescriptor*        fDesc;
-    SkScalerContext*     fScalerContext;
+    SkGlyphCache         *fNext, *fPrev;

[mtklein, 2015/07/21 19:35:52]

I think I'd generally prefer

SkGlyphCache* fNext;
SkGlyphCache* fPrev;
SkDescriptor* fDesc;
SkScalerContext* fScalerContext;
SkPaint::FontMetrics fFontMetrics;

I don't mind Type* const, but it's rarely interesting that the pointer's not
going to change, and it's easily confused with the more important const Type*.

[herb_g, 2015/07/21 22:27:34]

T * const is nicer in multithreaded cases, and it documents the invariant that
this does not change. 

+    SkDescriptor         * const fDesc;
+    SkScalerContext      * const fScalerContext;
     SkPaint::FontMetrics fFontMetrics;
 
-    // A quick lookup to avoid the binary search looking for glyphs in fGlyphArray.
-    uint16_t             fGlyphHash[kHashCount];
+    // Map from a combined GlyphID and sub-pixel position to a SkGlyph.
+    SkTHashTable<SkGlyph, PackedGlyphID, SkGlyph::GlyphHashTraits> fGlyphMap;
 
-    // Contains the SkGlyphs that are used by fGlyphHash and fCharToGlyphHash. The ~0 element is
-    // reserved for a sentinel SkGlyph that reduces the logic to check for collisions in the hash
-    // arrays. The ~0 element has an fID of SkGlyph::kImpossibleID which never matches any
-    // combined id generated for a char or a glyph.
-    SkTDArray<SkGlyph>   fGlyphArray;
     SkChunkAlloc         fGlyphAlloc;
 
-    // no reason to use the same kHashCount as fGlyphHash, but we do for now
-    // Dynamically allocated when chars are encountered.
-    SkAutoTArray<CharGlyphRec> fCharToGlyphHash;
+    SkAutoTArray<CharGlyphRec> fPackedUnicharIDToPackedGlyphID;
 
     // used to track (approx) how much ram is tied-up in this cache
-    size_t  fMemoryUsed;
-
-#ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
-    int fHashHitCount;
-    int fHashMissCount;
-#endif
+    size_t               fMemoryUsed;
 
-    AuxProcRec* fAuxProcList;
+    AuxProcRec*          fAuxProcList;
 };
 
 class SkAutoGlyphCacheBase {