1 //===- llvm/unittest/ADT/PriorityWorklist.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 // PriorityWorklist unit tests.
10 //
11 //===----------------------------------------------------------------------===//
12
13 #include "llvm/ADT/PriorityWorklist.h"
14 #include "gtest/gtest.h"
15 #include <list>
16 #include <vector>
17
18 namespace {
19
20 using namespace llvm;
21
22 template <typename T> class PriorityWorklistTest : public ::testing::Test {};
23 typedef ::testing::Types<PriorityWorklist<int>, SmallPriorityWorklist<int, 2>>
24 TestTypes;
25 TYPED_TEST_SUITE(PriorityWorklistTest, TestTypes, );
26
TYPED_TEST(PriorityWorklistTest,Basic)27 TYPED_TEST(PriorityWorklistTest, Basic) {
28 TypeParam W;
29 EXPECT_TRUE(W.empty());
30 EXPECT_EQ(0u, W.size());
31 EXPECT_FALSE(W.count(42));
32
33 EXPECT_TRUE(W.insert(21));
34 EXPECT_TRUE(W.insert(42));
35 EXPECT_TRUE(W.insert(17));
36
37 EXPECT_FALSE(W.empty());
38 EXPECT_EQ(3u, W.size());
39 EXPECT_TRUE(W.count(42));
40
41 EXPECT_FALSE(W.erase(75));
42 EXPECT_EQ(3u, W.size());
43 EXPECT_EQ(17, W.back());
44
45 EXPECT_TRUE(W.erase(17));
46 EXPECT_FALSE(W.count(17));
47 EXPECT_EQ(2u, W.size());
48 EXPECT_EQ(42, W.back());
49
50 W.clear();
51 EXPECT_TRUE(W.empty());
52 EXPECT_EQ(0u, W.size());
53
54 EXPECT_TRUE(W.insert(21));
55 EXPECT_TRUE(W.insert(42));
56 EXPECT_TRUE(W.insert(12));
57 EXPECT_TRUE(W.insert(17));
58 EXPECT_TRUE(W.count(12));
59 EXPECT_TRUE(W.count(17));
60 EXPECT_EQ(4u, W.size());
61 EXPECT_EQ(17, W.back());
62 EXPECT_TRUE(W.erase(12));
63 EXPECT_FALSE(W.count(12));
64 EXPECT_TRUE(W.count(17));
65 EXPECT_EQ(3u, W.size());
66 EXPECT_EQ(17, W.back());
67
68 EXPECT_FALSE(W.insert(42));
69 EXPECT_EQ(3u, W.size());
70 EXPECT_EQ(42, W.pop_back_val());
71 EXPECT_EQ(17, W.pop_back_val());
72 EXPECT_EQ(21, W.pop_back_val());
73 EXPECT_TRUE(W.empty());
74 }
75
TYPED_TEST(PriorityWorklistTest,InsertSequence)76 TYPED_TEST(PriorityWorklistTest, InsertSequence) {
77 TypeParam W;
78 ASSERT_TRUE(W.insert(2));
79 ASSERT_TRUE(W.insert(4));
80 ASSERT_TRUE(W.insert(7));
81 // Insert a sequence that has internal duplicates and a duplicate among
82 // existing entries.
83 W.insert(std::vector<int>({42, 13, 42, 7, 8}));
84 EXPECT_EQ(8, W.pop_back_val());
85 EXPECT_EQ(7, W.pop_back_val());
86 EXPECT_EQ(42, W.pop_back_val());
87 EXPECT_EQ(13, W.pop_back_val());
88 EXPECT_EQ(4, W.pop_back_val());
89 EXPECT_EQ(2, W.pop_back_val());
90 ASSERT_TRUE(W.empty());
91
92 // Simpler tests with various other input types.
93 ASSERT_TRUE(W.insert(2));
94 ASSERT_TRUE(W.insert(7));
95 // Use a non-random-access container.
96 W.insert(std::list<int>({7, 5}));
97 EXPECT_EQ(5, W.pop_back_val());
98 EXPECT_EQ(7, W.pop_back_val());
99 EXPECT_EQ(2, W.pop_back_val());
100 ASSERT_TRUE(W.empty());
101
102 ASSERT_TRUE(W.insert(2));
103 ASSERT_TRUE(W.insert(7));
104 // Use a raw array.
105 int A[] = {7, 5};
106 W.insert(A);
107 EXPECT_EQ(5, W.pop_back_val());
108 EXPECT_EQ(7, W.pop_back_val());
109 EXPECT_EQ(2, W.pop_back_val());
110 ASSERT_TRUE(W.empty());
111
112 ASSERT_TRUE(W.insert(2));
113 ASSERT_TRUE(W.insert(7));
114 // Inserting an empty sequence does nothing.
115 W.insert(std::vector<int>());
116 EXPECT_EQ(7, W.pop_back_val());
117 EXPECT_EQ(2, W.pop_back_val());
118 ASSERT_TRUE(W.empty());
119 }
120
TYPED_TEST(PriorityWorklistTest,EraseIf)121 TYPED_TEST(PriorityWorklistTest, EraseIf) {
122 TypeParam W;
123 W.insert(23);
124 W.insert(10);
125 W.insert(47);
126 W.insert(42);
127 W.insert(23);
128 W.insert(13);
129 W.insert(26);
130 W.insert(42);
131 EXPECT_EQ(6u, W.size());
132
133 EXPECT_FALSE(W.erase_if([](int i) { return i > 100; }));
134 EXPECT_EQ(6u, W.size());
135 EXPECT_EQ(42, W.back());
136
137 EXPECT_TRUE(W.erase_if([](int i) {
138 assert(i != 0 && "Saw a null value!");
139 return (i & 1) == 0;
140 }));
141 EXPECT_EQ(3u, W.size());
142 EXPECT_FALSE(W.count(42));
143 EXPECT_FALSE(W.count(26));
144 EXPECT_FALSE(W.count(10));
145 EXPECT_FALSE(W.insert(47));
146 EXPECT_FALSE(W.insert(23));
147 EXPECT_EQ(23, W.pop_back_val());
148 EXPECT_EQ(47, W.pop_back_val());
149 EXPECT_EQ(13, W.pop_back_val());
150 }
151
152 }
153