SkTHash.h 12 KB

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