unittests/ADT/PriorityWorklistTest.cpp

   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 #include <list>
  17 #include <vector>
  18
  19 namespace {
  20
  21 using namespace llvm;
  22
  23 template <typename T> class PriorityWorklistTest : public ::testing::Test {};
  24 typedef ::testing::Types<PriorityWorklist<int>, SmallPriorityWorklist<int, 2>>
  25     TestTypes;
  26 TYPED_TEST_CASE(PriorityWorklistTest, TestTypes);
  27
  28 TYPED_TEST(PriorityWorklistTest, Basic) {
  29   TypeParam W;
  30   EXPECT_TRUE(W.empty());
  31   EXPECT_EQ(0u, W.size());
  32   EXPECT_FALSE(W.count(42));
  33
  34   EXPECT_TRUE(W.insert(21));
  35   EXPECT_TRUE(W.insert(42));
  36   EXPECT_TRUE(W.insert(17));
  37
  38   EXPECT_FALSE(W.empty());
  39   EXPECT_EQ(3u, W.size());
  40   EXPECT_TRUE(W.count(42));
  41
  42   EXPECT_FALSE(W.erase(75));
  43   EXPECT_EQ(3u, W.size());
  44   EXPECT_EQ(17, W.back());
  45
  46   EXPECT_TRUE(W.erase(17));
  47   EXPECT_FALSE(W.count(17));
  48   EXPECT_EQ(2u, W.size());
  49   EXPECT_EQ(42, W.back());
  50
  51   W.clear();
  52   EXPECT_TRUE(W.empty());
  53   EXPECT_EQ(0u, W.size());
  54
  55   EXPECT_TRUE(W.insert(21));
  56   EXPECT_TRUE(W.insert(42));
  57   EXPECT_TRUE(W.insert(12));
  58   EXPECT_TRUE(W.insert(17));
  59   EXPECT_TRUE(W.count(12));
  60   EXPECT_TRUE(W.count(17));
  61   EXPECT_EQ(4u, W.size());
  62   EXPECT_EQ(17, W.back());
  63   EXPECT_TRUE(W.erase(12));
  64   EXPECT_FALSE(W.count(12));
  65   EXPECT_TRUE(W.count(17));
  66   EXPECT_EQ(3u, W.size());
  67   EXPECT_EQ(17, W.back());
  68
  69   EXPECT_FALSE(W.insert(42));
  70   EXPECT_EQ(3u, W.size());
  71   EXPECT_EQ(42, W.pop_back_val());
  72   EXPECT_EQ(17, W.pop_back_val());
  73   EXPECT_EQ(21, W.pop_back_val());
  74   EXPECT_TRUE(W.empty());
  75 }
  76
  77 TYPED_TEST(PriorityWorklistTest, InsertSequence) {
  78   TypeParam W;
  79   ASSERT_TRUE(W.insert(2));
  80   ASSERT_TRUE(W.insert(4));
  81   ASSERT_TRUE(W.insert(7));
  82   // Insert a sequence that has internal duplicates and a duplicate among
  83   // existing entries.
  84   W.insert(std::vector<int>({42, 13, 42, 7, 8}));
  85   EXPECT_EQ(8, W.pop_back_val());
  86   EXPECT_EQ(7, W.pop_back_val());
  87   EXPECT_EQ(42, W.pop_back_val());
  88   EXPECT_EQ(13, W.pop_back_val());
  89   EXPECT_EQ(4, W.pop_back_val());
  90   EXPECT_EQ(2, W.pop_back_val());
  91   ASSERT_TRUE(W.empty());
  92
  93   // Simpler tests with various other input types.
  94   ASSERT_TRUE(W.insert(2));
  95   ASSERT_TRUE(W.insert(7));
  96   // Use a non-random-access container.
  97   W.insert(std::list<int>({7, 5}));
  98   EXPECT_EQ(5, W.pop_back_val());
  99   EXPECT_EQ(7, W.pop_back_val());
 100   EXPECT_EQ(2, W.pop_back_val());
 101   ASSERT_TRUE(W.empty());
 102
 103   ASSERT_TRUE(W.insert(2));
 104   ASSERT_TRUE(W.insert(7));
 105   // Use a raw array.
 106   int A[] = {7, 5};
 107   W.insert(A);
 108   EXPECT_EQ(5, W.pop_back_val());
 109   EXPECT_EQ(7, W.pop_back_val());
 110   EXPECT_EQ(2, W.pop_back_val());
 111   ASSERT_TRUE(W.empty());
 112
 113   ASSERT_TRUE(W.insert(2));
 114   ASSERT_TRUE(W.insert(7));
 115   // Inserting an empty sequence does nothing.
 116   W.insert(std::vector<int>());
 117   EXPECT_EQ(7, W.pop_back_val());
 118   EXPECT_EQ(2, W.pop_back_val());
 119   ASSERT_TRUE(W.empty());
 120 }
 121
 122 TYPED_TEST(PriorityWorklistTest, EraseIf) {
 123   TypeParam W;
 124   W.insert(23);
 125   W.insert(10);
 126   W.insert(47);
 127   W.insert(42);
 128   W.insert(23);
 129   W.insert(13);
 130   W.insert(26);
 131   W.insert(42);
 132   EXPECT_EQ(6u, W.size());
 133
 134   EXPECT_FALSE(W.erase_if([](int i) { return i > 100; }));
 135   EXPECT_EQ(6u, W.size());
 136   EXPECT_EQ(42, W.back());
 137
 138   EXPECT_TRUE(W.erase_if([](int i) {
 139     assert(i != 0 && "Saw a null value!");
 140     return (i & 1) == 0;
 141   }));
 142   EXPECT_EQ(3u, W.size());
 143   EXPECT_FALSE(W.count(42));
 144   EXPECT_FALSE(W.count(26));
 145   EXPECT_FALSE(W.count(10));
 146   EXPECT_FALSE(W.insert(47));
 147   EXPECT_FALSE(W.insert(23));
 148   EXPECT_EQ(23, W.pop_back_val());
 149   EXPECT_EQ(47, W.pop_back_val());
 150   EXPECT_EQ(13, W.pop_back_val());
 151 }
 152
 153 }