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