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 | |
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 | |
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 | |
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 | |