Replace GrTHash with SkTDynamicHash

Mike: SkTDynamicHash changes
Brian: Ganesh changes

This removes three instances of GrTHash leaving the ones in GrTextStrike.h

R=mtklein@google.com, bsalomon@google.com

Author: robertphillips@google.com

Review URL: https://codereview.chromium.org/402693003

9 files changed, 262 insertions, 158 deletions

diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h
index 445a45df85..496dc8d141 100644
--- a/src/core/SkTDynamicHash.h
+++ b/src/core/SkTDynamicHash.h
@@ -57,6 +57,33 @@ public:
         int fCurrentIndex;
     };
 
+    class ConstIter {
+    public:
+        explicit ConstIter(const SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
+            SkASSERT(hash);
+            ++(*this);
+        }
+        bool done() const {
+            SkASSERT(fCurrentIndex <= fHash->fCapacity);
+            return fCurrentIndex == fHash->fCapacity;
+        }
+        const T& operator*() const {
+            SkASSERT(!this->done());
+            return *this->current();
+        }
+        void operator++() {
+            do {
+                fCurrentIndex++;
+            } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
+        }
+
+    private:
+        const T* current() const { return fHash->fArray[fCurrentIndex]; }
+
+        const SkTDynamicHash* fHash;
+        int fCurrentIndex;
+    };
+
     int count() const { return fCount; }
 
     // Return the entry with this key if we have it, otherwise NULL.
@@ -85,13 +112,29 @@ public:
         SkASSERT(this->validate());
     }
 
-    // Remove the entry with this key.  We reqire that an entry with this key is present.
+    // Remove the entry with this key.  We require that an entry with this key is present.
     void remove(const Key& key) {
         SkASSERT(NULL != this->find(key));
         this->innerRemove(key);
         SkASSERT(this->validate());
     }
 
+    void rewind() {
+        if (NULL != fArray) {
+            sk_bzero(fArray, sizeof(T*)* fCapacity);
+        }
+        fCount = 0;
+        fDeleted = 0;
+    }
+
+    void reset() { 
+        fCount = 0; 
+        fDeleted = 0; 
+        fCapacity = 0; 
+        sk_free(fArray); 
+        fArray = NULL; 
+    }
+
 protected:
     // These methods are used by tests only.
 
diff --git a/src/gpu/GrBinHashKey.h b/src/gpu/GrBinHashKey.h
index 585a1a1c01..06ff931808 100644
--- a/src/gpu/GrBinHashKey.h
+++ b/src/gpu/GrBinHashKey.h
@@ -10,9 +10,67 @@
 #ifndef GrBinHashKey_DEFINED
 #define GrBinHashKey_DEFINED
 
