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