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 16using namespace __orc_rt; 17 18TEST(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 27TEST(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 39TEST(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 51TEST(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 63TEST(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 82TEST(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 95TEST(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 108TEST(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