experimental dynamic-hash (disabled)

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

3 files changed, 205 insertions, 22 deletions

diff --git a/src/core/SkScaledImageCache.cpp b/src/core/SkScaledImageCache.cpp
index b8590f5b65..147697af4e 100644
--- a/src/core/SkScaledImageCache.cpp
+++ b/src/core/SkScaledImageCache.cpp
@@ -14,7 +14,7 @@
     #define SK_DEFAULT_IMAGE_CACHE_LIMIT     (2 * 1024 * 1024)
 #endif
 
-#if 1
+
  // Implemented from en.wikipedia.org/wiki/MurmurHash.
 static uint32_t compute_hash(const uint32_t data[], int count) {
     uint32_t hash = 0;
@@ -40,20 +40,6 @@ static uint32_t compute_hash(const uint32_t data[], int count) {
 
     return hash;
 }
-#else
-static uint32_t mix(uint32_t a, uint32_t b) {
-    return ((a >> 1) | (a << 31)) ^ b;
-}
-
-static uint32_t compute_hash(const uint32_t data[], int count) {
-    uint32_t hash = 0;
-
-    for (int i = 0; i < count; ++i) {
-        hash = mix(hash, data[i]);
-    }
-    return hash;
-}
-#endif
 
 struct Key {
     bool init(const SkBitmap& bm, SkScalar scaleX, SkScalar scaleY) {
@@ -76,7 +62,7 @@ struct Key {
         return true;
     }
 
-    bool operator<(const Key& other) {
+    bool operator<(const Key& other) const {
         const uint32_t* a = &fGenID;
         const uint32_t* b = &other.fGenID;
         for (int i = 0; i < 7; ++i) {
@@ -90,7 +76,7 @@ struct Key {
         return false;
     }
 
-    bool operator==(const Key& other) {
+    bool operator==(const Key& other) const {
         const uint32_t* a = &fHash;
         const uint32_t* b = &other.fHash;
         for (int i = 0; i < 8; ++i) {
@@ -141,9 +127,36 @@ struct SkScaledImageCache::Rec {
     const SkMipMap* fMip;
 };
 
+#include "SkTDynamicHash.h"
+
+static const Key& key_from_rec(const SkScaledImageCache::Rec& rec) {
+    return rec.fKey;
+}
+
+static uint32_t hash_from_key(const Key& key) {
+    return key.fHash;
+}
+
+static bool eq_rec_key(const SkScaledImageCache::Rec& rec, const Key& key) {
+    return rec.fKey == key;
+}
+
+class SkScaledImageCache::Hash : public SkTDynamicHash<SkScaledImageCache::Rec,
+                                   Key, key_from_rec, hash_from_key,
+                                   eq_rec_key> {};
+
+///////////////////////////////////////////////////////////////////////////////
+
+//#define USE_HASH
+
 SkScaledImageCache::SkScaledImageCache(size_t byteLimit) {
     fHead = NULL;
     fTail = NULL;
+#ifdef USE_HASH
+    fHash = new Hash;
+#else
+    fHash = NULL;
+#endif
     fBytesUsed = 0;
     fByteLimit = byteLimit;
     fCount = 0;
@@ -156,6 +169,7 @@ SkScaledImageCache::~SkScaledImageCache() {
         SkDELETE(rec);
         rec = next;
     }
+    delete fHash;
 }
 
 SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(const SkBitmap& orig,
@@ -166,16 +180,23 @@ SkScaledImageCache::Rec* SkScaledImageCache::findAndLock(const SkBitmap& orig,
         return NULL;
     }
 
+#ifdef USE_HASH
+    Rec* rec = fHash->find(key);
+#else
     Rec* rec = fHead;
     while (rec != NULL) {
         if (rec->fKey == key) {
-            this->moveToHead(rec);  // for our LRU
-            rec->fLockCount += 1;
-            return rec;
+            break;
         }
         rec = rec->fNext;
     }
-    return NULL;
+#endif
+
+    if (rec) {
+        this->moveToHead(rec);  // for our LRU
+        rec->fLockCount += 1;
+    }
+    return rec;
 }
 
 SkScaledImageCache::ID* SkScaledImageCache::findAndLock(const SkBitmap& orig,
@@ -225,6 +246,10 @@ SkScaledImageCache::ID* SkScaledImageCache::addAndLock(const SkBitmap& orig,
     this->addToHead(rec);
     SkASSERT(1 == rec->fLockCount);
 
+#ifdef USE_HASH
+    fHash->add(key, rec);
+#endif
+
     // We may (now) be overbudget, so see if we need to purge something.
     this->purgeAsNeeded();
     return (ID*)rec;
@@ -241,6 +266,10 @@ SkScaledImageCache::ID* SkScaledImageCache::addAndLockMip(const SkBitmap& orig,
     this->addToHead(rec);
     SkASSERT(1 == rec->fLockCount);
 
+#ifdef USE_HASH
+    fHash->add(key, rec);
+#endif
+
     // We may (now) be overbudget, so see if we need to purge something.
     this->purgeAsNeeded();
     return (ID*)rec;
@@ -292,6 +321,10 @@ void SkScaledImageCache::purgeAsNeeded() {
             SkASSERT(used <= bytesUsed);
             bytesUsed -= used;
             this->detach(rec);
+#ifdef USE_HASH
+            fHash->remove(rec->fKey);
+#endif
+            
             SkDELETE(rec);
             fCount -= 1;
         }
diff --git a/src/core/SkScaledImageCache.h b/src/core/SkScaledImageCache.h
index 6ec62751f5..32474b7f61 100644
--- a/src/core/SkScaledImageCache.h
+++ b/src/core/SkScaledImageCache.h
@@ -88,11 +88,15 @@ public:
      */
     size_t setByteLimit(size_t newLimit);
 
-private:
+public:
     struct Rec;
+private:
     Rec*    fHead;
     Rec*    fTail;
 
+    class Hash;
+    Hash*   fHash;
+
     size_t  fBytesUsed;
     size_t  fByteLimit;
     int     fCount;
diff --git a/src/core/SkTDynamicHash.h b/src/core/SkTDynamicHash.h
new file mode 100644
index 0000000000..665028abaa
--- /dev/null
+++ b/src/core/SkTDynamicHash.h
@@ -0,0 +1,146 @@
+/*
+ * Copyright 2013 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+#ifndef SkTDynamicHash_DEFINED
+#define SkTDynamicHash_DEFINED
+
+#include "SkTypes.h"
+
+template <typename T, typename KEY, const KEY& (KEY_FROM_T)(const T&),
+uint32_t (HASH_FROM_KEY)(const Key&), bool (EQ_T_KEY)(const T&, const Key&)>
+class SkTDynamicHash {
+private:
+    T* fStorage[1];
+    T** fArray;
+    int fCapacity;
+    int fCountUsed;
+    int fCountDeleted;
+    
+    unsigned hashMask() const { return fCapacity - 1; }
+    const T* deletedValue() const { return reinterpret_cast<const T*>(-1); }
+    
+public:
+    SkTDynamicHash() {
+        fArray = fStorage;
+        fCapacity = 1;
+        fCountUsed = fCountDeleted = 0;
+    }
+    ~SkTDynamicHash() {
+        if (fArray != fStorage) {
+            sk_free(fArray);
+        }
+    }
+    
+    T* find(const KEY& key) {
+        const T* const deleted = this->deletedValue();
+        const unsigned mask = this->hashMask();
+        int index = HASH_FROM_KEY(key) & mask;
+        const int origIndex = index;
+        int delta = 1;
+        
+        do {
+            T* candidate = fArray[index];
+            if (NULL == candidate) {
+                return NULL;
+            }
+            if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
+                return candidate;
+            }
+            index = (index + delta) & mask;
+            delta <<= 1;
+        } while (index != origIndex);
+        return NULL;
+    }
+    
+    bool add(const KEY& key, T* newElement, bool autoGrow = true) {
+        const T* const deleted = this->deletedValue();
+        for (;;) {
+            const unsigned mask = this->hashMask();
+            int index = HASH_FROM_KEY(key) & mask;
+            const int origIndex = index;
+            int delta = 1;
+            
+            do {
+                const T* candidate = fArray[index];
+                if (NULL == candidate || deleted == candidate) {
+                    fArray[index] = newElement;
+                    fCountUsed += 1;
+                    if (deleted == candidate) {
+                        SkASSERT(fCountDeleted > 0);
+                        fCountDeleted -= 1;
+                    }
+                    return true;
+                }
+                index = (index + delta) & mask;
+                delta <<= 1;
+            } while (index != origIndex);
+            if (autoGrow) {
+                this->grow();
+            } else {
+                return false;
+            }
+        }
+        SkASSERT(!"never get here");
+        return false;
+    }
+    
+    void remove(const KEY& key) {
+        const T* const deleted = this->deletedValue();
+        const unsigned mask = this->hashMask();
+        const uint32_t hash = HASH_FROM_KEY(key);
+        int index = hash & mask;
+        SkDEBUGCODE(const int origIndex = index;)
+        int delta = 1;
+        
+        for (;;) {
+            const T* candidate = fArray[index];
+            SkASSERT(candidate);
+            if (deleted != candidate && EQ_T_KEY(*candidate, key)) {
+                fArray[index] = const_cast<T*>(deleted);
+                fCountDeleted += 1;
+                break;
+            }
+            index = (index + delta) & mask;
+            delta <<= 1;
+            SkASSERT(index != origIndex);
+        }
+        this->checkStrink();
+    }
+    
+private:
+    void grow() {
+        const T* const deleted = this->deletedValue();
+        
+        int oldCapacity = fCapacity;
+        T** oldArray = fArray;
+        
+        int newCapacity = oldCapacity << 1;
+        T** newArray = (T**)sk_malloc_throw(sizeof(T*) * newCapacity);
+        sk_bzero(newArray, sizeof(T*) * newCapacity);
+        
+        SkDEBUGCODE(int oldCountUsed = fCountUsed;)
+        fArray = newArray;
+        fCapacity = newCapacity;
+        fCountUsed = 0;
+        fCountDeleted = 0;
+        
+        for (int i = 0; i < oldCapacity; ++i) {
+            T* elem = oldArray[i];
+            if (NULL == elem || deleted == elem) {
+                continue;
+            }
+            SkDEBUGCODE(bool success =) this->add(KEY_FROM_T(*elem), elem, false);
+            SkASSERT(success);
+        }
+        SkASSERT(oldCountUsed == fCountUsed);
+        sk_free(oldArray);
+    }
+    
+    void checkStrink() {}
+};
+
+#endif