diff -r 000000000000 -r 6474c204b198 gfx/skia/trunk/src/core/SkTDynamicHash.h
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/gfx/skia/trunk/src/core/SkTDynamicHash.h	Wed Dec 31 06:09:35 2014 +0100
@@ -0,0 +1,238 @@
+/*
+ * 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 "SkMath.h"
+#include "SkTemplates.h"
+#include "SkTypes.h"
+
+template <typename T,
+          typename Key,
+          const Key& (GetKey)(const T&),
+          uint32_t (Hash)(const Key&),
+          bool (Equal)(const T&, const Key&),
+          int kGrowPercent = 75>  // Larger -> more memory efficient, but slower.
+class SkTDynamicHash {
+public:
+    SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(NULL) {
+        SkASSERT(this->validate());
+    }
+
+    ~SkTDynamicHash() {
+        sk_free(fArray);
+    }
+
+    class Iter {
+    public:
+        explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
+            SkASSERT(hash);
+            ++(*this);
+        }
+        bool done() const {
+            SkASSERT(fCurrentIndex <= fHash->fCapacity);
+            return fCurrentIndex == fHash->fCapacity;
+        }
+        T& operator*() const {
+            SkASSERT(!this->done());
+            return *this->current();
+        }
+        void operator++() {
+            do {
+                fCurrentIndex++;
+            } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
+        }
+
+    private:
+        T* current() const { return fHash->fArray[fCurrentIndex]; }
+
+        SkTDynamicHash* fHash;
+        int fCurrentIndex;
+    };
+
+    int count() const { return fCount; }
+
+    // Return the entry with this key if we have it, otherwise NULL.
+    T* find(const Key& key) const {
+        int index = this->firstIndex(key);
+        for (int round = 0; round < fCapacity; round++) {
+            T* candidate = fArray[index];
+            if (Empty() == candidate) {
+                return NULL;
+            }
+            if (Deleted() != candidate && Equal(*candidate, key)) {
+                return candidate;
+            }
+            index = this->nextIndex(index, round);
+        }
+        SkASSERT(fCapacity == 0);
+        return NULL;
+    }
+
+    // Add an entry with this key.  We require that no entry with newEntry's key is already present.
+    void add(T* newEntry) {
+        SkASSERT(NULL == this->find(GetKey(*newEntry)));
+        this->maybeGrow();
+        this->innerAdd(newEntry);
+        SkASSERT(this->validate());
+    }
+
+    // Remove the entry with this key.  We reqire that an entry with this key is present.
+    void remove(const Key& key) {
+        SkASSERT(NULL != this->find(key));
+        this->innerRemove(key);
+        SkASSERT(this->validate());
+    }
+
+protected:
+    // These methods are used by tests only.
+
+    int capacity() const { return fCapacity; }
+
+    // How many collisions do we go through before finding where this entry should be inserted?
+    int countCollisions(const Key& key) const {
+        int index = this->firstIndex(key);
+        for (int round = 0; round < fCapacity; round++) {
+            const T* candidate = fArray[index];
+            if (Empty() == candidate || Deleted() == candidate || Equal(*candidate, key)) {
+                return round;
+            }
+            index = this->nextIndex(index, round);
+        }
+        SkASSERT(fCapacity == 0);
+        return 0;
+    }
+
+private:
+    // We have two special values to indicate an empty or deleted entry.
+    static T* Empty()   { return reinterpret_cast<T*>(0); }  // i.e. NULL
+    static T* Deleted() { return reinterpret_cast<T*>(1); }  // Also an invalid pointer.
+
+    bool validate() const {
+        #define SKTDYNAMICHASH_CHECK(x) SkASSERT((x)); if (!(x)) return false
+        static const int kLarge = 50;  // Arbitrary, tweak to suit your patience.
+
+        // O(1) checks, always done.
+        // Is capacity sane?
+        SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
+
+        // O(N) checks, skipped when very large.
+        if (fCount < kLarge * kLarge) {
+            // Are fCount and fDeleted correct, and are all elements findable?
+            int count = 0, deleted = 0;
+            for (int i = 0; i < fCapacity; i++) {
+                if (Deleted() == fArray[i]) {
+                    deleted++;
+                } else if (Empty() != fArray[i]) {
+                    count++;
+                    SKTDYNAMICHASH_CHECK(NULL != this->find(GetKey(*fArray[i])));
+                }
+            }
+            SKTDYNAMICHASH_CHECK(count == fCount);
+            SKTDYNAMICHASH_CHECK(deleted == fDeleted);
+        }
+
+        // O(N^2) checks, skipped when large.
+        if (fCount < kLarge) {
+            // Are all entries unique?
+            for (int i = 0; i < fCapacity; i++) {
+                if (Empty() == fArray[i] || Deleted() == fArray[i]) {
+                    continue;
+                }
+                for (int j = i+1; j < fCapacity; j++) {
+                    if (Empty() == fArray[j] || Deleted() == fArray[j]) {
+                        continue;
+                    }
+                    SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
+                    SKTDYNAMICHASH_CHECK(!Equal(*fArray[i], GetKey(*fArray[j])));
+                    SKTDYNAMICHASH_CHECK(!Equal(*fArray[j], GetKey(*fArray[i])));
+                }
+            }
+        }
+        #undef SKTDYNAMICHASH_CHECK
+        return true;
+    }
+
+    void innerAdd(T* newEntry) {
+        const Key& key = GetKey(*newEntry);
+        int index = this->firstIndex(key);
+        for (int round = 0; round < fCapacity; round++) {
+            const T* candidate = fArray[index];
+            if (Empty() == candidate || Deleted() == candidate) {
+                if (Deleted() == candidate) {
+                    fDeleted--;
+                }
+                fCount++;
+                fArray[index] = newEntry;
+                return;
+            }
+            index = this->nextIndex(index, round);
+        }
+        SkASSERT(fCapacity == 0);
+    }
+
+    void innerRemove(const Key& key) {
+        const int firstIndex = this->firstIndex(key);
+        int index = firstIndex;
+        for (int round = 0; round < fCapacity; round++) {
+            const T* candidate = fArray[index];
+            if (Deleted() != candidate && Equal(*candidate, key)) {
+                fDeleted++;
+                fCount--;
+                fArray[index] = Deleted();
+                return;
+            }
+            index = this->nextIndex(index, round);
+        }
+        SkASSERT(fCapacity == 0);
+    }
+
+    void maybeGrow() {
+        if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
+            this->resize(fCapacity > 0 ? fCapacity * 2 : 4);
+        }
+    }
+
+    void resize(int newCapacity) {
+        SkDEBUGCODE(int oldCount = fCount;)
+        int oldCapacity = fCapacity;
+        SkAutoTMalloc<T*> oldArray(fArray);
+
+        fCount = fDeleted = 0;
+        fCapacity = newCapacity;
+        fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity);
+
+        for (int i = 0; i < oldCapacity; i++) {
+            T* entry = oldArray[i];
+            if (Empty() != entry && Deleted() != entry) {
+                this->innerAdd(entry);
+            }
+        }
+        SkASSERT(oldCount == fCount);
+    }
+
+    // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
+    uint32_t hashMask() const { return fCapacity - 1; }
+
+    int firstIndex(const Key& key) const {
+        return Hash(key) & this->hashMask();
+    }
+
+    // Given index at round N, what is the index to check at N+1?  round should start at 0.
+    int nextIndex(int index, int round) const {
+        // This will search a power-of-two array fully without repeating an index.
+        return (index + round + 1) & this->hashMask();
+    }
+
+    int fCount;     // Number of non Empty(), non Deleted() entries in fArray.
+    int fDeleted;   // Number of Deleted() entries in fArray.
+    int fCapacity;  // Number of entries in fArray.  Always a power of 2.
+    T** fArray;
+};
+
+#endif