1 //===-- interval_set_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_set.h" 14 #include "gtest/gtest.h" 15 16 using namespace __orc_rt; 17 18 TEST(IntervalSetTest, DefaultConstructed) { 19 // Check that a default-constructed IntervalSet behaves as expected. 20 IntervalSet<unsigned, IntervalCoalescing::Enabled> S; 21 22 EXPECT_TRUE(S.empty()); 23 EXPECT_TRUE(S.begin() == S.end()); 24 EXPECT_TRUE(S.find(0) == S.end()); 25 } 26 27 TEST(IntervalSetTest, InsertSingleElement) { 28 // Check that a set with a single element inserted behaves as expected. 29 IntervalSet<unsigned, IntervalCoalescing::Enabled> S; 30 31 S.insert(7, 8); 32 33 EXPECT_FALSE(S.empty()); 34 EXPECT_EQ(std::next(S.begin()), S.end()); 35 EXPECT_EQ(S.find(7), S.begin()); 36 EXPECT_EQ(S.find(8), S.end()); 37 } 38 39 TEST(IntervalSetTest, InsertCoalesceWithPrevious) { 40 // Check that insertions coalesce with previous ranges. 41 IntervalSet<unsigned, IntervalCoalescing::Enabled> S; 42 43 S.insert(7, 8); 44 S.insert(8, 9); 45 46 EXPECT_FALSE(S.empty()); 47 EXPECT_EQ(std::next(S.begin()), S.end()); // Should see just one range. 48 EXPECT_EQ(S.find(7), S.find(8)); // 7 and 8 should point to same range. 49 } 50 51 TEST(IntervalSetTest, InsertCoalesceWithFollowing) { 52 // Check that insertions coalesce with following ranges. 53 IntervalSet<unsigned, IntervalCoalescing::Enabled> S; 54 55 S.insert(8, 9); 56 S.insert(7, 8); 57 58 EXPECT_FALSE(S.empty()); 59 EXPECT_EQ(std::next(S.begin()), S.end()); // Should see just one range. 60 EXPECT_EQ(S.find(7), S.find(8)); // 7 and 8 should point to same range. 61 } 62 63 TEST(IntervalSetTest, InsertCoalesceBoth) { 64 // Check that insertions coalesce with ranges on both sides. 65 IntervalSet<unsigned, IntervalCoalescing::Enabled> S; 66 67 S.insert(7, 8); 68 S.insert(9, 10); 69 70 // Check no coalescing yet. 71 EXPECT_NE(S.find(7), S.find(9)); 72 73 // Insert a 3rd range to trigger coalescing on both sides. 74 S.insert(8, 9); 75 76 EXPECT_FALSE(S.empty()); 77 EXPECT_EQ(std::next(S.begin()), S.end()); // Should see just one range. 78 EXPECT_EQ(S.find(7), S.find(8)); // 7, 8, and 9 should point to same range. 79 EXPECT_EQ(S.find(8), S.find(9)); 80 } 81 82 TEST(IntervalSetTest, EraseSplittingLeft) { 83 // Check that removal of a trailing subrange succeeds, but leaves the 84 // residual range in-place. 85 IntervalSet<unsigned, IntervalCoalescing::Enabled> S; 86 87 S.insert(7, 10); 88 EXPECT_FALSE(S.empty()); 89 S.erase(9, 10); 90 EXPECT_EQ(std::next(S.begin()), S.end()); 91 EXPECT_EQ(S.begin()->first, 7U); 92 EXPECT_EQ(S.begin()->second, 9U); 93 } 94 95 TEST(IntervalSetTest, EraseSplittingRight) { 96 // Check that removal of a leading subrange succeeds, but leaves the 97 // residual range in-place. 98 IntervalSet<unsigned, IntervalCoalescing::Enabled> S; 99 100 S.insert(7, 10); 101 EXPECT_FALSE(S.empty()); 102 S.erase(7, 8); 103 EXPECT_EQ(std::next(S.begin()), S.end()); 104 EXPECT_EQ(S.begin()->first, 8U); 105 EXPECT_EQ(S.begin()->second, 10U); 106 } 107 108 TEST(IntervalSetTest, EraseSplittingBoth) { 109 // Check that removal of an interior subrange leaves both the leading and 110 // trailing residual subranges in-place. 111 IntervalSet<unsigned, IntervalCoalescing::Enabled> S; 112 113 S.insert(7, 10); 114 EXPECT_FALSE(S.empty()); 115 S.erase(8, 9); 116 EXPECT_EQ(std::next(std::next(S.begin())), S.end()); 117 EXPECT_EQ(S.begin()->first, 7U); 118 EXPECT_EQ(S.begin()->second, 8U); 119 EXPECT_EQ(std::next(S.begin())->first, 9U); 120 EXPECT_EQ(std::next(S.begin())->second, 10U); 121 } 122