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..1d3ae57b2eaf2d83b71aaaf6c8fd4adfb0c3a955 100644
--- a/src/core/SkGlyphCache.h
+++ b/src/core/SkGlyphCache.h
@@ -12,6 +12,7 @@
 #include "SkChunkAlloc.h"
 #include "SkDescriptor.h"
 #include "SkGlyph.h"
+#include "SkTHash.h"
 #include "SkScalerContext.h"
 #include "SkTemplates.h"
 #include "SkTDArray.h"
@@ -20,6 +21,16 @@ class SkPaint;
 
 class SkGlyphCache_Globals;
 
+class GlyphTrait {

[mtklein, 2015/06/30 16:20:47]

Might want to call this SkGlyphHashTraits, or nest it in SkGlyphCache as
SkGlyphCache::GlyphHashTraits?

[herb_g, 2015/07/06 16:32:19]

Done.

+public:
+    static int32_t GetKey(const SkGlyph& glyph) {

[reed1, 2015/06/29 20:59:48]

nit: do we really need signed -vs- unsigned 32 ints?

[mtklein, 2015/06/30 16:20:47]

+1, particularly because fID is an uint32_t (and is always passed as one).  I'd
be pretty pro SkGlyphID typedef.

[herb_g, 2015/07/06 16:32:19]

Done.

[herb_g, 2015/07/06 16:32:19]

Done.

+        return glyph.fID;
+    }
+    static uint32_t Hash(int32_t glyphId) {
+        return SkChecksum::CheapMix(glyphId);
+    }
+};
+
 // 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
@@ -183,7 +194,7 @@ private:
 
     struct CharGlyphRec {
         uint32_t    fID;    // unichar + subpixel
-        uint16_t    fGlyphIndex;
+        uint32_t    fCombinedID;

[mtklein, 2015/06/30 16:20:47]

Boy this is getting confusing.  Can we name these something like

fUnicharAndSubpixel
fGlyphID

?

Is the first an ID?  Is the second any more combined than GlyphIDs are normally?

[herb_g, 2015/07/06 16:32:19]

This is really a glyphID and subpixel positioning. Done.

     };
 
     struct AuxProcRec {
@@ -206,12 +217,11 @@ private:
 
     // 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);
+    SkGlyph* lookupMetrics(uint32_t id, 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;
@@ -227,13 +237,15 @@ private:
     SkPaint::FontMetrics fFontMetrics;
 
     // A quick lookup to avoid the binary search looking for glyphs in fGlyphArray.
-    uint16_t             fGlyphHash[kHashCount];
+    //uint16_t             fGlyphHash[kHashCount];
 
     // 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;
+    //SkTDArray<SkGlyph>   fGlyphArray;

[mtklein, 2015/06/30 16:20:47]

Let's kill off the dead code and update the comments everywhere (e.g. the
comments below at 251-252 too) ?

[herb_g, 2015/07/06 16:32:19]

Done.

+    SkTHashTable<SkGlyph, int32_t, GlyphTrait> fGlyphMap;
+
     SkChunkAlloc         fGlyphAlloc;
 
     // no reason to use the same kHashCount as fGlyphHash, but we do for now