/*
|
* Copyright (c) 2016, Google Inc.
|
* All rights reserved.
|
* Use of this source code is governed by a BSD-style license that can be
|
* found in the LICENSE file.
|
*/
|
|
#ifndef PERFTOOLS_INTERVALMAP_TEST_H_
|
#define PERFTOOLS_INTERVALMAP_TEST_H_
|
|
#include <utility>
|
#include <vector>
|
|
#include "int_compat.h"
|
#include "intervalmap.h"
|
#include "string_compat.h"
|
#include "test_compat.h"
|
|
namespace perftools {
|
namespace {
|
|
class Command {
|
public:
|
virtual ~Command() {}
|
virtual void ExecuteOn(IntervalMap<string>* map) const = 0;
|
};
|
|
class SetCommand : public Command {
|
public:
|
SetCommand(uint64 start, uint64 limit, const char* value)
|
: start_(start), limit_(limit), value_(value) {}
|
|
void ExecuteOn(IntervalMap<string>* map) const override {
|
map->Set(start_, limit_, value_);
|
}
|
|
private:
|
const uint64 start_;
|
const uint64 limit_;
|
const char* value_;
|
};
|
|
class NumIntervalsCommand : public Command {
|
public:
|
explicit NumIntervalsCommand(uint64 expected) : expected_(expected) {}
|
|
void ExecuteOn(IntervalMap<string>* map) const override {
|
ASSERT_EQ(expected_, map->Size());
|
}
|
|
private:
|
const uint64 expected_;
|
};
|
|
class LookupCommand : public Command {
|
public:
|
LookupCommand(uint64 from, uint64 to, const char* expected)
|
: from_(from), to_(to), expected_(expected) {}
|
|
void ExecuteOn(IntervalMap<string>* map) const override {
|
for (uint64 key = from_; key <= to_; ++key) {
|
string result;
|
ASSERT_TRUE(map->Lookup(key, &result)) << "Did not find value for key: "
|
<< key;
|
ASSERT_EQ(expected_, result) << "For key: " << key
|
<< " Found value: " << result
|
<< ". Expected: " << expected_;
|
}
|
}
|
|
private:
|
const uint64 from_;
|
const uint64 to_;
|
const char* expected_;
|
};
|
|
class FailLookupCommand : public Command {
|
public:
|
explicit FailLookupCommand(std::vector<uint64> keys)
|
: keys_(std::move(keys)) {}
|
|
void ExecuteOn(IntervalMap<string>* map) const override {
|
string result;
|
for (auto key : keys_) {
|
ASSERT_FALSE(map->Lookup(key, &result)) << "Found value for key: " << key;
|
}
|
}
|
|
private:
|
std::vector<uint64> keys_;
|
};
|
|
class FindNextCommand : public Command {
|
public:
|
FindNextCommand(uint64 key, uint64 expected_start, uint64 expected_limit,
|
const char* expected_value)
|
: key_(key),
|
expected_start_(expected_start),
|
expected_limit_(expected_limit),
|
expected_value_(expected_value) {}
|
|
void ExecuteOn(IntervalMap<string>* map) const override {
|
uint64 start;
|
uint64 limit;
|
string value;
|
ASSERT_TRUE(map->FindNext(key_, &start, &limit, &value))
|
<< "Did not find a next interval for key: " << key_;
|
bool matches_expected = expected_start_ == start &&
|
expected_limit_ == limit &&
|
expected_value_ == value;
|
ASSERT_TRUE(matches_expected)
|
<< "Found incorrect interval for key: " << key_ << ". "
|
<< "Expected start: " << expected_start_ << ". "
|
<< "Expected limit: " << expected_start_ << ". "
|
<< "Expected value: " << expected_value_ << ". "
|
<< "Found start: " << start << ". "
|
<< "Found limit: " << limit << ". "
|
<< "Found value: " << value << ". ";
|
}
|
|
private:
|
uint64 key_;
|
uint64 expected_start_;
|
uint64 expected_limit_;
|
const char* expected_value_;
|
};
|
|
class FailFindNextCommand : public Command {
|
public:
|
explicit FailFindNextCommand(uint64 key) : key_(key) {}
|
|
void ExecuteOn(IntervalMap<string>* map) const override {
|
uint64 start;
|
uint64 limit;
|
string value;
|
ASSERT_FALSE(map->FindNext(key_, &start, &limit, &value))
|
<< "Found interval for: " << key_ << ". "
|
<< "start: " << start << ". "
|
<< "limit: " << limit << ". "
|
<< "value: " << value << ". "
|
<< "Did not find a next interval for key: " << key_;
|
}
|
|
private:
|
uint64 key_;
|
};
|
|
std::shared_ptr<Command> Set(uint64 start, uint64 limit, const char* value) {
|
return std::make_shared<SetCommand>(start, limit, value);
|
}
|
|
std::shared_ptr<Command> NumIntervals(uint64 size) {
|
return std::make_shared<NumIntervalsCommand>(size);
|
}
|
|
// Looks up every key in the interval [from, to] and expects them all to be
|
// equal to expected.
|
std::shared_ptr<Command> Lookup(uint64 from, uint64 to, const char* expected) {
|
return std::make_shared<LookupCommand>(from, to, expected);
|
}
|
|
std::shared_ptr<Command> FailLookup(std::vector<uint64> keys) {
|
return std::make_shared<FailLookupCommand>(keys);
|
}
|
|
std::shared_ptr<Command> FindNext(uint64 key, uint64 start, uint64 limit,
|
const char* expected) {
|
return std::make_shared<FindNextCommand>(key, start, limit, expected);
|
}
|
|
std::shared_ptr<Command> FailFindNext(uint64 key) {
|
return std::make_shared<FailFindNextCommand>(key);
|
}
|
|
class IntervalMapTest
|
: public ::testing::TestWithParam<std::vector<std::shared_ptr<Command>>> {};
|
|
const std::vector<std::shared_ptr<Command>> tests[] = {
|
{
|
// Simple set/lookup
|
Set(0, 10, "Added"), NumIntervals(1), Lookup(0, 9, "Added"),
|
FailLookup({10, 11}),
|
},
|
{
|
// Total overwrite same start
|
Set(5, 10, "Added"), Set(5, 20, "Overwrite"), NumIntervals(1),
|
Lookup(5, 19, "Overwrite"), FailLookup({3, 4, 20, 21}),
|
},
|
{
|
// No overwrite, start of one equals limit of other
|
Set(5, 10, "Segment 1"), Set(10, 20, "Segment 2"), NumIntervals(2),
|
Lookup(5, 9, "Segment 1"), Lookup(10, 19, "Segment 2"),
|
FailLookup({3, 4, 20, 21}),
|
},
|
{
|
// Right side overwrite
|
Set(5, 10, "Added"), Set(8, 12, "Overwrite"), NumIntervals(2),
|
Lookup(5, 7, "Added"), Lookup(8, 11, "Overwrite"),
|
FailLookup({3, 4, 12, 13}),
|
},
|
{
|
// Left side overwrite
|
Set(5, 10, "Added"), Set(3, 8, "Overwrite"), NumIntervals(2),
|
Lookup(8, 9, "Added"), Lookup(3, 7, "Overwrite"),
|
FailLookup({1, 2, 12, 13}),
|
},
|
{
|
// Total overwrite
|
Set(5, 10, "Added"), Set(3, 12, "Overwrite"), NumIntervals(1),
|
Lookup(3, 11, "Overwrite"), FailLookup({1, 2, 12, 13}),
|
},
|
{
|
// Internal overwrite
|
Set(4, 11, "Added"), Set(6, 9, "Overwrite"), NumIntervals(3),
|
Lookup(4, 5, "Added"), Lookup(6, 8, "Overwrite"),
|
Lookup(9, 10, "Added"), FailLookup({2, 3, 11, 12}),
|
},
|
{
|
// Exact overwrite
|
Set(5, 10, "Added"), Set(5, 10, "Overwrite"), NumIntervals(1),
|
Lookup(5, 9, "Overwrite"), FailLookup({3, 4, 10, 11}),
|
},
|
{
|
// Same left side overwrite
|
Set(5, 10, "Added"), Set(5, 8, "Overwrite"), NumIntervals(2),
|
Lookup(5, 7, "Overwrite"), Lookup(8, 9, "Added"),
|
FailLookup({3, 4, 10, 11}),
|
},
|
{
|
// Multiple total overwrite
|
Set(5, 10, "SEG 1"), Set(8, 12, "SEG 2"), Set(16, 22, "SEG 3"),
|
Set(25, 26, "SEG 4"), Set(3, 30, "Overwrite"), NumIntervals(1),
|
Lookup(3, 29, "Overwrite"), FailLookup({1, 2, 30, 31}),
|
},
|
{
|
// Multiple total overwrite, left side free
|
Set(5, 10, "SEG 1"), Set(8, 12, "SEG 2"), Set(16, 22, "SEG 3"),
|
Set(25, 26, "SEG 4"), Set(7, 30, "Overwrite"), NumIntervals(2),
|
Lookup(5, 6, "SEG 1"), Lookup(7, 29, "Overwrite"),
|
FailLookup({3, 4, 30, 31}),
|
},
|
{
|
// Multiple total overwrite, right side free
|
Set(5, 10, "SEG 1"), Set(8, 12, "SEG 2"), Set(16, 22, "SEG 3"),
|
Set(25, 32, "SEG 4"), Set(3, 30, "Overwrite"), NumIntervals(2),
|
Lookup(3, 29, "Overwrite"), Lookup(30, 31, "SEG 4"),
|
FailLookup({1, 2, 32, 33}),
|
},
|
{
|
// Multiple total overwrite, both sides free
|
Set(5, 10, "SEG 1"), Set(8, 12, "SEG 2"), Set(16, 22, "SEG 3"),
|
Set(25, 32, "SEG 4"), Set(7, 30, "Overwrite"), NumIntervals(3),
|
Lookup(5, 6, "SEG 1"), Lookup(7, 29, "Overwrite"),
|
Lookup(30, 31, "SEG 4"), FailLookup({3, 4, 32, 33}),
|
},
|
{
|
// Two segments partly overwritten
|
Set(5, 10, "SEG 1"), Set(17, 25, "SEG 2"), Set(8, 20, "Overwrite"),
|
NumIntervals(3), Lookup(5, 7, "SEG 1"), Lookup(8, 19, "Overwrite"),
|
Lookup(20, 24, "SEG 2"), FailLookup({3, 4, 25, 26}),
|
},
|
{
|
// Loop through interval map using FindNext
|
Set(5, 10, "SEG 1"), Set(15, 20, "SEG 2"), FindNext(0, 5, 10, "SEG 1"),
|
FindNext(10, 15, 20, "SEG 2"), FailFindNext(20),
|
},
|
};
|
|
TEST_P(IntervalMapTest, GenericTest) {
|
IntervalMap<string> map;
|
const auto& commands = GetParam();
|
for (const auto& command : commands) {
|
command->ExecuteOn(&map);
|
// Failed asserts in subroutines aren't actually fatal so we have to return
|
// manually.
|
if (HasFatalFailure()) return;
|
}
|
}
|
|
INSTANTIATE_TEST_CASE_P(AllIntervalMapTests, IntervalMapTest,
|
::testing::ValuesIn(tests));
|
|
} // namespace
|
} // namespace perftools
|
|
int main(int argc, char** argv) {
|
::testing::InitGoogleTest(&argc, argv);
|
return RUN_ALL_TESTS();
|
}
|
|
#endif // PERFTOOLS_INTERVALMAP_TEST_H_
|
