1 /* 2 * Copyright (c) 2016, Google Inc. 3 * All rights reserved. 4 * Use of this source code is governed by a BSD-style license that can be 5 * found in the LICENSE file. 6 */ 7 8 #ifndef PERFTOOLS_INTERVALMAP_TEST_H_ 9 #define PERFTOOLS_INTERVALMAP_TEST_H_ 10 11 #include <utility> 12 #include <vector> 13 14 #include "int_compat.h" 15 #include "intervalmap.h" 16 #include "string_compat.h" 17 #include "test_compat.h" 18 19 namespace perftools { 20 namespace { 21 22 class Command { 23 public: 24 virtual ~Command() {} 25 virtual void ExecuteOn(IntervalMap<string>* map) const = 0; 26 }; 27 28 class SetCommand : public Command { 29 public: 30 SetCommand(uint64 start, uint64 limit, const char* value) 31 : start_(start), limit_(limit), value_(value) {} 32 33 void ExecuteOn(IntervalMap<string>* map) const override { 34 map->Set(start_, limit_, value_); 35 } 36 37 private: 38 const uint64 start_; 39 const uint64 limit_; 40 const char* value_; 41 }; 42 43 class NumIntervalsCommand : public Command { 44 public: 45 explicit NumIntervalsCommand(uint64 expected) : expected_(expected) {} 46 47 void ExecuteOn(IntervalMap<string>* map) const override { 48 ASSERT_EQ(expected_, map->Size()); 49 } 50 51 private: 52 const uint64 expected_; 53 }; 54 55 class LookupCommand : public Command { 56 public: 57 LookupCommand(uint64 from, uint64 to, const char* expected) 58 : from_(from), to_(to), expected_(expected) {} 59 60 void ExecuteOn(IntervalMap<string>* map) const override { 61 for (uint64 key = from_; key <= to_; ++key) { 62 string result; 63 ASSERT_TRUE(map->Lookup(key, &result)) << "Did not find value for key: " 64 << key; 65 ASSERT_EQ(expected_, result) << "For key: " << key 66 << " Found value: " << result 67 << ". Expected: " << expected_; 68 } 69 } 70 71 private: 72 const uint64 from_; 73 const uint64 to_; 74 const char* expected_; 75 }; 76 77 class FailLookupCommand : public Command { 78 public: 79 explicit FailLookupCommand(std::vector<uint64> keys) 80 : keys_(std::move(keys)) {} 81 82 void ExecuteOn(IntervalMap<string>* map) const override { 83 string result; 84 for (auto key : keys_) { 85 ASSERT_FALSE(map->Lookup(key, &result)) << "Found value for key: " << key; 86 } 87 } 88 89 private: 90 std::vector<uint64> keys_; 91 }; 92 93 class FindNextCommand : public Command { 94 public: 95 FindNextCommand(uint64 key, uint64 expected_start, uint64 expected_limit, 96 const char* expected_value) 97 : key_(key), 98 expected_start_(expected_start), 99 expected_limit_(expected_limit), 100 expected_value_(expected_value) {} 101 102 void ExecuteOn(IntervalMap<string>* map) const override { 103 uint64 start; 104 uint64 limit; 105 string value; 106 ASSERT_TRUE(map->FindNext(key_, &start, &limit, &value)) 107 << "Did not find a next interval for key: " << key_; 108 bool matches_expected = expected_start_ == start && 109 expected_limit_ == limit && 110 expected_value_ == value; 111 ASSERT_TRUE(matches_expected) 112 << "Found incorrect interval for key: " << key_ << ". " 113 << "Expected start: " << expected_start_ << ". " 114 << "Expected limit: " << expected_start_ << ". " 115 << "Expected value: " << expected_value_ << ". " 116 << "Found start: " << start << ". " 117 << "Found limit: " << limit << ". " 118 << "Found value: " << value << ". "; 119 } 120 121 private: 122 uint64 key_; 123 uint64 expected_start_; 124 uint64 expected_limit_; 125 const char* expected_value_; 126 }; 127 128 class FailFindNextCommand : public Command { 129 public: 130 explicit FailFindNextCommand(uint64 key) : key_(key) {} 131 132 void ExecuteOn(IntervalMap<string>* map) const override { 133 uint64 start; 134 uint64 limit; 135 string value; 136 ASSERT_FALSE(map->FindNext(key_, &start, &limit, &value)) 137 << "Found interval for: " << key_ << ". " 138 << "start: " << start << ". " 139 << "limit: " << limit << ". " 140 << "value: " << value << ". " 141 << "Did not find a next interval for key: " << key_; 142 } 143 144 private: 145 uint64 key_; 146 }; 147 148 std::shared_ptr<Command> Set(uint64 start, uint64 limit, const char* value) { 149 return std::make_shared<SetCommand>(start, limit, value); 150 } 151 152 std::shared_ptr<Command> NumIntervals(uint64 size) { 153 return std::make_shared<NumIntervalsCommand>(size); 154 } 155 156 // Looks up every key in the interval [from, to] and expects them all to be 157 // equal to expected. 158 std::shared_ptr<Command> Lookup(uint64 from, uint64 to, const char* expected) { 159 return std::make_shared<LookupCommand>(from, to, expected); 160 } 161 162 std::shared_ptr<Command> FailLookup(std::vector<uint64> keys) { 163 return std::make_shared<FailLookupCommand>(keys); 164 } 165 166 std::shared_ptr<Command> FindNext(uint64 key, uint64 start, uint64 limit, 167 const char* expected) { 168 return std::make_shared<FindNextCommand>(key, start, limit, expected); 169 } 170 171 std::shared_ptr<Command> FailFindNext(uint64 key) { 172 return std::make_shared<FailFindNextCommand>(key); 173 } 174 175 class IntervalMapTest 176 : public ::testing::TestWithParam<std::vector<std::shared_ptr<Command>>> {}; 177 178 const std::vector<std::shared_ptr<Command>> tests[] = { 179 { 180 // Simple set/lookup 181 Set(0, 10, "Added"), NumIntervals(1), Lookup(0, 9, "Added"), 182 FailLookup({10, 11}), 183 }, 184 { 185 // Total overwrite same start 186 Set(5, 10, "Added"), Set(5, 20, "Overwrite"), NumIntervals(1), 187 Lookup(5, 19, "Overwrite"), FailLookup({3, 4, 20, 21}), 188 }, 189 { 190 // No overwrite, start of one equals limit of other 191 Set(5, 10, "Segment 1"), Set(10, 20, "Segment 2"), NumIntervals(2), 192 Lookup(5, 9, "Segment 1"), Lookup(10, 19, "Segment 2"), 193 FailLookup({3, 4, 20, 21}), 194 }, 195 { 196 // Right side overwrite 197 Set(5, 10, "Added"), Set(8, 12, "Overwrite"), NumIntervals(2), 198 Lookup(5, 7, "Added"), Lookup(8, 11, "Overwrite"), 199 FailLookup({3, 4, 12, 13}), 200 }, 201 { 202 // Left side overwrite 203 Set(5, 10, "Added"), Set(3, 8, "Overwrite"), NumIntervals(2), 204 Lookup(8, 9, "Added"), Lookup(3, 7, "Overwrite"), 205 FailLookup({1, 2, 12, 13}), 206 }, 207 { 208 // Total overwrite 209 Set(5, 10, "Added"), Set(3, 12, "Overwrite"), NumIntervals(1), 210 Lookup(3, 11, "Overwrite"), FailLookup({1, 2, 12, 13}), 211 }, 212 { 213 // Internal overwrite 214 Set(4, 11, "Added"), Set(6, 9, "Overwrite"), NumIntervals(3), 215 Lookup(4, 5, "Added"), Lookup(6, 8, "Overwrite"), 216 Lookup(9, 10, "Added"), FailLookup({2, 3, 11, 12}), 217 }, 218 { 219 // Exact overwrite 220 Set(5, 10, "Added"), Set(5, 10, "Overwrite"), NumIntervals(1), 221 Lookup(5, 9, "Overwrite"), FailLookup({3, 4, 10, 11}), 222 }, 223 { 224 // Same left side overwrite 225 Set(5, 10, "Added"), Set(5, 8, "Overwrite"), NumIntervals(2), 226 Lookup(5, 7, "Overwrite"), Lookup(8, 9, "Added"), 227 FailLookup({3, 4, 10, 11}), 228 }, 229 { 230 // Multiple total overwrite 231 Set(5, 10, "SEG 1"), Set(8, 12, "SEG 2"), Set(16, 22, "SEG 3"), 232 Set(25, 26, "SEG 4"), Set(3, 30, "Overwrite"), NumIntervals(1), 233 Lookup(3, 29, "Overwrite"), FailLookup({1, 2, 30, 31}), 234 }, 235 { 236 // Multiple total overwrite, left side free 237 Set(5, 10, "SEG 1"), Set(8, 12, "SEG 2"), Set(16, 22, "SEG 3"), 238 Set(25, 26, "SEG 4"), Set(7, 30, "Overwrite"), NumIntervals(2), 239 Lookup(5, 6, "SEG 1"), Lookup(7, 29, "Overwrite"), 240 FailLookup({3, 4, 30, 31}), 241 }, 242 { 243 // Multiple total overwrite, right side free 244 Set(5, 10, "SEG 1"), Set(8, 12, "SEG 2"), Set(16, 22, "SEG 3"), 245 Set(25, 32, "SEG 4"), Set(3, 30, "Overwrite"), NumIntervals(2), 246 Lookup(3, 29, "Overwrite"), Lookup(30, 31, "SEG 4"), 247 FailLookup({1, 2, 32, 33}), 248 }, 249 { 250 // Multiple total overwrite, both sides free 251 Set(5, 10, "SEG 1"), Set(8, 12, "SEG 2"), Set(16, 22, "SEG 3"), 252 Set(25, 32, "SEG 4"), Set(7, 30, "Overwrite"), NumIntervals(3), 253 Lookup(5, 6, "SEG 1"), Lookup(7, 29, "Overwrite"), 254 Lookup(30, 31, "SEG 4"), FailLookup({3, 4, 32, 33}), 255 }, 256 { 257 // Two segments partly overwritten 258 Set(5, 10, "SEG 1"), Set(17, 25, "SEG 2"), Set(8, 20, "Overwrite"), 259 NumIntervals(3), Lookup(5, 7, "SEG 1"), Lookup(8, 19, "Overwrite"), 260 Lookup(20, 24, "SEG 2"), FailLookup({3, 4, 25, 26}), 261 }, 262 { 263 // Loop through interval map using FindNext 264 Set(5, 10, "SEG 1"), Set(15, 20, "SEG 2"), FindNext(0, 5, 10, "SEG 1"), 265 FindNext(10, 15, 20, "SEG 2"), FailFindNext(20), 266 }, 267 }; 268 269 TEST_P(IntervalMapTest, GenericTest) { 270 IntervalMap<string> map; 271 const auto& commands = GetParam(); 272 for (const auto& command : commands) { 273 command->ExecuteOn(&map); 274 // Failed asserts in subroutines aren't actually fatal so we have to return 275 // manually. 276 if (HasFatalFailure()) return; 277 } 278 } 279 280 INSTANTIATE_TEST_CASE_P(AllIntervalMapTests, IntervalMapTest, 281 ::testing::ValuesIn(tests)); 282 283 } // namespace 284 } // namespace perftools 285 286 int main(int argc, char** argv) { 287 ::testing::InitGoogleTest(&argc, argv); 288 return RUN_ALL_TESTS(); 289 } 290 291 #endif // PERFTOOLS_INTERVALMAP_TEST_H_ 292
