1//===-- RangeTest.cpp -----------------------------------------------------===//
2//
3// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4// See https://llvm.org/LICENSE.txt for license information.
5// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6//
7//===----------------------------------------------------------------------===//
8
9#include "lldb/Utility/RangeMap.h"
10#include "gmock/gmock.h"
11#include "gtest/gtest.h"
12
13using namespace lldb_private;
14
15TEST(RangeVector, CombineConsecutiveRanges) {
16 using RangeVector = RangeVector<uint32_t, uint32_t>;
17 using Entry = RangeVector::Entry;
18
19 RangeVector V;
20 V.Append(base: 0, size: 1);
21 V.Append(base: 5, size: 1);
22 V.Append(base: 6, size: 1);
23 V.Append(base: 10, size: 9);
24 V.Append(base: 15, size: 1);
25 V.Append(base: 20, size: 9);
26 V.Append(base: 21, size: 9);
27 V.Sort();
28 V.CombineConsecutiveRanges();
29 EXPECT_THAT(V, testing::ElementsAre(Entry(0, 1), Entry(5, 2), Entry(10, 9),
30 Entry(20, 10)));
31
32 V.Clear();
33 V.Append(base: 0, size: 20);
34 V.Append(base: 5, size: 1);
35 V.Append(base: 10, size: 1);
36 V.Sort();
37 V.CombineConsecutiveRanges();
38 EXPECT_THAT(V, testing::ElementsAre(Entry(0, 20)));
39}
40
41TEST(RangeVector, GetOverlaps) {
42 using RangeVector = RangeVector<uint32_t, uint32_t>;
43
44 RangeVector V1;
45 RangeVector V2;
46 RangeVector Expected;
47 // same range
48 V1.Append(base: 0, size: 1);
49 V2.Append(base: 0, size: 1);
50 Expected.Append(base: 0, size: 1);
51
52 // no overlap
53 V1.Append(base: 2, size: 2);
54 V2.Append(base: 4, size: 1);
55
56 // same base overlap
57 V1.Append(base: 10, size: 5);
58 V2.Append(base: 10, size: 3);
59 Expected.Append(base: 10, size: 3);
60
61 // same end overlap
62 V1.Append(base: 27, size: 1);
63 V2.Append(base: 20, size: 8);
64 Expected.Append(base: 27, size: 1);
65
66 // smaller base overlap
67 V1.Append(base: 33, size: 4);
68 V2.Append(base: 30, size: 5);
69 Expected.Append(base: 33, size: 2);
70
71 // larger base overlap
72 V1.Append(base: 46, size: 3);
73 V2.Append(base: 40, size: 7);
74 Expected.Append(base: 46, size: 1);
75
76 // encompass 1 range
77 V1.Append(base: 50, size: 9);
78 V2.Append(base: 51, size: 7);
79 Expected.Append(base: 51, size: 7);
80
81 // encompass 2 ranges
82 V1.Append(base: 60, size: 9);
83 V2.Append(base: 60, size: 3);
84 V2.Append(base: 65, size: 3);
85 Expected.Append(base: 60, size: 3);
86 Expected.Append(base: 65, size: 3);
87
88 V1.Sort();
89 V2.Sort();
90 Expected.Sort();
91
92 EXPECT_EQ(RangeVector::GetOverlaps(V1, V2), Expected);
93 EXPECT_EQ(RangeVector::GetOverlaps(V2, V1), Expected);
94}
95
96using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>;
97using EntryT = RangeDataVectorT::Entry;
98
99static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {
100 return testing::Pointee(inner_matcher: testing::Field(field: &EntryT::data, matcher: ID));
101}
102
103std::vector<uint32_t> FindEntryIndexes(uint32_t address, RangeDataVectorT map) {
104 std::vector<uint32_t> result;
105 map.FindEntryIndexesThatContain(addr: address, indexes&: result);
106 return result;
107}
108
109TEST(RangeDataVector, FindEntryThatContains) {
110 RangeDataVectorT Map;
111 uint32_t NextID = 0;
112 Map.Append(entry: EntryT(0, 10, NextID++));
113 Map.Append(entry: EntryT(10, 10, NextID++));
114 Map.Append(entry: EntryT(20, 10, NextID++));
115 Map.Sort();
116
117 EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0));
118 EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0));
119 EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1));
120 EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1));
121 EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2));
122 EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2));
123 EXPECT_THAT(Map.FindEntryThatContains(30), nullptr);
124}
125
126TEST(RangeDataVector, FindEntryThatContains_Overlap) {
127 RangeDataVectorT Map;
128 uint32_t NextID = 0;
129 Map.Append(entry: EntryT(0, 40, NextID++));
130 Map.Append(entry: EntryT(10, 20, NextID++));
131 Map.Append(entry: EntryT(20, 10, NextID++));
132 Map.Sort();
133
134 // With overlapping intervals, the intention seems to be to return the first
135 // interval which contains the address.
136 EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0));
137
138 // However, this does not always succeed.
139 // TODO: This should probably return the range (0, 40) as well.
140 EXPECT_THAT(Map.FindEntryThatContains(35), nullptr);
141}
142
143TEST(RangeDataVector, CustomSort) {
144 // First the default ascending order sorting of the data field.
145 auto Map = RangeDataVectorT();
146 Map.Append(entry: EntryT(0, 10, 50));
147 Map.Append(entry: EntryT(0, 10, 52));
148 Map.Append(entry: EntryT(0, 10, 53));
149 Map.Append(entry: EntryT(0, 10, 51));
150 Map.Sort();
151
152 EXPECT_THAT(Map.GetSize(), 4);
153 EXPECT_THAT(Map.GetEntryRef(0).data, 50);
154 EXPECT_THAT(Map.GetEntryRef(1).data, 51);
155 EXPECT_THAT(Map.GetEntryRef(2).data, 52);
156 EXPECT_THAT(Map.GetEntryRef(3).data, 53);
157
158 // And then a custom descending order sorting of the data field.
159 class CtorParam {};
160 class CustomSort {
161 public:
162 CustomSort(CtorParam) {}
163 bool operator()(const uint32_t a_data, const uint32_t b_data) {
164 return a_data > b_data;
165 }
166 };
167 using RangeDataVectorCustomSortT =
168 RangeDataVector<uint32_t, uint32_t, uint32_t, 0, CustomSort>;
169 using EntryT = RangeDataVectorT::Entry;
170
171 auto MapC = RangeDataVectorCustomSortT(CtorParam());
172 MapC.Append(entry: EntryT(0, 10, 50));
173 MapC.Append(entry: EntryT(0, 10, 52));
174 MapC.Append(entry: EntryT(0, 10, 53));
175 MapC.Append(entry: EntryT(0, 10, 51));
176 MapC.Sort();
177
178 EXPECT_THAT(MapC.GetSize(), 4);
179 EXPECT_THAT(MapC.GetEntryRef(0).data, 53);
180 EXPECT_THAT(MapC.GetEntryRef(1).data, 52);
181 EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
182 EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
183}
184
185TEST(RangeDataVector, FindEntryIndexesThatContain) {
186 RangeDataVectorT Map;
187 Map.Append(entry: EntryT(0, 10, 10));
188 Map.Append(entry: EntryT(10, 10, 11));
189 Map.Append(entry: EntryT(20, 10, 12));
190 Map.Sort();
191
192 EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
193 EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
194 EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
195 EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
196 EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
197 EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
198 EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
199}
200
201TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
202 RangeDataVectorT Map;
203 Map.Append(entry: EntryT(0, 40, 10));
204 Map.Append(entry: EntryT(10, 20, 11));
205 Map.Append(entry: EntryT(20, 10, 12));
206 Map.Sort();
207
208 EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
209 EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
210 EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
211 EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
212 EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
213 EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
214 EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
215 EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
216 EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
217}
218

source code of lldb/unittests/Utility/RangeMapTest.cpp