GrTHashCache -> GrTHashTable
The class is Table, but the file's Cache. That's confusing.
BUG=
R=bsalomon@google.com
Review URL: https://codereview.chromium.org/32523004
git-svn-id: http://skia.googlecode.com/svn/trunk@11898 2bbb7eff-a529-9590-31e7-b0007b416f81
diff --git a/src/gpu/GrTHashTable.h b/src/gpu/GrTHashTable.h
new file mode 100644
index 0000000..803a680
--- /dev/null
+++ b/src/gpu/GrTHashTable.h
@@ -0,0 +1,246 @@
+
+/*
+ * Copyright 2010 Google Inc.
+ *
+ * Use of this source code is governed by a BSD-style license that can be
+ * found in the LICENSE file.
+ */
+
+
+
+#ifndef GrTHashTable_DEFINED
+#define GrTHashTable_DEFINED
+
+#include "GrTypes.h"
+#include "SkTDArray.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*) const { return true; }
+};
+
+/**
+ * Key needs
+ * static bool EQ(const Entry&, const HashKey&);
+ * static bool LT(const Entry&, const HashKey&);
+ * uint32_t getHash() const;
+ *
+ * Allows duplicate key entries but on find you may get
+ * any of the duplicate entries returned.
+ */
+template <typename T, typename Key, size_t kHashBits> class GrTHashTable {
+public:
+ GrTHashTable() { sk_bzero(fHash, sizeof(fHash)); }
+ ~GrTHashTable() {}
+
+ 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*);
+ T* removeAt(int index, uint32_t hash);
+ void removeAll();
+ void deleteAll();
+ void unrefAll();
+
+ /**
+ * Return the index for the element, using a linear search.
+ */
+ int slowFindIndex(T* elem) const { return fSorted.find(elem); }
+
+#ifdef SK_DEBUG
+ void validate() const;
+ bool contains(T*) const;
+#endif
+
+ // testing
+ const SkTDArray<T*>& getArray() const { return fSorted; }
+ SkTDArray<T*>& getArray() { return fSorted; }
+private:
+ enum {
+ kHashCount = 1 << kHashBits,
+ kHashMask = kHashCount - 1
+ };
+ static unsigned hash2Index(uint32_t hash) {
+ hash ^= hash >> 16;
+ if (kHashBits <= 8) {
+ hash ^= hash >> 8;
+ }
+ return hash & kHashMask;
+ }
+
+ mutable T* fHash[kHashCount];
+ SkTDArray<T*> fSorted;
+
+ // search fSorted, and return the found index, or ~index of where it
+ // should be inserted
+ int searchArray(const Key&) const;
+};
+
+///////////////////////////////////////////////////////////////////////////////
+
+template <typename T, typename Key, size_t kHashBits>
+int GrTHashTable<T, Key, kHashBits>::searchArray(const Key& key) const {
+ int count = fSorted.count();
+ if (0 == count) {
+ // we should insert it at 0
+ return ~0;
+ }
+
+ const T* const* array = fSorted.begin();
+ int high = count - 1;
+ int low = 0;
+ while (high > low) {
+ int index = (low + high) >> 1;
+ if (Key::LT(*array[index], key)) {
+ low = index + 1;
+ } else {
+ high = index;
+ }
+ }
+
+ // check if we found it
+ if (Key::EQ(*array[high], key)) {
+ // above search should have found the first occurrence if there
+ // are multiple.
+ SkASSERT(0 == high || Key::LT(*array[high - 1], key));
+ return high;
+ }
+
+ // now return the ~ of where we should insert it
+ if (Key::LT(*array[high], key)) {
+ high += 1;
+ }
+ return ~high;
+}
+
+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) && 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.
+ SkASSERT(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];
+ }
+ }
+
+ return NULL;
+}
+
+template <typename T, typename Key, size_t kHashBits>
+bool GrTHashTable<T, Key, kHashBits>::insert(const Key& key, T* elem) {
+ int index = this->searchArray(key);
+ bool first = index < 0;
+ if (first) {
+ // turn it into the actual index
+ index = ~index;
+ }
+ // add it to our array
+ *fSorted.insert(index) = elem;
+ // update our hash table (overwrites any dupe's position in the hash)
+ fHash[hash2Index(key.getHash())] = elem;
+ return first;
+}
+
+template <typename T, typename Key, size_t kHashBits>
+void GrTHashTable<T, Key, kHashBits>::remove(const Key& key, const T* elem) {
+ int index = hash2Index(key.getHash());
+ if (fHash[index] == elem) {
+ fHash[index] = NULL;
+ }
+
+ // remove from our sorted array
+ index = this->searchArray(key);
+ SkASSERT(index >= 0);
+ // if there are multiple matches searchArray will give us the first match
+ // march forward until we find elem.
+ while (elem != fSorted[index]) {
+ ++index;
+ SkASSERT(index < fSorted.count());
+ }
+ SkASSERT(elem == fSorted[index]);
+ fSorted.remove(index);
+}
+
+template <typename T, typename Key, size_t kHashBits>
+T* GrTHashTable<T, Key, kHashBits>::removeAt(int elemIndex, uint32_t hash) {
+ int hashIndex = hash2Index(hash);
+ if (fHash[hashIndex] == fSorted[elemIndex]) {
+ fHash[hashIndex] = NULL;
+ }
+ // remove from our sorted array
+ T* elem = fSorted[elemIndex];
+ fSorted.remove(elemIndex);
+ return elem;
+}
+
+template <typename T, typename Key, size_t kHashBits>
+void GrTHashTable<T, Key, kHashBits>::removeAll() {
+ fSorted.reset();
+ sk_bzero(fHash, sizeof(fHash));
+}
+
+template <typename T, typename Key, size_t kHashBits>
+void GrTHashTable<T, Key, kHashBits>::deleteAll() {
+ fSorted.deleteAll();
+ sk_bzero(fHash, sizeof(fHash));
+}
+
+template <typename T, typename Key, size_t kHashBits>
+void GrTHashTable<T, Key, kHashBits>::unrefAll() {
+ fSorted.unrefAll();
+ sk_bzero(fHash, sizeof(fHash));
+}
+
+#ifdef SK_DEBUG
+template <typename T, typename Key, size_t kHashBits>
+void GrTHashTable<T, Key, kHashBits>::validate() const {
+ int count = fSorted.count();
+ for (int i = 1; i < count; i++) {
+ SkASSERT(Key::LT(*fSorted[i - 1], *fSorted[i]) ||
+ Key::EQ(*fSorted[i - 1], *fSorted[i]));
+ }
+}
+
+template <typename T, typename Key, size_t kHashBits>
+bool GrTHashTable<T, Key, kHashBits>::contains(T* elem) const {
+ int index = fSorted.find(elem);
+ return index >= 0;
+}
+
+#endif
+
+#endif