251 lines
7.4 KiB
C++
251 lines
7.4 KiB
C++
// Copyright 2014, ARM Limited
|
|
// 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 "test-runner.h"
|
|
|
|
#include "vixl/invalset.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>::Key(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.min_element() == Obj(-123, 456));
|
|
|
|
set.erase(Obj(-123, 456));
|
|
VIXL_CHECK(set.min_element_key() == 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.min_element());
|
|
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.min_element() == Obj(-1, -1));
|
|
VIXL_CHECK(set.min_element_key() == -1);
|
|
VIXL_CHECK(set.min_element().key_ == set.min_element_key());
|
|
|
|
// 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.min_element() == Obj(-max_index, max_index));
|
|
VIXL_CHECK(set.min_element().key_ == set.min_element_key());
|
|
|
|
set.erase(Obj(0, 0));
|
|
VIXL_CHECK(set.min_element() == Obj(-max_index, max_index));
|
|
set.erase(set.min_element());
|
|
VIXL_CHECK(set.min_element() == 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));
|
|
|
|
// Test with only preallocated elements in the set.
|
|
for (unsigned i = 0; i < kNPreallocatedElements; i++) {
|
|
set.insert(Obj(i, i));
|
|
}
|
|
|
|
size_t size = 0;
|
|
for (InvalSetIterator<TestSet> it(&set); !it.Done(); it.Advance()) {
|
|
size++;
|
|
}
|
|
VIXL_CHECK(size == set.size());
|
|
|
|
// Test with more elements.
|
|
for (unsigned i = kNPreallocatedElements;
|
|
i < 4 * kNPreallocatedElements;
|
|
i++) {
|
|
set.insert(Obj(i, i));
|
|
}
|
|
|
|
size = 0;
|
|
for (InvalSetIterator<TestSet> it(&set); !it.Done(); it.Advance()) {
|
|
size++;
|
|
}
|
|
VIXL_CHECK(size == set.size());
|
|
|
|
// Test after an element has been deleted.
|
|
size = 0;
|
|
set.erase(Obj(0, 0));
|
|
for (InvalSetIterator<TestSet> it(&set); !it.Done(); it.Advance()) {
|
|
size++;
|
|
}
|
|
VIXL_CHECK(size == set.size());
|
|
}
|
|
|
|
} // namespace vixl
|