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