1// Copyright 2014, VIXL authors 2// All rights reserved. 3// 4// Redistribution and use in source and binary forms, with or without 5// modification, are permitted provided that the following conditions are met: 6// 7// * Redistributions of source code must retain the above copyright notice, 8// this list of conditions and the following disclaimer. 9// * Redistributions in binary form must reproduce the above copyright notice, 10// this list of conditions and the following disclaimer in the documentation 11// and/or other materials provided with the distribution. 12// * Neither the name of ARM Limited nor the names of its contributors may be 13// used to endorse or promote products derived from this software without 14// specific prior written permission. 15// 16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND 17// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED 18// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE 19// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE 20// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL 21// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR 22// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER 23// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, 24// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 25// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 26 27#include "invalset-vixl.h" 28#include "test-runner.h" 29 30namespace vixl { 31 32// This file contains tests for the `InvalSet` and `InvalSetIterator` classes. 33 34#define TEST(name) TEST_(INVALSET_##name) 35 36typedef ptrdiff_t KeyType; 37typedef ptrdiff_t ValType; 38 39// We test with an object for which the key and the value are distinct. 40class Obj { 41 public: 42 Obj() {} 43 Obj(KeyType key, ValType val) : key_(key), val_(val) {} 44 KeyType key_; 45 ValType val_; 46 47 bool operator==(const Obj& other) const { 48 return (key_ == other.key_) && (val_ == other.val_); 49 } 50 bool operator<(const Obj& other) const { 51 return (key_ < other.key_) || ((key_ == other.key_) && (val_ < other.val_)); 52 } 53 bool operator<=(const Obj& other) const { 54 return (key_ <= other.key_) || 55 ((key_ == other.key_) && (val_ <= other.val_)); 56 } 57 bool operator>(const Obj& other) const { 58 return (key_ > other.key_) || ((key_ == other.key_) && (val_ > other.val_)); 59 } 60}; 61 62static const unsigned kNPreallocatedElements = 8; 63static const KeyType kInvalidKey = PTRDIFF_MAX; 64static const size_t kReclaimFrom = 1000; 65static const unsigned kReclaimFactor = 10; 66 67typedef InvalSet<Obj, 68 kNPreallocatedElements, 69 KeyType, 70 kInvalidKey, 71 kReclaimFrom, 72 kReclaimFactor> TestSet; 73 74template <> 75inline KeyType InvalSet<Obj, 76 kNPreallocatedElements, 77 KeyType, 78 kInvalidKey, 79 kReclaimFrom, 80 kReclaimFactor>::GetKey(const Obj& obj) { 81 return obj.key_; 82} 83template <> 84inline void InvalSet<Obj, 85 kNPreallocatedElements, 86 KeyType, 87 kInvalidKey, 88 kReclaimFrom, 89 kReclaimFactor>::SetKey(Obj* obj, KeyType key) { 90 obj->key_ = key; 91} 92 93 94TEST(basic_test) { 95 TestSet set; 96 VIXL_CHECK(set.empty() && (set.size() == 0)); 97 98 for (unsigned i = 0; i < kNPreallocatedElements; i++) { 99 set.insert(Obj(i, i)); 100 } 101 VIXL_CHECK(set.size() == kNPreallocatedElements); 102 103 set.insert(Obj(-123, 456)); 104 set.insert(Obj(2718, 2871828)); 105 VIXL_CHECK(set.size() == kNPreallocatedElements + 2); 106 VIXL_CHECK(set.GetMinElement() == Obj(-123, 456)); 107 108 set.erase(Obj(-123, 456)); 109 VIXL_CHECK(set.GetMinElementKey() == 0); 110 111 set.clear(); 112 VIXL_CHECK(set.empty() && (set.size() == 0)); 113} 114 115 116TEST(valid_element) { 117 VIXL_CHECK(TestSet::IsValid(Obj(0, 0))); 118 VIXL_CHECK(TestSet::IsValid(Obj(-1, 0))); 119 VIXL_CHECK(TestSet::IsValid(Obj(kInvalidKey - 1, 0))); 120 VIXL_CHECK(!TestSet::IsValid(Obj(kInvalidKey, 0))); 121} 122 123 124TEST(insert) { 125 TestSet set; 126 VIXL_CHECK(set.empty() && (set.size() == 0)); 127 128 for (unsigned i = 0; i < kNPreallocatedElements; i++) { 129 set.insert(Obj(i, i)); 130 } 131 VIXL_CHECK(set.size() == kNPreallocatedElements); 132 set.insert(Obj(-123, 1)); 133 VIXL_CHECK(set.size() == kNPreallocatedElements + 1); 134 set.insert(Obj(-123, 2)); 135 set.insert(Obj(-123, 3)); 136 VIXL_CHECK(set.size() == kNPreallocatedElements + 3); 137 138 set.clear(); 139 VIXL_CHECK(set.empty() && (set.size() == 0)); 140} 141 142 143TEST(erase) { 144 TestSet set; 145 VIXL_CHECK(set.empty() && (set.size() == 0)); 146 147 // Test with only preallocated elements in the set. 148 VIXL_STATIC_ASSERT(kNPreallocatedElements >= 2); 149 set.insert(Obj(2718, 0)); 150 set.erase(Obj(2718, 0)); 151 VIXL_CHECK(set.empty() && (set.size() == 0)); 152 set.insert(Obj(2718, 0)); 153 VIXL_CHECK(set.size() == 1); 154 set.insert(Obj(2718, 1)); 155 VIXL_CHECK(set.size() == 2); 156 set.erase(Obj(2718, 0)); 157 VIXL_CHECK(set.size() == 1); 158 159 // Test with more elements. 160 for (unsigned i = 0; i < 100 * kNPreallocatedElements; i++) { 161 set.insert(Obj(i * i, i % 30)); 162 set.insert(Obj(i, -1)); 163 } 164 size_t max_size = set.size(); 165 set.erase(Obj(100, -1)); 166 VIXL_CHECK(set.size() == max_size - 1); 167 for (size_t i = 2; i <= max_size; i++) { 168 set.erase(set.GetMinElement()); 169 VIXL_CHECK(set.size() == max_size - i); 170 } 171 172 VIXL_CHECK(set.empty() && (set.size() == 0)); 173} 174 175 176TEST(min) { 177 TestSet set; 178 VIXL_CHECK(set.empty() && (set.size() == 0)); 179 180 // Test with only preallocated elements in the set. 181 VIXL_STATIC_ASSERT(kNPreallocatedElements >= 4); 182 set.insert(Obj(-1, -1)); 183 set.insert(Obj(-1, 0)); 184 set.insert(Obj(0, 0)); 185 set.insert(Obj(1, 0)); 186 VIXL_CHECK(set.GetMinElement() == Obj(-1, -1)); 187 VIXL_CHECK(set.GetMinElementKey() == -1); 188 VIXL_CHECK(set.GetMinElement().key_ == set.GetMinElementKey()); 189 190 // Test with more elements. 191 set.clear(); 192 int max_index = 100 * kNPreallocatedElements; 193 for (int i = 0; i <= max_index; i++) { 194 // Insert elements out of order. 195 int sign = ((i % 2) == 0) ? -1 : 1; 196 set.insert(Obj(sign * i, i)); 197 } 198 VIXL_CHECK(set.GetMinElement() == Obj(-max_index, max_index)); 199 VIXL_CHECK(set.GetMinElement().key_ == set.GetMinElementKey()); 200 201 set.erase(Obj(0, 0)); 202 VIXL_CHECK(set.GetMinElement() == Obj(-max_index, max_index)); 203 set.erase(set.GetMinElement()); 204 VIXL_CHECK(set.GetMinElement() == Obj(-(max_index - 2), max_index - 2)); 205 206 set.clear(); 207 VIXL_CHECK(set.empty() && (set.size() == 0)); 208} 209 210 211TEST(iterator) { 212 TestSet set; 213 VIXL_CHECK(set.empty() && (set.size() == 0)); 214 215 // Ensure that set.begin() == set.end() for the empty set. 216 VIXL_CHECK(set.begin() == set.end()); 217 218 // Test with only preallocated elements in the set. 219 size_t expected_total = 0; 220 for (unsigned i = 0; i < kNPreallocatedElements; i++) { 221 set.insert(Obj(i, i)); 222 expected_total += i; 223 } 224 225 size_t size = 0; 226 size_t total = 0; 227 for (InvalSetIterator<TestSet> it = set.begin(); it != set.end(); ++it) { 228 total += it->val_; 229 size++; 230 } 231 VIXL_CHECK(size == set.size()); 232 VIXL_CHECK(total == expected_total); 233 234 // Test with more elements. 235 for (unsigned i = kNPreallocatedElements; i < 4 * kNPreallocatedElements; 236 i++) { 237 set.insert(Obj(i, i)); 238 expected_total += i; 239 } 240 241 size = 0; 242 total = 0; 243 for (InvalSetIterator<TestSet> it = set.begin(); it != set.end(); ++it) { 244 total += it->val_; 245 size++; 246 } 247 VIXL_CHECK(size == set.size()); 248 VIXL_CHECK(total == expected_total); 249 250 // Test after elements have been deleted. 251 // - Select an interesting list of elements to erase. 252 std::vector<Obj> to_erase; 253 unsigned step = 0; 254 for (unsigned i = 0; i < set.size(); i += step, step++) { 255 to_erase.push_back(Obj(i, i)); 256 } 257 to_erase.push_back(Obj(set.size() - 1, set.size() - 1)); // The last element. 258 to_erase.push_back(Obj(set.size(), set.size())); // Not in the set. 259 260 // - Erase one at a time, retesting after each one. 261 while (!to_erase.empty()) { 262 size_t erased = set.erase(to_erase.back()); 263 if (erased > 0) { 264 VIXL_CHECK(erased == 1); 265 expected_total -= to_erase.back().val_; 266 } else { 267 } 268 to_erase.pop_back(); 269 270 size = 0; 271 total = 0; 272 for (InvalSetIterator<TestSet> it = set.begin(); it != set.end(); ++it) { 273 total += it->val_; 274 size++; 275 } 276 VIXL_CHECK(size == set.size()); 277 VIXL_CHECK(total == expected_total); 278 } 279} 280 281 282#if __cplusplus >= 201103L 283TEST(iterator_cxx11) { 284 TestSet set; 285 VIXL_CHECK(set.empty() && (set.size() == 0)); 286 287 // Test with only preallocated elements in the set. 288 size_t expected_total = 0; 289 for (unsigned i = 0; i < kNPreallocatedElements; i++) { 290 set.insert(Obj(i, i)); 291 expected_total += i; 292 } 293 294 size_t size = 0; 295 size_t total = 0; 296 for (auto object : set) { 297 total += object.val_; 298 size++; 299 } 300 VIXL_CHECK(size == set.size()); 301 VIXL_CHECK(total == expected_total); 302 303 // Test with more elements. 304 for (unsigned i = kNPreallocatedElements; i < 4 * kNPreallocatedElements; 305 i++) { 306 set.insert(Obj(i, i)); 307 expected_total += i; 308 } 309 310 size = 0; 311 total = 0; 312 for (auto object : set) { 313 total += object.val_; 314 size++; 315 } 316 VIXL_CHECK(size == set.size()); 317 VIXL_CHECK(total == expected_total); 318 319 // Test after elements have been deleted. 320 // - Select an interesting list of elements to erase. 321 std::vector<Obj> to_erase; 322 unsigned step = 0; 323 for (unsigned i = 0; i < set.size(); i += step, step++) { 324 to_erase.push_back(Obj(i, i)); 325 } 326 to_erase.push_back(Obj(set.size() - 1, set.size() - 1)); // The last element. 327 to_erase.push_back(Obj(set.size(), set.size())); // Not in the set. 328 329 // - Erase one at a time, retesting after each one. 330 while (!to_erase.empty()) { 331 size_t erased = set.erase(to_erase.back()); 332 if (erased > 0) { 333 VIXL_CHECK(erased == 1); 334 expected_total -= to_erase.back().val_; 335 } else { 336 } 337 to_erase.pop_back(); 338 339 size = 0; 340 total = 0; 341 for (auto object : set) { 342 total += object.val_; 343 size++; 344 } 345 VIXL_CHECK(size == set.size()); 346 VIXL_CHECK(total == expected_total); 347 } 348} 349#endif 350 351 352TEST(stl_forward_iterator) { 353 { 354 TestSet::iterator default_it; // Default-constructible. 355 TestSet::iterator copy_it(default_it); // Copy-constructible. 356 copy_it = default_it; // Copy-assignable. 357 } // Destructible. 358 359 TestSet set1; 360 VIXL_CHECK(set1.empty() && (set1.size() == 0)); 361 362 TestSet set2; 363 VIXL_CHECK(set2.empty() && (set2.size() == 0)); 364 365 // Test with only preallocated elements in the set. 366 for (unsigned i = 0; i < kNPreallocatedElements; i++) { 367 set1.insert(Obj(i, 1)); 368 set2.insert(Obj(i, 2)); 369 } 370 371 TestSet::iterator it1_a = set1.begin(); 372 TestSet::iterator it1_b = set1.begin(); 373 374 // Incrementable (whilst valid). 375 it1_a++; 376 ++it1_b; 377 378 // Testable for equivalence. 379 VIXL_CHECK(it1_a == it1_b); 380 VIXL_CHECK(set1.begin() != set1.end()); 381 VIXL_CHECK(set2.begin() != set2.end()); 382 VIXL_CHECK(set1.begin() != set2.begin()); 383 VIXL_CHECK(set1.end() != set2.end()); 384 385 // Dereferencable. 386 VIXL_CHECK((*it1_a++).key_ == 1); 387 VIXL_CHECK(((*it1_a).key_ == 2) && ((*it1_a).val_ == 1)); 388 *it1_b = Obj(42, 1); 389 VIXL_CHECK((it1_b->key_ == 42) && (it1_b->val_ == 1)); 390 391#if __cplusplus >= 201103L 392 // Swappable. 393 std::swap(it1_a, it1_b); 394 VIXL_CHECK(it1_a->key_ == 42); 395 VIXL_CHECK(it1_b->key_ == 2); 396#endif 397} 398 399 400} // namespace vixl 401