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 new (this) SkTHashTable; 33 } 34 35 // How many entries are in the table? 36 int count() const { return fCount; } 37 38 // Approximately how many bytes of memory do we use beyond sizeof(*this)? 39 size_t approxBytesUsed() const { return fCapacity * sizeof(Slot); } 40 41 // !!!!!!!!!!!!!!!!! CAUTION !!!!!!!!!!!!!!!!! 42 // set(), find() and foreach() all allow mutable access to table entries. 43 // If you change an entry so that it no longer has the same key, all hell 44 // will break loose. Do not do that! 45 // 46 // Please prefer to use SkTHashMap or SkTHashSet, which do not have this danger. 47 48 // The pointers returned by set() and find() are valid only until the next call to set(). 49 // The pointers you receive in foreach() are only valid for its duration. 50 51 // Copy val into the hash table, returning a pointer to the copy now in the table. 52 // If there already is an entry in the table with the same key, we overwrite it. 53 T* set(T val) { 54 if (4 * fCount >= 3 * fCapacity) { 55 this->resize(fCapacity > 0 ? fCapacity * 2 : 4); 56 } 57 return this->uncheckedSet(std::move(val)); 58 } 59 60 // If there is an entry in the table with this key, return a pointer to it. If not, null. 61 T* find(const K& key) const { 62 uint32_t hash = Hash(key); 63 int index = hash & (fCapacity-1); 64 for (int n = 0; n < fCapacity; n++) { 65 Slot& s = fSlots[index]; 66 if (s.empty()) { 67 return nullptr; 68 } 69 if (hash == s.hash && key == Traits::GetKey(s.val)) { 70 return &s.val; 71 } 72 index = this->next(index); 73 } 74 SkASSERT(fCapacity == 0); 75 return nullptr; 76 } 77 78 // Remove the value with this key from the hash table. 79 void remove(const K& key) { 80 SkASSERT(this->find(key)); 81 82 uint32_t hash = Hash(key); 83 int index = hash & (fCapacity-1); 84 for (int n = 0; n < fCapacity; n++) { 85 Slot& s = fSlots[index]; 86 SkASSERT(!s.empty()); 87 if (hash == s.hash && key == Traits::GetKey(s.val)) { 88 fCount--; 89 break; 90 } 91 index = this->next(index); 92 } 93 94 // Rearrange elements to restore the invariants for linear probing. 95 for (;;) { 96 Slot& emptySlot = fSlots[index]; 97 int emptyIndex = index; 98 int originalIndex; 99 // Look for an element that can be moved into the empty slot. 100 // If the empty slot is in between where an element landed, and its native slot, then 101 // move it to the empty slot. Don't move it if its native slot is in between where 102 // the element landed and the empty slot. 103 // [native] <= [empty] < [candidate] == GOOD, can move candidate to empty slot 104 // [empty] < [native] < [candidate] == BAD, need to leave candidate where it is 105 do { 106 index = this->next(index); 107 Slot& s = fSlots[index]; 108 if (s.empty()) { 109 // We're done shuffling elements around. Clear the last empty slot. 110 emptySlot = Slot(); 111 return; 112 } 113 originalIndex = s.hash & (fCapacity - 1); 114 } while ((index <= originalIndex && originalIndex < emptyIndex) 115 || (originalIndex < emptyIndex && emptyIndex < index) 116 || (emptyIndex < index && index <= originalIndex)); 117 // Move the element to the empty slot. 118 Slot& moveFrom = fSlots[index]; 119 emptySlot = std::move(moveFrom); 120 } 121 } 122 123 // Call fn on every entry in the table. You may mutate the entries, but be very careful. 124 template <typename Fn> // f(T*) 125 void foreach(Fn&& fn) { 126 for (int i = 0; i < fCapacity; i++) { 127 if (!fSlots[i].empty()) { 128 fn(&fSlots[i].val); 129 } 130 } 131 } 132 133 // Call fn on every entry in the table. You may not mutate anything. 134 template <typename Fn> // f(T) or f(const T&) 135 void foreach(Fn&& fn) const { 136 for (int i = 0; i < fCapacity; i++) { 137 if (!fSlots[i].empty()) { 138 fn(fSlots[i].val); 139 } 140 } 141 } 142 143private: 144 T* uncheckedSet(T&& val) { 145 const K& key = Traits::GetKey(val); 146 uint32_t hash = Hash(key); 147 int index = hash & (fCapacity-1); 148 for (int n = 0; n < fCapacity; n++) { 149 Slot& s = fSlots[index]; 150 if (s.empty()) { 151 // New entry. 152 s.val = std::move(val); 153 s.hash = hash; 154 fCount++; 155 return &s.val; 156 } 157 if (hash == s.hash && key == Traits::GetKey(s.val)) { 158 // Overwrite previous entry. 159 // Note: this triggers extra copies when adding the same value repeatedly. 160 s.val = std::move(val); 161 return &s.val; 162 } 163 164 index = this->next(index); 165 } 166 SkASSERT(false); 167 return nullptr; 168 } 169 170 void resize(int capacity) { 171 int oldCapacity = fCapacity; 172 SkDEBUGCODE(int oldCount = fCount); 173 174 fCount = 0; 175 fCapacity = capacity; 176 SkAutoTArray<Slot> oldSlots(capacity); 177 oldSlots.swap(fSlots); 178 179 for (int i = 0; i < oldCapacity; i++) { 180 Slot& s = oldSlots[i]; 181 if (!s.empty()) { 182 this->uncheckedSet(std::move(s.val)); 183 } 184 } 185 SkASSERT(fCount == oldCount); 186 } 187 188 int next(int index) const { 189 index--; 190 if (index < 0) { index += fCapacity; } 191 return index; 192 } 193 194 static uint32_t Hash(const K& key) { 195 uint32_t hash = Traits::Hash(key); 196 return hash ? hash : 1; // We reserve hash 0 to mark empty. 197 } 198 199 struct Slot { 200 Slot() : hash(0) {} 201 Slot(T&& v, uint32_t h) : val(std::move(v)), hash(h) {} 202 Slot(Slot&& o) { *this = std::move(o); } 203 Slot& operator=(Slot&& o) { 204 val = std::move(o.val); 205 hash = o.hash; 206 return *this; 207 } 208 209 bool empty() const { return this->hash == 0; } 210 211 T val; 212 uint32_t hash; 213 }; 214 215 int fCount, fCapacity; 216 SkAutoTArray<Slot> fSlots; 217}; 218 219// Maps K->V. A more user-friendly wrapper around SkTHashTable, suitable for most use cases. 220// K and V are treated as ordinary copyable C++ types, with no assumed relationship between the two. 221template <typename K, typename V, typename HashK = SkGoodHash> 222class SkTHashMap : SkNoncopyable { 223public: 224 SkTHashMap() {} 225 226 // Clear the map. 227 void reset() { fTable.reset(); } 228 229 // How many key/value pairs are in the table? 230 int count() const { return fTable.count(); } 231 232 // Approximately how many bytes of memory do we use beyond sizeof(*this)? 233 size_t approxBytesUsed() const { return fTable.approxBytesUsed(); } 234 235 // N.B. The pointers returned by set() and find() are valid only until the next call to set(). 236 237 // Set key to val in the table, replacing any previous value with the same key. 238 // We copy both key and val, and return a pointer to the value copy now in the table. 239 V* set(K key, V val) { 240 Pair* out = fTable.set({std::move(key), std::move(val)}); 241 return &out->val; 242 } 243 244 // If there is key/value entry in the table with this key, return a pointer to the value. 245 // If not, return null. 246 V* find(const K& key) const { 247 if (Pair* p = fTable.find(key)) { 248 return &p->val; 249 } 250 return nullptr; 251 } 252 253 // Remove the key/value entry in the table with this key. 254 void remove(const K& key) { 255 SkASSERT(this->find(key)); 256 fTable.remove(key); 257 } 258 259 // Call fn on every key/value pair in the table. You may mutate the value but not the key. 260 template <typename Fn> // f(K, V*) or f(const K&, V*) 261 void foreach(Fn&& fn) { 262 fTable.foreach([&fn](Pair* p){ fn(p->key, &p->val); }); 263 } 264 265 // Call fn on every key/value pair in the table. You may not mutate anything. 266 template <typename Fn> // f(K, V), f(const K&, V), f(K, const V&) or f(const K&, const V&). 267 void foreach(Fn&& fn) const { 268 fTable.foreach([&fn](const Pair& p){ fn(p.key, p.val); }); 269 } 270 271private: 272 struct Pair { 273 K key; 274 V val; 275 static const K& GetKey(const Pair& p) { return p.key; } 276 static uint32_t Hash(const K& key) { return HashK()(key); } 277 }; 278 279 SkTHashTable<Pair, K> fTable; 280}; 281 282// A set of T. T is treated as an ordiary copyable C++ type. 283template <typename T, typename HashT = SkGoodHash> 284class SkTHashSet : SkNoncopyable { 285public: 286 SkTHashSet() {} 287 288 // Clear the set. 289 void reset() { fTable.reset(); } 290 291 // How many items are in the set? 292 int count() const { return fTable.count(); } 293 294 // Approximately how many bytes of memory do we use beyond sizeof(*this)? 295 size_t approxBytesUsed() const { return fTable.approxBytesUsed(); } 296 297 // Copy an item into the set. 298 void add(T item) { fTable.set(std::move(item)); } 299 300 // Is this item in the set? 301 bool contains(const T& item) const { return SkToBool(this->find(item)); } 302 303 // If an item equal to this is in the set, return a pointer to it, otherwise null. 304 // This pointer remains valid until the next call to add(). 305 const T* find(const T& item) const { return fTable.find(item); } 306 307 // Remove the item in the set equal to this. 308 void remove(const T& item) { 309 SkASSERT(this->contains(item)); 310 fTable.remove(item); 311 } 312 313 // Call fn on every item in the set. You may not mutate anything. 314 template <typename Fn> // f(T), f(const T&) 315 void foreach (Fn&& fn) const { 316 fTable.foreach(fn); 317 } 318 319private: 320 struct Traits { 321 static const T& GetKey(const T& item) { return item; } 322 static uint32_t Hash(const T& item) { return HashT()(item); } 323 }; 324 SkTHashTable<T, T, Traits> fTable; 325}; 326 327#endif//SkTHash_DEFINED 328