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