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
  17 namespace {
  18
  19 using namespace llvm;
  20
  21 template <typename T> class PriorityWorklistTest : public ::testing::Test {};
  22 typedef ::testing::Types<PriorityWorklist<int>, SmallPriorityWorklist<int, 2>>
  23     TestTypes;
  24 TYPED_TEST_CASE(PriorityWorklistTest, TestTypes);
  25
  26 TYPED_TEST(PriorityWorklistTest, Basic) {
  27   TypeParam W;
  28   EXPECT_TRUE(W.empty());
  29   EXPECT_EQ(0u, W.size());
  30   EXPECT_FALSE(W.count(42));
  31
  32   EXPECT_TRUE(W.insert(21));
  33   EXPECT_TRUE(W.insert(42));
  34   EXPECT_TRUE(W.insert(17));
  35
  36   EXPECT_FALSE(W.empty());
  37   EXPECT_EQ(3u, W.size());
  38   EXPECT_TRUE(W.count(42));
  39
  40   EXPECT_FALSE(W.erase(75));
  41   EXPECT_EQ(3u, W.size());
  42   EXPECT_EQ(17, W.back());
  43
  44   EXPECT_TRUE(W.erase(17));
  45   EXPECT_FALSE(W.count(17));
  46   EXPECT_EQ(2u, W.size());
  47   EXPECT_EQ(42, W.back());
  48
  49   W.clear();
  50   EXPECT_TRUE(W.empty());
  51   EXPECT_EQ(0u, W.size());
  52
  53   EXPECT_TRUE(W.insert(21));
  54   EXPECT_TRUE(W.insert(42));
  55   EXPECT_TRUE(W.insert(12));
  56   EXPECT_TRUE(W.insert(17));
  57   EXPECT_TRUE(W.count(12));
  58   EXPECT_TRUE(W.count(17));
  59   EXPECT_EQ(4u, W.size());
  60   EXPECT_EQ(17, W.back());
  61   EXPECT_TRUE(W.erase(12));
  62   EXPECT_FALSE(W.count(12));
  63   EXPECT_TRUE(W.count(17));
  64   EXPECT_EQ(3u, W.size());
  65   EXPECT_EQ(17, W.back());
  66
  67   EXPECT_FALSE(W.insert(42));
  68   EXPECT_EQ(3u, W.size());
  69   EXPECT_EQ(42, W.pop_back_val());
  70   EXPECT_EQ(17, W.pop_back_val());
  71   EXPECT_EQ(21, W.pop_back_val());
  72   EXPECT_TRUE(W.empty());
  73 }
  74
  75 TYPED_TEST(PriorityWorklistTest, EraseIf) {
  76   TypeParam W;
  77   W.insert(23);
  78   W.insert(10);
  79   W.insert(47);
  80   W.insert(42);
  81   W.insert(23);
  82   W.insert(13);
  83   W.insert(26);
  84   W.insert(42);
  85   EXPECT_EQ(6u, W.size());
  86
  87   EXPECT_FALSE(W.erase_if([](int i) { return i > 100; }));
  88   EXPECT_EQ(6u, W.size());
  89   EXPECT_EQ(42, W.back());
  90
  91   EXPECT_TRUE(W.erase_if([](int i) {
  92     assert(i != 0 && "Saw a null value!");
  93     return (i & 1) == 0;
  94   }));
  95   EXPECT_EQ(3u, W.size());
  96   EXPECT_FALSE(W.count(42));
  97   EXPECT_FALSE(W.count(26));
  98   EXPECT_FALSE(W.count(10));
  99   EXPECT_FALSE(W.insert(47));
 100   EXPECT_FALSE(W.insert(23));
 101   EXPECT_EQ(23, W.pop_back_val());
 102   EXPECT_EQ(47, W.pop_back_val());
 103   EXPECT_EQ(13, W.pop_back_val());
 104 }
 105
 106 }