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