12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===-- sanitizer_bvgraph_test.cc -----------------------------------------===// 22d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 32d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// The LLVM Compiler Infrastructure 42d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 52d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This file is distributed under the University of Illinois Open Source 62d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// License. See LICENSE.TXT for details. 72d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 82d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 92d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// This file is a part of Sanitizer runtime. 112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Tests for sanitizer_bvgraph.h. 122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_common/sanitizer_bvgraph.h" 152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_test_utils.h" 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "gtest/gtest.h" 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include <algorithm> 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include <vector> 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include <set> 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesusing namespace __sanitizer; 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesusing namespace std; 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestypedef BasicBitVector<u8> BV1; 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestypedef BasicBitVector<> BV2; 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestypedef TwoLevelBitVector<> BV3; 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestypedef TwoLevelBitVector<3, BasicBitVector<u8> > BV4; 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<class G> 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid PrintGraph(const G &g) { 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < g.size(); i++) { 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr j = 0; j < g.size(); j++) { 362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines fprintf(stderr, "%d", g.hasEdge(i, j)); 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines fprintf(stderr, "\n"); 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesclass SimpleGraph { 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void clear() { s_.clear(); } 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool addEdge(uptr from, uptr to) { 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return s_.insert(idx(from, to)).second; 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool removeEdge(uptr from, uptr to) { 502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return s_.erase(idx(from, to)); 512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines template <class G> 532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void checkSameAs(G *g) { 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (set<uptr>::iterator it = s_.begin(); it != s_.end(); ++it) { 552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr from = *it >> 16; 562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr to = *it & ((1 << 16) - 1); 572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g->removeEdge(from, to)); 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g->empty()); 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx(uptr from, uptr to) { 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LE(from|to, 1 << 16); 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return (from << 16) + to; 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines set<uptr> s_; 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid BasicTest() { 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BVGraph<BV> g; 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.clear(); 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV target; 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines SimpleGraph s_g; 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines set<uptr> s; 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines set<uptr> s_target; 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines int num_reachable = 0; 782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (int it = 0; it < 1000; it++) { 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines target.clear(); 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s_target.clear(); 812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (int t = 0; t < 4; t++) { 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx = (uptr)my_rand() % g.size(); 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(target.setBit(idx), s_target.insert(idx).second); 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr from = my_rand() % g.size(); 862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr to = my_rand() % g.size(); 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to)); 882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.hasEdge(from, to)); 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (int i = 0; i < 10; i++) { 902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines from = my_rand() % g.size(); 912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool is_reachable = g.isReachable(from, target); 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (is_reachable) { 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr path[BV::kSize]; 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr len; 952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (len = 1; len < BV::kSize; len++) { 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (g.findPath(from, target, path, len) == len) 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines break; 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_LT(len, BV::kSize); 1002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(target.getBit(path[len - 1])); 1012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // fprintf(stderr, "reachable: %zd; path %zd {%zd %zd %zd}\n", 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // from, len, path[0], path[1], path[2]); 1032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines num_reachable++; 1042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_GT(num_reachable, 0); 1082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(BVGraph, BasicTest) { 1112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BasicTest<BV1>(); 1122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BasicTest<BV2>(); 1132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BasicTest<BV3>(); 1142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BasicTest<BV4>(); 1152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 1182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RemoveEdges() { 1192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines SimpleGraph s_g; 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BVGraph<BV> g; 1212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.clear(); 1222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV bv; 1232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines set<uptr> s; 1242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (int it = 0; it < 100; it++) { 1252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s.clear(); 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bv.clear(); 1272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s_g.clear(); 1282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.clear(); 1292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr j = 0; j < g.size() * 2; j++) { 1302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr from = my_rand() % g.size(); 1312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr to = my_rand() % g.size(); 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(g.addEdge(from, to), s_g.addEdge(from, to)); 1332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr j = 0; j < 5; j++) { 1352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx = my_rand() % g.size(); 1362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s.insert(idx); 1372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bv.setBit(idx); 1382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (it % 2) { 1412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.removeEdgesFrom(bv); 1422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (set<uptr>::iterator from = s.begin(); from != s.end(); ++from) { 1432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr to = 0; to < g.size(); to++) 1442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s_g.removeEdge(*from, to); 1452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } else { 1472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.removeEdgesTo(bv); 1482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (set<uptr>::iterator to = s.begin(); to != s.end(); ++to) { 1492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr from = 0; from < g.size(); from++) 1502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s_g.removeEdge(from, *to); 1512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines s_g.checkSameAs(&g); 1542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(BVGraph, RemoveEdges) { 1582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RemoveEdges<BV1>(); 1592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RemoveEdges<BV2>(); 1602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RemoveEdges<BV3>(); 1612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RemoveEdges<BV4>(); 1622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 1632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 1652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid Test_isReachable() { 1662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr path[5]; 1672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BVGraph<BV> g; 1682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.clear(); 1692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV target; 1702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines target.clear(); 1712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr t0 = 0; 1722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr t1 = g.size() - 1; 1732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines target.setBit(t0); 1742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines target.setBit(t1); 1752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr f0 = 1; 1772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr f1 = 2; 1782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr f2 = g.size() / 2; 1792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr f3 = g.size() - 2; 1802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.isReachable(f0, target)); 1822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.isReachable(f1, target)); 1832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.isReachable(f2, target)); 1842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.isReachable(f3, target)); 1852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(f0, f1); 1872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(f1, f2); 1882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(f2, f3); 1892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.isReachable(f0, target)); 1902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.isReachable(f1, target)); 1912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.isReachable(f2, target)); 1922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.isReachable(f3, target)); 1932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(f1, t0); 1952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.isReachable(f0, target)); 1962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.isReachable(f1, target)); 1972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.isReachable(f2, target)); 1982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.isReachable(f3, target)); 1992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(g.findPath(f0, target, path, ARRAY_SIZE(path)), 3U); 2002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(path[0], f0); 2012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(path[1], f1); 2022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(path[2], t0); 2032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(g.findPath(f1, target, path, ARRAY_SIZE(path)), 2U); 2042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(path[0], f1); 2052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(path[1], t0); 2062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(f3, t1); 2082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.isReachable(f0, target)); 2092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.isReachable(f1, target)); 2102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.isReachable(f2, target)); 2112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.isReachable(f3, target)); 2122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(BVGraph, isReachable) { 2152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Test_isReachable<BV1>(); 2162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Test_isReachable<BV2>(); 2172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Test_isReachable<BV3>(); 2182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines Test_isReachable<BV4>(); 2192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 2222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid LongCycle() { 2232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BVGraph<BV> g; 2242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.clear(); 2252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines vector<uptr> path_vec(g.size()); 2262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr *path = path_vec.data(); 2272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr start = 5; 2282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = start; i < g.size() - 1; i++) { 2292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(i, i + 1); 2302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr j = 0; j < start; j++) 2312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(i, j); 2322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Bad graph that looks like this: 2342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 00000000000000 2352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 00000000000000 2362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 00000000000000 2372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 00000000000000 2382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 00000000000000 2392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 11111010000000 2402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 11111001000000 2412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 11111000100000 2422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 11111000010000 2432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 11111000001000 2442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 11111000000100 2452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 11111000000010 2462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 11111000000001 2472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // if (g.size() <= 64) PrintGraph(g); 2482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV target; 2492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = start + 1; i < g.size(); i += 11) { 2502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // if ((i & (i - 1)) == 0) fprintf(stderr, "Path: : %zd\n", i); 2512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines target.clear(); 2522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines target.setBit(i); 2532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.isReachable(start, target)); 2542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(g.findPath(start, target, path, g.size()), i - start + 1); 2552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 2562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(BVGraph, LongCycle) { 2592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines LongCycle<BV1>(); 2602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines LongCycle<BV2>(); 2612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines LongCycle<BV3>(); 2622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines LongCycle<BV4>(); 2632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 2662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid ShortestPath() { 2672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr path[8]; 2682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BVGraph<BV> g; 2692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.clear(); 2702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV t7; 2712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines t7.clear(); 2722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines t7.setBit(7); 2732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 1=>2=>3=>4=>5=>6=>7 2742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // 1=>7 2752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(1, 2); 2762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(2, 3); 2772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(3, 4); 2782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(4, 5); 2792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(5, 6); 2802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(6, 7); 2812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.addEdge(1, 7); 2822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.isReachable(1, t7)); 2832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // No path of length 1. 2842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(0U, g.findPath(1, t7, path, 1)); 2852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Trying to find a path of len 2..6 gives path of len 2. 2862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, g.findPath(1, t7, path, 2)); 2872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, g.findPath(1, t7, path, 3)); 2882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, g.findPath(1, t7, path, 4)); 2892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, g.findPath(1, t7, path, 5)); 2902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, g.findPath(1, t7, path, 6)); 2912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Trying to find a path of len 7 gives path of len 7, because this is DFS. 2922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(7U, g.findPath(1, t7, path, 7)); 2932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // But findShortestPath will find the shortest path. 2942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 2)); 2952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, g.findShortestPath(1, t7, path, 7)); 2962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 2972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 2982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(BVGraph, ShortestPath) { 2992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ShortestPath<BV1>(); 3002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ShortestPath<BV2>(); 3012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ShortestPath<BV3>(); 3022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines ShortestPath<BV4>(); 3032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate <class BV> 3062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesvoid RunAddEdgesTest() { 3072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BVGraph<BV> g; 3082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV from; 3092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines const int kMaxEdges = 10; 3102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr added_edges[kMaxEdges]; 3112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines g.clear(); 3122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines from.clear(); 3132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(0U, g.addEdges(from, 0, added_edges, kMaxEdges)); 3142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges)); 3152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines from.setBit(0); 3162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(1U, g.addEdges(from, 1, added_edges, kMaxEdges)); 3172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(0U, added_edges[0]); 3182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(0U, g.addEdges(from, 1, added_edges, kMaxEdges)); 3192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines from.clear(); 3212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines from.setBit(1); 3222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(1U, g.addEdges(from, 4, added_edges, kMaxEdges)); 3232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.hasEdge(1, 4)); 3242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.hasEdge(1, 5)); 3252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(1U, added_edges[0]); 3262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines from.setBit(2); 3272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines from.setBit(3); 3282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, g.addEdges(from, 4, added_edges, kMaxEdges)); 3292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.hasEdge(2, 4)); 3302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.hasEdge(2, 5)); 3312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_TRUE(g.hasEdge(3, 4)); 3322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_FALSE(g.hasEdge(3, 5)); 3332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(2U, added_edges[0]); 3342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines EXPECT_EQ(3U, added_edges[1]); 3352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 3362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 3372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen HinesTEST(BVGraph, AddEdgesTest) { 3382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines RunAddEdgesTest<BV2>(); 3392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} 340