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 TEST(RangeDataVector, FindEntryThatContains) { 23 RangeDataVectorT Map; 24 uint32_t NextID = 0; 25 Map.Append(EntryT(0, 10, NextID++)); 26 Map.Append(EntryT(10, 10, NextID++)); 27 Map.Append(EntryT(20, 10, NextID++)); 28 Map.Sort(); 29 30 EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0)); 31 EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0)); 32 EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1)); 33 EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1)); 34 EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2)); 35 EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2)); 36 EXPECT_THAT(Map.FindEntryThatContains(30), nullptr); 37 } 38 39 TEST(RangeDataVector, FindEntryThatContains_Overlap) { 40 RangeDataVectorT Map; 41 uint32_t NextID = 0; 42 Map.Append(EntryT(0, 40, NextID++)); 43 Map.Append(EntryT(10, 20, NextID++)); 44 Map.Append(EntryT(20, 10, NextID++)); 45 Map.Sort(); 46 47 // With overlapping intervals, the intention seems to be to return the first 48 // interval which contains the address. 49 EXPECT_THAT(Map.FindEntryThatContains(25), EntryIs(0)); 50 51 // However, this does not always succeed. 52 // TODO: This should probably return the range (0, 40) as well. 53 EXPECT_THAT(Map.FindEntryThatContains(35), nullptr); 54 } 55 56 TEST(RangeDataVector, CustomSort) { 57 // First the default ascending order sorting of the data field. 58 auto Map = RangeDataVectorT(); 59 Map.Append(EntryT(0, 10, 50)); 60 Map.Append(EntryT(0, 10, 52)); 61 Map.Append(EntryT(0, 10, 53)); 62 Map.Append(EntryT(0, 10, 51)); 63 Map.Sort(); 64 65 EXPECT_THAT(Map.GetSize(), 4); 66 EXPECT_THAT(Map.GetEntryRef(0).data, 50); 67 EXPECT_THAT(Map.GetEntryRef(1).data, 51); 68 EXPECT_THAT(Map.GetEntryRef(2).data, 52); 69 EXPECT_THAT(Map.GetEntryRef(3).data, 53); 70 71 // And then a custom descending order sorting of the data field. 72 class CtorParam {}; 73 class CustomSort { 74 public: 75 CustomSort(CtorParam) {} 76 bool operator()(const uint32_t a_data, const uint32_t b_data) { 77 return a_data > b_data; 78 } 79 }; 80 using RangeDataVectorCustomSortT = 81 RangeDataVector<uint32_t, uint32_t, uint32_t, 0, CustomSort>; 82 using EntryT = RangeDataVectorT::Entry; 83 84 auto MapC = RangeDataVectorCustomSortT(CtorParam()); 85 MapC.Append(EntryT(0, 10, 50)); 86 MapC.Append(EntryT(0, 10, 52)); 87 MapC.Append(EntryT(0, 10, 53)); 88 MapC.Append(EntryT(0, 10, 51)); 89 MapC.Sort(); 90 91 EXPECT_THAT(MapC.GetSize(), 4); 92 EXPECT_THAT(MapC.GetEntryRef(0).data, 53); 93 EXPECT_THAT(MapC.GetEntryRef(1).data, 52); 94 EXPECT_THAT(MapC.GetEntryRef(2).data, 51); 95 EXPECT_THAT(MapC.GetEntryRef(3).data, 50); 96 } 97