llvm/unittests/ADT/PriorityWorklistTest.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-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 }