mtklein | fb8307c | 2015-04-01 11:21:27 -0700 | [diff] [blame] | 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 | |
Mike Klein | c0bd9f9 | 2019-04-23 12:05:21 -0500 | [diff] [blame] | 8 | #include "include/core/SkRefCnt.h" |
| 9 | #include "include/core/SkString.h" |
| 10 | #include "include/private/SkChecksum.h" |
| 11 | #include "include/private/SkTHash.h" |
| 12 | #include "tests/Test.h" |
mtklein | 979e0ea | 2015-02-12 13:20:08 -0800 | [diff] [blame] | 13 | |
mtklein | 02f46cf | 2015-03-20 13:48:42 -0700 | [diff] [blame] | 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 | } |
mtklein | 979e0ea | 2015-02-12 13:20:08 -0800 | [diff] [blame] | 20 | |
| 21 | DEF_TEST(HashMap, r) { |
mtklein | 02f46cf | 2015-03-20 13:48:42 -0700 | [diff] [blame] | 22 | SkTHashMap<int, double> map; |
mtklein | 979e0ea | 2015-02-12 13:20:08 -0800 | [diff] [blame] | 23 | |
| 24 | map.set(3, 4.0); |
| 25 | REPORTER_ASSERT(r, map.count() == 1); |
| 26 | |
mtklein | 469a3fe | 2015-08-07 09:33:37 -0700 | [diff] [blame] | 27 | REPORTER_ASSERT(r, map.approxBytesUsed() > 0); |
| 28 | |
mtklein | 979e0ea | 2015-02-12 13:20:08 -0800 | [diff] [blame] | 29 | double* found = map.find(3); |
| 30 | REPORTER_ASSERT(r, found); |
| 31 | REPORTER_ASSERT(r, *found == 4.0); |
| 32 | |
mtklein | 02f46cf | 2015-03-20 13:48:42 -0700 | [diff] [blame] | 33 | map.foreach([](int key, double* d){ *d = -key; }); |
| 34 | REPORTER_ASSERT(r, count(map) == 1); |
| 35 | |
mtklein | 979e0ea | 2015-02-12 13:20:08 -0800 | [diff] [blame] | 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++) { |
tfarina | 567ff2f | 2015-04-27 07:01:44 -0700 | [diff] [blame] | 48 | double* found = map.find(i); |
mtklein | 979e0ea | 2015-02-12 13:20:08 -0800 | [diff] [blame] | 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); |
mtklein | 2aa1f7e | 2015-02-20 12:35:32 -0800 | [diff] [blame] | 57 | |
mtklein | 33d73c3 | 2015-04-21 06:53:56 -0700 | [diff] [blame] | 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 | |
mtklein | 2aa1f7e | 2015-02-20 12:35:32 -0800 | [diff] [blame] | 67 | map.reset(); |
| 68 | REPORTER_ASSERT(r, map.count() == 0); |
Florin Malita | 053730d | 2017-03-10 11:51:07 -0500 | [diff] [blame] | 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 | } |
mtklein | 979e0ea | 2015-02-12 13:20:08 -0800 | [diff] [blame] | 84 | } |
| 85 | |
mtklein | 979e0ea | 2015-02-12 13:20:08 -0800 | [diff] [blame] | 86 | DEF_TEST(HashSet, r) { |
mtklein | 02f46cf | 2015-03-20 13:48:42 -0700 | [diff] [blame] | 87 | SkTHashSet<SkString> set; |
mtklein | 979e0ea | 2015-02-12 13:20:08 -0800 | [diff] [blame] | 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"))); |
mtklein | 2aa1f7e | 2015-02-20 12:35:32 -0800 | [diff] [blame] | 97 | |
mtklein | fb8307c | 2015-04-01 11:21:27 -0700 | [diff] [blame] | 98 | REPORTER_ASSERT(r, set.find(SkString("Hello"))); |
| 99 | REPORTER_ASSERT(r, *set.find(SkString("Hello")) == SkString("Hello")); |
| 100 | |
mtklein | 33d73c3 | 2015-04-21 06:53:56 -0700 | [diff] [blame] | 101 | set.remove(SkString("Hello")); |
| 102 | REPORTER_ASSERT(r, !set.contains(SkString("Hello"))); |
| 103 | REPORTER_ASSERT(r, set.count() == 1); |
| 104 | |
mtklein | 2aa1f7e | 2015-02-20 12:35:32 -0800 | [diff] [blame] | 105 | set.reset(); |
| 106 | REPORTER_ASSERT(r, set.count() == 0); |
mtklein | 979e0ea | 2015-02-12 13:20:08 -0800 | [diff] [blame] | 107 | } |
fmalita | 79ca081 | 2015-02-12 17:32:49 -0800 | [diff] [blame] | 108 | |
| 109 | namespace { |
| 110 | |
| 111 | class CopyCounter { |
| 112 | public: |
halcanary | 96fcdcc | 2015-08-27 07:41:13 -0700 | [diff] [blame] | 113 | CopyCounter() : fID(0), fCounter(nullptr) {} |
fmalita | 79ca081 | 2015-02-12 17:32:49 -0800 | [diff] [blame] | 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 | |
Mike Klein | db402ca | 2016-12-13 12:46:05 -0500 | [diff] [blame] | 130 | CopyCounter(CopyCounter&& other) { *this = std::move(other); } |
| 131 | void operator=(CopyCounter&& other) { |
| 132 | fID = other.fID; |
| 133 | fCounter = other.fCounter; |
| 134 | } |
| 135 | |
| 136 | |
fmalita | 79ca081 | 2015-02-12 17:32:49 -0800 | [diff] [blame] | 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 | |
mtklein | c8d1dd4 | 2015-10-15 12:23:01 -0700 | [diff] [blame] | 146 | struct HashCopyCounter { |
| 147 | uint32_t operator()(const CopyCounter&) const { |
| 148 | return 0; // let them collide, what do we care? |
| 149 | } |
| 150 | }; |
fmalita | 79ca081 | 2015-02-12 17:32:49 -0800 | [diff] [blame] | 151 | |
| 152 | } |
| 153 | |
| 154 | DEF_TEST(HashSetCopyCounter, r) { |
mtklein | c8d1dd4 | 2015-10-15 12:23:01 -0700 | [diff] [blame] | 155 | SkTHashSet<CopyCounter, HashCopyCounter> set; |
fmalita | 79ca081 | 2015-02-12 17:32:49 -0800 | [diff] [blame] | 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 | } |
Mike Klein | 4284ec6 | 2019-01-09 13:20:57 -0500 | [diff] [blame] | 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 | } |
Herb Derby | 2fc9fa6 | 2019-12-12 15:07:11 -0500 | [diff] [blame] | 202 | |
Mike Klein | 16701ee | 2020-03-14 10:03:50 -0500 | [diff] [blame] | 203 | DEF_TEST(HashTableGrowsAndShrinks, r) { |
| 204 | SkTHashSet<int> s; |
| 205 | auto check_count_cap = [&](int count, int cap) { |
| 206 | REPORTER_ASSERT(r, s.count() == count); |
| 207 | REPORTER_ASSERT(r, s.approxBytesUsed() == (sizeof(int) + sizeof(uint32_t)) * cap); |
| 208 | }; |
| 209 | |
| 210 | // Add and remove some elements to test basic growth and shrink patterns. |
| 211 | check_count_cap(0,0); |
| 212 | s.add(1); check_count_cap(1,4); |
| 213 | s.add(2); check_count_cap(2,4); |
| 214 | s.add(3); check_count_cap(3,4); |
| 215 | s.add(4); check_count_cap(4,8); |
| 216 | |
| 217 | s.remove(4); check_count_cap(3,8); |
| 218 | s.remove(3); check_count_cap(2,4); |
| 219 | s.remove(2); check_count_cap(1,4); |
| 220 | s.remove(1); check_count_cap(0,4); |
| 221 | |
| 222 | s.add(1); check_count_cap(1,4); |
| 223 | s.add(2); check_count_cap(2,4); |
| 224 | s.add(3); check_count_cap(3,4); |
| 225 | s.add(4); check_count_cap(4,8); |
| 226 | |
| 227 | // Add and remove single elements repeatedly to test hysteresis |
| 228 | // avoids reallocating these small tables all the time. |
| 229 | for (int i = 0; i < 10; i++) { |
| 230 | s. add(5); check_count_cap(5,8); |
| 231 | s.remove(5); check_count_cap(4,8); |
| 232 | } |
| 233 | |
| 234 | s.remove(4); check_count_cap(3,8); |
| 235 | for (int i = 0; i < 10; i++) { |
| 236 | s. add(4); check_count_cap(4,8); |
| 237 | s.remove(4); check_count_cap(3,8); |
| 238 | } |
| 239 | |
| 240 | s.remove(3); check_count_cap(2,4); |
| 241 | for (int i = 0; i < 10; i++) { |
| 242 | s. add(4); check_count_cap(3,4); |
| 243 | s.remove(4); check_count_cap(2,4); |
| 244 | } |
| 245 | |
| 246 | s.remove(2); check_count_cap(1,4); |
| 247 | for (int i = 0; i < 10; i++) { |
| 248 | s. add(2); check_count_cap(2,4); |
| 249 | s.remove(2); check_count_cap(1,4); |
| 250 | } |
| 251 | } |