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 "include/core/SkTypes.h" 12 #include "include/private/SkChecksum.h" 13 #include "include/private/SkTemplates.h" 14 #include <new> 15 #include <utility> 16 17 // Before trying to use SkTHashTable, look below to see if SkTHashMap or SkTHashSet works for you. 18 // They're easier to use, usually perform the same, and have fewer sharp edges. 19 20 // T and K are treated as ordinary copyable C++ types. 21 // Traits must have: 22 // - static K GetKey(T) 23 // - static uint32_t Hash(K) 24 // If the key is large and stored inside T, you may want to make K a const&. 25 // Similarly, if T is large you might want it to be a pointer. 26 template <typename T, typename K, typename Traits = T> 27 class SkTHashTable { 28 public: 29 SkTHashTable() = default; 30 ~SkTHashTable() = default; 31 SkTHashTable(const SkTHashTable & that)32 SkTHashTable(const SkTHashTable& that) { *this = that; } SkTHashTable(SkTHashTable && that)33 SkTHashTable( SkTHashTable&& that) { *this = std::move(that); } 34 35 SkTHashTable& operator=(const SkTHashTable& that) { 36 if (this != &that) { 37 fCount = that.fCount; 38 fCapacity = that.fCapacity; 39 fSlots.reset(that.fCapacity); 40 for (int i = 0; i < fCapacity; i++) { 41 fSlots[i] = that.fSlots[i]; 42 } 43 } 44 return *this; 45 } 46 47 SkTHashTable& operator=(SkTHashTable&& that) { 48 if (this != &that) { 49 fCount = that.fCount; 50 fCapacity = that.fCapacity; 51 fSlots = std::move(that.fSlots); 52 53 that.fCount = that.fCapacity = 0; 54 } 55 return *this; 56 } 57 58 // Clear the table. reset()59 void reset() { *this = SkTHashTable(); } 60 61 // How many entries are in the table? count()62 int count() const { return fCount; } 63 64 // How many slots does the table contain? (Note that unlike an array, hash tables can grow 65 // before reaching 100% capacity.) capacity()66 int capacity() const { return fCapacity; } 67 68 // Approximately how many bytes of memory do we use beyond sizeof(*this)? approxBytesUsed()69 size_t approxBytesUsed() const { return fCapacity * sizeof(Slot); } 70 71 // !!!!!!!!!!!!!!!!! CAUTION !!!!!!!!!!!!!!!!! 72 // set(), find() and foreach() all allow mutable access to table entries. 73 // If you change an entry so that it no longer has the same key, all hell 74 // will break loose. Do not do that! 75 // 76 // Please prefer to use SkTHashMap or SkTHashSet, which do not have this danger. 77 78 // The pointers returned by set() and find() are valid only until the next call to set(). 79 // The pointers you receive in foreach() are only valid for its duration. 80 81 // Copy val into the hash table, returning a pointer to the copy now in the table. 82 // If there already is an entry in the table with the same key, we overwrite it. set(T val)83 T* set(T val) { 84 if (4 * fCount >= 3 * fCapacity) { 85 this->resize(fCapacity > 0 ? fCapacity * 2 : 4); 86 } 87 return this->uncheckedSet(std::move(val)); 88 } 89 90 // If there is an entry in the table with this key, return a pointer to it. If not, null. find(const K & key)91 T* find(const K& key) const { 92 uint32_t hash = Hash(key); 93 int index = hash & (fCapacity-1); 94 for (int n = 0; n < fCapacity; n++) { 95 Slot& s = fSlots[index]; 96 if (s.empty()) { 97 return nullptr; 98 } 99 if (hash == s.hash && key == Traits::GetKey(s.val)) { 100 return &s.val; 101 } 102 index = this->next(index); 103 } 104 SkASSERT(fCapacity == 0); 105 return nullptr; 106 } 107 108 // If there is an entry in the table with this key, return it. If not, null. 109 // This only works for pointer type T, and cannot be used to find an nullptr entry. findOrNull(const K & key)110 T findOrNull(const K& key) const { 111 if (T* p = this->find(key)) { 112 return *p; 113 } 114 return nullptr; 115 } 116 117 // Remove the value with this key from the hash table. remove(const K & key)118 void remove(const K& key) { 119 SkASSERT(this->find(key)); 120 121 uint32_t hash = Hash(key); 122 int index = hash & (fCapacity-1); 123 for (int n = 0; n < fCapacity; n++) { 124 Slot& s = fSlots[index]; 125 SkASSERT(!s.empty()); 126 if (hash == s.hash && key == Traits::GetKey(s.val)) { 127 this->removeSlot(index); 128 if (4 * fCount <= fCapacity && fCapacity > 4) { 129 this->resize(fCapacity / 2); 130 } 131 return; 132 } 133 index = this->next(index); 134 } 135 } 136 137 // Call fn on every entry in the table. You may mutate the entries, but be very careful. 138 template <typename Fn> // f(T*) foreach(Fn && fn)139 void foreach(Fn&& fn) { 140 for (int i = 0; i < fCapacity; i++) { 141 if (!fSlots[i].empty()) { 142 fn(&fSlots[i].val); 143 } 144 } 145 } 146 147 // Call fn on every entry in the table. You may not mutate anything. 148 template <typename Fn> // f(T) or f(const T&) foreach(Fn && fn)149 void foreach(Fn&& fn) const { 150 for (int i = 0; i < fCapacity; i++) { 151 if (!fSlots[i].empty()) { 152 fn(fSlots[i].val); 153 } 154 } 155 } 156 157 // A basic iterator-like class which disallows mutation; sufficient for range-based for loops. 158 // Intended for use by SkTHashMap and SkTHashSet via begin() and end(). 159 // Adding or removing elements may invalidate all iterators. 160 template <typename SlotVal> 161 class Iter { 162 public: 163 using TTable = SkTHashTable<T, K, Traits>; 164 Iter(const TTable * table,int slot)165 Iter(const TTable* table, int slot) : fTable(table), fSlot(slot) {} 166 MakeBegin(const TTable * table)167 static Iter MakeBegin(const TTable* table) { 168 return Iter{table, table->firstPopulatedSlot()}; 169 } 170 MakeEnd(const TTable * table)171 static Iter MakeEnd(const TTable* table) { 172 return Iter{table, table->capacity()}; 173 } 174 175 const SlotVal& operator*() const { 176 return *fTable->slot(fSlot); 177 } 178 179 const SlotVal* operator->() const { 180 return fTable->slot(fSlot); 181 } 182 183 bool operator==(const Iter& that) const { 184 // Iterators from different tables shouldn't be compared against each other. 185 SkASSERT(fTable == that.fTable); 186 return fSlot == that.fSlot; 187 } 188 189 bool operator!=(const Iter& that) const { 190 return !(*this == that); 191 } 192 193 Iter& operator++() { 194 fSlot = fTable->nextPopulatedSlot(fSlot); 195 return *this; 196 } 197 198 Iter operator++(int) { 199 Iter old = *this; 200 this->operator++(); 201 return old; 202 } 203 204 protected: 205 const TTable* fTable; 206 int fSlot; 207 }; 208 209 private: 210 // Finds the first non-empty slot for an iterator. firstPopulatedSlot()211 int firstPopulatedSlot() const { 212 for (int i = 0; i < fCapacity; i++) { 213 if (!fSlots[i].empty()) { 214 return i; 215 } 216 } 217 return fCapacity; 218 } 219 220 // Increments an iterator's slot. nextPopulatedSlot(int currentSlot)221 int nextPopulatedSlot(int currentSlot) const { 222 for (int i = currentSlot + 1; i < fCapacity; i++) { 223 if (!fSlots[i].empty()) { 224 return i; 225 } 226 } 227 return fCapacity; 228 } 229 230 // Reads from an iterator's slot. slot(int i)231 const T* slot(int i) const { 232 SkASSERT(!fSlots[i].empty()); 233 return &fSlots[i].val; 234 } 235 uncheckedSet(T && val)236 T* uncheckedSet(T&& val) { 237 const K& key = Traits::GetKey(val); 238 SkASSERT(key == key); 239 uint32_t hash = Hash(key); 240 int index = hash & (fCapacity-1); 241 for (int n = 0; n < fCapacity; n++) { 242 Slot& s = fSlots[index]; 243 if (s.empty()) { 244 // New entry. 245 s.val = std::move(val); 246 s.hash = hash; 247 fCount++; 248 return &s.val; 249 } 250 if (hash == s.hash && key == Traits::GetKey(s.val)) { 251 // Overwrite previous entry. 252 // Note: this triggers extra copies when adding the same value repeatedly. 253 s.val = std::move(val); 254 return &s.val; 255 } 256 257 index = this->next(index); 258 } 259 SkASSERT(false); 260 return nullptr; 261 } 262 resize(int capacity)263 void resize(int capacity) { 264 int oldCapacity = fCapacity; 265 SkDEBUGCODE(int oldCount = fCount); 266 267 fCount = 0; 268 fCapacity = capacity; 269 SkAutoTArray<Slot> oldSlots = std::move(fSlots); 270 fSlots = SkAutoTArray<Slot>(capacity); 271 272 for (int i = 0; i < oldCapacity; i++) { 273 Slot& s = oldSlots[i]; 274 if (!s.empty()) { 275 this->uncheckedSet(std::move(s.val)); 276 } 277 } 278 SkASSERT(fCount == oldCount); 279 } 280 removeSlot(int index)281 void removeSlot(int index) { 282 fCount--; 283 284 // Rearrange elements to restore the invariants for linear probing. 285 for (;;) { 286 Slot& emptySlot = fSlots[index]; 287 int emptyIndex = index; 288 int originalIndex; 289 // Look for an element that can be moved into the empty slot. 290 // If the empty slot is in between where an element landed, and its native slot, then 291 // move it to the empty slot. Don't move it if its native slot is in between where 292 // the element landed and the empty slot. 293 // [native] <= [empty] < [candidate] == GOOD, can move candidate to empty slot 294 // [empty] < [native] < [candidate] == BAD, need to leave candidate where it is 295 do { 296 index = this->next(index); 297 Slot& s = fSlots[index]; 298 if (s.empty()) { 299 // We're done shuffling elements around. Clear the last empty slot. 300 emptySlot = Slot(); 301 return; 302 } 303 originalIndex = s.hash & (fCapacity - 1); 304 } while ((index <= originalIndex && originalIndex < emptyIndex) 305 || (originalIndex < emptyIndex && emptyIndex < index) 306 || (emptyIndex < index && index <= originalIndex)); 307 // Move the element to the empty slot. 308 Slot& moveFrom = fSlots[index]; 309 emptySlot = std::move(moveFrom); 310 } 311 } 312 next(int index)313 int next(int index) const { 314 index--; 315 if (index < 0) { index += fCapacity; } 316 return index; 317 } 318 Hash(const K & key)319 static uint32_t Hash(const K& key) { 320 uint32_t hash = Traits::Hash(key) & 0xffffffff; 321 return hash ? hash : 1; // We reserve hash 0 to mark empty. 322 } 323 324 struct Slot { 325 Slot() = default; SlotSlot326 Slot(T&& v, uint32_t h) : val(std::move(v)), hash(h) {} 327 emptySlot328 bool empty() const { return this->hash == 0; } 329 330 T val{}; 331 uint32_t hash = 0; 332 }; 333 334 int fCount = 0, 335 fCapacity = 0; 336 SkAutoTArray<Slot> fSlots; 337 }; 338 339 // Maps K->V. A more user-friendly wrapper around SkTHashTable, suitable for most use cases. 340 // K and V are treated as ordinary copyable C++ types, with no assumed relationship between the two. 341 template <typename K, typename V, typename HashK = SkGoodHash> 342 class SkTHashMap { 343 public: 344 // Clear the map. reset()345 void reset() { fTable.reset(); } 346 347 // How many key/value pairs are in the table? count()348 int count() const { return fTable.count(); } 349 350 // Approximately how many bytes of memory do we use beyond sizeof(*this)? approxBytesUsed()351 size_t approxBytesUsed() const { return fTable.approxBytesUsed(); } 352 353 // N.B. The pointers returned by set() and find() are valid only until the next call to set(). 354 355 // Set key to val in the table, replacing any previous value with the same key. 356 // We copy both key and val, and return a pointer to the value copy now in the table. set(K key,V val)357 V* set(K key, V val) { 358 Pair* out = fTable.set({std::move(key), std::move(val)}); 359 return &out->second; 360 } 361 362 // If there is key/value entry in the table with this key, return a pointer to the value. 363 // If not, return null. find(const K & key)364 V* find(const K& key) const { 365 if (Pair* p = fTable.find(key)) { 366 return &p->second; 367 } 368 return nullptr; 369 } 370 371 V& operator[](const K& key) { 372 if (V* val = this->find(key)) { 373 return *val; 374 } 375 return *this->set(key, V{}); 376 } 377 378 // Remove the key/value entry in the table with this key. remove(const K & key)379 void remove(const K& key) { 380 SkASSERT(this->find(key)); 381 fTable.remove(key); 382 } 383 384 // Call fn on every key/value pair in the table. You may mutate the value but not the key. 385 template <typename Fn> // f(K, V*) or f(const K&, V*) foreach(Fn && fn)386 void foreach(Fn&& fn) { 387 fTable.foreach([&fn](Pair* p){ fn(p->first, &p->second); }); 388 } 389 390 // Call fn on every key/value pair in the table. You may not mutate anything. 391 template <typename Fn> // f(K, V), f(const K&, V), f(K, const V&) or f(const K&, const V&). foreach(Fn && fn)392 void foreach(Fn&& fn) const { 393 fTable.foreach([&fn](const Pair& p){ fn(p.first, p.second); }); 394 } 395 396 // Dereferencing an iterator gives back a key-value pair, suitable for structured binding. 397 struct Pair : public std::pair<K, V> { 398 using std::pair<K, V>::pair; GetKeyPair399 static const K& GetKey(const Pair& p) { return p.first; } HashPair400 static auto Hash(const K& key) { return HashK()(key); } 401 }; 402 403 using Iter = typename SkTHashTable<Pair, K>::template Iter<std::pair<K, V>>; 404 begin()405 Iter begin() const { 406 return Iter::MakeBegin(&fTable); 407 } 408 end()409 Iter end() const { 410 return Iter::MakeEnd(&fTable); 411 } 412 413 private: 414 SkTHashTable<Pair, K> fTable; 415 }; 416 417 // A set of T. T is treated as an ordinary copyable C++ type. 418 template <typename T, typename HashT = SkGoodHash> 419 class SkTHashSet { 420 public: 421 // Clear the set. reset()422 void reset() { fTable.reset(); } 423 424 // How many items are in the set? count()425 int count() const { return fTable.count(); } 426 427 // Is empty? empty()428 bool empty() const { return fTable.count() == 0; } 429 430 // Approximately how many bytes of memory do we use beyond sizeof(*this)? approxBytesUsed()431 size_t approxBytesUsed() const { return fTable.approxBytesUsed(); } 432 433 // Copy an item into the set. add(T item)434 void add(T item) { fTable.set(std::move(item)); } 435 436 // Is this item in the set? contains(const T & item)437 bool contains(const T& item) const { return SkToBool(this->find(item)); } 438 439 // If an item equal to this is in the set, return a pointer to it, otherwise null. 440 // This pointer remains valid until the next call to add(). find(const T & item)441 const T* find(const T& item) const { return fTable.find(item); } 442 443 // Remove the item in the set equal to this. remove(const T & item)444 void remove(const T& item) { 445 SkASSERT(this->contains(item)); 446 fTable.remove(item); 447 } 448 449 // Call fn on every item in the set. You may not mutate anything. 450 template <typename Fn> // f(T), f(const T&) foreach(Fn && fn)451 void foreach (Fn&& fn) const { 452 fTable.foreach(fn); 453 } 454 455 private: 456 struct Traits { GetKeyTraits457 static const T& GetKey(const T& item) { return item; } HashTraits458 static auto Hash(const T& item) { return HashT()(item); } 459 }; 460 461 public: 462 using Iter = typename SkTHashTable<T, T, Traits>::template Iter<T>; 463 begin()464 Iter begin() const { 465 return Iter::MakeBegin(&fTable); 466 } 467 end()468 Iter end() const { 469 return Iter::MakeEnd(&fTable); 470 } 471 472 private: 473 SkTHashTable<T, T, Traits> fTable; 474 }; 475 476 #endif//SkTHash_DEFINED 477