HashTest.cpp 5.1 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161162163164165166167168169170171172173174175176177178179180181182183184185186187188189190191192193194195196197198199200201
  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. #include "include/core/SkRefCnt.h"
  8. #include "include/core/SkString.h"
  9. #include "include/private/SkChecksum.h"
  10. #include "include/private/SkTHash.h"
  11. #include "tests/Test.h"
  12. // Tests use of const foreach(). map.count() is of course the better way to do this.
  13. static int count(const SkTHashMap<int, double>& map) {
  14. int n = 0;
  15. map.foreach([&n](int, double) { n++; });
  16. return n;
  17. }
  18. DEF_TEST(HashMap, r) {
  19. SkTHashMap<int, double> map;
  20. map.set(3, 4.0);
  21. REPORTER_ASSERT(r, map.count() == 1);
  22. REPORTER_ASSERT(r, map.approxBytesUsed() > 0);
  23. double* found = map.find(3);
  24. REPORTER_ASSERT(r, found);
  25. REPORTER_ASSERT(r, *found == 4.0);
  26. map.foreach([](int key, double* d){ *d = -key; });
  27. REPORTER_ASSERT(r, count(map) == 1);
  28. found = map.find(3);
  29. REPORTER_ASSERT(r, found);
  30. REPORTER_ASSERT(r, *found == -3.0);
  31. REPORTER_ASSERT(r, !map.find(2));
  32. const int N = 20;
  33. for (int i = 0; i < N; i++) {
  34. map.set(i, 2.0*i);
  35. }
  36. for (int i = 0; i < N; i++) {
  37. double* found = map.find(i);
  38. REPORTER_ASSERT(r, found);
  39. REPORTER_ASSERT(r, *found == i*2.0);
  40. }
  41. for (int i = N; i < 2*N; i++) {
  42. REPORTER_ASSERT(r, !map.find(i));
  43. }
  44. REPORTER_ASSERT(r, map.count() == N);
  45. for (int i = 0; i < N/2; i++) {
  46. map.remove(i);
  47. }
  48. for (int i = 0; i < N; i++) {
  49. double* found = map.find(i);
  50. REPORTER_ASSERT(r, (found == nullptr) == (i < N/2));
  51. }
  52. REPORTER_ASSERT(r, map.count() == N/2);
  53. map.reset();
  54. REPORTER_ASSERT(r, map.count() == 0);
  55. {
  56. // Test that we don't leave dangling values in empty slots.
  57. SkTHashMap<int, sk_sp<SkRefCnt>> refMap;
  58. auto ref = sk_make_sp<SkRefCnt>();
  59. REPORTER_ASSERT(r, ref->unique());
  60. refMap.set(0, ref);
  61. REPORTER_ASSERT(r, refMap.count() == 1);
  62. REPORTER_ASSERT(r, !ref->unique());
  63. refMap.remove(0);
  64. REPORTER_ASSERT(r, refMap.count() == 0);
  65. REPORTER_ASSERT(r, ref->unique());
  66. }
  67. }
  68. DEF_TEST(HashSet, r) {
  69. SkTHashSet<SkString> set;
  70. set.add(SkString("Hello"));
  71. set.add(SkString("World"));
  72. REPORTER_ASSERT(r, set.count() == 2);
  73. REPORTER_ASSERT(r, set.contains(SkString("Hello")));
  74. REPORTER_ASSERT(r, set.contains(SkString("World")));
  75. REPORTER_ASSERT(r, !set.contains(SkString("Goodbye")));
  76. REPORTER_ASSERT(r, set.find(SkString("Hello")));
  77. REPORTER_ASSERT(r, *set.find(SkString("Hello")) == SkString("Hello"));
  78. set.remove(SkString("Hello"));
  79. REPORTER_ASSERT(r, !set.contains(SkString("Hello")));
  80. REPORTER_ASSERT(r, set.count() == 1);
  81. set.reset();
  82. REPORTER_ASSERT(r, set.count() == 0);
  83. }
  84. namespace {
  85. class CopyCounter {
  86. public:
  87. CopyCounter() : fID(0), fCounter(nullptr) {}
  88. CopyCounter(uint32_t id, uint32_t* counter) : fID(id), fCounter(counter) {}
  89. CopyCounter(const CopyCounter& other)
  90. : fID(other.fID)
  91. , fCounter(other.fCounter) {
  92. SkASSERT(fCounter);
  93. *fCounter += 1;
  94. }
  95. void operator=(const CopyCounter& other) {
  96. fID = other.fID;
  97. fCounter = other.fCounter;
  98. *fCounter += 1;
  99. }
  100. CopyCounter(CopyCounter&& other) { *this = std::move(other); }
  101. void operator=(CopyCounter&& other) {
  102. fID = other.fID;
  103. fCounter = other.fCounter;
  104. }
  105. bool operator==(const CopyCounter& other) const {
  106. return fID == other.fID;
  107. }
  108. private:
  109. uint32_t fID;
  110. uint32_t* fCounter;
  111. };
  112. struct HashCopyCounter {
  113. uint32_t operator()(const CopyCounter&) const {
  114. return 0; // let them collide, what do we care?
  115. }
  116. };
  117. }
  118. DEF_TEST(HashSetCopyCounter, r) {
  119. SkTHashSet<CopyCounter, HashCopyCounter> set;
  120. uint32_t globalCounter = 0;
  121. CopyCounter copyCounter1(1, &globalCounter);
  122. CopyCounter copyCounter2(2, &globalCounter);
  123. REPORTER_ASSERT(r, globalCounter == 0);
  124. set.add(copyCounter1);
  125. REPORTER_ASSERT(r, globalCounter == 1);
  126. REPORTER_ASSERT(r, set.contains(copyCounter1));
  127. REPORTER_ASSERT(r, globalCounter == 1);
  128. set.add(copyCounter1);
  129. // We allow copies for same-value adds for now.
  130. REPORTER_ASSERT(r, globalCounter == 2);
  131. set.add(copyCounter2);
  132. REPORTER_ASSERT(r, globalCounter == 3);
  133. REPORTER_ASSERT(r, set.contains(copyCounter1));
  134. REPORTER_ASSERT(r, set.contains(copyCounter2));
  135. REPORTER_ASSERT(r, globalCounter == 3);
  136. set.add(copyCounter1);
  137. set.add(copyCounter2);
  138. // We allow copies for same-value adds for now.
  139. REPORTER_ASSERT(r, globalCounter == 5);
  140. }
  141. DEF_TEST(HashFindOrNull, r) {
  142. struct Entry {
  143. int key = 0;
  144. int val = 0;
  145. };
  146. struct HashTraits {
  147. static int GetKey(const Entry* e) { return e->key; }
  148. static uint32_t Hash(int key) { return key; }
  149. };
  150. SkTHashTable<Entry*, int, HashTraits> table;
  151. REPORTER_ASSERT(r, nullptr == table.findOrNull(7));
  152. Entry seven = { 7, 24 };
  153. table.set(&seven);
  154. REPORTER_ASSERT(r, &seven == table.findOrNull(7));
  155. }