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(KS: 7, KE: 8);
44 S.insert(KS: 8, KE: 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(KS: 8, KE: 9);
56 S.insert(KS: 7, KE: 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(KS: 7, KE: 8);
68 S.insert(KS: 9, KE: 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(KS: 8, KE: 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(KS: 7, KE: 10);
88 EXPECT_FALSE(S.empty());
89 S.erase(KS: 9, KE: 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(KS: 7, KE: 10);
101 EXPECT_FALSE(S.empty());
102 S.erase(KS: 7, KE: 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(KS: 7, KE: 10);
114 EXPECT_FALSE(S.empty());
115 S.erase(KS: 8, KE: 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

source code of compiler-rt/lib/orc/tests/unit/interval_set_test.cpp