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