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