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_tree.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 IntervalTree::Interval & a,const IntervalTree::Interval & b)32 inline bool operator==(const IntervalTree::Interval& a,
33 const IntervalTree::Interval& b) {
34 return std::tie(a.start, a.end, a.id) == std::tie(b.start, b.end, b.id);
35 }
36
37 namespace {
38
39 using Interval = IntervalTree::Interval;
40 using testing::IsEmpty;
41 using testing::UnorderedElementsAre;
42
CreateIntervals(std::vector<std::pair<uint32_t,uint32_t>> periods)43 std::vector<Interval> CreateIntervals(
44 std::vector<std::pair<uint32_t, uint32_t>> periods) {
45 std::vector<Interval> res;
46 uint32_t id = 0;
47 for (auto period : periods) {
48 res.push_back({period.first, period.second, id++});
49 }
50 return res;
51 }
52
TEST(IntervalTree,Trivial)53 TEST(IntervalTree, Trivial) {
54 std::vector<Interval> interval({{10, 20, 5}});
55 IntervalTree tree(interval);
56 std::vector<uint32_t> overlaps;
57 tree.FindOverlaps(5, 30, overlaps);
58
59 ASSERT_THAT(overlaps, UnorderedElementsAre(5));
60 }
61
TEST(IntervalTree,Simple)62 TEST(IntervalTree, Simple) {
63 auto intervals = CreateIntervals({{0, 10}, {5, 20}, {30, 40}});
64 IntervalTree tree(intervals);
65 std::vector<uint32_t> overlaps;
66 tree.FindOverlaps(4, 30, overlaps);
67
68 ASSERT_THAT(overlaps, UnorderedElementsAre(0, 1));
69 }
70
TEST(IntervalTree,SinglePointOverlap)71 TEST(IntervalTree, SinglePointOverlap) {
72 auto intervals = CreateIntervals({{10, 20}});
73 IntervalTree tree(intervals);
74 std::vector<uint32_t> overlaps;
75
76 // Overlaps at the start point only
77 tree.FindOverlaps(10, 10, overlaps);
78 ASSERT_THAT(overlaps, IsEmpty());
79
80 overlaps.clear();
81
82 // Overlaps at the end point only
83 tree.FindOverlaps(20, 20, overlaps);
84 ASSERT_THAT(overlaps, IsEmpty());
85 }
86
TEST(IntervalTree,NoOverlaps)87 TEST(IntervalTree, NoOverlaps) {
88 auto intervals = CreateIntervals({{10, 20}, {30, 40}});
89 IntervalTree tree(intervals);
90 std::vector<uint32_t> overlaps;
91
92 // Before all intervals
93 tree.FindOverlaps(5, 9, overlaps);
94 ASSERT_THAT(overlaps, IsEmpty());
95 overlaps.clear();
96
97 // Between intervals
98 tree.FindOverlaps(21, 29, overlaps);
99 ASSERT_THAT(overlaps, IsEmpty());
100 overlaps.clear();
101
102 // After all intervals
103 tree.FindOverlaps(41, 50, overlaps);
104 ASSERT_THAT(overlaps, IsEmpty());
105 }
106
TEST(IntervalTree,IdenticalIntervals)107 TEST(IntervalTree, IdenticalIntervals) {
108 auto intervals = CreateIntervals({{10, 20}, {10, 20}});
109 IntervalTree tree(intervals);
110 std::vector<uint32_t> overlaps;
111 tree.FindOverlaps(10, 20, overlaps);
112 ASSERT_THAT(overlaps, UnorderedElementsAre(0, 1));
113 }
114
TEST(IntervalTree,MultipleOverlapsVariousPositions)115 TEST(IntervalTree, MultipleOverlapsVariousPositions) {
116 auto intervals = CreateIntervals({{5, 15}, {10, 20}, {12, 22}, {25, 35}});
117 IntervalTree tree(intervals);
118
119 std::vector<uint32_t> overlaps;
120 /// Starts before, ends within
121 tree.FindOverlaps(9, 11, overlaps);
122 ASSERT_THAT(overlaps, UnorderedElementsAre(0, 1));
123
124 overlaps.clear();
125 // Starts within, ends within
126 tree.FindOverlaps(13, 21, overlaps);
127 ASSERT_THAT(overlaps, UnorderedElementsAre(0, 1, 2));
128
129 overlaps.clear();
130 // Starts within, ends after
131 tree.FindOverlaps(18, 26, overlaps);
132 ASSERT_THAT(overlaps, UnorderedElementsAre(1, 2, 3));
133 }
134
TEST(IntervalTree,OverlappingEndpoints)135 TEST(IntervalTree, OverlappingEndpoints) {
136 auto intervals = CreateIntervals({{10, 20}, {20, 30}});
137 IntervalTree tree(intervals);
138 std::vector<uint32_t> overlaps;
139
140 tree.FindOverlaps(19, 21, overlaps);
141 ASSERT_THAT(overlaps, UnorderedElementsAre(0, 1));
142 }
143
TEST(IntervalTree,Stress)144 TEST(IntervalTree, Stress) {
145 static constexpr size_t kCount = 9249;
146 std::minstd_rand0 rng(42);
147
148 std::vector<std::pair<uint32_t, uint32_t>> periods;
149 uint32_t prev_max = 0;
150 for (uint32_t i = 0; i < kCount; ++i) {
151 prev_max += static_cast<uint32_t>(rng()) % 100;
152 periods.push_back(
153 {prev_max, prev_max + (static_cast<uint32_t>(rng()) % 100)});
154 }
155 auto intervals = CreateIntervals(periods);
156 IntervalTree tree(intervals);
157 std::vector<uint32_t> overlaps;
158 tree.FindOverlaps(periods.front().first, periods.back().first + 1, overlaps);
159
160 EXPECT_EQ(overlaps.size(), kCount);
161 }
162
163 } // namespace
164 } // namespace perfetto::trace_processor
165