153 lines · cpp
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-exception6//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 18namespace {19 20using namespace llvm;21 22template <typename T> class PriorityWorklistTest : public ::testing::Test {};23using TestTypes =24 ::testing::Types<PriorityWorklist<int>, SmallPriorityWorklist<int, 2>>;25TYPED_TEST_SUITE(PriorityWorklistTest, TestTypes, );26 27TYPED_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 76TYPED_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 among82 // 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 121TYPED_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