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
13 using namespace lldb_private;
14
TEST(RangeVector,CombineConsecutiveRanges)15 TEST(RangeVector, CombineConsecutiveRanges) {
16 using RangeVector = RangeVector<uint32_t, uint32_t>;
17 using Entry = RangeVector::Entry;
18
19 RangeVector V;
20 V.Append(0, 1);
21 V.Append(5, 1);
22 V.Append(6, 1);
23 V.Append(10, 9);
24 V.Append(15, 1);
25 V.Append(20, 9);
26 V.Append(21, 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(0, 20);
34 V.Append(5, 1);
35 V.Append(10, 1);
36 V.Sort();
37 V.CombineConsecutiveRanges();
38 EXPECT_THAT(V, testing::ElementsAre(Entry(0, 20)));
39 }
40
41 using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>;
42 using EntryT = RangeDataVectorT::Entry;
43
EntryIs(uint32_t ID)44 static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {
45 return testing::Pointee(testing::Field(&EntryT::data, ID));
46 }
47
FindEntryIndexes(uint32_t address,RangeDataVectorT map)48 std::vector<uint32_t> FindEntryIndexes(uint32_t address, RangeDataVectorT map) {
49 std::vector<uint32_t> result;
50 map.FindEntryIndexesThatContain(address, result);
51 return result;
52 }
53
TEST(RangeDataVector,FindEntryThatContains)54 TEST(RangeDataVector, FindEntryThatContains) {
55 RangeDataVectorT Map;
56 uint32_t NextID = 0;
57 Map.Append(EntryT(0, 10, NextID++));
58 Map.Append(EntryT(10, 10, NextID++));
59 Map.Append(EntryT(20, 10, NextID++));
60 Map.Sort();
61
62 EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0));
63 EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0));
64 EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1));
65 EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1));
66 EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2));
67 EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2));
68 EXPECT_THAT(Map.FindEntryThatContains(30), nullptr);
69 }
70
TEST(RangeDataVector,FindEntryThatContains_Overlap)71 TEST(RangeDataVector, FindEntryThatContains_Overlap) {
72 RangeDataVectorT Map;
73 uint32_t NextID = 0;
74 Map.Append(EntryT(0, 40, NextID++));
75 Map.Append(EntryT(10, 20, NextID++));
76 Map.Append(EntryT(20, 10, NextID++));
77 Map.Sort();
78
79 // With overlapping intervals, the intention seems to be to return the first
80 // interval which contains the address.
81 EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0));
82
83 // However, this does not always succeed.
84 // TODO: This should probably return the range (0, 40) as well.
85 EXPECT_THAT(Map.FindEntryThatContains(35), nullptr);
86 }
87
TEST(RangeDataVector,CustomSort)88 TEST(RangeDataVector, CustomSort) {
89 // First the default ascending order sorting of the data field.
90 auto Map = RangeDataVectorT();
91 Map.Append(EntryT(0, 10, 50));
92 Map.Append(EntryT(0, 10, 52));
93 Map.Append(EntryT(0, 10, 53));
94 Map.Append(EntryT(0, 10, 51));
95 Map.Sort();
96
97 EXPECT_THAT(Map.GetSize(), 4);
98 EXPECT_THAT(Map.GetEntryRef(0).data, 50);
99 EXPECT_THAT(Map.GetEntryRef(1).data, 51);
100 EXPECT_THAT(Map.GetEntryRef(2).data, 52);
101 EXPECT_THAT(Map.GetEntryRef(3).data, 53);
102
103 // And then a custom descending order sorting of the data field.
104 class CtorParam {};
105 class CustomSort {
106 public:
107 CustomSort(CtorParam) {}
108 bool operator()(const uint32_t a_data, const uint32_t b_data) {
109 return a_data > b_data;
110 }
111 };
112 using RangeDataVectorCustomSortT =
113 RangeDataVector<uint32_t, uint32_t, uint32_t, 0, CustomSort>;
114 using EntryT = RangeDataVectorT::Entry;
115
116 auto MapC = RangeDataVectorCustomSortT(CtorParam());
117 MapC.Append(EntryT(0, 10, 50));
118 MapC.Append(EntryT(0, 10, 52));
119 MapC.Append(EntryT(0, 10, 53));
120 MapC.Append(EntryT(0, 10, 51));
121 MapC.Sort();
122
123 EXPECT_THAT(MapC.GetSize(), 4);
124 EXPECT_THAT(MapC.GetEntryRef(0).data, 53);
125 EXPECT_THAT(MapC.GetEntryRef(1).data, 52);
126 EXPECT_THAT(MapC.GetEntryRef(2).data, 51);
127 EXPECT_THAT(MapC.GetEntryRef(3).data, 50);
128 }
129
TEST(RangeDataVector,FindEntryIndexesThatContain)130 TEST(RangeDataVector, FindEntryIndexesThatContain) {
131 RangeDataVectorT Map;
132 Map.Append(EntryT(0, 10, 10));
133 Map.Append(EntryT(10, 10, 11));
134 Map.Append(EntryT(20, 10, 12));
135 Map.Sort();
136
137 EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
138 EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
139 EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));
140 EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));
141 EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));
142 EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));
143 EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());
144 }
145
TEST(RangeDataVector,FindEntryIndexesThatContain_Overlap)146 TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
147 RangeDataVectorT Map;
148 Map.Append(EntryT(0, 40, 10));
149 Map.Append(EntryT(10, 20, 11));
150 Map.Append(EntryT(20, 10, 12));
151 Map.Sort();
152
153 EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));
154 EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));
155 EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));
156 EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));
157 EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));
158 EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));
159 EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));
160 EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));
161 EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());
162 }
163