SkTHash.h revision fb8307c6b78bfbaa5e969a9df0c007c232d6251d
1/* 2 * Copyright 2015 Google Inc. 3 * 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8#ifndef SkTHash_DEFINED 9#define SkTHash_DEFINED 10 11#include "SkChecksum.h" 12#include "SkTypes.h" 13#include "SkTemplates.h" 14 15// Before trying to use SkTHashTable, look below to see if SkTHashMap or SkTHashSet works for you. 16// They're easier to use, usually perform the same, and have fewer sharp edges. 17 18// T and K are treated as ordinary copyable C++ types. 19// Traits must have: 20// - static K GetKey(T) 21// - static uint32_t Hash(K) 22// If the key is large and stored inside T, you may want to make K a const&. 23// Similarly, if T is large you might want it to be a pointer. 24template <typename T, typename K, typename Traits = T> 25class SkTHashTable : SkNoncopyable { 26public: 27 SkTHashTable() : fCount(0), fCapacity(0) {} 28 29 // Clear the table. 30 void reset() { 31 this->~SkTHashTable(); 32 SkNEW_PLACEMENT(this, SkTHashTable); 33 } 34 35 // How many entries are in the table? 36 int count() const { return fCount; } 37 38 // !!!!!!!!!!!!!!!!! CAUTION !!!!!!!!!!!!!!!!! 39 // set(), find() and foreach() all allow mutable access to table entries. 40 // If you change an entry so that it no longer has the same key, all hell 41 // will break loose. Do not do that! 42 // 43 // Please prefer to use SkTHashMap or SkTHashSet, which do not have this danger. 44 45 // The pointers returned by set() and find() are valid only until the next call to set(). 46 // The pointers you receive in foreach() are only valid for its duration. 47 48 // Copy val into the hash table, returning a pointer to the copy now in the table. 49 // If there already is an entry in the table with the same key, we overwrite it. 50 T* set(const T& val) { 51 if (4 * fCount >= 3 * fCapacity) { 52 this->resize(fCapacity > 0 ? fCapacity * 2 : 4); 53 } 54 return this->uncheckedSet(val); 55 } 56 57 // If there is an entry in the table with this key, return a pointer to it. If not, NULL. 58 T* find(const K& key) const { 59 uint32_t hash = Hash(key); 60 int index = hash & (fCapacity-1); 61 for (int n = 0; n < fCapacity; n++) { 62 Slot& s = fSlots[index]; 63 if (s.empty()) { 64 return NULL; 65 } 66 if (hash == s.hash && key == Traits::GetKey(s.val)) { 67 return &s.val; 68 } 69 index = this->next(index, n); 70 } 71 SkASSERT(fCapacity == 0); 72 return NULL; 73 } 74 75 // Call fn on every entry in the table. You may mutate the entries, but be very careful. 76 template <typename Fn> // f(T*) 77 void foreach(Fn&& fn) { 78 for (int i = 0; i < fCapacity; i++) { 79 if (!fSlots[i].empty()) { 80 fn(&fSlots[i].val); 81 } 82 } 83 } 84 85 // Call fn on every entry in the table. You may not mutate anything. 86 template <typename Fn> // f(T) or f(const T&) 87 void foreach(Fn&& fn) const { 88 for (int i = 0; i < fCapacity; i++) { 89 if (!fSlots[i].empty()) { 90 fn(fSlots[i].val); 91 } 92 } 93 } 94 95private: 96 T* uncheckedSet(const T& val) { 97 const K& key = Traits::GetKey(val); 98 uint32_t hash = Hash(key); 99 int index = hash & (fCapacity-1); 100 for (int n = 0; n < fCapacity; n++) { 101 Slot& s = fSlots[index]; 102 if (s.empty()) { 103 // New entry. 104 s.val = val; 105 s.hash = hash; 106 fCount++; 107 return &s.val; 108 } 109 if (hash == s.hash && key == Traits::GetKey(s.val)) { 110 // Overwrite previous entry. 111 // Note: this triggers extra copies when adding the same value repeatedly. 112 s.val = val; 113 return &s.val; 114 } 115 index = this->next(index, n); 116 } 117 SkASSERT(false); 118 return NULL; 119 } 120 121 void resize(int capacity) { 122 int oldCapacity = fCapacity; 123 SkDEBUGCODE(int oldCount = fCount); 124 125 fCount = 0; 126 fCapacity = capacity; 127 SkAutoTArray<Slot> oldSlots(capacity); 128 oldSlots.swap(fSlots); 129 130 for (int i = 0; i < oldCapacity; i++) { 131 const Slot& s = oldSlots[i]; 132 if (!s.empty()) { 133 this->uncheckedSet(s.val); 134 } 135 } 136 SkASSERT(fCount == oldCount); 137 } 138 139 int next(int index, int n) const { 140 // A valid strategy explores all slots in [0, fCapacity) as n walks from 0 to fCapacity-1. 141 // Both of these strategies are valid: 142 //return (index + 0 + 1) & (fCapacity-1); // Linear probing. 143 return (index + n + 1) & (fCapacity-1); // Quadratic probing. 144 } 145 146 static uint32_t Hash(const K& key) { 147 uint32_t hash = Traits::Hash(key); 148 return hash == 0 ? 1 : hash; // We reserve hash == 0 to mark empty slots. 149 } 150 151 struct Slot { 152 Slot() : hash(0) {} 153 bool empty() const { return hash == 0; } 154 155 T val; 156 uint32_t hash; 157 }; 158 159 int fCount, fCapacity; 160 SkAutoTArray<Slot> fSlots; 161}; 162 163// Maps K->V. A more user-friendly wrapper around SkTHashTable, suitable for most use cases. 164// K and V are treated as ordinary copyable C++ types, with no assumed relationship between the two. 165template <typename K, typename V, uint32_t(*HashK)(const K&) = &SkGoodHash> 166class SkTHashMap : SkNoncopyable { 167public: 168 SkTHashMap() {} 169 170 // Clear the map. 171 void reset() { fTable.reset(); } 172 173 // How many key/value pairs are in the table? 174 int count() const { return fTable.count(); } 175 176 // N.B. The pointers returned by set() and find() are valid only until the next call to set(). 177 178 // Set key to val in the table, replacing any previous value with the same key. 179 // We copy both key and val, and return a pointer to the value copy now in the table. 180 V* set(const K& key, const V& val) { 181 Pair in = { key, val }; 182 Pair* out = fTable.set(in); 183 return &out->val; 184 } 185 186 // If there is key/value entry in the table with this key, return a pointer to the value. 187 // If not, return NULL. 188 V* find(const K& key) const { 189 if (Pair* p = fTable.find(key)) { 190 return &p->val; 191 } 192 return NULL; 193 } 194 195 // Call fn on every key/value pair in the table. You may mutate the value but not the key. 196 template <typename Fn> // f(K, V*) or f(const K&, V*) 197 void foreach(Fn&& fn) { 198 fTable.foreach([&fn](Pair* p){ fn(p->key, &p->val); }); 199 } 200 201 // Call fn on every key/value pair in the table. You may not mutate anything. 202 template <typename Fn> // f(K, V), f(const K&, V), f(K, const V&) or f(const K&, const V&). 203 void foreach(Fn&& fn) const { 204 fTable.foreach([&fn](const Pair& p){ fn(p.key, p.val); }); 205 } 206 207private: 208 struct Pair { 209 K key; 210 V val; 211 static const K& GetKey(const Pair& p) { return p.key; } 212 static uint32_t Hash(const K& key) { return HashK(key); } 213 }; 214 215 SkTHashTable<Pair, K> fTable; 216}; 217 218// A set of T. T is treated as an ordiary copyable C++ type. 219template <typename T, uint32_t(*HashT)(const T&) = &SkGoodHash> 220class SkTHashSet : SkNoncopyable { 221public: 222 SkTHashSet() {} 223 224 // Clear the set. 225 void reset() { fTable.reset(); } 226 227 // How many items are in the set? 228 int count() const { return fTable.count(); } 229 230 // Copy an item into the set. 231 void add(const T& item) { fTable.set(item); } 232 233 // Is this item in the set? 234 bool contains(const T& item) const { return SkToBool(this->find(item)); } 235 236 // If an item equal to this is in the set, return a pointer to it, otherwise null. 237 // This pointer remains valid until the next call to add(). 238 const T* find(const T& item) const { return fTable.find(item); } 239 240private: 241 struct Traits { 242 static const T& GetKey(const T& item) { return item; } 243 static uint32_t Hash(const T& item) { return HashT(item); } 244 }; 245 SkTHashTable<T, T, Traits> fTable; 246}; 247 248#endif//SkTHash_DEFINED 249