// Copyright 2014, VIXL authors
// All rights reserved.
//
// Redistribution and use in source and binary forms, with or without
// modification, are permitted provided that the following conditions are met:
//
// * Redistributions of source code must retain the above copyright notice,
// this list of conditions and the following disclaimer.
// * Redistributions in binary form must reproduce the above copyright notice,
// this list of conditions and the following disclaimer in the documentation
// and/or other materials provided with the distribution.
// * Neither the name of ARM Limited nor the names of its contributors may be
// used to endorse or promote products derived from this software without
// specific prior written permission.
//
// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS CONTRIBUTORS "AS IS" AND
// ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED
// WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE
// DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT OWNER OR CONTRIBUTORS BE LIABLE
// FOR ANY DIRECT, INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL
// DAMAGES (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR
// SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER
// CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY,
// OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
#include "invalset-vixl.h"
#include "test-runner.h"
namespace vixl {
// This file contains tests for the `InvalSet` and `InvalSetIterator` classes.
#define TEST(name) TEST_(INVALSET_##name)
typedef ptrdiff_t KeyType;
typedef ptrdiff_t ValType;
// We test with an object for which the key and the value are distinct.
class Obj {
public:
Obj() {}
Obj(KeyType key, ValType val) : key_(key), val_(val) {}
KeyType key_;
ValType val_;
bool operator==(const Obj& other) const {
return (key_ == other.key_) && (val_ == other.val_);
}
bool operator<(const Obj& other) const {
return (key_ < other.key_) || ((key_ == other.key_) && (val_ < other.val_));
}
bool operator<=(const Obj& other) const {
return (key_ <= other.key_) ||
((key_ == other.key_) && (val_ <= other.val_));
}
bool operator>(const Obj& other) const {
return (key_ > other.key_) || ((key_ == other.key_) && (val_ > other.val_));
}
};
static const unsigned kNPreallocatedElements = 8;
static const KeyType kInvalidKey = PTRDIFF_MAX;
static const size_t kReclaimFrom = 1000;
static const unsigned kReclaimFactor = 10;
typedef InvalSet<Obj,
kNPreallocatedElements,
KeyType,
kInvalidKey,
kReclaimFrom,
kReclaimFactor> TestSet;
template <>
inline KeyType InvalSet<Obj,
kNPreallocatedElements,
KeyType,
kInvalidKey,
kReclaimFrom,
kReclaimFactor>::GetKey(const Obj& obj) {
return obj.key_;
}
template <>
inline void InvalSet<Obj,
kNPreallocatedElements,
KeyType,
kInvalidKey,
kReclaimFrom,
kReclaimFactor>::SetKey(Obj* obj, KeyType key) {
obj->key_ = key;
}
TEST(basic_test) {
TestSet set;
VIXL_CHECK(set.empty() && (set.size() == 0));
for (unsigned i = 0; i < kNPreallocatedElements; i++) {
set.insert(Obj(i, i));
}
VIXL_CHECK(set.size() == kNPreallocatedElements);
set.insert(Obj(-123, 456));
set.insert(Obj(2718, 2871828));
VIXL_CHECK(set.size() == kNPreallocatedElements + 2);
VIXL_CHECK(set.GetMinElement() == Obj(-123, 456));
set.erase(Obj(-123, 456));
VIXL_CHECK(set.GetMinElementKey() == 0);
set.clear();
VIXL_CHECK(set.empty() && (set.size() == 0));
}
TEST(valid_element) {
VIXL_CHECK(TestSet::IsValid(Obj(0, 0)));
VIXL_CHECK(TestSet::IsValid(Obj(-1, 0)));
VIXL_CHECK(TestSet::IsValid(Obj(kInvalidKey - 1, 0)));
VIXL_CHECK(!TestSet::IsValid(Obj(kInvalidKey, 0)));
}
TEST(insert) {
TestSet set;
VIXL_CHECK(set.empty() && (set.size() == 0));
for (unsigned i = 0; i < kNPreallocatedElements; i++) {
set.insert(Obj(i, i));
}
VIXL_CHECK(set.size() == kNPreallocatedElements);
set.insert(Obj(-123, 1));
VIXL_CHECK(set.size() == kNPreallocatedElements + 1);
set.insert(Obj(-123, 2));
set.insert(Obj(-123, 3));
VIXL_CHECK(set.size() == kNPreallocatedElements + 3);
set.clear();
VIXL_CHECK(set.empty() && (set.size() == 0));
}
TEST(erase) {
TestSet set;
VIXL_CHECK(set.empty() && (set.size() == 0));
// Test with only preallocated elements in the set.
VIXL_STATIC_ASSERT(kNPreallocatedElements >= 2);
set.insert(Obj(2718, 0));
set.erase(Obj(2718, 0));
VIXL_CHECK(set.empty() && (set.size() == 0));
set.insert(Obj(2718, 0));
VIXL_CHECK(set.size() == 1);
set.insert(Obj(2718, 1));
VIXL_CHECK(set.size() == 2);
set.erase(Obj(2718, 0));
VIXL_CHECK(set.size() == 1);
// Test with more elements.
for (unsigned i = 0; i < 100 * kNPreallocatedElements; i++) {
set.insert(Obj(i * i, i % 30));
set.insert(Obj(i, -1));
}
size_t max_size = set.size();
set.erase(Obj(100, -1));
VIXL_CHECK(set.size() == max_size - 1);
for (size_t i = 2; i <= max_size; i++) {
set.erase(set.GetMinElement());
VIXL_CHECK(set.size() == max_size - i);
}
VIXL_CHECK(set.empty() && (set.size() == 0));
}
TEST(min) {
TestSet set;
VIXL_CHECK(set.empty() && (set.size() == 0));
// Test with only preallocated elements in the set.
VIXL_STATIC_ASSERT(kNPreallocatedElements >= 4);
set.insert(Obj(-1, -1));
set.insert(Obj(-1, 0));
set.insert(Obj(0, 0));
set.insert(Obj(1, 0));
VIXL_CHECK(set.GetMinElement() == Obj(-1, -1));
VIXL_CHECK(set.GetMinElementKey() == -1);
VIXL_CHECK(set.GetMinElement().key_ == set.GetMinElementKey());
// Test with more elements.
set.clear();
int max_index = 100 * kNPreallocatedElements;
for (int i = 0; i <= max_index; i++) {
// Insert elements out of order.
int sign = ((i % 2) == 0) ? -1 : 1;
set.insert(Obj(sign * i, i));
}
VIXL_CHECK(set.GetMinElement() == Obj(-max_index, max_index));
VIXL_CHECK(set.GetMinElement().key_ == set.GetMinElementKey());
set.erase(Obj(0, 0));
VIXL_CHECK(set.GetMinElement() == Obj(-max_index, max_index));
set.erase(set.GetMinElement());
VIXL_CHECK(set.GetMinElement() == Obj(-(max_index - 2), max_index - 2));
set.clear();
VIXL_CHECK(set.empty() && (set.size() == 0));
}
TEST(iterator) {
TestSet set;
VIXL_CHECK(set.empty() && (set.size() == 0));
// Ensure that set.begin() == set.end() for the empty set.
VIXL_CHECK(set.begin() == set.end());
// Test with only preallocated elements in the set.
size_t expected_total = 0;
for (unsigned i = 0; i < kNPreallocatedElements; i++) {
set.insert(Obj(i, i));
expected_total += i;
}
size_t size = 0;
size_t total = 0;
for (InvalSetIterator<TestSet> it = set.begin(); it != set.end(); ++it) {
total += it->val_;
size++;
}
VIXL_CHECK(size == set.size());
VIXL_CHECK(total == expected_total);
// Test with more elements.
for (unsigned i = kNPreallocatedElements; i < 4 * kNPreallocatedElements;
i++) {
set.insert(Obj(i, i));
expected_total += i;
}
size = 0;
total = 0;
for (InvalSetIterator<TestSet> it = set.begin(); it != set.end(); ++it) {
total += it->val_;
size++;
}
VIXL_CHECK(size == set.size());
VIXL_CHECK(total == expected_total);
// Test after elements have been deleted.
// - Select an interesting list of elements to erase.
std::vector<Obj> to_erase;
unsigned step = 0;
for (unsigned i = 0; i < set.size(); i += step, step++) {
to_erase.push_back(Obj(i, i));
}
to_erase.push_back(Obj(set.size() - 1, set.size() - 1)); // The last element.
to_erase.push_back(Obj(set.size(), set.size())); // Not in the set.
// - Erase one at a time, retesting after each one.
while (!to_erase.empty()) {
size_t erased = set.erase(to_erase.back());
if (erased > 0) {
VIXL_CHECK(erased == 1);
expected_total -= to_erase.back().val_;
} else {
}
to_erase.pop_back();
size = 0;
total = 0;
for (InvalSetIterator<TestSet> it = set.begin(); it != set.end(); ++it) {
total += it->val_;
size++;
}
VIXL_CHECK(size == set.size());
VIXL_CHECK(total == expected_total);
}
}
#if __cplusplus >= 201103L
TEST(iterator_cxx11) {
TestSet set;
VIXL_CHECK(set.empty() && (set.size() == 0));
// Test with only preallocated elements in the set.
size_t expected_total = 0;
for (unsigned i = 0; i < kNPreallocatedElements; i++) {
set.insert(Obj(i, i));
expected_total += i;
}
size_t size = 0;
size_t total = 0;
for (auto object : set) {
total += object.val_;
size++;
}
VIXL_CHECK(size == set.size());
VIXL_CHECK(total == expected_total);
// Test with more elements.
for (unsigned i = kNPreallocatedElements; i < 4 * kNPreallocatedElements;
i++) {
set.insert(Obj(i, i));
expected_total += i;
}
size = 0;
total = 0;
for (auto object : set) {
total += object.val_;
size++;
}
VIXL_CHECK(size == set.size());
VIXL_CHECK(total == expected_total);
// Test after elements have been deleted.
// - Select an interesting list of elements to erase.
std::vector<Obj> to_erase;
unsigned step = 0;
for (unsigned i = 0; i < set.size(); i += step, step++) {
to_erase.push_back(Obj(i, i));
}
to_erase.push_back(Obj(set.size() - 1, set.size() - 1)); // The last element.
to_erase.push_back(Obj(set.size(), set.size())); // Not in the set.
// - Erase one at a time, retesting after each one.
while (!to_erase.empty()) {
size_t erased = set.erase(to_erase.back());
if (erased > 0) {
VIXL_CHECK(erased == 1);
expected_total -= to_erase.back().val_;
} else {
}
to_erase.pop_back();
size = 0;
total = 0;
for (auto object : set) {
total += object.val_;
size++;
}
VIXL_CHECK(size == set.size());
VIXL_CHECK(total == expected_total);
}
}
#endif
TEST(stl_forward_iterator) {
{
TestSet::iterator default_it; // Default-constructible.
TestSet::iterator copy_it(default_it); // Copy-constructible.
copy_it = default_it; // Copy-assignable.
} // Destructible.
TestSet set1;
VIXL_CHECK(set1.empty() && (set1.size() == 0));
TestSet set2;
VIXL_CHECK(set2.empty() && (set2.size() == 0));
// Test with only preallocated elements in the set.
for (unsigned i = 0; i < kNPreallocatedElements; i++) {
set1.insert(Obj(i, 1));
set2.insert(Obj(i, 2));
}
TestSet::iterator it1_a = set1.begin();
TestSet::iterator it1_b = set1.begin();
// Incrementable (whilst valid).
it1_a++;
++it1_b;
// Testable for equivalence.
VIXL_CHECK(it1_a == it1_b);
VIXL_CHECK(set1.begin() != set1.end());
VIXL_CHECK(set2.begin() != set2.end());
VIXL_CHECK(set1.begin() != set2.begin());
VIXL_CHECK(set1.end() != set2.end());
// Dereferencable.
VIXL_CHECK((*it1_a++).key_ == 1);
VIXL_CHECK(((*it1_a).key_ == 2) && ((*it1_a).val_ == 1));
*it1_b = Obj(42, 1);
VIXL_CHECK((it1_b->key_ == 42) && (it1_b->val_ == 1));
#if __cplusplus >= 201103L
// Swappable.
std::swap(it1_a, it1_b);
VIXL_CHECK(it1_a->key_ == 42);
VIXL_CHECK(it1_b->key_ == 2);
#endif
}
} // namespace vixl