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, SignedBaseType) { 16 using RangeVector = RangeVector<int32_t, uint32_t>; 17 using Entry = RangeVector::Entry; 18 19 RangeVector V; 20 V.Append(10, 5); 21 V.Append(-3, 6); 22 V.Append(-10, 3); 23 V.Sort(); 24 EXPECT_THAT(V, 25 testing::ElementsAre(Entry(-10, 3), Entry(-3, 6), Entry(10, 5))); 26 Entry e = *V.begin(); 27 EXPECT_EQ(e.GetRangeBase(), -10); 28 EXPECT_EQ(e.GetByteSize(), 3u); 29 EXPECT_EQ(e.GetRangeEnd(), -7); 30 EXPECT_TRUE(e.Contains(-10)); 31 EXPECT_TRUE(e.Contains(-8)); 32 EXPECT_FALSE(e.Contains(-7)); 33 EXPECT_TRUE(e.Union(Entry(-8, 2))); 34 EXPECT_EQ(e, Entry(-10, 4)); 35 EXPECT_EQ(e.Intersect(Entry(-7, 3)), Entry(-7, 1)); 36 } 37 38 TEST(RangeVector, CombineConsecutiveRanges) { 39 using RangeVector = RangeVector<uint32_t, uint32_t>; 40 using Entry = RangeVector::Entry; 41 42 RangeVector V; 43 V.Append(0, 1); 44 V.Append(5, 1); 45 V.Append(6, 1); 46 V.Append(10, 9); 47 V.Append(15, 1); 48 V.Append(20, 9); 49 V.Append(21, 9); 50 V.Sort(); 51 V.CombineConsecutiveRanges(); 52 EXPECT_THAT(V, testing::ElementsAre(Entry(0, 1), Entry(5, 2), Entry(10, 9), 53 Entry(20, 10))); 54 55 V.Clear(); 56 V.Append(0, 20); 57 V.Append(5, 1); 58 V.Append(10, 1); 59 V.Sort(); 60 V.CombineConsecutiveRanges(); 61 EXPECT_THAT(V, testing::ElementsAre(Entry(0, 20))); 62 } 63 64 TEST(RangeVector, GetOverlaps) { 65 using RangeVector = RangeVector<uint32_t, uint32_t>; 66 67 RangeVector V1; 68 RangeVector V2; 69 RangeVector Expected; 70 // same range 71 V1.Append(0, 1); 72 V2.Append(0, 1); 73 Expected.Append(0, 1); 74 75 // no overlap 76 V1.Append(2, 2); 77 V2.Append(4, 1); 78 79 // same base overlap 80 V1.Append(10, 5); 81 V2.Append(10, 3); 82 Expected.Append(10, 3); 83 84 // same end overlap 85 V1.Append(27, 1); 86 V2.Append(20, 8); 87 Expected.Append(27, 1); 88 89 // smaller base overlap 90 V1.Append(33, 4); 91 V2.Append(30, 5); 92 Expected.Append(33, 2); 93 94 // larger base overlap 95 V1.Append(46, 3); 96 V2.Append(40, 7); 97 Expected.Append(46, 1); 98 99 // encompass 1 range 100 V1.Append(50, 9); 101 V2.Append(51, 7); 102 Expected.Append(51, 7); 103 104 // encompass 2 ranges 105 V1.Append(60, 9); 106 V2.Append(60, 3); 107 V2.Append(65, 3); 108 Expected.Append(60, 3); 109 Expected.Append(65, 3); 110 111 V1.Sort(); 112 V2.Sort(); 113 Expected.Sort(); 114 115 EXPECT_EQ(RangeVector::GetOverlaps(V1, V2), Expected); 116 EXPECT_EQ(RangeVector::GetOverlaps(V2, V1), Expected); 117 } 118 119 using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>; 120 using EntryT = RangeDataVectorT::Entry; 121 122 static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) { 123 return testing::Pointee(testing::Field(&EntryT::data, ID)); 124 } 125 126 std::vector<uint32_t> FindEntryIndexes(uint32_t address, RangeDataVectorT map) { 127 std::vector<uint32_t> result; 128 map.FindEntryIndexesThatContain(address, result); 129 return result; 130 } 131 132 TEST(RangeDataVector, FindEntryThatContains) { 133 RangeDataVectorT Map; 134 uint32_t NextID = 0; 135 Map.Append(EntryT(0, 10, NextID++)); 136 Map.Append(EntryT(10, 10, NextID++)); 137 Map.Append(EntryT(20, 10, NextID++)); 138 Map.Sort(); 139 140 EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0)); 141 EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0)); 142 EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1)); 143 EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1)); 144 EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2)); 145 EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2)); 146 EXPECT_THAT(Map.FindEntryThatContains(30), nullptr); 147 } 148 149 TEST(RangeDataVector, FindEntryThatContains_Overlap) { 150 RangeDataVectorT Map; 151 uint32_t NextID = 0; 152 Map.Append(EntryT(0, 40, NextID++)); 153 Map.Append(EntryT(10, 20, NextID++)); 154 Map.Append(EntryT(20, 10, NextID++)); 155 Map.Sort(); 156 157 // With overlapping intervals, the intention seems to be to return the first 158 // interval which contains the address. 159 EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0)); 160 161 // However, this does not always succeed. 162 // TODO: This should probably return the range (0, 40) as well. 163 EXPECT_THAT(Map.FindEntryThatContains(35), nullptr); 164 } 165 166 TEST(RangeDataVector, CustomSort) { 167 // First the default ascending order sorting of the data field. 168 auto Map = RangeDataVectorT(); 169 Map.Append(EntryT(0, 10, 50)); 170 Map.Append(EntryT(0, 10, 52)); 171 Map.Append(EntryT(0, 10, 53)); 172 Map.Append(EntryT(0, 10, 51)); 173 Map.Sort(); 174 175 EXPECT_THAT(Map.GetSize(), 4); 176 EXPECT_THAT(Map.GetEntryRef(0).data, 50); 177 EXPECT_THAT(Map.GetEntryRef(1).data, 51); 178 EXPECT_THAT(Map.GetEntryRef(2).data, 52); 179 EXPECT_THAT(Map.GetEntryRef(3).data, 53); 180 181 // And then a custom descending order sorting of the data field. 182 class CtorParam {}; 183 class CustomSort { 184 public: 185 CustomSort(CtorParam) {} 186 bool operator()(const uint32_t a_data, const uint32_t b_data) { 187 return a_data > b_data; 188 } 189 }; 190 using RangeDataVectorCustomSortT = 191 RangeDataVector<uint32_t, uint32_t, uint32_t, 0, CustomSort>; 192 using EntryT = RangeDataVectorT::Entry; 193 194 auto MapC = RangeDataVectorCustomSortT(CtorParam()); 195 MapC.Append(EntryT(0, 10, 50)); 196 MapC.Append(EntryT(0, 10, 52)); 197 MapC.Append(EntryT(0, 10, 53)); 198 MapC.Append(EntryT(0, 10, 51)); 199 MapC.Sort(); 200 201 EXPECT_THAT(MapC.GetSize(), 4); 202 EXPECT_THAT(MapC.GetEntryRef(0).data, 53); 203 EXPECT_THAT(MapC.GetEntryRef(1).data, 52); 204 EXPECT_THAT(MapC.GetEntryRef(2).data, 51); 205 EXPECT_THAT(MapC.GetEntryRef(3).data, 50); 206 } 207 208 TEST(RangeDataVector, FindEntryIndexesThatContain) { 209 RangeDataVectorT Map; 210 Map.Append(EntryT(0, 10, 10)); 211 Map.Append(EntryT(10, 10, 11)); 212 Map.Append(EntryT(20, 10, 12)); 213 Map.Sort(); 214 215 EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10)); 216 EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10)); 217 EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11)); 218 EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11)); 219 EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12)); 220 EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12)); 221 EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre()); 222 } 223 224 TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) { 225 RangeDataVectorT Map; 226 Map.Append(EntryT(0, 40, 10)); 227 Map.Append(EntryT(10, 20, 11)); 228 Map.Append(EntryT(20, 10, 12)); 229 Map.Sort(); 230 231 EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10)); 232 EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10)); 233 EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11)); 234 EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11)); 235 EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12)); 236 EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12)); 237 EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10)); 238 EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10)); 239 EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre()); 240 } 241