Added functor to GrTHashCache to allow discovery of un-reffed resources

http://codereview.appspot.com/6503126/



git-svn-id: http://skia.googlecode.com/svn/trunk@5587 2bbb7eff-a529-9590-31e7-b0007b416f81

3 files changed, 213 insertions, 9 deletions

diff --git a/gyp/tests.gyp b/gyp/tests.gyp
index dcfd1b49f8..874bb7f642 100644
--- a/gyp/tests.gyp
+++ b/gyp/tests.gyp
@@ -51,6 +51,7 @@
         '../tests/GrContextFactoryTest.cpp',
         '../tests/GradientTest.cpp',
         '../tests/GrMemoryPoolTest.cpp',
+        '../tests/HashCacheTest.cpp',
         '../tests/InfRectTest.cpp',
         '../tests/MathTest.cpp',
         '../tests/MatrixTest.cpp',
diff --git a/src/gpu/GrTHashCache.h b/src/gpu/GrTHashCache.h
index 8651c35c22..118b76a006 100644
--- a/src/gpu/GrTHashCache.h
+++ b/src/gpu/GrTHashCache.h
@@ -13,6 +13,15 @@
 
 #include "GrTDArray.h"
 
+// GrTDefaultFindFunctor implements the default find behavior for 
+// GrTHashTable (i.e., return the first resource that matches the 
+// provided key)
+template <typename T> class GrTDefaultFindFunctor {
+public:
+    // always accept the first element examined
+    bool operator()(const T* elem) const { return true; }
+};
+
 /**
  *  Key needs
  *      static bool EQ(const Entry&, const HashKey&);
@@ -29,6 +38,7 @@ public:
 
     int count() const { return fSorted.count(); }
     T*  find(const Key&) const;
+    template <typename FindFuncType> T*  find(const Key&, const FindFuncType&) const;
     // return true if key was unique when inserted.
     bool insert(const Key&, T*);
     void remove(const Key&, const T*);
@@ -109,20 +119,43 @@ int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const {
 
 template <typename T, typename Key, size_t kHashBits>
 T* GrTHashTable<T, Key, kHashBits>::find(const Key& key) const {
+    GrTDefaultFindFunctor<T> find;
+
+    return this->find(key, find);
+}
+
+template <typename T, typename Key, size_t kHashBits>
+template <typename FindFuncType>
+T* GrTHashTable<T, Key, kHashBits>::find(const Key& key, const FindFuncType& findFunc) const {
+
     int hashIndex = hash2Index(key.getHash());
     T* elem = fHash[hashIndex];
 
-    if (NULL == elem || !Key::EQ(*elem, key)) {
-        // bsearch for the key in our sorted array
-        int index = this->searchArray(key);
-        if (index < 0) {
-            return NULL;
+    if (NULL != elem && Key::EQ(*elem, key) && findFunc(elem)) {
+        return elem;
+    }                                             
+
+    // bsearch for the key in our sorted array
+    int index = this->searchArray(key);
+    if (index < 0) {
+        return NULL;
+    }
+
+    const T* const* array = fSorted.begin();
+
+    // above search should have found the first occurrence if there
+    // are multiple.
+    GrAssert(0 == index || Key::LT(*array[index - 1], key));
+
+    for ( ; index < count() && Key::EQ(*array[index], key); ++index) {
+        if (findFunc(fSorted[index])) {
+            // update the hash
+            fHash[hashIndex] = fSorted[index];
+            return fSorted[index];
         }
-        elem = fSorted[index];
-        // update the hash
-        fHash[hashIndex] = elem;
     }
-    return elem;
+
+    return NULL;
 }
 
 template <typename T, typename Key, size_t kHashBits>
diff --git a/tests/HashCacheTest.cpp b/tests/HashCacheTest.cpp
new file mode 100644
index 0000000000..0b15fa63f7
--- /dev/null
+++ b/tests/HashCacheTest.cpp
@@ -0,0 +1,170 @@
+/*
+ * Copyright 2012 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+
+#include "Test.h"
+
+// This is a GR test
+#if SK_SUPPORT_GPU
+#include "..\src\gpu\GrTHashCache.h"
+
+struct HashElement {
+    int     fKey;
+    int     fValue;
+};
+
+class GrFindPositivesFunctor {
+public:
+    // only return elements with positive values
+    bool operator()(const HashElement* elem) const { 
+        return elem->fValue > 0;
+    }
+};
+
+class GrFindNegativesFunctor {
+public:
+    // only return elements with negative values
+    bool operator()(const HashElement* elem) const { 
+        return elem->fValue < 0;
+    }
+};
+
+class HashKey {
+public:
+    HashKey(int key) : fKey(key) {}
+
+    uint32_t getHash() const { return fKey; }
+
+    static bool LT(const HashElement& entry, const HashKey& key) {
+        return entry.fKey < key.fKey;
+    }
+    static bool EQ(const HashElement& entry, const HashKey& key) {
+        return entry.fKey == key.fKey;
+    }
+
+#if GR_DEBUG
+    static uint32_t GetHash(const HashElement& entry) {
+        return entry.fKey;
+    }
+    static bool LT(const HashElement& a, const HashElement& b) {
+        return a.fKey < b.fKey;
+    }
+    static bool EQ(const HashElement& a, const HashElement& b) {
+        return a.fKey == b.fKey;
+    }
+#endif
+
+protected:
+    int fKey;
+};
+
+////////////////////////////////////////////////////////////////////////////////
+static void TestHashCache(skiatest::Reporter* reporter, GrContext* context) {
+
+    GrTHashTable<HashElement, HashKey, 4> cache;
+
+    HashElement negHashElements[10] = { 
+        { 0,  0 }, 
+        { 1, -1 },
+        { 2, -2 }, 
+        { 3, -3 }, 
+        { 4, -4 }, 
+        { 5, -5 }, 
+        { 6, -6 }, 
+        { 7, -7 }, 
+        { 8, -8 }, 
+        { 9, -9 }
+    };
+    HashElement posHashElements[10] = { 
+        { 0, 0 }, 
+        { 1, 1 },
+        { 2, 2 }, 
+        { 3, 3 }, 
+        { 4, 4 }, 
+        { 5, 5 }, 
+        { 6, 6 }, 
+        { 7, 7 }, 
+        { 8, 8 }, 
+        { 9, 9 }
+    };
+
+    // add i: -i pairs
+    for (int i = 0; i < 10; ++i) {
+        cache.insert(HashKey(i), &negHashElements[i]);
+    }
+
+    REPORTER_ASSERT(reporter, 10 == cache.count());
+
+    // look for all i's and assert we found the -i's
+    for (int i = 0; i < 10; ++i) {
+        HashElement* found = cache.find(i);
+        REPORTER_ASSERT(reporter, NULL != found && -i == found->fValue);
+    }
+
+    // look for something not in the cache
+    {
+        HashElement* found = cache.find(10);
+        REPORTER_ASSERT(reporter, NULL == found);
+    }
+
+    // add i:i duplicates (so each i will have a positive & negative entry)
+    for (int i = 0; i < 10; ++i) {
+        cache.insert(i, &posHashElements[i]);
+    }
+
+    REPORTER_ASSERT(reporter, 20 == cache.count());
+    
+    // test out the find functor to find all the positive values
+    {
+        GrFindPositivesFunctor findPos;
+
+        HashElement* found = cache.find(0, findPos);
+        REPORTER_ASSERT(reporter, NULL == found);
+
+        for (int i = 1; i < 10; ++i) {
+            found = cache.find(i, findPos);
+
+            REPORTER_ASSERT(reporter, NULL != found && found->fValue > 0);
+        }
+    }
+
+    // make sure finding the positives wasn't a fluke - find the negatives
+    {
+        GrFindNegativesFunctor findNeg;
+
+        HashElement* found = cache.find(0, findNeg);
+        REPORTER_ASSERT(reporter, NULL == found);
+
+        for (int i = 1; i < 10; ++i) {
+            found = cache.find(i, findNeg);
+
+            REPORTER_ASSERT(reporter, NULL != found && found->fValue < 0);
+        }
+    }
+
+    // remove the 0:0 entries
+    {
+        cache.remove(0, &negHashElements[0]);
+        cache.remove(0, &posHashElements[0]);
+        REPORTER_ASSERT(reporter, 18 == cache.count());
+
+        HashElement* found = cache.find(0);
+        REPORTER_ASSERT(reporter, NULL == found);
+    }
+
+    // remove all
+    {
+        cache.removeAll();
+        REPORTER_ASSERT(reporter, 0 == cache.count());
+    }
+}
+
+////////////////////////////////////////////////////////////////////////////////
+#include "TestClassDef.h"
+DEFINE_GPUTESTCLASS("HashCache", HashCacheTestClass, TestHashCache)
+
+#endif