122 lines · cpp
1//===- IntervalSetTest.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-exception6//7//===----------------------------------------------------------------------===//8//9// This file is a part of the ORC runtime.10//11//===----------------------------------------------------------------------===//12 13#include "orc-rt/IntervalSet.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 the84 // 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 the97 // 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 and110 // 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