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