llvm-project

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

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
TEST(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(0, 1);
49
  V2.Append(0, 1);
50
  Expected.Append(0, 1);
51

52
  // no overlap
53
  V1.Append(2, 2);
54
  V2.Append(4, 1);
55

56
  // same base overlap
57
  V1.Append(10, 5);
58
  V2.Append(10, 3);
59
  Expected.Append(10, 3);
60

61
  // same end overlap
62
  V1.Append(27, 1);
63
  V2.Append(20, 8);
64
  Expected.Append(27, 1);
65

66
  // smaller base overlap
67
  V1.Append(33, 4);
68
  V2.Append(30, 5);
69
  Expected.Append(33, 2);
70

71
  // larger base overlap
72
  V1.Append(46, 3);
73
  V2.Append(40, 7);
74
  Expected.Append(46, 1);
75

76
  // encompass 1 range
77
  V1.Append(50, 9);
78
  V2.Append(51, 7);
79
  Expected.Append(51, 7);
80

81
  // encompass 2 ranges
82
  V1.Append(60, 9);
83
  V2.Append(60, 3);
84
  V2.Append(65, 3);
85
  Expected.Append(60, 3);
86
  Expected.Append(65, 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

96
using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>;
97
using EntryT = RangeDataVectorT::Entry;
98

99
static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {
100
  return testing::Pointee(testing::Field(&EntryT::data, ID));
101
}
102

103
std::vector<uint32_t> FindEntryIndexes(uint32_t address, RangeDataVectorT map) {
104
  std::vector<uint32_t> result;
105
  map.FindEntryIndexesThatContain(address, result);
106
  return result;
107
}
108

109
TEST(RangeDataVector, FindEntryThatContains) {
110
  RangeDataVectorT Map;
111
  uint32_t NextID = 0;
112
  Map.Append(EntryT(0, 10, NextID++));
113
  Map.Append(EntryT(10, 10, NextID++));
114
  Map.Append(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

126
TEST(RangeDataVector, FindEntryThatContains_Overlap) {
127
  RangeDataVectorT Map;
128
  uint32_t NextID = 0;
129
  Map.Append(EntryT(0, 40, NextID++));
130
  Map.Append(EntryT(10, 20, NextID++));
131
  Map.Append(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

143
TEST(RangeDataVector, CustomSort) {
144
  // First the default ascending order sorting of the data field.
145
  auto Map = RangeDataVectorT();
146
  Map.Append(EntryT(0, 10, 50));
147
  Map.Append(EntryT(0, 10, 52));
148
  Map.Append(EntryT(0, 10, 53));
149
  Map.Append(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(EntryT(0, 10, 50));
173
  MapC.Append(EntryT(0, 10, 52));
174
  MapC.Append(EntryT(0, 10, 53));
175
  MapC.Append(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

185
TEST(RangeDataVector, FindEntryIndexesThatContain) {
186
  RangeDataVectorT Map;
187
  Map.Append(EntryT(0, 10, 10));
188
  Map.Append(EntryT(10, 10, 11));
189
  Map.Append(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

201
TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {
202
  RangeDataVectorT Map;
203
  Map.Append(EntryT(0, 40, 10));
204
  Map.Append(EntryT(10, 20, 11));
205
  Map.Append(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