| OLD | NEW |
| 1 /* | 1 /* |
| 2 * Copyright 2013 Google Inc. | 2 * Copyright 2013 Google Inc. |
| 3 * | 3 * |
| 4 * Use of this source code is governed by a BSD-style license that can be | 4 * Use of this source code is governed by a BSD-style license that can be |
| 5 * found in the LICENSE file. | 5 * found in the LICENSE file. |
| 6 */ | 6 */ |
| 7 | 7 |
| 8 #include "SkTDynamicHash.h" | 8 #include "SkTDynamicHash.h" |
| 9 #include "Test.h" | 9 #include "Test.h" |
| 10 | 10 |
| (...skipping 82 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
| 93 ASSERT(hash.countCollisions(5) == 1); | 93 ASSERT(hash.countCollisions(5) == 1); |
| 94 ASSERT(hash.countCollisions(9) == 1); | 94 ASSERT(hash.countCollisions(9) == 1); |
| 95 | 95 |
| 96 // Second is one step away. | 96 // Second is one step away. |
| 97 hash.add(&b); | 97 hash.add(&b); |
| 98 ASSERT(hash.countCollisions(1) == 0); | 98 ASSERT(hash.countCollisions(1) == 0); |
| 99 ASSERT(hash.countCollisions(5) == 1); | 99 ASSERT(hash.countCollisions(5) == 1); |
| 100 ASSERT(hash.countCollisions(9) == 2); | 100 ASSERT(hash.countCollisions(9) == 2); |
| 101 | 101 |
| 102 // We can find our data right? | 102 // We can find our data right? |
| 103 ASSERT(hash.find(1) != NULL); | 103 ASSERT(hash.find(1) != nullptr); |
| 104 ASSERT(hash.find(1)->value == 2.0); | 104 ASSERT(hash.find(1)->value == 2.0); |
| 105 ASSERT(hash.find(5) != NULL); | 105 ASSERT(hash.find(5) != nullptr); |
| 106 ASSERT(hash.find(5)->value == 3.0); | 106 ASSERT(hash.find(5)->value == 3.0); |
| 107 | 107 |
| 108 // These aren't in the hash. | 108 // These aren't in the hash. |
| 109 ASSERT(hash.find(2) == NULL); | 109 ASSERT(hash.find(2) == nullptr); |
| 110 ASSERT(hash.find(9) == NULL); | 110 ASSERT(hash.find(9) == nullptr); |
| 111 } | 111 } |
| 112 | 112 |
| 113 DEF_TEST(DynamicHash_remove, reporter) { | 113 DEF_TEST(DynamicHash_remove, reporter) { |
| 114 Hash hash; | 114 Hash hash; |
| 115 | 115 |
| 116 // These collide. | 116 // These collide. |
| 117 Entry a = { 1, 2.0 }; | 117 Entry a = { 1, 2.0 }; |
| 118 Entry b = { 5, 3.0 }; | 118 Entry b = { 5, 3.0 }; |
| 119 Entry c = { 9, 4.0 }; | 119 Entry c = { 9, 4.0 }; |
| 120 | 120 |
| 121 hash.add(&a); | 121 hash.add(&a); |
| 122 hash.add(&b); | 122 hash.add(&b); |
| 123 hash.remove(1); | 123 hash.remove(1); |
| 124 // a should be marked deleted, and b should still be findable. | 124 // a should be marked deleted, and b should still be findable. |
| 125 | 125 |
| 126 ASSERT(hash.find(1) == NULL); | 126 ASSERT(hash.find(1) == nullptr); |
| 127 ASSERT(hash.find(5) != NULL); | 127 ASSERT(hash.find(5) != nullptr); |
| 128 ASSERT(hash.find(5)->value == 3.0); | 128 ASSERT(hash.find(5)->value == 3.0); |
| 129 | 129 |
| 130 // This will go in the same slot as 'a' did before. | 130 // This will go in the same slot as 'a' did before. |
| 131 ASSERT(hash.countCollisions(9) == 0); | 131 ASSERT(hash.countCollisions(9) == 0); |
| 132 hash.add(&c); | 132 hash.add(&c); |
| 133 ASSERT(hash.find(9) != NULL); | 133 ASSERT(hash.find(9) != nullptr); |
| 134 ASSERT(hash.find(9)->value == 4.0); | 134 ASSERT(hash.find(9)->value == 4.0); |
| 135 ASSERT(hash.find(5) != NULL); | 135 ASSERT(hash.find(5) != nullptr); |
| 136 ASSERT(hash.find(5)->value == 3.0); | 136 ASSERT(hash.find(5)->value == 3.0); |
| 137 } | 137 } |
| 138 | 138 |
| 139 template<typename T> static void TestIter(skiatest::Reporter* reporter) { | 139 template<typename T> static void TestIter(skiatest::Reporter* reporter) { |
| 140 Hash hash; | 140 Hash hash; |
| 141 | 141 |
| 142 int count = 0; | 142 int count = 0; |
| 143 // this should fall out of loop immediately | 143 // this should fall out of loop immediately |
| 144 for (T iter(&hash); !iter.done(); ++iter) { | 144 for (T iter(&hash); !iter.done(); ++iter) { |
| 145 ++count; | 145 ++count; |
| 146 } | 146 } |
| 147 ASSERT(0 == count); | 147 ASSERT(0 == count); |
| 148 | 148 |
| 149 // These collide. | 149 // These collide. |
| 150 Entry a = { 1, 2.0 }; | 150 Entry a = { 1, 2.0 }; |
| 151 Entry b = { 5, 3.0 }; | 151 Entry b = { 5, 3.0 }; |
| 152 Entry c = { 9, 4.0 }; | 152 Entry c = { 9, 4.0 }; |
| 153 | 153 |
| 154 hash.add(&a); | 154 hash.add(&a); |
| 155 hash.add(&b); | 155 hash.add(&b); |
| 156 hash.add(&c); | 156 hash.add(&c); |
| 157 | 157 |
| 158 // should see all 3 unique keys when iterating over hash | 158 // should see all 3 unique keys when iterating over hash |
| 159 count = 0; | 159 count = 0; |
| 160 int keys[3] = {0, 0, 0}; | 160 int keys[3] = {0, 0, 0}; |
| 161 for (T iter(&hash); !iter.done(); ++iter) { | 161 for (T iter(&hash); !iter.done(); ++iter) { |
| 162 int key = (*iter).key; | 162 int key = (*iter).key; |
| 163 keys[count] = key; | 163 keys[count] = key; |
| 164 ASSERT(hash.find(key) != NULL); | 164 ASSERT(hash.find(key) != nullptr); |
| 165 ++count; | 165 ++count; |
| 166 } | 166 } |
| 167 ASSERT(3 == count); | 167 ASSERT(3 == count); |
| 168 ASSERT(keys[0] != keys[1]); | 168 ASSERT(keys[0] != keys[1]); |
| 169 ASSERT(keys[0] != keys[2]); | 169 ASSERT(keys[0] != keys[2]); |
| 170 ASSERT(keys[1] != keys[2]); | 170 ASSERT(keys[1] != keys[2]); |
| 171 | 171 |
| 172 // should see 2 unique keys when iterating over hash that aren't 1 | 172 // should see 2 unique keys when iterating over hash that aren't 1 |
| 173 hash.remove(1); | 173 hash.remove(1); |
| 174 count = 0; | 174 count = 0; |
| 175 memset(keys, 0, sizeof(keys)); | 175 memset(keys, 0, sizeof(keys)); |
| 176 for (T iter(&hash); !iter.done(); ++iter) { | 176 for (T iter(&hash); !iter.done(); ++iter) { |
| 177 int key = (*iter).key; | 177 int key = (*iter).key; |
| 178 keys[count] = key; | 178 keys[count] = key; |
| 179 ASSERT(key != 1); | 179 ASSERT(key != 1); |
| 180 ASSERT(hash.find(key) != NULL); | 180 ASSERT(hash.find(key) != nullptr); |
| 181 ++count; | 181 ++count; |
| 182 } | 182 } |
| 183 ASSERT(2 == count); | 183 ASSERT(2 == count); |
| 184 ASSERT(keys[0] != keys[1]); | 184 ASSERT(keys[0] != keys[1]); |
| 185 } | 185 } |
| 186 | 186 |
| 187 DEF_TEST(DynamicHash_iterator, reporter) { | 187 DEF_TEST(DynamicHash_iterator, reporter) { |
| 188 TestIter<Hash::Iter>(reporter); | 188 TestIter<Hash::Iter>(reporter); |
| 189 TestIter<Hash::ConstIter>(reporter); | 189 TestIter<Hash::ConstIter>(reporter); |
| 190 } | 190 } |
| (...skipping 17 matching lines...) Expand all Loading... |
| 208 ASSERT(hash.capacity() == 4); | 208 ASSERT(hash.capacity() == 4); |
| 209 } | 209 } |
| 210 ASSERT(hash.count() == 0); | 210 ASSERT(hash.count() == 0); |
| 211 | 211 |
| 212 // make sure things still work | 212 // make sure things still work |
| 213 hash.add(&a); | 213 hash.add(&a); |
| 214 hash.add(&b); | 214 hash.add(&b); |
| 215 ASSERT(hash.count() == 2); | 215 ASSERT(hash.count() == 2); |
| 216 ASSERT(hash.capacity() == 4); | 216 ASSERT(hash.capacity() == 4); |
| 217 | 217 |
| 218 ASSERT(hash.find(1) != NULL); | 218 ASSERT(hash.find(1) != nullptr); |
| 219 ASSERT(hash.find(2) != NULL); | 219 ASSERT(hash.find(2) != nullptr); |
| 220 } | 220 } |
| 221 | 221 |
| 222 DEF_TEST(DynamicHash_reset, reporter) { | 222 DEF_TEST(DynamicHash_reset, reporter) { |
| 223 TestResetOrRewind(reporter, true); | 223 TestResetOrRewind(reporter, true); |
| 224 } | 224 } |
| 225 | 225 |
| 226 DEF_TEST(DynamicHash_rewind, reporter) { | 226 DEF_TEST(DynamicHash_rewind, reporter) { |
| 227 TestResetOrRewind(reporter, false); | 227 TestResetOrRewind(reporter, false); |
| 228 } | 228 } |
| OLD | NEW |