ProbingHashMapTests.cpp 7.5 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201202203204205206207208209210211212213214215216217218219220221222223224225226227228229230231232233234235236237238239240241242243244245246247248249250251252253254255256257258259260261262263264265266267268269270271272273274275276277278279280281282283284285286287288289290291292293294295296297298299300301302303304305306307308309310311312313314315316317318319320321322323324325326327328
  1. #include "tests/ProbingHashMapTests.h"
  2. #include <stdio.h>
  3. #include "data/ProbingHashMap.h"
  4. #include "test/Test.h"
  5. using IntMap = Core::ProbingHashMap<int, int>;
  6. static void testAdd() {
  7. IntMap map;
  8. CORE_TEST_ERROR(map.add(5, 4));
  9. int* value = map.search(5);
  10. CORE_TEST_NOT_NULL(value);
  11. if(value != nullptr) {
  12. CORE_TEST_EQUAL(4, *value);
  13. }
  14. }
  15. static void testMultipleAdd() {
  16. IntMap map;
  17. CORE_TEST_ERROR(map.add(5, 4));
  18. CORE_TEST_ERROR(map.add(10, 3));
  19. CORE_TEST_ERROR(map.add(15, 2));
  20. CORE_TEST_TRUE(map.contains(5));
  21. CORE_TEST_TRUE(map.contains(10));
  22. CORE_TEST_TRUE(map.contains(15));
  23. int* a = map.search(5);
  24. int* b = map.search(10);
  25. int* c = map.search(15);
  26. CORE_TEST_NOT_NULL(a);
  27. CORE_TEST_NOT_NULL(b);
  28. CORE_TEST_NOT_NULL(c);
  29. if(a != nullptr && b != nullptr && c != nullptr) {
  30. CORE_TEST_EQUAL(4, *a);
  31. CORE_TEST_EQUAL(3, *b);
  32. CORE_TEST_EQUAL(2, *c);
  33. }
  34. }
  35. static void testSearch() {
  36. IntMap map;
  37. CORE_TEST_NULL(map.search(6));
  38. }
  39. static void testAddReplace() {
  40. IntMap map;
  41. CORE_TEST_ERROR(map.add(5, 4));
  42. CORE_TEST_ERROR(map.add(5, 10));
  43. CORE_TEST_TRUE(map.contains(5));
  44. int* a = map.search(5);
  45. CORE_TEST_NOT_NULL(a);
  46. if(a != nullptr) {
  47. CORE_TEST_EQUAL(10, *a);
  48. }
  49. }
  50. static void testClear() {
  51. IntMap map;
  52. CORE_TEST_ERROR(map.add(5, 4));
  53. CORE_TEST_ERROR(map.add(4, 10));
  54. map.clear();
  55. CORE_TEST_FALSE(map.contains(5));
  56. CORE_TEST_FALSE(map.contains(4));
  57. }
  58. static void testOverflow() {
  59. IntMap map;
  60. for(int i = 0; i < 100000; i++) {
  61. CORE_TEST_ERROR(map.add(i, i));
  62. }
  63. for(int i = 0; i < 100000; i++) {
  64. CORE_TEST_TRUE(map.contains(i));
  65. }
  66. }
  67. static int aInstances = 0;
  68. struct A final {
  69. int a;
  70. int b;
  71. A(int a_, int b_) : a(a_), b(b_) {
  72. aInstances++;
  73. }
  74. A(const A& o) : a(o.a), b(o.b) {
  75. aInstances++;
  76. }
  77. A(A&& o) : a(o.a), b(o.b) {
  78. aInstances++;
  79. }
  80. ~A() {
  81. aInstances--;
  82. }
  83. A& operator=(const A& o) = default;
  84. A& operator=(A&& o) = default;
  85. bool operator==(const A& other) const {
  86. return a == other.a && b == other.b;
  87. }
  88. template<typename String>
  89. check_return Core::Error toString(String& s) const {
  90. CORE_RETURN_ERROR(s.append("A("));
  91. CORE_RETURN_ERROR(s.append(a));
  92. CORE_RETURN_ERROR(s.append(", "));
  93. CORE_RETURN_ERROR(s.append(b));
  94. CORE_RETURN_ERROR(s.append(")"));
  95. return Core::Error::NONE;
  96. }
  97. };
  98. static void testEmplace() {
  99. {
  100. Core::ProbingHashMap<int, A> map;
  101. A* ar = nullptr;
  102. CORE_TEST_ERROR(map.tryEmplace(ar, 0, 3, 4));
  103. CORE_TEST_ERROR(map.tryEmplace(ar, 3, 4, 5));
  104. CORE_TEST_ERROR(map.tryEmplace(ar, 20, 5, 6));
  105. CORE_TEST_EQUAL(Core::Error::EXISTING_KEY, map.tryEmplace(ar, 3, 6, 7));
  106. CORE_TEST_EQUAL(Core::Error::EXISTING_KEY,
  107. map.tryEmplace(ar, 20, 7, 8));
  108. A* a = map.search(0);
  109. A* b = map.search(3);
  110. A* c = map.search(20);
  111. CORE_TEST_NOT_NULL(a);
  112. CORE_TEST_NOT_NULL(b);
  113. CORE_TEST_NOT_NULL(c);
  114. if(a != nullptr && b != nullptr && c != nullptr) {
  115. CORE_TEST_EQUAL(A(3, 4), *a);
  116. CORE_TEST_EQUAL(A(4, 5), *b);
  117. CORE_TEST_EQUAL(A(5, 6), *c);
  118. }
  119. }
  120. CORE_TEST_EQUAL(0, aInstances);
  121. }
  122. static void testToString1() {
  123. IntMap map;
  124. CORE_TEST_ERROR(map.add(1, 3));
  125. CORE_TEST_ERROR(map.add(2, 4));
  126. CORE_TEST_ERROR(map.add(3, 5));
  127. CORE_TEST_STRING("[2 = 4, 1 = 3, 3 = 5]", map);
  128. }
  129. static void testToString2() {
  130. IntMap map;
  131. CORE_TEST_ERROR(map.add(1, 3));
  132. CORE_TEST_STRING("[1 = 3]", map);
  133. }
  134. static void testToString3() {
  135. IntMap map;
  136. CORE_TEST_STRING("[]", map);
  137. }
  138. static void testCopy() {
  139. IntMap map;
  140. CORE_TEST_ERROR(map.add(1, 3));
  141. CORE_TEST_ERROR(map.add(2, 4));
  142. CORE_TEST_ERROR(map.add(3, 5));
  143. IntMap copy;
  144. CORE_TEST_ERROR(copy.copyFrom(map));
  145. int* a[6] = {map.search(1), map.search(2), map.search(3),
  146. copy.search(1), copy.search(2), copy.search(3)};
  147. for(int i = 0; i < 3; i++) {
  148. CORE_TEST_NOT_NULL(a[i]);
  149. CORE_TEST_NOT_NULL(a[i + 3]);
  150. if(a[i] != nullptr && a[i + 3] != nullptr) {
  151. CORE_TEST_EQUAL(*(a[i]), *(a[i + 3]));
  152. }
  153. }
  154. }
  155. static void testMove() {
  156. IntMap map;
  157. CORE_TEST_ERROR(map.add(1, 3));
  158. CORE_TEST_ERROR(map.add(2, 4));
  159. CORE_TEST_ERROR(map.add(3, 5));
  160. IntMap move(Core::move(map));
  161. int* a = move.search(1);
  162. int* b = move.search(2);
  163. int* c = move.search(3);
  164. CORE_TEST_NOT_NULL(a);
  165. CORE_TEST_NOT_NULL(b);
  166. CORE_TEST_NOT_NULL(c);
  167. if(a != nullptr && b != nullptr && c != nullptr) {
  168. CORE_TEST_EQUAL(3, *a);
  169. CORE_TEST_EQUAL(4, *b);
  170. CORE_TEST_EQUAL(5, *c);
  171. }
  172. }
  173. static void testMoveAssignment() {
  174. IntMap map;
  175. CORE_TEST_ERROR(map.add(1, 3));
  176. CORE_TEST_ERROR(map.add(2, 4));
  177. CORE_TEST_ERROR(map.add(3, 5));
  178. IntMap move;
  179. move = Core::move(map);
  180. int* a = move.search(1);
  181. int* b = move.search(2);
  182. int* c = move.search(3);
  183. CORE_TEST_NOT_NULL(a);
  184. CORE_TEST_NOT_NULL(b);
  185. CORE_TEST_NOT_NULL(c);
  186. if(a != nullptr && b != nullptr && c != nullptr) {
  187. CORE_TEST_EQUAL(3, *a);
  188. CORE_TEST_EQUAL(4, *b);
  189. CORE_TEST_EQUAL(5, *c);
  190. }
  191. }
  192. static void testEntryForEach() {
  193. IntMap map;
  194. CORE_TEST_ERROR(map.add(5, 4));
  195. CORE_TEST_ERROR(map.add(10, 3));
  196. CORE_TEST_ERROR(map.add(15, 2));
  197. int counter = 0;
  198. for(auto entry : map) {
  199. counter += entry.getKey() + entry.value;
  200. }
  201. CORE_TEST_EQUAL(39, counter);
  202. const IntMap& cmap = map;
  203. counter = 0;
  204. for(auto entry : cmap) {
  205. counter += entry.getKey() + entry.value;
  206. }
  207. CORE_TEST_EQUAL(39, counter);
  208. }
  209. static void testKeyForEach() {
  210. IntMap map;
  211. CORE_TEST_ERROR(map.add(5, 4));
  212. CORE_TEST_ERROR(map.add(10, 3));
  213. CORE_TEST_ERROR(map.add(15, 2));
  214. int counter = 0;
  215. for(const int& key : map.getKeys()) {
  216. counter += key;
  217. }
  218. CORE_TEST_EQUAL(30, counter);
  219. const IntMap& cmap = map;
  220. counter = 0;
  221. for(const int& key : cmap.getKeys()) {
  222. counter += key;
  223. }
  224. CORE_TEST_EQUAL(30, counter);
  225. }
  226. static void testValueForEach() {
  227. IntMap map;
  228. CORE_TEST_ERROR(map.add(5, 4));
  229. CORE_TEST_ERROR(map.add(10, 3));
  230. CORE_TEST_ERROR(map.add(15, 2));
  231. int counter = 0;
  232. for(int& value : map.getValues()) {
  233. counter += value;
  234. }
  235. CORE_TEST_EQUAL(9, counter);
  236. const IntMap& cmap = map;
  237. counter = 0;
  238. for(const int& value : cmap.getValues()) {
  239. counter += value;
  240. }
  241. CORE_TEST_EQUAL(9, counter);
  242. }
  243. template<typename T>
  244. static void testType() {
  245. Core::ProbingHashMap<T, int> m;
  246. CORE_TEST_ERROR(m.add(T(), 3));
  247. }
  248. static void testTypes() {
  249. testType<char>();
  250. testType<signed char>();
  251. testType<signed short>();
  252. testType<signed int>();
  253. testType<signed long>();
  254. testType<signed long long>();
  255. testType<unsigned char>();
  256. testType<unsigned short>();
  257. testType<unsigned int>();
  258. testType<unsigned long>();
  259. testType<unsigned long long>();
  260. }
  261. void Core::ProbingHashMapTests::test() {
  262. testAdd();
  263. testMultipleAdd();
  264. testSearch();
  265. testAddReplace();
  266. testClear();
  267. testOverflow();
  268. testEmplace();
  269. testToString1();
  270. testToString2();
  271. testToString3();
  272. testCopy();
  273. testMove();
  274. testMoveAssignment();
  275. testEntryForEach();
  276. testKeyForEach();
  277. testValueForEach();
  278. testTypes();
  279. }