compiler-rt/lib/orc/tests/unit/interval_map_test.cpp

   1 //===-- interval_map_test.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 // This file is a part of the ORC runtime.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "interval_map.h"
  14 #include "gtest/gtest.h"
  15
  16 using namespace __orc_rt;
  17
  18 TEST(IntervalMapTest, DefaultConstructed) {
  19   // Check that a default-constructed IntervalMap behaves as expected.
  20   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;
  21
  22   EXPECT_TRUE(M.empty());
  23   EXPECT_TRUE(M.begin() == M.end());
  24   EXPECT_TRUE(M.find(0) == M.end());
  25 }
  26
  27 TEST(IntervalMapTest, InsertSingleElement) {
  28   // Check that a map with a single element inserted behaves as expected.
  29   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;
  30
  31   M.insert(7, 8, 42);
  32
  33   EXPECT_FALSE(M.empty());
  34   EXPECT_EQ(std::next(M.begin()), M.end());
  35   EXPECT_EQ(M.find(7), M.begin());
  36   EXPECT_EQ(M.find(8), M.end());
  37   EXPECT_EQ(M.lookup(7), 42U);
  38   EXPECT_EQ(M.lookup(8), 0U); // 8 not present, so should return unsigned().
  39 }
  40
  41 TEST(IntervalMapTest, InsertCoalesceWithPrevious) {
  42   // Check that insertions coalesce with previous ranges that share the same
  43   // value. Also check that they _don't_ coalesce if the values are different.
  44
  45   // Check that insertion coalesces with previous range when values are equal.
  46   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M1;
  47
  48   M1.insert(7, 8, 42);
  49   M1.insert(8, 9, 42);
  50
  51   EXPECT_FALSE(M1.empty());
  52   EXPECT_EQ(std::next(M1.begin()), M1.end()); // Should see just one range.
  53   EXPECT_EQ(M1.find(7), M1.find(8)); // 7 and 8 should point to same range.
  54   EXPECT_EQ(M1.lookup(7), 42U);      // Value should be preserved.
  55
  56   // Check that insertion does not coalesce with previous range when values are
  57   // not equal.
  58   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M2;
  59
  60   M2.insert(7, 8, 42);
  61   M2.insert(8, 9, 7);
  62
  63   EXPECT_FALSE(M2.empty());
  64   EXPECT_EQ(std::next(std::next(M2.begin())), M2.end()); // Expect two ranges.
  65   EXPECT_NE(M2.find(7), M2.find(8)); // 7 and 8 should be different ranges.
  66   EXPECT_EQ(M2.lookup(7), 42U); // Keys 7 and 8 should map to different values.
  67   EXPECT_EQ(M2.lookup(8), 7U);
  68 }
  69
  70 TEST(IntervalMapTest, InsertCoalesceWithFollowing) {
  71   // Check that insertions coalesce with following ranges that share the same
  72   // value. Also check that they _don't_ coalesce if the values are different.
  73
  74   // Check that insertion coalesces with following range when values are equal.
  75   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M1;
  76
  77   M1.insert(8, 9, 42);
  78   M1.insert(7, 8, 42);
  79
  80   EXPECT_FALSE(M1.empty());
  81   EXPECT_EQ(std::next(M1.begin()), M1.end()); // Should see just one range.
  82   EXPECT_EQ(M1.find(7), M1.find(8)); // 7 and 8 should point to same range.
  83   EXPECT_EQ(M1.lookup(7), 42U);      // Value should be preserved.
  84
  85   // Check that insertion does not coalesce with previous range when values are
  86   // not equal.
  87   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M2;
  88
  89   M2.insert(8, 9, 42);
  90   M2.insert(7, 8, 7);
  91
  92   EXPECT_FALSE(M2.empty());
  93   EXPECT_EQ(std::next(std::next(M2.begin())), M2.end()); // Expect two ranges.
  94   EXPECT_EQ(M2.lookup(7), 7U); // Keys 7 and 8 should map to different values.
  95   EXPECT_EQ(M2.lookup(8), 42U);
  96 }
  97
  98 TEST(IntervalMapTest, InsertCoalesceBoth) {
  99   // Check that insertions coalesce with ranges on both sides where posssible.
 100   // Also check that they _don't_ coalesce if the values are different.
 101
 102   // Check that insertion coalesces with both previous and following ranges
 103   // when values are equal.
 104   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M1;
 105
 106   M1.insert(7, 8, 42);
 107   M1.insert(9, 10, 42);
 108
 109   // Check no coalescing yet.
 110   EXPECT_NE(M1.find(7), M1.find(9));
 111
 112   // Insert a 3rd range to trigger coalescing on both sides.
 113   M1.insert(8, 9, 42);
 114
 115   EXPECT_FALSE(M1.empty());
 116   EXPECT_EQ(std::next(M1.begin()), M1.end()); // Should see just one range.
 117   EXPECT_EQ(M1.find(7), M1.find(8)); // 7, 8, and 9 should point to same range.
 118   EXPECT_EQ(M1.find(8), M1.find(9));
 119   EXPECT_EQ(M1.lookup(7), 42U); // Value should be preserved.
 120
 121   // Check that insertion does not coalesce with previous range when values are
 122   // not equal.
 123   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M2;
 124
 125   M2.insert(7, 8, 42);
 126   M2.insert(8, 9, 7);
 127   M2.insert(9, 10, 42);
 128
 129   EXPECT_FALSE(M2.empty());
 130   // Expect three ranges.
 131   EXPECT_EQ(std::next(std::next(std::next(M2.begin()))), M2.end());
 132   EXPECT_NE(M2.find(7), M2.find(8)); // All keys should map to different ranges.
 133   EXPECT_NE(M2.find(8), M2.find(9));
 134   EXPECT_EQ(M2.lookup(7), 42U); // Key 7, 8, and 9 should map to different vals.
 135   EXPECT_EQ(M2.lookup(8), 7U);
 136   EXPECT_EQ(M2.lookup(9), 42U);
 137 }
 138
 139 TEST(IntervalMapTest, EraseSingleElement) {
 140   // Check that we can insert and then remove a single range.
 141   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;
 142
 143   M.insert(7, 10, 42);
 144   EXPECT_FALSE(M.empty());
 145   M.erase(7, 10);
 146   EXPECT_TRUE(M.empty());
 147 }
 148
 149 TEST(IntervalMapTest, EraseSplittingLeft) {
 150   // Check that removal of a trailing subrange succeeds, but leaves the
 151   // residual range in-place.
 152   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;
 153
 154   M.insert(7, 10, 42);
 155   EXPECT_FALSE(M.empty());
 156   M.erase(9, 10);
 157   EXPECT_EQ(std::next(M.begin()), M.end());
 158   EXPECT_EQ(M.begin()->first.first, 7U);
 159   EXPECT_EQ(M.begin()->first.second, 9U);
 160 }
 161
 162 TEST(IntervalMapTest, EraseSplittingRight) {
 163   // Check that removal of a leading subrange succeeds, but leaves the
 164   // residual range in-place.
 165   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;
 166
 167   M.insert(7, 10, 42);
 168   EXPECT_FALSE(M.empty());
 169   M.erase(7, 8);
 170   EXPECT_EQ(std::next(M.begin()), M.end());
 171   EXPECT_EQ(M.begin()->first.first, 8U);
 172   EXPECT_EQ(M.begin()->first.second, 10U);
 173 }
 174
 175 TEST(IntervalMapTest, EraseSplittingBoth) {
 176   // Check that removal of an interior subrange leaves both the leading and
 177   // trailing residual subranges in-place.
 178   IntervalMap<unsigned, unsigned, IntervalCoalescing::Enabled> M;
 179
 180   M.insert(7, 10, 42);
 181   EXPECT_FALSE(M.empty());
 182   M.erase(8, 9);
 183   EXPECT_EQ(std::next(std::next(M.begin())), M.end());
 184   EXPECT_EQ(M.begin()->first.first, 7U);
 185   EXPECT_EQ(M.begin()->first.second, 8U);
 186   EXPECT_EQ(std::next(M.begin())->first.first, 9U);
 187   EXPECT_EQ(std::next(M.begin())->first.second, 10U);
 188 }
 189
 190 TEST(IntervalMapTest, NonCoalescingMapPermitsNonComparableKeys) {
 191   // Test that values that can't be equality-compared are still usable when
 192   // coalescing is disabled and behave as expected.
 193
 194   struct S {}; // Struct with no equality comparison.
 195
 196   IntervalMap<unsigned, S, IntervalCoalescing::Disabled> M;
 197
 198   M.insert(7, 8, S());
 199
 200   EXPECT_FALSE(M.empty());
 201   EXPECT_EQ(std::next(M.begin()), M.end());
 202   EXPECT_EQ(M.find(7), M.begin());
 203   EXPECT_EQ(M.find(8), M.end());
 204 }