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 = 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 } 170