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