262 lines · cpp
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-exception6//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, 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 38TEST(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 64TEST(RangeVector, GetOverlaps) {65 using RangeVector = RangeVector<uint32_t, uint32_t>;66 67 RangeVector V1;68 RangeVector V2;69 RangeVector Expected;70 // same range71 V1.Append(0, 1);72 V2.Append(0, 1);73 Expected.Append(0, 1);74 75 // no overlap76 V1.Append(2, 2);77 V2.Append(4, 1);78 79 // same base overlap80 V1.Append(10, 5);81 V2.Append(10, 3);82 Expected.Append(10, 3);83 84 // same end overlap85 V1.Append(27, 1);86 V2.Append(20, 8);87 Expected.Append(27, 1);88 89 // smaller base overlap90 V1.Append(33, 4);91 V2.Append(30, 5);92 Expected.Append(33, 2);93 94 // larger base overlap95 V1.Append(46, 3);96 V2.Append(40, 7);97 Expected.Append(46, 1);98 99 // encompass 1 range100 V1.Append(50, 9);101 V2.Append(51, 7);102 Expected.Append(51, 7);103 104 // encompass 2 ranges105 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 119using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>;120using EntryT = RangeDataVectorT::Entry;121 122static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {123 return testing::Pointee(testing::Field(&EntryT::data, ID));124}125 126std::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 132TEST(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 149TEST(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 first158 // 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 166TEST(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 208TEST(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 224TEST(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 242TEST(RangeDataVector, CombineConsecutiveEntriesWithEqualData) {243 RangeDataVectorT Map;244 Map.Append(EntryT(0, 10, 47));245 Map.Append(EntryT(10, 10, 47));246 Map.Sort();247 Map.CombineConsecutiveEntriesWithEqualData();248 EXPECT_THAT(FindEntryIndexes(5, Map), testing::ElementsAre(47));249 EXPECT_THAT(FindEntryIndexes(15, Map), testing::ElementsAre(47));250 EXPECT_THAT(FindEntryIndexes(25, Map), testing::ElementsAre());251 252 Map.Clear();253 Map.Append(EntryT(0, 10, 47));254 Map.Append(EntryT(20, 10, 47));255 Map.Sort();256 Map.CombineConsecutiveEntriesWithEqualData();257 EXPECT_THAT(FindEntryIndexes(5, Map), testing::ElementsAre(47));258 EXPECT_THAT(FindEntryIndexes(15, Map), testing::ElementsAre());259 EXPECT_THAT(FindEntryIndexes(25, Map), testing::ElementsAre(47));260 EXPECT_THAT(FindEntryIndexes(35, Map), testing::ElementsAre());261}262