| /* |
| * 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_ |