1 //===- llvm/unittest/ADT/PriorityWorklist.cpp -----------------------------===//
2 //
3 // The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 //
10 // PriorityWorklist unit tests.
11 //
12 //===----------------------------------------------------------------------===//
13
14 #include "llvm/ADT/PriorityWorklist.h"
15 #include "gtest/gtest.h"
16
17 namespace {
18
19 using namespace llvm;
20
21 template <typename T> class PriorityWorklistTest : public ::testing::Test {};
22 typedef ::testing::Types<PriorityWorklist<int>, SmallPriorityWorklist<int, 2>>
23 TestTypes;
24 TYPED_TEST_CASE(PriorityWorklistTest, TestTypes);
25
TYPED_TEST(PriorityWorklistTest,Basic)26 TYPED_TEST(PriorityWorklistTest, Basic) {
27 TypeParam W;
28 EXPECT_TRUE(W.empty());
29 EXPECT_EQ(0u, W.size());
30 EXPECT_FALSE(W.count(42));
31
32 EXPECT_TRUE(W.insert(21));
33 EXPECT_TRUE(W.insert(42));
34 EXPECT_TRUE(W.insert(17));
35
36 EXPECT_FALSE(W.empty());
37 EXPECT_EQ(3u, W.size());
38 EXPECT_TRUE(W.count(42));
39
40 EXPECT_FALSE(W.erase(75));
41 EXPECT_EQ(3u, W.size());
42 EXPECT_EQ(17, W.back());
43
44 EXPECT_TRUE(W.erase(17));
45 EXPECT_FALSE(W.count(17));
46 EXPECT_EQ(2u, W.size());
47 EXPECT_EQ(42, W.back());
48
49 W.clear();
50 EXPECT_TRUE(W.empty());
51 EXPECT_EQ(0u, W.size());
52
53 EXPECT_TRUE(W.insert(21));
54 EXPECT_TRUE(W.insert(42));
55 EXPECT_TRUE(W.insert(12));
56 EXPECT_TRUE(W.insert(17));
57 EXPECT_TRUE(W.count(12));
58 EXPECT_TRUE(W.count(17));
59 EXPECT_EQ(4u, W.size());
60 EXPECT_EQ(17, W.back());
61 EXPECT_TRUE(W.erase(12));
62 EXPECT_FALSE(W.count(12));
63 EXPECT_TRUE(W.count(17));
64 EXPECT_EQ(3u, W.size());
65 EXPECT_EQ(17, W.back());
66
67 EXPECT_FALSE(W.insert(42));
68 EXPECT_EQ(3u, W.size());
69 EXPECT_EQ(42, W.pop_back_val());
70 EXPECT_EQ(17, W.pop_back_val());
71 EXPECT_EQ(21, W.pop_back_val());
72 EXPECT_TRUE(W.empty());
73 }
74
TYPED_TEST(PriorityWorklistTest,EraseIf)75 TYPED_TEST(PriorityWorklistTest, EraseIf) {
76 TypeParam W;
77 W.insert(23);
78 W.insert(10);
79 W.insert(47);
80 W.insert(42);
81 W.insert(23);
82 W.insert(13);
83 W.insert(26);
84 W.insert(42);
85 EXPECT_EQ(6u, W.size());
86
87 EXPECT_FALSE(W.erase_if([](int i) { return i > 100; }));
88 EXPECT_EQ(6u, W.size());
89 EXPECT_EQ(42, W.back());
90
91 EXPECT_TRUE(W.erase_if([](int i) {
92 assert(i != 0 && "Saw a null value!");
93 return (i & 1) == 0;
94 }));
95 EXPECT_EQ(3u, W.size());
96 EXPECT_FALSE(W.count(42));
97 EXPECT_FALSE(W.count(26));
98 EXPECT_FALSE(W.count(10));
99 EXPECT_FALSE(W.insert(47));
100 EXPECT_FALSE(W.insert(23));
101 EXPECT_EQ(23, W.pop_back_val());
102 EXPECT_EQ(47, W.pop_back_val());
103 EXPECT_EQ(13, W.pop_back_val());
104 }
105
106 }
107