+#include "SkChecksum.h"
 #include "GrTypes.h"
 
 /**
+ *  GrMurmur3HashKey is a hash key class that can take a data chunk of any predetermined
+ *  length. It uses the Murmur3 hash function. It is intended to be used with
+ *  SkTDynamicHash (where GrBinHashKey is for GrTHashTable).
+ */
+template<size_t KEY_SIZE_IN_BYTES>
+class GrMurmur3HashKey {
+public:
+    GrMurmur3HashKey() {
+        this->reset();
+    }
+
+    void reset() {
+        fHash = 0;
+#ifdef SK_DEBUG
+        fIsValid = false;
+#endif
+    }
+
+    void setKeyData(const uint32_t* data) {
+        SK_COMPILE_ASSERT(KEY_SIZE_IN_BYTES % 4 == 0, key_size_mismatch);
+        memcpy(fData, data, KEY_SIZE_IN_BYTES);
+
+        fHash = SkChecksum::Murmur3(fData, KEY_SIZE_IN_BYTES);
+#ifdef SK_DEBUG
+        fIsValid = true;
+#endif
+    }
+
+    bool operator==(const GrMurmur3HashKey& other) const {
+        if (fHash != other.fHash) {
+            return false;
+        }
+
+        return !memcmp(fData, other.fData, KEY_SIZE_IN_BYTES);
+    }
+
+    uint32_t getHash() const {
+        SkASSERT(fIsValid);
+        return fHash;
+    }
+
+    const uint8_t* getData() const {
+        SkASSERT(fIsValid);
+        return reinterpret_cast<const uint8_t*>(fData);
+    }
+
+private:
+    uint32_t fHash;
+    uint32_t fData[KEY_SIZE_IN_BYTES / sizeof(uint32_t)];  // Buffer for key storage.
+
+#ifdef SK_DEBUG
+public:
+    bool                fIsValid;
+#endif
+};
+
+/**
  *  GrBinHashKey is a hash key class that can take a data chunk of any predetermined
  *  length. The hash function used is the One-at-a-Time Hash
  *  (http://burtleburtle.net/bob/hash/doobs.html).
diff --git a/src/gpu/GrLayerCache.cpp b/src/gpu/GrLayerCache.cpp
index ff26750df7..1a0923004b 100644
--- a/src/gpu/GrLayerCache.cpp
+++ b/src/gpu/GrLayerCache.cpp
@@ -9,67 +9,11 @@
 #include "GrGpu.h"
 #include "GrLayerCache.h"
 
-/**
- *  PictureLayerKey just wraps a saveLayer's id in a picture for GrTHashTable.
- */
-class GrLayerCache::PictureLayerKey {
-public:
-    PictureLayerKey(uint32_t pictureID, int layerID)
-        : fPictureID(pictureID)
-        , fLayerID(layerID) {
-    }
-
-    uint32_t pictureID() const { return fPictureID; }
-    int layerID() const { return fLayerID; }
-
-    uint32_t getHash() const { return (fPictureID << 16) | fLayerID; }
-
-    static bool LessThan(const GrCachedLayer& layer, const PictureLayerKey& key) {
-        if (layer.pictureID() == key.pictureID()) {
-            return layer.layerID() < key.layerID();
-        }
-
-        return layer.pictureID() < key.pictureID();
-    }
-
-    static bool Equals(const GrCachedLayer& layer, const PictureLayerKey& key) {
-        return layer.pictureID() == key.pictureID() && layer.layerID() == key.layerID();
-    }
-
-private:
-    uint32_t fPictureID;
-    int      fLayerID;
-};
-
-/**
- *  PictureKey just wraps a picture's unique ID for GrTHashTable. It is used to
- *  look up a picture's GrPictureInfo (i.e., its GrPlot usage).
- */
-class GrLayerCache::PictureKey {
-public:
-    PictureKey(uint32_t pictureID) : fPictureID(pictureID) { }
-
-    uint32_t pictureID() const { return fPictureID; }
-
-    uint32_t getHash() const { return fPictureID; }
-
-    static bool LessThan(const GrPictureInfo& pictInfo, const PictureKey& key) {
-        return pictInfo.fPictureID < key.pictureID();
-    }
-
-    static bool Equals(const GrPictureInfo& pictInfo, const PictureKey& key) {
-        return pictInfo.fPictureID == key.pictureID();
-
-    }
-
-private:
-    uint32_t fPictureID;
-};
-
 #ifdef SK_DEBUG
 void GrCachedLayer::validate(const GrTexture* backingTexture) const {
-    SkASSERT(SK_InvalidGenID != fPictureID);
-    SkASSERT(-1 != fLayerID);
+    SkASSERT(SK_InvalidGenID != fKey.getPictureID());
+    SkASSERT(-1 != fKey.getLayerID());
+
 
     if (NULL != fTexture) {
         // If the layer is in some texture then it must occupy some rectangle
@@ -122,12 +66,13 @@ GrLayerCache::GrLayerCache(GrContext* context)
 }
 
 GrLayerCache::~GrLayerCache() {
-    SkTDArray<GrCachedLayer*>& layerArray = fLayerHash.getArray();
-    for (int i = 0; i < fLayerHash.count(); ++i) {
-        this->unlock(layerArray[i]);
-    }
 
-    fLayerHash.deleteAll();
+    SkTDynamicHash<GrCachedLayer, GrCachedLayer::Key>::Iter iter(&fLayerHash);
+    for (; !iter.done(); ++iter) {
+        GrCachedLayer* layer = &(*iter);
+        this->unlock(layer);
+        SkDELETE(layer);
+    }
 
     // The atlas only lets go of its texture when the atlas is deleted. 
     fAtlas.free();    
@@ -147,12 +92,14 @@ void GrLayerCache::initAtlas() {
 }
 
 void GrLayerCache::freeAll() {
-    SkTDArray<GrCachedLayer*>& layerArray = fLayerHash.getArray();
-    for (int i = 0; i < fLayerHash.count(); ++i) {
-        this->unlock(layerArray[i]);
-    }
 
-    fLayerHash.deleteAll();
+    SkTDynamicHash<GrCachedLayer, GrCachedLayer::Key>::Iter iter(&fLayerHash);
+    for (; !iter.done(); ++iter) {
+        GrCachedLayer* layer = &(*iter);
+        this->unlock(layer);
+        SkDELETE(layer);
+    }
+    fLayerHash.rewind();
 
     // The atlas only lets go of its texture when the atlas is deleted. 
     fAtlas.free();
@@ -164,21 +111,21 @@ void GrLayerCache::freeAll() {
 }
 
 GrCachedLayer* GrLayerCache::createLayer(const SkPicture* picture, int layerID) {
-    SkASSERT(picture->uniqueID() != SK_InvalidGenID);
+    SkASSERT(picture->uniqueID() != SK_InvalidGenID && layerID >= 0);
 
     GrCachedLayer* layer = SkNEW_ARGS(GrCachedLayer, (picture->uniqueID(), layerID));
-    fLayerHash.insert(PictureLayerKey(picture->uniqueID(), layerID), layer);
+    fLayerHash.add(layer);
     return layer;
 }
 
 GrCachedLayer* GrLayerCache::findLayer(const SkPicture* picture, int layerID) {
-    SkASSERT(picture->uniqueID() != SK_InvalidGenID);
-    return fLayerHash.find(PictureLayerKey(picture->uniqueID(), layerID));
+    SkASSERT(picture->uniqueID() != SK_InvalidGenID && layerID >= 0);
+    return fLayerHash.find(GrCachedLayer::Key(picture->uniqueID(), layerID));
 }
 
 GrCachedLayer* GrLayerCache::findLayerOrCreate(const SkPicture* picture, int layerID) {
-    SkASSERT(picture->uniqueID() != SK_InvalidGenID);
-    GrCachedLayer* layer = fLayerHash.find(PictureLayerKey(picture->uniqueID(), layerID));
+    SkASSERT(picture->uniqueID() != SK_InvalidGenID && layerID >= 0);
+    GrCachedLayer* layer = fLayerHash.find(GrCachedLayer::Key(picture->uniqueID(), layerID));
     if (NULL == layer) {
         layer = this->createLayer(picture, layerID);
     }
@@ -203,10 +150,10 @@ bool GrLayerCache::lock(GrCachedLayer* layer, const GrTextureDesc& desc) {
 
 #if USE_ATLAS
     {
-        GrPictureInfo* pictInfo = fPictureHash.find(PictureKey(layer->pictureID()));
+        GrPictureInfo* pictInfo = fPictureHash.find(layer->pictureID());
         if (NULL == pictInfo) {
             pictInfo = SkNEW_ARGS(GrPictureInfo, (layer->pictureID()));
-            fPictureHash.insert(PictureKey(layer->pictureID()), pictInfo);
+            fPictureHash.add(pictInfo);
         }
 
         SkIPoint16 loc;
@@ -243,7 +190,7 @@ void GrLayerCache::unlock(GrCachedLayer* layer) {
     if (layer->isAtlased()) {
         SkASSERT(layer->texture() == fAtlas->getTexture());
 
-        GrPictureInfo* pictInfo = fPictureHash.find(PictureKey(layer->pictureID()));
+        GrPictureInfo* pictInfo = fPictureHash.find(layer->pictureID());
         SkASSERT(NULL != pictInfo);
         pictInfo->fPlotUsage.isEmpty(); // just to silence compiler warnings for the time being
 
@@ -256,9 +203,9 @@ void GrLayerCache::unlock(GrCachedLayer* layer) {
 
 #ifdef SK_DEBUG
 void GrLayerCache::validate() const {
-    const SkTDArray<GrCachedLayer*>& layerArray = fLayerHash.getArray();
-    for (int i = 0; i < fLayerHash.count(); ++i) {
-        layerArray[i]->validate(fAtlas->getTexture());
+    SkTDynamicHash<GrCachedLayer, GrCachedLayer::Key>::ConstIter iter(&fLayerHash);
+    for (; !iter.done(); ++iter) {
+        (*iter).validate(fAtlas->getTexture());
     }
 }
 
@@ -279,31 +226,25 @@ private:
 void GrLayerCache::purge(const SkPicture* picture) {
     SkDEBUGCODE(GrAutoValidateCache avc(this);)
 
-    // This is somewhat of an abuse of GrTHashTable. We need to find all the
-    // layers associated with 'picture' but the usual hash calls only look for
-    // exact key matches. This code peeks into the hash table's innards to
-    // find all the 'picture'-related layers.
-    // TODO: use a different data structure for the layer hash?
+    // We need to find all the layers associated with 'picture' and remove them.
     SkTDArray<GrCachedLayer*> toBeRemoved;
 
-    const SkTDArray<GrCachedLayer*>& layerArray = fLayerHash.getArray();
-    for (int i = 0; i < fLayerHash.count(); ++i) {
-        if (picture->uniqueID() == layerArray[i]->pictureID()) {
-            *toBeRemoved.append() = layerArray[i];
+    SkTDynamicHash<GrCachedLayer, GrCachedLayer::Key>::Iter iter(&fLayerHash);
+    for (; !iter.done(); ++iter) {
+        if (picture->uniqueID() == (*iter).pictureID()) {
+            *toBeRemoved.append() = &(*iter);
         }
     }
 
     for (int i = 0; i < toBeRemoved.count(); ++i) {
         this->unlock(toBeRemoved[i]);
-
-        PictureLayerKey key(picture->uniqueID(), toBeRemoved[i]->layerID());
-        fLayerHash.remove(key, toBeRemoved[i]);
+        fLayerHash.remove(GrCachedLayer::GetKey(*toBeRemoved[i]));
         SkDELETE(toBeRemoved[i]);
     }
 
-    GrPictureInfo* pictInfo = fPictureHash.find(PictureKey(picture->uniqueID()));
+    GrPictureInfo* pictInfo = fPictureHash.find(picture->uniqueID());
     if (NULL != pictInfo) {
-        fPictureHash.remove(PictureKey(picture->uniqueID()), pictInfo);
+        fPictureHash.remove(picture->uniqueID());
         SkDELETE(pictInfo);
     }
 }
diff --git a/src/gpu/GrLayerCache.h b/src/gpu/GrLayerCache.h
index 347fa232ab..3d4c98a0d7 100644
--- a/src/gpu/GrLayerCache.h
+++ b/src/gpu/GrLayerCache.h
@@ -12,9 +12,10 @@
 
 #include "GrAllocPool.h"
 #include "GrAtlas.h"
-#include "GrTHashTable.h"
 #include "GrPictureUtils.h"
 #include "GrRect.h"
+#include "SkChecksum.h"
+#include "SkTDynamicHash.h"
 
 class SkPicture;
 
@@ -22,9 +23,14 @@ class SkPicture;
 // plot may be used to store layers from multiple pictures.
 struct GrPictureInfo {
 public:
+    // for SkTDynamicHash - just use the pictureID as the hash key
+    static const uint32_t& GetKey(const GrPictureInfo& pictInfo) { return pictInfo.fPictureID; }
+    static uint32_t Hash(const uint32_t& key) { return SkChecksum::Mix(key); }
+
+    // GrPictureInfo proper
     GrPictureInfo(uint32_t pictureID) : fPictureID(pictureID) { }
 
-    uint32_t fPictureID;
+    const uint32_t fPictureID;
 
     GrAtlas::ClientPlotUsage  fPlotUsage;
 };
@@ -37,16 +43,40 @@ public:
 // Atlased layers also get a pointer to the plot in which they reside.
 struct GrCachedLayer {
 public:
+    // For SkTDynamicHash
+    struct Key {
+        Key(uint32_t pictureID, int layerID) : fPictureID(pictureID) , fLayerID(layerID) {}
+
+        bool operator==(const Key& other) const {
+            return fPictureID == other.fPictureID && fLayerID == other.fLayerID;
+        }
+
+        uint32_t getPictureID() const { return fPictureID; }
+        int      getLayerID() const { return fLayerID; }
+
+    private:
+        // ID of the picture of which this layer is a part
+        const uint32_t fPictureID;
+        // fLayerID is the index of this layer in the picture (one of 0 .. #layers).
+        const int      fLayerID;
+    };
+
+    static const Key& GetKey(const GrCachedLayer& layer) { return layer.fKey; }
+    static uint32_t Hash(const Key& key) { 
+        return SkChecksum::Mix((key.getPictureID() << 16) | key.getLayerID());
+    }
+
+    // GrCachedLayer proper
     GrCachedLayer(uint32_t pictureID, int layerID) 
-        : fPlot(NULL) {
-        fPictureID = pictureID;
-        fLayerID = layerID;
-        fTexture = NULL;
-        fRect = GrIRect16::MakeEmpty();
+        : fKey(pictureID, layerID)
+        , fTexture(NULL)
+        , fRect(GrIRect16::MakeEmpty())
+        , fPlot(NULL) {
+        SkASSERT(SK_InvalidGenID != pictureID && layerID >= 0);
     }
 
-    uint32_t pictureID() const { return fPictureID; }
-    int layerID() const { return fLayerID; }
+    uint32_t pictureID() const { return fKey.getPictureID(); }
+    int layerID() const { return fKey.getLayerID(); }
 
     // This call takes over the caller's ref
     void setTexture(GrTexture* texture, const GrIRect16& rect) {
@@ -71,12 +101,7 @@ public:
     SkDEBUGCODE(void validate(const GrTexture* backingTexture) const;)
 
 private:
-    // ID of the picture of which this layer is a part
-    uint32_t        fPictureID;
-
-    // fLayerID is only valid when fPicture != kInvalidGenID in which case it
-    // is the index of this layer in the picture (one of 0 .. #layers).
-    int             fLayerID;
+    const Key       fKey;
 
     // fTexture is a ref on the atlasing texture for atlased layers and a
     // ref on a GrTexture for non-atlased textures. In both cases, if this is
@@ -138,11 +163,9 @@ private:
     // is leaked and never cleans itself up we still want to be able to 
     // remove the GrPictureInfo once its layers are purged from all the atlas
     // plots).
-    class PictureKey;
-    GrTHashTable<GrPictureInfo, PictureKey, 7> fPictureHash;
+    SkTDynamicHash<GrPictureInfo, uint32_t> fPictureHash;
 
-    class PictureLayerKey;
-    GrTHashTable<GrCachedLayer, PictureLayerKey, 7> fLayerHash;
+    SkTDynamicHash<GrCachedLayer, GrCachedLayer::Key> fLayerHash;
 
     void initAtlas();
     GrCachedLayer* createLayer(const SkPicture* picture, int layerID);
diff --git a/src/gpu/effects/GrTextureStripAtlas.cpp b/src/gpu/effects/GrTextureStripAtlas.cpp
index 0aa9dc3514..e3927c0d1f 100644
--- a/src/gpu/effects/GrTextureStripAtlas.cpp
+++ b/src/gpu/effects/GrTextureStripAtlas.cpp
@@ -17,17 +17,17 @@
     #define VALIDATE
 #endif
 
+class GrTextureStripAtlas::Hash : public SkTDynamicHash<GrTextureStripAtlas::AtlasEntry, 
+                                                        GrTextureStripAtlas::AtlasEntry::Key> {};
+
 int32_t GrTextureStripAtlas::gCacheCount = 0;
 
-GrTHashTable<GrTextureStripAtlas::AtlasEntry,
-                GrTextureStripAtlas::AtlasHashKey, 8>*
-                            GrTextureStripAtlas::gAtlasCache = NULL;
+GrTextureStripAtlas::Hash* GrTextureStripAtlas::gAtlasCache = NULL;
 
-GrTHashTable<GrTextureStripAtlas::AtlasEntry, GrTextureStripAtlas::AtlasHashKey, 8>*
-GrTextureStripAtlas::GetCache() {
+GrTextureStripAtlas::Hash* GrTextureStripAtlas::GetCache() {
 
     if (NULL == gAtlasCache) {
-        gAtlasCache = SkNEW((GrTHashTable<AtlasEntry, AtlasHashKey, 8>));
+        gAtlasCache = SkNEW(Hash);
     }
 
     return gAtlasCache;
@@ -40,7 +40,7 @@ void GrTextureStripAtlas::CleanUp(const GrContext*, void* info) {
     AtlasEntry* entry = static_cast<AtlasEntry*>(info);
 
     // remove the cache entry
-    GetCache()->remove(entry->fKey, entry);
+    GetCache()->remove(entry->fKey);
 
     // remove the actual entry
     SkDELETE(entry);
@@ -52,7 +52,7 @@ void GrTextureStripAtlas::CleanUp(const GrContext*, void* info) {
 }
 
 GrTextureStripAtlas* GrTextureStripAtlas::GetAtlas(const GrTextureStripAtlas::Desc& desc) {
-    AtlasHashKey key;
+    AtlasEntry::Key key;
     key.setKeyData(desc.asKey());
     AtlasEntry* entry = GetCache()->find(key);
     if (NULL == entry) {
@@ -63,7 +63,7 @@ GrTextureStripAtlas* GrTextureStripAtlas::GetAtlas(const GrTextureStripAtlas::De
 
         desc.fContext->addCleanUp(CleanUp, entry);
 
-        GetCache()->insert(key, entry);
+        GetCache()->add(entry);
     }
 
     return entry->fAtlas;
diff --git a/src/gpu/effects/GrTextureStripAtlas.h b/src/gpu/effects/GrTextureStripAtlas.h
index 5227cc38bd..6d2fb8fdf8 100644
--- a/src/gpu/effects/GrTextureStripAtlas.h
+++ b/src/gpu/effects/GrTextureStripAtlas.h
@@ -9,10 +9,10 @@
 #define GrTextureStripAtlas_DEFINED
 
 #include "GrBinHashKey.h"
-#include "GrTHashTable.h"
 #include "SkBitmap.h"
 #include "SkGr.h"
 #include "SkTDArray.h"
+#include "SkTDynamicHash.h"
 #include "SkTypes.h"
 
 /**
@@ -135,23 +135,24 @@ private:
     static void CleanUp(const GrContext* context, void* info);
 
     // Hash table entry for atlases
-    class AtlasEntry;
-    class AtlasHashKey : public GrBinHashKey<sizeof(GrTextureStripAtlas::Desc)> {
-    public:
-        static bool Equals(const AtlasEntry& entry, const AtlasHashKey& key);
-        static bool LessThan(const AtlasEntry& entry, const AtlasHashKey& key);
-    };
     class AtlasEntry : public ::SkNoncopyable {
     public:
+        // for SkTDynamicHash
+        class Key : public GrMurmur3HashKey<sizeof(GrTextureStripAtlas::Desc)> {};
+        static const Key& GetKey(const AtlasEntry& entry) { return entry.fKey; }
+        static uint32_t Hash(const Key& key) { return key.getHash(); }
+
+        // AtlasEntry proper
         AtlasEntry() : fAtlas(NULL) {}
         ~AtlasEntry() { SkDELETE(fAtlas); }
-        AtlasHashKey fKey;
+        Key fKey;
         GrTextureStripAtlas* fAtlas;
     };
 
-    static GrTHashTable<AtlasEntry, AtlasHashKey, 8>* gAtlasCache;
+    class Hash;
+    static Hash* gAtlasCache;
 
-    static GrTHashTable<AtlasEntry, AtlasHashKey, 8>* GetCache();
+    static Hash* GetCache();
 
     // We increment gCacheCount for each atlas
     static int32_t gCacheCount;
@@ -181,14 +182,4 @@ private:
     SkTDArray<AtlasRow*> fKeyTable;
 };
 
-inline bool GrTextureStripAtlas::AtlasHashKey::Equals(const AtlasEntry& entry,
-                                                      const AtlasHashKey& key) {
-    return entry.fKey == key;
-}
-
-inline bool GrTextureStripAtlas::AtlasHashKey::LessThan(const AtlasEntry& entry,
-                                                        const AtlasHashKey& key) {
-    return entry.fKey < key;
-}
-
 #endif
diff --git a/src/gpu/gl/GrGpuGL.h b/src/gpu/gl/GrGpuGL.h
index a2c636d2aa..52e7b86f4a 100644
--- a/src/gpu/gl/GrGpuGL.h
+++ b/src/gpu/gl/GrGpuGL.h
@@ -19,7 +19,6 @@
 #include "GrGLVertexArray.h"
 #include "GrGLVertexBuffer.h"
 #include "GrGpu.h"
-#include "GrTHashTable.h"
 #include "SkTypes.h"
 
 #ifdef SK_DEVELOPER
diff --git a/tests/DynamicHashTest.cpp b/tests/DynamicHashTest.cpp
index b2da6f3888..4a5bb850f8 100644
--- a/tests/DynamicHashTest.cpp
+++ b/tests/DynamicHashTest.cpp
@@ -136,12 +136,12 @@ DEF_TEST(DynamicHash_remove, reporter) {
     ASSERT(hash.find(5)->value == 3.0);
 }
 
-DEF_TEST(DynamicHash_iterator, reporter) {
+template<typename T> static void TestIter(skiatest::Reporter* reporter) {
     Hash hash;
 
     int count = 0;
     // this should fall out of loop immediately
-    for (Hash::Iter iter(&hash); !iter.done(); ++iter) {
+    for (T iter(&hash); !iter.done(); ++iter) {
         ++count;
     }
     ASSERT(0 == count);
@@ -158,7 +158,7 @@ DEF_TEST(DynamicHash_iterator, reporter) {
     // should see all 3 unique keys when iterating over hash
     count = 0;
     int keys[3] = {0, 0, 0};
-    for (Hash::Iter iter(&hash); !iter.done(); ++iter) {
+    for (T iter(&hash); !iter.done(); ++iter) {
         int key = (*iter).key;
         keys[count] = key;
         ASSERT(hash.find(key) != NULL);
@@ -172,8 +172,8 @@ DEF_TEST(DynamicHash_iterator, reporter) {
     // should see 2 unique keys when iterating over hash that aren't 1
     hash.remove(1);
     count = 0;
-    memset(keys,0,sizeof(keys));
-    for (Hash::Iter iter(&hash); !iter.done(); ++iter) {
+    memset(keys, 0, sizeof(keys));
+    for (T iter(&hash); !iter.done(); ++iter) {
         int key = (*iter).key;
         keys[count] = key;
         ASSERT(key != 1);
@@ -183,3 +183,46 @@ DEF_TEST(DynamicHash_iterator, reporter) {
     ASSERT(2 == count);
     ASSERT(keys[0] != keys[1]);
 }
+
+DEF_TEST(DynamicHash_iterator, reporter) {
+    TestIter<Hash::Iter>(reporter);
+    TestIter<Hash::ConstIter>(reporter);
+}
+
+static void TestResetOrRewind(skiatest::Reporter* reporter, bool testReset) {
+    Hash hash;
+    Entry a = { 1, 2.0 };
+    Entry b = { 2, 3.0 };
+
+    ASSERT(hash.capacity() == 0);
+    hash.add(&a);
+    hash.add(&b);
+    ASSERT(hash.count() == 2);
+    ASSERT(hash.capacity() == 4);
+
+    if (testReset) {
+        hash.reset();
+        ASSERT(hash.capacity() == 0);
+    } else {
+        hash.rewind();
+        ASSERT(hash.capacity() == 4);
+    }
+    ASSERT(hash.count() == 0);
+
+    // make sure things still work
+    hash.add(&a);
+    hash.add(&b);
+    ASSERT(hash.count() == 2);
+    ASSERT(hash.capacity() == 4);
+
+    ASSERT(hash.find(1) != NULL);
+    ASSERT(hash.find(2) != NULL);
+}
+
+DEF_TEST(DynamicHash_reset, reporter) {
+    TestResetOrRewind(reporter, true);
+}
+
+DEF_TEST(DynamicHash_rewind, reporter) {
+    TestResetOrRewind(reporter, false);
+}
diff --git a/tests/GrBinHashKeyTest.cpp b/tests/GrBinHashKeyTest.cpp
index fbcf4822a7..2efd2f9324 100644
--- a/tests/GrBinHashKeyTest.cpp
+++ b/tests/GrBinHashKeyTest.cpp
@@ -12,19 +12,16 @@
 
 #include "Test.h"
 
-DEF_TEST(GrBinHashKey, reporter) {
+template<typename KeyType> static void TestHash(skiatest::Reporter* reporter) {
     const char* testStringA_ = "abcdABCD";
     const char* testStringB_ = "abcdBBCD";
     const uint32_t* testStringA = reinterpret_cast<const uint32_t*>(testStringA_);
     const uint32_t* testStringB = reinterpret_cast<const uint32_t*>(testStringB_);
-    enum {
-        kDataLenUsedForKey = 8
-    };
 
-    GrBinHashKey<kDataLenUsedForKey> keyA;
+    KeyType keyA;
     keyA.setKeyData(testStringA);
     // test copy constructor and comparison
-    GrBinHashKey<kDataLenUsedForKey> keyA2(keyA);
+    KeyType keyA2(keyA);
     REPORTER_ASSERT(reporter, keyA == keyA2);
     REPORTER_ASSERT(reporter, keyA.getHash() == keyA2.getHash());
     // test re-init
@@ -32,10 +29,19 @@ DEF_TEST(GrBinHashKey, reporter) {
     REPORTER_ASSERT(reporter, keyA == keyA2);
     REPORTER_ASSERT(reporter, keyA.getHash() == keyA2.getHash());
     // test sorting
-    GrBinHashKey<kDataLenUsedForKey> keyB;
+    KeyType keyB;
     keyB.setKeyData(testStringB);
-    REPORTER_ASSERT(reporter, keyA < keyB);
     REPORTER_ASSERT(reporter, keyA.getHash() != keyB.getHash());
 }
 
+
+DEF_TEST(GrBinHashKey, reporter) {
+    enum {
+        kDataLenUsedForKey = 8
+    };
+
+    TestHash<GrBinHashKey<kDataLenUsedForKey> >(reporter);
+    TestHash<GrMurmur3HashKey<kDataLenUsedForKey> >(reporter);
+}
+
 #endif