166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman//===- llvm/unittest/ADT/SmallBitVectorTest.cpp - SmallBitVector tests ----===// 266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman// 366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman// The LLVM Compiler Infrastructure 466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman// 566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman// This file is distributed under the University of Illinois Open Source 666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman// License. See LICENSE.TXT for details. 766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman// 866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman//===----------------------------------------------------------------------===// 966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 1066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman#include "llvm/ADT/SmallBitVector.h" 1166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman#include "gtest/gtest.h" 1266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 1366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Baumanusing namespace llvm; 1466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 1566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Baumannamespace { 1666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 1766b8ab22586debccb1f787d4d52b7f042d4ddeb8John BaumanTEST(SmallBitVectorTest, TrivialOperation) { 1866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman SmallBitVector Vec; 1966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(0U, Vec.count()); 2066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(0U, Vec.size()); 2166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec.any()); 2266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.all()); 2366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.none()); 2466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.empty()); 2566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 2666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(5, true); 2766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(5U, Vec.count()); 2866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(5U, Vec.size()); 2966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.any()); 3066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.all()); 3166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec.none()); 3266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec.empty()); 3366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 3466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(11); 3566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(5U, Vec.count()); 3666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(11U, Vec.size()); 3766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.any()); 3866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec.all()); 3966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec.none()); 4066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec.empty()); 4166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 4266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman SmallBitVector Inv = ~Vec; 4366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(6U, Inv.count()); 4466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(11U, Inv.size()); 4566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Inv.any()); 4666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Inv.all()); 4766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Inv.none()); 4866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Inv.empty()); 4966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 5066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Inv == Vec); 5166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Inv != Vec); 5266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec = ~Vec; 5366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Inv == Vec); 5466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Inv != Vec); 5566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 5666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman // Add some "interesting" data to Vec. 5766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(23, true); 5866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(25, false); 5966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(26, true); 6066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(29, false); 6166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(33, true); 6266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(57, false); 6366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman unsigned Count = 0; 6466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) { 6566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman ++Count; 6666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec[i]); 6766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.test(i)); 6866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman } 6966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(Count, Vec.count()); 7066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(Count, 23u); 7166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec[0]); 7266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec[32]); 7366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec[56]); 7466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(61, false); 7566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 7666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman SmallBitVector Copy = Vec; 7766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman SmallBitVector Alt(3, false); 7866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Alt.resize(6, true); 7966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman std::swap(Alt, Vec); 8066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Copy == Alt); 8166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.size() == 6); 8266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.count() == 3); 8366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.find_first() == 3); 8466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman std::swap(Copy, Vec); 8566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 8666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman // Add some more "interesting" data. 8766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(68, true); 8866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(78, false); 8966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(89, true); 9066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(90, false); 9166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(91, true); 9266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.resize(130, false); 9366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Count = 0; 9466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman for (unsigned i = Vec.find_first(); i != -1u; i = Vec.find_next(i)) { 9566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman ++Count; 9666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec[i]); 9766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.test(i)); 9866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman } 9966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(Count, Vec.count()); 10066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(Count, 42u); 10166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec[0]); 10266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec[32]); 10366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec[60]); 10466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec[129]); 10566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 10666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.flip(60); 10766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec[60]); 10866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(Count + 1, Vec.count()); 10966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.flip(60); 11066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec[60]); 11166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(Count, Vec.count()); 11266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 11366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.reset(32); 11466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec[32]); 11566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(Count - 1, Vec.count()); 11666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.set(32); 11766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec[32]); 11866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(Count, Vec.count()); 11966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 12066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.flip(); 12166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(Vec.size() - Count, Vec.count()); 12266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 12366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.reset(); 12466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(0U, Vec.count()); 12566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(130U, Vec.size()); 12666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec.any()); 12766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec.all()); 12866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.none()); 12966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec.empty()); 13066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 13166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Inv = ~SmallBitVector(); 13266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(0U, Inv.count()); 13366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(0U, Inv.size()); 13466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Inv.any()); 13566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Inv.all()); 13666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Inv.none()); 13766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Inv.empty()); 13866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 13966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec.clear(); 14066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(0U, Vec.count()); 14166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(0U, Vec.size()); 14266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(Vec.any()); 14366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.all()); 14466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.none()); 14566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.empty()); 14666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman} 14766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 14866b8ab22586debccb1f787d4d52b7f042d4ddeb8John BaumanTEST(SmallBitVectorTest, CompoundAssignment) { 14966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman SmallBitVector A; 15066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman A.resize(10); 15166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman A.set(4); 15266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman A.set(7); 15366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 15466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman SmallBitVector B; 15566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman B.resize(50); 15666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman B.set(5); 15766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman B.set(18); 15866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 15966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman A |= B; 16066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(A.test(4)); 16166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(A.test(5)); 16266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(A.test(7)); 16366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(A.test(18)); 16466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(4U, A.count()); 16566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(50U, A.size()); 16666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 16766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman B.resize(10); 16866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman B.set(); 16966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman B.reset(2); 17066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman B.reset(7); 17166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman A &= B; 17266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(A.test(2)); 17366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_FALSE(A.test(7)); 17466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(2U, A.count()); 17566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(50U, A.size()); 17666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 17766b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman B.resize(100); 17866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman B.set(); 17966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 18066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman A ^= B; 18166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(A.test(2)); 18266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(A.test(7)); 18366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(98U, A.count()); 18466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(100U, A.size()); 18566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman} 18666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 18766b8ab22586debccb1f787d4d52b7f042d4ddeb8John BaumanTEST(SmallBitVectorTest, ProxyIndex) { 18866b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman SmallBitVector Vec(3); 18966b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.none()); 19066b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec[0] = Vec[1] = Vec[2] = true; 19166b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_EQ(Vec.size(), Vec.count()); 19266b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman Vec[2] = Vec[1] = Vec[0] = false; 19366b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman EXPECT_TRUE(Vec.none()); 19466b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman} 19566b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman 19666b8ab22586debccb1f787d4d52b7f042d4ddeb8John Bauman} 197