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
TEST(IntervalSetTest,DefaultConstructed)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
TEST(IntervalSetTest,InsertSingleElement)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
TEST(IntervalSetTest,InsertCoalesceWithPrevious)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
TEST(IntervalSetTest,InsertCoalesceWithFollowing)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
TEST(IntervalSetTest,InsertCoalesceBoth)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
TEST(IntervalSetTest,EraseSplittingLeft)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
TEST(IntervalSetTest,EraseSplittingRight)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
TEST(IntervalSetTest,EraseSplittingBoth)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