|
120
|
1 //===- llvm/unittest/ADT/PriorityWorklist.cpp -----------------------------===//
|
|
|
2 //
|
|
147
|
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
|
|
120
|
6 //
|
|
|
7 //===----------------------------------------------------------------------===//
|
|
|
8 //
|
|
|
9 // PriorityWorklist unit tests.
|
|
|
10 //
|
|
|
11 //===----------------------------------------------------------------------===//
|
|
|
12
|
|
|
13 #include "llvm/ADT/PriorityWorklist.h"
|
|
|
14 #include "gtest/gtest.h"
|
|
121
|
15 #include <list>
|
|
|
16 #include <vector>
|
|
120
|
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_CASE(PriorityWorklistTest, TestTypes);
|
|
|
26
|
|
|
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
|
|
121
|
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
|
|
120
|
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 }
|
