SkTDynamicHash.h 9.6 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298
  1. /*
  2. * Copyright 2013 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 SkTDynamicHash_DEFINED
  8. #define SkTDynamicHash_DEFINED
  9. #include "include/core/SkMath.h"
  10. #include "include/core/SkTypes.h"
  11. #include "include/private/SkTemplates.h"
  12. // Traits requires:
  13. // static const Key& GetKey(const T&) { ... }
  14. // static uint32_t Hash(const Key&) { ... }
  15. // We'll look on T for these by default, or you can pass a custom Traits type.
  16. template <typename T,
  17. typename Key,
  18. typename Traits = T,
  19. int kGrowPercent = 75> // Larger -> more memory efficient, but slower.
  20. class SkTDynamicHash {
  21. public:
  22. SkTDynamicHash() : fCount(0), fDeleted(0), fCapacity(0), fArray(nullptr) {
  23. SkASSERT(this->validate());
  24. }
  25. ~SkTDynamicHash() {
  26. sk_free(fArray);
  27. }
  28. class Iter {
  29. public:
  30. explicit Iter(SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
  31. SkASSERT(hash);
  32. ++(*this);
  33. }
  34. bool done() const {
  35. SkASSERT(fCurrentIndex <= fHash->fCapacity);
  36. return fCurrentIndex == fHash->fCapacity;
  37. }
  38. T& operator*() const {
  39. SkASSERT(!this->done());
  40. return *this->current();
  41. }
  42. void operator++() {
  43. do {
  44. fCurrentIndex++;
  45. } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
  46. }
  47. private:
  48. T* current() const { return fHash->fArray[fCurrentIndex]; }
  49. SkTDynamicHash* fHash;
  50. int fCurrentIndex;
  51. };
  52. class ConstIter {
  53. public:
  54. explicit ConstIter(const SkTDynamicHash* hash) : fHash(hash), fCurrentIndex(-1) {
  55. SkASSERT(hash);
  56. ++(*this);
  57. }
  58. bool done() const {
  59. SkASSERT(fCurrentIndex <= fHash->fCapacity);
  60. return fCurrentIndex == fHash->fCapacity;
  61. }
  62. const T& operator*() const {
  63. SkASSERT(!this->done());
  64. return *this->current();
  65. }
  66. void operator++() {
  67. do {
  68. fCurrentIndex++;
  69. } while (!this->done() && (this->current() == Empty() || this->current() == Deleted()));
  70. }
  71. private:
  72. const T* current() const { return fHash->fArray[fCurrentIndex]; }
  73. const SkTDynamicHash* fHash;
  74. int fCurrentIndex;
  75. };
  76. int count() const { return fCount; }
  77. // Return the entry with this key if we have it, otherwise nullptr.
  78. T* find(const Key& key) const {
  79. int index = this->firstIndex(key);
  80. for (int round = 0; round < fCapacity; round++) {
  81. SkASSERT(index >= 0 && index < fCapacity);
  82. T* candidate = fArray[index];
  83. if (Empty() == candidate) {
  84. return nullptr;
  85. }
  86. if (Deleted() != candidate && GetKey(*candidate) == key) {
  87. return candidate;
  88. }
  89. index = this->nextIndex(index, round);
  90. }
  91. SkASSERT(fCapacity == 0);
  92. return nullptr;
  93. }
  94. // Add an entry with this key. We require that no entry with newEntry's key is already present.
  95. void add(T* newEntry) {
  96. SkASSERT(nullptr == this->find(GetKey(*newEntry)));
  97. this->maybeGrow();
  98. this->innerAdd(newEntry);
  99. SkASSERT(this->validate());
  100. }
  101. // Remove the entry with this key. We require that an entry with this key is present.
  102. void remove(const Key& key) {
  103. SkASSERT(this->find(key));
  104. this->innerRemove(key);
  105. SkASSERT(this->validate());
  106. }
  107. void rewind() {
  108. if (fArray) {
  109. sk_bzero(fArray, sizeof(T*)* fCapacity);
  110. }
  111. fCount = 0;
  112. fDeleted = 0;
  113. }
  114. void reset() {
  115. fCount = 0;
  116. fDeleted = 0;
  117. fCapacity = 0;
  118. sk_free(fArray);
  119. fArray = nullptr;
  120. }
  121. protected:
  122. // These methods are used by tests only.
  123. int capacity() const { return fCapacity; }
  124. // How many collisions do we go through before finding where this entry should be inserted?
  125. int countCollisions(const Key& key) const {
  126. int index = this->firstIndex(key);
  127. for (int round = 0; round < fCapacity; round++) {
  128. SkASSERT(index >= 0 && index < fCapacity);
  129. const T* candidate = fArray[index];
  130. if (Empty() == candidate || Deleted() == candidate || GetKey(*candidate) == key) {
  131. return round;
  132. }
  133. index = this->nextIndex(index, round);
  134. }
  135. SkASSERT(fCapacity == 0);
  136. return 0;
  137. }
  138. private:
  139. // We have two special values to indicate an empty or deleted entry.
  140. static T* Empty() { return reinterpret_cast<T*>(0); } // i.e. nullptr
  141. static T* Deleted() { return reinterpret_cast<T*>(1); } // Also an invalid pointer.
  142. bool validate() const {
  143. #define SKTDYNAMICHASH_CHECK(x) SkASSERT(x); if (!(x)) return false
  144. static const int kLarge = 50; // Arbitrary, tweak to suit your patience.
  145. // O(1) checks, always done.
  146. // Is capacity sane?
  147. SKTDYNAMICHASH_CHECK(SkIsPow2(fCapacity));
  148. // O(N) checks, skipped when very large.
  149. if (fCount < kLarge * kLarge) {
  150. // Are fCount and fDeleted correct, and are all elements findable?
  151. int count = 0, deleted = 0;
  152. for (int i = 0; i < fCapacity; i++) {
  153. if (Deleted() == fArray[i]) {
  154. deleted++;
  155. } else if (Empty() != fArray[i]) {
  156. count++;
  157. SKTDYNAMICHASH_CHECK(this->find(GetKey(*fArray[i])));
  158. }
  159. }
  160. SKTDYNAMICHASH_CHECK(count == fCount);
  161. SKTDYNAMICHASH_CHECK(deleted == fDeleted);
  162. }
  163. // O(N^2) checks, skipped when large.
  164. if (fCount < kLarge) {
  165. // Are all entries unique?
  166. for (int i = 0; i < fCapacity; i++) {
  167. if (Empty() == fArray[i] || Deleted() == fArray[i]) {
  168. continue;
  169. }
  170. for (int j = i+1; j < fCapacity; j++) {
  171. if (Empty() == fArray[j] || Deleted() == fArray[j]) {
  172. continue;
  173. }
  174. SKTDYNAMICHASH_CHECK(fArray[i] != fArray[j]);
  175. SKTDYNAMICHASH_CHECK(!(GetKey(*fArray[i]) == GetKey(*fArray[j])));
  176. }
  177. }
  178. }
  179. #undef SKTDYNAMICHASH_CHECK
  180. return true;
  181. }
  182. void innerAdd(T* newEntry) {
  183. const Key& key = GetKey(*newEntry);
  184. int index = this->firstIndex(key);
  185. for (int round = 0; round < fCapacity; round++) {
  186. SkASSERT(index >= 0 && index < fCapacity);
  187. const T* candidate = fArray[index];
  188. if (Empty() == candidate || Deleted() == candidate) {
  189. if (Deleted() == candidate) {
  190. fDeleted--;
  191. }
  192. fCount++;
  193. fArray[index] = newEntry;
  194. return;
  195. }
  196. index = this->nextIndex(index, round);
  197. }
  198. SkASSERT(fCapacity == 0);
  199. }
  200. void innerRemove(const Key& key) {
  201. const int firstIndex = this->firstIndex(key);
  202. int index = firstIndex;
  203. for (int round = 0; round < fCapacity; round++) {
  204. SkASSERT(index >= 0 && index < fCapacity);
  205. const T* candidate = fArray[index];
  206. if (Deleted() != candidate && GetKey(*candidate) == key) {
  207. fDeleted++;
  208. fCount--;
  209. fArray[index] = Deleted();
  210. return;
  211. }
  212. index = this->nextIndex(index, round);
  213. }
  214. SkASSERT(fCapacity == 0);
  215. }
  216. void maybeGrow() {
  217. if (100 * (fCount + fDeleted + 1) > fCapacity * kGrowPercent) {
  218. auto newCapacity = fCapacity > 0 ? fCapacity : 4;
  219. // Only grow the storage when most non-empty entries are
  220. // in active use. Otherwise, just purge the tombstones.
  221. if (fCount > fDeleted) {
  222. newCapacity *= 2;
  223. }
  224. SkASSERT(newCapacity > fCount + 1);
  225. this->resize(newCapacity);
  226. }
  227. }
  228. void resize(int newCapacity) {
  229. SkDEBUGCODE(int oldCount = fCount;)
  230. int oldCapacity = fCapacity;
  231. SkAutoTMalloc<T*> oldArray(fArray);
  232. fCount = fDeleted = 0;
  233. fCapacity = newCapacity;
  234. fArray = (T**)sk_calloc_throw(sizeof(T*) * fCapacity);
  235. for (int i = 0; i < oldCapacity; i++) {
  236. T* entry = oldArray[i];
  237. if (Empty() != entry && Deleted() != entry) {
  238. this->innerAdd(entry);
  239. }
  240. }
  241. SkASSERT(oldCount == fCount);
  242. }
  243. // fCapacity is always a power of 2, so this masks the correct low bits to index into our hash.
  244. uint32_t hashMask() const { return fCapacity - 1; }
  245. int firstIndex(const Key& key) const {
  246. return Hash(key) & this->hashMask();
  247. }
  248. // Given index at round N, what is the index to check at N+1? round should start at 0.
  249. int nextIndex(int index, int round) const {
  250. // This will search a power-of-two array fully without repeating an index.
  251. return (index + round + 1) & this->hashMask();
  252. }
  253. static const Key& GetKey(const T& t) { return Traits::GetKey(t); }
  254. static uint32_t Hash(const Key& key) { return Traits::Hash(key); }
  255. int fCount; // Number of non Empty(), non Deleted() entries in fArray.
  256. int fDeleted; // Number of Deleted() entries in fArray.
  257. int fCapacity; // Number of entries in fArray. Always a power of 2.
  258. T** fArray;
  259. };
  260. #endif