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 using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>; 42 using EntryT = RangeDataVectorT::Entry; 43 44 static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) { 45 return testing::Pointee(testing::Field(&EntryT::data, ID)); 46 } 47 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 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 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 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 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 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