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

src/core/SkGlyphCache.h

 /*
  * Copyright 2006 The Android Open Source Project
  *
  * Use of this source code is governed by a BSD-style license that can be found in the LICENSE file.
  */
 
 #ifndef SkGlyphCache_DEFINED
 #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"
 
 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
 
 /** \class SkGlyphCache
 
     This class represents a strike: a specific combination of typeface, size, matrix, etc., and
     holds the glyphs for that strike. Calling any of the getUnichar.../getGlyphID... methods will
     return the requested glyph, either instantly if it is already cached, or by first generating
     it and then adding it to the strike.
@@ skipping 143 matching lines @@
     };
 
     enum {
         kHashBits           = 8,
         kHashCount          = 1 << kHashBits,
         kHashMask           = kHashCount - 1
     };
 
     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 {
         AuxProcRec* fNext;
         void (*fProc)(void*);
         void* fData;
     };
 
     // SkGlyphCache takes ownership of the scalercontext.
     SkGlyphCache(SkTypeface*, const SkDescriptor*, SkScalerContext*);
     ~SkGlyphCache();
 
     // 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);
 
     // 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);
+    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;
     }
 
     void invokeAndRemoveAuxProcs();
 
     inline static SkGlyphCache* FindTail(SkGlyphCache* head);
 
     SkGlyphCache*        fNext, *fPrev;
     SkDescriptor*        fDesc;
     SkScalerContext*     fScalerContext;
     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
     // Dynamically allocated when chars are encountered.
     SkAutoTArray<CharGlyphRec> fCharToGlyphHash;
 
     // used to track (approx) how much ram is tied-up in this cache
     size_t  fMemoryUsed;
 
 #ifdef SK_GLYPHCACHE_TRACK_HASH_STATS
@@ skipping 68 matching lines @@
                             const SkMatrix* matrix) {
         fCache = paint.detachCache(surfaceProps, matrix, true);
     }
 
 private:
     SkAutoGlyphCacheNoGamma() : SkAutoGlyphCacheBase() {}
 };
 #define SkAutoGlyphCacheNoGamma(...) SK_REQUIRE_LOCAL_VAR(SkAutoGlyphCacheNoGamma)
 
 #endif