unittests/ADT/SparseBitVectorTest.cpp

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