DynamicHashTest.cpp 5.9 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263
  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. #include "include/core/SkTypes.h"
  8. #include "src/core/SkTDynamicHash.h"
  9. #include "tests/Test.h"
  10. #include <cstring>
  11. namespace {
  12. struct Entry {
  13. int key;
  14. double value;
  15. static const int& GetKey(const Entry& entry) { return entry.key; }
  16. static uint32_t Hash(const int& key) { return key; }
  17. };
  18. class Hash : public SkTDynamicHash<Entry, int> {
  19. public:
  20. Hash() : INHERITED() {}
  21. // Promote protected methods to public for this test.
  22. int capacity() const { return this->INHERITED::capacity(); }
  23. int countCollisions(const int& key) const { return this->INHERITED::countCollisions(key); }
  24. private:
  25. typedef SkTDynamicHash<Entry, int> INHERITED;
  26. };
  27. } // namespace
  28. #define ASSERT(x) REPORTER_ASSERT(reporter, x)
  29. DEF_TEST(DynamicHash_growth, reporter) {
  30. Entry a = { 1, 2.0 };
  31. Entry b = { 2, 3.0 };
  32. Entry c = { 3, 4.0 };
  33. Entry d = { 4, 5.0 };
  34. Entry e = { 5, 6.0 };
  35. Hash hash;
  36. ASSERT(hash.capacity() == 0);
  37. hash.add(&a);
  38. ASSERT(hash.capacity() == 4);
  39. hash.add(&b);
  40. ASSERT(hash.capacity() == 4);
  41. hash.add(&c);
  42. ASSERT(hash.capacity() == 4);
  43. hash.add(&d);
  44. ASSERT(hash.capacity() == 8);
  45. hash.add(&e);
  46. ASSERT(hash.capacity() == 8);
  47. ASSERT(hash.count() == 5);
  48. }
  49. DEF_TEST(DynamicHash_growth_bounded, reporter) {
  50. Entry a = { 1, 2.0 };
  51. Entry b = { 2, 3.0 };
  52. Entry c = { 3, 4.0 };
  53. Entry d = { 4, 5.0 };
  54. Entry e = { 5, 6.0 };
  55. Hash hash;
  56. ASSERT(hash.capacity() == 0);
  57. hash.add(&a);
  58. ASSERT(hash.capacity() == 4);
  59. hash.remove(a.key);
  60. hash.add(&b);
  61. ASSERT(hash.capacity() == 4);
  62. hash.remove(b.key);
  63. hash.add(&c);
  64. ASSERT(hash.capacity() == 4);
  65. hash.remove(c.key);
  66. hash.add(&d);
  67. ASSERT(hash.capacity() == 4);
  68. hash.remove(d.key);
  69. hash.add(&e);
  70. ASSERT(hash.capacity() == 4);
  71. ASSERT(hash.count() == 1);
  72. }
  73. DEF_TEST(DynamicHash_add, reporter) {
  74. Hash hash;
  75. Entry a = { 1, 2.0 };
  76. Entry b = { 2, 3.0 };
  77. ASSERT(hash.count() == 0);
  78. hash.add(&a);
  79. ASSERT(hash.count() == 1);
  80. hash.add(&b);
  81. ASSERT(hash.count() == 2);
  82. }
  83. DEF_TEST(DynamicHash_lookup, reporter) {
  84. Hash hash;
  85. // These collide.
  86. Entry a = { 1, 2.0 };
  87. Entry b = { 5, 3.0 };
  88. // Before we insert anything, nothing can collide.
  89. ASSERT(hash.countCollisions(1) == 0);
  90. ASSERT(hash.countCollisions(5) == 0);
  91. ASSERT(hash.countCollisions(9) == 0);
  92. // First is easy.
  93. hash.add(&a);
  94. ASSERT(hash.countCollisions(1) == 0);
  95. ASSERT(hash.countCollisions(5) == 1);
  96. ASSERT(hash.countCollisions(9) == 1);
  97. // Second is one step away.
  98. hash.add(&b);
  99. ASSERT(hash.countCollisions(1) == 0);
  100. ASSERT(hash.countCollisions(5) == 1);
  101. ASSERT(hash.countCollisions(9) == 2);
  102. // We can find our data right?
  103. ASSERT(hash.find(1) != nullptr);
  104. ASSERT(hash.find(1)->value == 2.0);
  105. ASSERT(hash.find(5) != nullptr);
  106. ASSERT(hash.find(5)->value == 3.0);
  107. // These aren't in the hash.
  108. ASSERT(hash.find(2) == nullptr);
  109. ASSERT(hash.find(9) == nullptr);
  110. }
  111. DEF_TEST(DynamicHash_remove, reporter) {
  112. Hash hash;
  113. // These collide.
  114. Entry a = { 1, 2.0 };
  115. Entry b = { 5, 3.0 };
  116. Entry c = { 9, 4.0 };
  117. hash.add(&a);
  118. hash.add(&b);
  119. hash.remove(1);
  120. // a should be marked deleted, and b should still be findable.
  121. ASSERT(hash.find(1) == nullptr);
  122. ASSERT(hash.find(5) != nullptr);
  123. ASSERT(hash.find(5)->value == 3.0);
  124. // This will go in the same slot as 'a' did before.
  125. ASSERT(hash.countCollisions(9) == 0);
  126. hash.add(&c);
  127. ASSERT(hash.find(9) != nullptr);
  128. ASSERT(hash.find(9)->value == 4.0);
  129. ASSERT(hash.find(5) != nullptr);
  130. ASSERT(hash.find(5)->value == 3.0);
  131. }
  132. template<typename T> static void TestIter(skiatest::Reporter* reporter) {
  133. Hash hash;
  134. int count = 0;
  135. // this should fall out of loop immediately
  136. for (T iter(&hash); !iter.done(); ++iter) {
  137. ++count;
  138. }
  139. ASSERT(0 == count);
  140. // These collide.
  141. Entry a = { 1, 2.0 };
  142. Entry b = { 5, 3.0 };
  143. Entry c = { 9, 4.0 };
  144. hash.add(&a);
  145. hash.add(&b);
  146. hash.add(&c);
  147. // should see all 3 unique keys when iterating over hash
  148. count = 0;
  149. int keys[3] = {0, 0, 0};
  150. for (T iter(&hash); !iter.done(); ++iter) {
  151. int key = (*iter).key;
  152. keys[count] = key;
  153. ASSERT(hash.find(key) != nullptr);
  154. ++count;
  155. }
  156. ASSERT(3 == count);
  157. ASSERT(keys[0] != keys[1]);
  158. ASSERT(keys[0] != keys[2]);
  159. ASSERT(keys[1] != keys[2]);
  160. // should see 2 unique keys when iterating over hash that aren't 1
  161. hash.remove(1);
  162. count = 0;
  163. memset(keys, 0, sizeof(keys));
  164. for (T iter(&hash); !iter.done(); ++iter) {
  165. int key = (*iter).key;
  166. keys[count] = key;
  167. ASSERT(key != 1);
  168. ASSERT(hash.find(key) != nullptr);
  169. ++count;
  170. }
  171. ASSERT(2 == count);
  172. ASSERT(keys[0] != keys[1]);
  173. }
  174. DEF_TEST(DynamicHash_iterator, reporter) {
  175. TestIter<Hash::Iter>(reporter);
  176. TestIter<Hash::ConstIter>(reporter);
  177. }
  178. static void TestResetOrRewind(skiatest::Reporter* reporter, bool testReset) {
  179. Hash hash;
  180. Entry a = { 1, 2.0 };
  181. Entry b = { 2, 3.0 };
  182. ASSERT(hash.capacity() == 0);
  183. hash.add(&a);
  184. hash.add(&b);
  185. ASSERT(hash.count() == 2);
  186. ASSERT(hash.capacity() == 4);
  187. if (testReset) {
  188. hash.reset();
  189. ASSERT(hash.capacity() == 0);
  190. } else {
  191. hash.rewind();
  192. ASSERT(hash.capacity() == 4);
  193. }
  194. ASSERT(hash.count() == 0);
  195. // make sure things still work
  196. hash.add(&a);
  197. hash.add(&b);
  198. ASSERT(hash.count() == 2);
  199. ASSERT(hash.capacity() == 4);
  200. ASSERT(hash.find(1) != nullptr);
  201. ASSERT(hash.find(2) != nullptr);
  202. }
  203. DEF_TEST(DynamicHash_reset, reporter) {
  204. TestResetOrRewind(reporter, true);
  205. }
  206. DEF_TEST(DynamicHash_rewind, reporter) {
  207. TestResetOrRewind(reporter, false);
  208. }