diff options
-rw-r--r-- | gyp/tests.gypi | 1 | ||||
-rw-r--r-- | include/core/SkTemplates.h | 5 | ||||
-rw-r--r-- | src/core/SkTHash.h | 206 | ||||
-rw-r--r-- | tests/HashTest.cpp | 57 |
4 files changed, 269 insertions, 0 deletions
diff --git a/gyp/tests.gypi b/gyp/tests.gypi index e1a9a37609..25e1b7ae8c 100644 --- a/gyp/tests.gypi +++ b/gyp/tests.gypi @@ -117,6 +117,7 @@ '../tests/GrTBSearchTest.cpp', '../tests/GrTRecorderTest.cpp', '../tests/GradientTest.cpp', + '../tests/HashTest.cpp', '../tests/ImageCacheTest.cpp', '../tests/ImageDecodingTest.cpp', '../tests/ImageFilterTest.cpp', diff --git a/include/core/SkTemplates.h b/include/core/SkTemplates.h index c26e4422b5..b18556b452 100644 --- a/include/core/SkTemplates.h +++ b/include/core/SkTemplates.h @@ -254,6 +254,11 @@ public: return fArray[index]; } + void swap(SkAutoTArray& other) { + SkTSwap(fArray, other.fArray); + SkDEBUGCODE(SkTSwap(fCount, other.fCount)); + } + private: T* fArray; SkDEBUGCODE(int fCount;) diff --git a/src/core/SkTHash.h b/src/core/SkTHash.h new file mode 100644 index 0000000000..5e317357ed --- /dev/null +++ b/src/core/SkTHash.h @@ -0,0 +1,206 @@ +#ifndef SkTHash_DEFINED +#define SkTHash_DEFINED + +#include "SkTypes.h" +#include "SkTemplates.h" + +// Before trying to use SkTHashTable, look below to see if SkTHashMap or SkTHashSet works for you. +// They're easier to use, usually perform the same, and have fewer sharp edges. + +// T and K are treated as ordinary copyable C++ types. +// Traits must have: +// - static K GetKey(T) +// - static uint32_t Hash(K) +// If the key is large and stored inside T, you may want to make K a const&. +// Similarly, if T is large you might want it to be a pointer. +template <typename T, typename K, typename Traits = T> +class SkTHashTable : SkNoncopyable { +public: + SkTHashTable() : fCount(0), fCapacity(0) {} + + // How many entries are in the table? + int count() const { return fCount; } + + // !!!!!!!!!!!!!!!!! CAUTION !!!!!!!!!!!!!!!!! + // set(), find() and foreach() all allow mutable access to table entries. + // If you change an entry so that it no longer has the same key, all hell + // will break loose. Do not do that! + // + // Please prefer to use SkTHashMap or SkTHashSet, which do not have this danger. + + // The pointers returned by set() and find() are valid only until the next call to set(). + // The pointers you receive in foreach() are only valid for its duration. + + // Copy val into the hash table, returning a pointer to the copy now in the table. + // If there already is an entry in the table with the same key, we overwrite it. + T* set(T val) { + if (4 * fCount >= 3 * fCapacity) { + this->resize(fCapacity > 0 ? fCapacity * 2 : 4); + } + return this->uncheckedSet(val); + } + + // If there is an entry in the table with this key, return a pointer to it. If not, NULL. + T* find(K key) const { + uint32_t hash = Hash(key); + int index = hash & (fCapacity-1); + for (int n = 0; n < fCapacity; n++) { + Slot& s = fSlots[index]; + if (s.empty()) { + return NULL; + } + if (hash == s.hash && key == Traits::GetKey(s.val)) { + return &s.val; + } + index = this->next(index, n); + } + SkASSERT(fCapacity == 0); + return NULL; + } + + // Call fn on every entry in the table. You may mutate the entries, but be very careful. + template <typename Arg> + void foreach(void(*fn)(T*, Arg), Arg arg) { + for (int i = 0; i < fCapacity; i++) { + Slot& s = fSlots[i]; + if (!s.empty()) { + fn(&s.val, arg); + } + } + } + +private: + T* uncheckedSet(T val) { + K key = Traits::GetKey(val); + uint32_t hash = Hash(key); + int index = hash & (fCapacity-1); + for (int n = 0; n < fCapacity; n++) { + Slot& s = fSlots[index]; + if (s.empty()) { + // New entry. + s.val = val; + s.hash = hash; + fCount++; + return &s.val; + } + if (hash == s.hash && key == Traits::GetKey(s.val)) { + // Overwrite previous entry. + s.val = val; + return &s.val; + } + index = this->next(index, n); + } + SkASSERT(false); + return NULL; + } + + void resize(int capacity) { + int oldCapacity = fCapacity; + SkDEBUGCODE(int oldCount = fCount); + + fCount = 0; + fCapacity = capacity; + SkAutoTArray<Slot> oldSlots(capacity); + oldSlots.swap(fSlots); + + for (int i = 0; i < oldCapacity; i++) { + const Slot& s = oldSlots[i]; + if (!s.empty()) { + this->uncheckedSet(s.val); + } + } + SkASSERT(fCount == oldCount); + } + + int next(int index, int n) const { + // A valid strategy explores all slots in [0, fCapacity) as n walks from 0 to fCapacity-1. + // Both of these strategies are valid: + //return (index + 0 + 1) & (fCapacity-1); // Linear probing. + return (index + n + 1) & (fCapacity-1); // Quadratic probing. + } + + static uint32_t Hash(K key) { + uint32_t hash = Traits::Hash(key); + return hash == 0 ? 1 : hash; // We reserve hash == 0 to mark empty slots. + } + + struct Slot { + Slot() : hash(0) {} + bool empty() const { return hash == 0; } + + T val; + uint32_t hash; + }; + + int fCount, fCapacity; + SkAutoTArray<Slot> fSlots; +}; + +// Maps K->V. A more user-friendly wrapper around SkTHashTable, suitable for most use cases. +// K and V are treated as ordinary copyable C++ types, with no assumed relationship between the two. +template <typename K, typename V, uint32_t(*HashK)(K)> +class SkTHashMap : SkNoncopyable { +public: + SkTHashMap() {} + + // How many key/value pairs are in the table? + int count() const { return fTable.count(); } + + // N.B. The pointers returned by set() and find() are valid only until the next call to set(). + + // Set key to val in the table, replacing any previous value with the same key. + // We copy both key and val, and return a pointer to the value copy now in the table. + V* set(K key, V val) { + Pair in = { key, val }; + Pair* out = fTable.set(in); + return &out->val; + } + + // If there is key/value entry in the table with this key, return a pointer to the value. + // If not, return NULL. + V* find(K key) const { + if (Pair* p = fTable.find(key)) { + return &p->val; + } + return NULL; + } + + // Call fn on every key/value pair in the table. You may mutate the value but not the key. + void foreach(void(*fn)(K, V*)) { fTable.foreach(ForEach, fn); } + +private: + struct Pair { + K key; + V val; + static K GetKey(Pair p) { return p.key; } + static uint32_t Hash(K key) { return HashK(key); } + }; + static void ForEach(Pair* p, void (*fn)(K, V*)) { fn(p->key, &p->val); } + + SkTHashTable<Pair, K> fTable; +}; + +// A set of T. T is treated as an ordiary copyable C++ type. +template <typename T, uint32_t(*HashT)(T)> +class SkTHashSet : SkNoncopyable { +public: + SkTHashSet() {} + + // How many items are in the set? + int count() const { return fTable.count(); } + + // Copy an item into the set. + void add(T item) { fTable.set(item); } + + // Is this item in the set? + bool contains(T item) const { return SkToBool(fTable.find(item)); } + +private: + struct Traits { + static T GetKey(T item) { return item; } + static uint32_t Hash(T item) { return HashT(item); } + }; + SkTHashTable<T, T, Traits> fTable; +}; + +#endif//SkTHash_DEFINED diff --git a/tests/HashTest.cpp b/tests/HashTest.cpp new file mode 100644 index 0000000000..24032a5ec5 --- /dev/null +++ b/tests/HashTest.cpp @@ -0,0 +1,57 @@ +#include "SkChecksum.h" +#include "SkString.h" +#include "SkTHash.h" +#include "Test.h" + +namespace { uint32_t hash_int(int k) { return SkChecksum::Mix(k); } } + +static void set_negative_key(int key, double* d) { *d = -key; } + +DEF_TEST(HashMap, r) { + SkTHashMap<int, double, hash_int> map; + + map.set(3, 4.0); + REPORTER_ASSERT(r, map.count() == 1); + + double* found = map.find(3); + REPORTER_ASSERT(r, found); + REPORTER_ASSERT(r, *found == 4.0); + + map.foreach(set_negative_key); + found = map.find(3); + REPORTER_ASSERT(r, found); + REPORTER_ASSERT(r, *found == -3.0); + + REPORTER_ASSERT(r, !map.find(2)); + + const int N = 20; + + for (int i = 0; i < N; i++) { + map.set(i, 2.0*i); + } + for (int i = 0; i < N; i++) { + double* found = map.find(i);; + REPORTER_ASSERT(r, found); + REPORTER_ASSERT(r, *found == i*2.0); + } + for (int i = N; i < 2*N; i++) { + REPORTER_ASSERT(r, !map.find(i)); + } + + REPORTER_ASSERT(r, map.count() == N); +} + +namespace { uint32_t hash_string(SkString s) { return s.size(); } } + +DEF_TEST(HashSet, r) { + SkTHashSet<SkString, hash_string> set; + + set.add(SkString("Hello")); + set.add(SkString("World")); + + REPORTER_ASSERT(r, set.count() == 2); + + REPORTER_ASSERT(r, set.contains(SkString("Hello"))); + REPORTER_ASSERT(r, set.contains(SkString("World"))); + REPORTER_ASSERT(r, !set.contains(SkString("Goodbye"))); +} |