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 using RangeDataVectorT = RangeDataVector<uint32_t, uint32_t, uint32_t>;
  42 using EntryT = RangeDataVectorT::Entry;
  43
  44 static testing::Matcher<const EntryT *> EntryIs(uint32_t ID) {
  45   return testing::Pointee(testing::Field(&EntryT::data, ID));
  46 }
  47
  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
  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
  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
  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
 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
 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 }