unittests/ADT/SparseBitVectorTest.cpp

   1 //===- llvm/unittest/ADT/SparseBitVectorTest.cpp - SparseBitVector tests --===//
   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 #include "llvm/ADT/SparseBitVector.h"
  11 #include "gtest/gtest.h"
  12
  13 using namespace llvm;
  14
  15 namespace {
  16
  17 TEST(SparseBitVectorTest, TrivialOperation) {
  18   SparseBitVector<> Vec;
  19   EXPECT_EQ(0U, Vec.count());
  20   EXPECT_FALSE(Vec.test(17));
  21   Vec.set(5);
  22   EXPECT_TRUE(Vec.test(5));
  23   EXPECT_FALSE(Vec.test(17));
  24   Vec.reset(6);
  25   EXPECT_TRUE(Vec.test(5));
  26   EXPECT_FALSE(Vec.test(6));
  27   Vec.reset(5);
  28   EXPECT_FALSE(Vec.test(5));
  29   EXPECT_TRUE(Vec.test_and_set(17));
  30   EXPECT_FALSE(Vec.test_and_set(17));
  31   EXPECT_TRUE(Vec.test(17));
  32   Vec.clear();
  33   EXPECT_FALSE(Vec.test(17));
  34 }
  35
  36 TEST(SparseBitVectorTest, IntersectWith) {
  37   SparseBitVector<> Vec, Other;
  38
  39   Vec.set(1);
  40   Other.set(1);
  41   EXPECT_FALSE(Vec &= Other);
  42   EXPECT_TRUE(Vec.test(1));
  43
  44   Vec.clear();
  45   Vec.set(5);
  46   Other.clear();
  47   Other.set(6);
  48   EXPECT_TRUE(Vec &= Other);
  49   EXPECT_TRUE(Vec.empty());
  50
  51   Vec.clear();
  52   Vec.set(5);
  53   Other.clear();
  54   Other.set(225);
  55   EXPECT_TRUE(Vec &= Other);
  56   EXPECT_TRUE(Vec.empty());
  57
  58   Vec.clear();
  59   Vec.set(225);
  60   Other.clear();
  61   Other.set(5);
  62   EXPECT_TRUE(Vec &= Other);
  63   EXPECT_TRUE(Vec.empty());
  64 }
  65
  66 TEST(SparseBitVectorTest, SelfAssignment) {
  67   SparseBitVector<> Vec, Other;
  68
  69   Vec.set(23);
  70   Vec.set(234);
  71   Vec = static_cast<SparseBitVector<> &>(Vec);
  72   EXPECT_TRUE(Vec.test(23));
  73   EXPECT_TRUE(Vec.test(234));
  74
  75   Vec.clear();
  76   Vec.set(17);
  77   Vec.set(256);
  78   EXPECT_FALSE(Vec |= Vec);
  79   EXPECT_TRUE(Vec.test(17));
  80   EXPECT_TRUE(Vec.test(256));
  81
  82   Vec.clear();
  83   Vec.set(56);
  84   Vec.set(517);
  85   EXPECT_FALSE(Vec &= Vec);
  86   EXPECT_TRUE(Vec.test(56));
  87   EXPECT_TRUE(Vec.test(517));
  88
  89   Vec.clear();
  90   Vec.set(99);
  91   Vec.set(333);
  92   EXPECT_TRUE(Vec.intersectWithComplement(Vec));
  93   EXPECT_TRUE(Vec.empty());
  94   EXPECT_FALSE(Vec.intersectWithComplement(Vec));
  95
  96   Vec.clear();
  97   Vec.set(28);
  98   Vec.set(43);
  99   Vec.intersectWithComplement(Vec, Vec);
 100   EXPECT_TRUE(Vec.empty());
 101
 102   Vec.clear();
 103   Vec.set(42);
 104   Vec.set(567);
 105   Other.set(55);
 106   Other.set(567);
 107   Vec.intersectWithComplement(Vec, Other);
 108   EXPECT_TRUE(Vec.test(42));
 109   EXPECT_FALSE(Vec.test(567));
 110
 111   Vec.clear();
 112   Vec.set(19);
 113   Vec.set(21);
 114   Other.clear();
 115   Other.set(19);
 116   Other.set(31);
 117   Vec.intersectWithComplement(Other, Vec);
 118   EXPECT_FALSE(Vec.test(19));
 119   EXPECT_TRUE(Vec.test(31));
 120
 121   Vec.clear();
 122   Vec.set(1);
 123   Other.clear();
 124   Other.set(59);
 125   Other.set(75);
 126   Vec.intersectWithComplement(Other, Other);
 127   EXPECT_TRUE(Vec.empty());
 128 }
 129
 130 TEST(SparseBitVectorTest, Find) {
 131   SparseBitVector<> Vec;
 132   Vec.set(1);
 133   EXPECT_EQ(1, Vec.find_first());
 134   EXPECT_EQ(1, Vec.find_last());
 135
 136   Vec.set(2);
 137   EXPECT_EQ(1, Vec.find_first());
 138   EXPECT_EQ(2, Vec.find_last());
 139
 140   Vec.set(0);
 141   Vec.set(3);
 142   EXPECT_EQ(0, Vec.find_first());
 143   EXPECT_EQ(3, Vec.find_last());
 144
 145   Vec.reset(1);
 146   Vec.reset(0);
 147   Vec.reset(3);
 148   EXPECT_EQ(2, Vec.find_first());
 149   EXPECT_EQ(2, Vec.find_last());
 150
 151   // Set some large bits to ensure we are pulling bits from more than just a
 152   // single bitword.
 153   Vec.set(500);
 154   Vec.set(2000);
 155   Vec.set(3000);
 156   Vec.set(4000);
 157   Vec.reset(2);
 158   EXPECT_EQ(500, Vec.find_first());
 159   EXPECT_EQ(4000, Vec.find_last());
 160
 161   Vec.reset(500);
 162   Vec.reset(3000);
 163   Vec.reset(4000);
 164   EXPECT_EQ(2000, Vec.find_first());
 165   EXPECT_EQ(2000, Vec.find_last());
 166
 167   Vec.clear();
 168 }
 169 }