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 
TEST(RangeVector,CombineConsecutiveRanges)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 
EntryIs(uint32_t ID)44 static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {
45   return testing::Pointee(testing::Field(&EntryT::data, ID));
46 }
47 
FindEntryIndexes(uint32_t address,RangeDataVectorT map)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 
TEST(RangeDataVector,FindEntryThatContains)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 
TEST(RangeDataVector,FindEntryThatContains_Overlap)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 
TEST(RangeDataVector,CustomSort)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 
TEST(RangeDataVector,FindEntryIndexesThatContain)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 
TEST(RangeDataVector,FindEntryIndexesThatContain_Overlap)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