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 |