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