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