llvm-project
217 строк · 6.5 Кб
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
13using namespace lldb_private;14
15TEST(RangeVector, CombineConsecutiveRanges) {16using RangeVector = RangeVector<uint32_t, uint32_t>;17using Entry = RangeVector::Entry;18
19RangeVector V;20V.Append(0, 1);21V.Append(5, 1);22V.Append(6, 1);23V.Append(10, 9);24V.Append(15, 1);25V.Append(20, 9);26V.Append(21, 9);27V.Sort();28V.CombineConsecutiveRanges();29EXPECT_THAT(V, testing::ElementsAre(Entry(0, 1), Entry(5, 2), Entry(10, 9),30Entry(20, 10)));31
32V.Clear();33V.Append(0, 20);34V.Append(5, 1);35V.Append(10, 1);36V.Sort();37V.CombineConsecutiveRanges();38EXPECT_THAT(V, testing::ElementsAre(Entry(0, 20)));39}
40
41TEST(RangeVector, GetOverlaps) {42using RangeVector = RangeVector<uint32_t, uint32_t>;43
44RangeVector V1;45RangeVector V2;46RangeVector Expected;47// same range48V1.Append(0, 1);49V2.Append(0, 1);50Expected.Append(0, 1);51
52// no overlap53V1.Append(2, 2);54V2.Append(4, 1);55
56// same base overlap57V1.Append(10, 5);58V2.Append(10, 3);59Expected.Append(10, 3);60
61// same end overlap62V1.Append(27, 1);63V2.Append(20, 8);64Expected.Append(27, 1);65
66// smaller base overlap67V1.Append(33, 4);68V2.Append(30, 5);69Expected.Append(33, 2);70
71// larger base overlap72V1.Append(46, 3);73V2.Append(40, 7);74Expected.Append(46, 1);75
76// encompass 1 range77V1.Append(50, 9);78V2.Append(51, 7);79Expected.Append(51, 7);80
81// encompass 2 ranges82V1.Append(60, 9);83V2.Append(60, 3);84V2.Append(65, 3);85Expected.Append(60, 3);86Expected.Append(65, 3);87
88V1.Sort();89V2.Sort();90Expected.Sort();91
92EXPECT_EQ(RangeVector::GetOverlaps(V1, V2), Expected);93EXPECT_EQ(RangeVector::GetOverlaps(V2, V1), Expected);94}
95
96using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>;97using EntryT = RangeDataVectorT::Entry;98
99static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {100return testing::Pointee(testing::Field(&EntryT::data, ID));101}
102
103std::vector<uint32_t> FindEntryIndexes(uint32_t address, RangeDataVectorT map) {104std::vector<uint32_t> result;105map.FindEntryIndexesThatContain(address, result);106return result;107}
108
109TEST(RangeDataVector, FindEntryThatContains) {110RangeDataVectorT Map;111uint32_t NextID = 0;112Map.Append(EntryT(0, 10, NextID++));113Map.Append(EntryT(10, 10, NextID++));114Map.Append(EntryT(20, 10, NextID++));115Map.Sort();116
117EXPECT_THAT(Map.FindEntryThatContains(0), EntryIs(0));118EXPECT_THAT(Map.FindEntryThatContains(9), EntryIs(0));119EXPECT_THAT(Map.FindEntryThatContains(10), EntryIs(1));120EXPECT_THAT(Map.FindEntryThatContains(19), EntryIs(1));121EXPECT_THAT(Map.FindEntryThatContains(20), EntryIs(2));122EXPECT_THAT(Map.FindEntryThatContains(29), EntryIs(2));123EXPECT_THAT(Map.FindEntryThatContains(30), nullptr);124}
125
126TEST(RangeDataVector, FindEntryThatContains_Overlap) {127RangeDataVectorT Map;128uint32_t NextID = 0;129Map.Append(EntryT(0, 40, NextID++));130Map.Append(EntryT(10, 20, NextID++));131Map.Append(EntryT(20, 10, NextID++));132Map.Sort();133
134// With overlapping intervals, the intention seems to be to return the first135// interval which contains the address.136EXPECT_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.140EXPECT_THAT(Map.FindEntryThatContains(35), nullptr);141}
142
143TEST(RangeDataVector, CustomSort) {144// First the default ascending order sorting of the data field.145auto Map = RangeDataVectorT();146Map.Append(EntryT(0, 10, 50));147Map.Append(EntryT(0, 10, 52));148Map.Append(EntryT(0, 10, 53));149Map.Append(EntryT(0, 10, 51));150Map.Sort();151
152EXPECT_THAT(Map.GetSize(), 4);153EXPECT_THAT(Map.GetEntryRef(0).data, 50);154EXPECT_THAT(Map.GetEntryRef(1).data, 51);155EXPECT_THAT(Map.GetEntryRef(2).data, 52);156EXPECT_THAT(Map.GetEntryRef(3).data, 53);157
158// And then a custom descending order sorting of the data field.159class CtorParam {};160class CustomSort {161public:162CustomSort(CtorParam) {}163bool operator()(const uint32_t a_data, const uint32_t b_data) {164return a_data > b_data;165}166};167using RangeDataVectorCustomSortT =168RangeDataVector<uint32_t, uint32_t, uint32_t, 0, CustomSort>;169using EntryT = RangeDataVectorT::Entry;170
171auto MapC = RangeDataVectorCustomSortT(CtorParam());172MapC.Append(EntryT(0, 10, 50));173MapC.Append(EntryT(0, 10, 52));174MapC.Append(EntryT(0, 10, 53));175MapC.Append(EntryT(0, 10, 51));176MapC.Sort();177
178EXPECT_THAT(MapC.GetSize(), 4);179EXPECT_THAT(MapC.GetEntryRef(0).data, 53);180EXPECT_THAT(MapC.GetEntryRef(1).data, 52);181EXPECT_THAT(MapC.GetEntryRef(2).data, 51);182EXPECT_THAT(MapC.GetEntryRef(3).data, 50);183}
184
185TEST(RangeDataVector, FindEntryIndexesThatContain) {186RangeDataVectorT Map;187Map.Append(EntryT(0, 10, 10));188Map.Append(EntryT(10, 10, 11));189Map.Append(EntryT(20, 10, 12));190Map.Sort();191
192EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));193EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));194EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(11));195EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(11));196EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(12));197EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(12));198EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre());199}
200
201TEST(RangeDataVector, FindEntryIndexesThatContain_Overlap) {202RangeDataVectorT Map;203Map.Append(EntryT(0, 40, 10));204Map.Append(EntryT(10, 20, 11));205Map.Append(EntryT(20, 10, 12));206Map.Sort();207
208EXPECT_THAT(FindEntryIndexes(0, Map), testing::ElementsAre(10));209EXPECT_THAT(FindEntryIndexes(9, Map), testing::ElementsAre(10));210EXPECT_THAT(FindEntryIndexes(10, Map), testing::ElementsAre(10, 11));211EXPECT_THAT(FindEntryIndexes(19, Map), testing::ElementsAre(10, 11));212EXPECT_THAT(FindEntryIndexes(20, Map), testing::ElementsAre(10, 11, 12));213EXPECT_THAT(FindEntryIndexes(29, Map), testing::ElementsAre(10, 11, 12));214EXPECT_THAT(FindEntryIndexes(30, Map), testing::ElementsAre(10));215EXPECT_THAT(FindEntryIndexes(39, Map), testing::ElementsAre(10));216EXPECT_THAT(FindEntryIndexes(40, Map), testing::ElementsAre());217}
218