190 lines · 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-exception6//7//===----------------------------------------------------------------------===//8 9#include "llvm/ADT/SparseBitVector.h"10#include "gtest/gtest.h"11 12using namespace llvm;13 14namespace {15 16TEST(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 56TEST(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 86TEST(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 150TEST(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 a172 // 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}190