1 /*
2 * Copyright (C) 2024 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "src/trace_processor/containers/interval_intersector.h"
18
19 #include <cstddef>
20 #include <cstdint>
21 #include <numeric>
22 #include <random>
23 #include <tuple>
24 #include <utility>
25 #include <vector>
26
27 #include "perfetto/base/compiler.h"
28 #include "test/gtest_and_gmock.h"
29
30 namespace perfetto::trace_processor {
31
operator ==(const Interval & a,const Interval & b)32 inline bool operator==(const Interval& a, const Interval& b) {
33 return std::tie(a.start, a.end, a.id) == std::tie(b.start, b.end, b.id);
34 }
35
36 namespace {
37
38 using Interval = Interval;
39 using testing::IsEmpty;
40 using testing::UnorderedElementsAre;
41
CreateIntervals(std::vector<std::pair<uint32_t,uint32_t>> periods)42 std::vector<Interval> CreateIntervals(
43 std::vector<std::pair<uint32_t, uint32_t>> periods) {
44 std::vector<Interval> res;
45 uint32_t id = 0;
46 for (auto period : periods) {
47 res.push_back({period.first, period.second, id++});
48 }
49 return res;
50 }
51
TEST(IntervalIntersector,IntervalTree_EmptyInput)52 TEST(IntervalIntersector, IntervalTree_EmptyInput) {
53 std::vector<Interval> intervals;
54 IntervalIntersector intersector(intervals,
55 IntervalIntersector::kIntervalTree);
56 std::vector<Id> overlaps;
57 intersector.FindOverlaps(0, 10, overlaps);
58 EXPECT_THAT(overlaps, IsEmpty());
59 }
60
TEST(IntervalIntersector,IntervalTree_SingleIntervalFullOverlap)61 TEST(IntervalIntersector, IntervalTree_SingleIntervalFullOverlap) {
62 auto intervals = CreateIntervals({{5, 15}});
63 IntervalIntersector intersector(intervals,
64 IntervalIntersector::kIntervalTree);
65 std::vector<Id> overlaps;
66 intersector.FindOverlaps(0, 20, overlaps);
67 EXPECT_THAT(overlaps, UnorderedElementsAre(0));
68 }
69
TEST(IntervalIntersector,IntervalTree_MultipleOverlaps)70 TEST(IntervalIntersector, IntervalTree_MultipleOverlaps) {
71 auto intervals = CreateIntervals({{0, 10}, {5, 15}, {20, 30}});
72 IntervalIntersector intersector(intervals,
73 IntervalIntersector::kIntervalTree);
74 std::vector<Id> overlaps;
75 intersector.FindOverlaps(8, 25, overlaps);
76 EXPECT_THAT(overlaps, UnorderedElementsAre(0, 1, 2));
77 }
78
TEST(IntervalIntersector,IntervalTree_NoOverlap)79 TEST(IntervalIntersector, IntervalTree_NoOverlap) {
80 auto intervals = CreateIntervals({{0, 5}, {10, 15}});
81 IntervalIntersector intersector(intervals,
82 IntervalIntersector::kIntervalTree);
83 std::vector<Id> overlaps;
84 intersector.FindOverlaps(6, 9, overlaps);
85 EXPECT_THAT(overlaps, IsEmpty());
86 }
87
88 // Tests for kBinarySearch Mode
89
TEST(IntervalIntersector,BinarySearch_EmptyInput)90 TEST(IntervalIntersector, BinarySearch_EmptyInput) {
91 std::vector<Interval> intervals;
92 IntervalIntersector intersector(intervals,
93 IntervalIntersector::kBinarySearch);
94 std::vector<Id> overlaps;
95 intersector.FindOverlaps(0, 10, overlaps);
96 EXPECT_THAT(overlaps, IsEmpty());
97 }
98
TEST(IntervalIntersector,BinarySearch_SingleIntervalFullOverlap)99 TEST(IntervalIntersector, BinarySearch_SingleIntervalFullOverlap) {
100 auto intervals = CreateIntervals({{5, 15}});
101 IntervalIntersector intersector(intervals,
102 IntervalIntersector::kBinarySearch);
103 std::vector<Id> overlaps;
104 intersector.FindOverlaps(0, 20, overlaps);
105 EXPECT_THAT(overlaps, UnorderedElementsAre(0));
106 }
107
TEST(IntervalIntersector,BinarySearch_MultipleOverlaps)108 TEST(IntervalIntersector, BinarySearch_MultipleOverlaps) {
109 auto intervals =
110 CreateIntervals({{0, 5}, {10, 15}, {20, 25}}); // Non-overlapping
111 IntervalIntersector intersector(intervals,
112 IntervalIntersector::kBinarySearch);
113 std::vector<Id> overlaps;
114 intersector.FindOverlaps(3, 22, overlaps);
115 EXPECT_THAT(overlaps, UnorderedElementsAre(0, 1, 2));
116 }
117
TEST(IntervalIntersector,BinarySearch_NoOverlap)118 TEST(IntervalIntersector, BinarySearch_NoOverlap) {
119 auto intervals = CreateIntervals({{0, 5}, {10, 15}});
120 IntervalIntersector intersector(intervals,
121 IntervalIntersector::kBinarySearch);
122 std::vector<Id> overlaps;
123 intersector.FindOverlaps(6, 9, overlaps);
124 EXPECT_THAT(overlaps, IsEmpty());
125 }
126
127 // Tests for kLinearScan Mode
128
TEST(IntervalIntersector,LinearScan_EmptyInput)129 TEST(IntervalIntersector, LinearScan_EmptyInput) {
130 std::vector<Interval> intervals;
131 IntervalIntersector intersector(intervals, IntervalIntersector::kLinearScan);
132 std::vector<Id> overlaps;
133 intersector.FindOverlaps(0, 10, overlaps);
134 EXPECT_THAT(overlaps, IsEmpty());
135 }
136
TEST(IntervalIntersector,LinearScan_SingleIntervalFullOverlap)137 TEST(IntervalIntersector, LinearScan_SingleIntervalFullOverlap) {
138 auto intervals = CreateIntervals({{5, 15}});
139 IntervalIntersector intersector(intervals, IntervalIntersector::kLinearScan);
140 std::vector<Id> overlaps;
141 intersector.FindOverlaps(0, 20, overlaps);
142 EXPECT_THAT(overlaps, UnorderedElementsAre(0));
143 }
144
TEST(IntervalIntersector,LinearScan_MultipleOverlaps)145 TEST(IntervalIntersector, LinearScan_MultipleOverlaps) {
146 auto intervals = CreateIntervals({{0, 10}, {5, 15}, {20, 30}});
147 IntervalIntersector intersector(intervals, IntervalIntersector::kLinearScan);
148 std::vector<Id> overlaps;
149 intersector.FindOverlaps(8, 25, overlaps);
150 EXPECT_THAT(overlaps, UnorderedElementsAre(0, 1, 2));
151 }
152
TEST(IntervalIntersector,LinearScan_NoOverlap)153 TEST(IntervalIntersector, LinearScan_NoOverlap) {
154 auto intervals = CreateIntervals({{0, 5}, {10, 15}});
155 IntervalIntersector intersector(intervals, IntervalIntersector::kLinearScan);
156 std::vector<Id> overlaps;
157 intersector.FindOverlaps(6, 9, overlaps);
158 EXPECT_THAT(overlaps, IsEmpty());
159 }
160
161 } // namespace
162 } // namespace perfetto::trace_processor
163