12d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===-- sanitizer_bvgraph.h -------------------------------------*- C++ -*-===// 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// BVGraph -- a directed graph. 122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// 132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines//===----------------------------------------------------------------------===// 142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#ifndef SANITIZER_BVGRAPH_H 162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#define SANITIZER_BVGRAPH_H 172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_common.h" 192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#include "sanitizer_bitvector.h" 202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesnamespace __sanitizer { 222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Directed graph of fixed size implemented as an array of bit vectors. 242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines// Not thread-safe, all accesses should be protected by an external lock. 252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinestemplate<class BV> 262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hinesclass BVGraph { 272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines public: 282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines enum SizeEnum { kSize = BV::kSize }; 292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr size() const { return kSize; } 302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // No CTOR. 312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void clear() { 322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < size(); i++) 332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines v[i].clear(); 342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool empty() const { 372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr i = 0; i < size(); i++) 382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!v[i].empty()) 392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return false; 402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return true; 412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if a new edge was added. 442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool addEdge(uptr from, uptr to) { 452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines check(from, to); 462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return v[from].setBit(to); 472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if at least one new edge was added. 502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr addEdges(const BV &from, uptr to, uptr added_edges[], 512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr max_added_edges) { 522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr res = 0; 532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines t1.copyFrom(from); 542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines while (!t1.empty()) { 552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr node = t1.getAndClearFirstOne(); 562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (v[node].setBit(to)) 572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (res < max_added_edges) 582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines added_edges[res++] = node; 592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // *EXPERIMENTAL* 642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if an edge from=>to exist. 652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // This function does not use any global state except for 'this' itself, 662d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // and thus can be called from different threads w/o locking. 672d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // This would be racy. 682d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // FIXME: investigate how much we can prove about this race being "benign". 692d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool hasEdge(uptr from, uptr to) { return v[from].getBit(to); } 702d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 712d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if the edge from=>to was removed. 722d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool removeEdge(uptr from, uptr to) { 732d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return v[from].clearBit(to); 742d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 752d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 762d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if at least one edge *=>to was removed. 772d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool removeEdgesTo(const BV &to) { 782d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool res = 0; 792d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr from = 0; from < size(); from++) { 802d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (v[from].setDifference(to)) 812d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines res = true; 822d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 832d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 842d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 852d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 862d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if at least one edge from=>* was removed. 872d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool removeEdgesFrom(const BV &from) { 882d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool res = false; 892d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines t1.copyFrom(from); 902d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines while (!t1.empty()) { 912d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx = t1.getAndClearFirstOne(); 922d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (!v[idx].empty()) { 932d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines v[idx].clear(); 942d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines res = true; 952d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 962d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 972d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res; 982d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 992d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1002d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void removeEdgesFrom(uptr from) { 1012d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return v[from].clear(); 1022d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1032d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1042d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool hasEdge(uptr from, uptr to) const { 1052d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines check(from, to); 1062d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return v[from].getBit(to); 1072d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1082d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1092d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Returns true if there is a path from the node 'from' 1102d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // to any of the nodes in 'targets'. 1112d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines bool isReachable(uptr from, const BV &targets) { 1122d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV &to_visit = t1, 1132d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines &visited = t2; 1142d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines to_visit.copyFrom(v[from]); 1152d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines visited.clear(); 1162d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines visited.setBit(from); 1172d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines while (!to_visit.empty()) { 1182d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx = to_visit.getAndClearFirstOne(); 1192d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (visited.setBit(idx)) 1202d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines to_visit.setUnion(v[idx]); 1212d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1222d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return targets.intersectsWith(visited); 1232d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1242d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1252d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Finds a path from 'from' to one of the nodes in 'target', 1262d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // stores up to 'path_size' items of the path into 'path', 1272d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // returns the path length, or 0 if there is no path of size 'path_size'. 1282d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr findPath(uptr from, const BV &targets, uptr *path, uptr path_size) { 1292d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (path_size == 0) 1302d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return 0; 1312d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines path[0] = from; 1322d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (targets.getBit(from)) 1332d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return 1; 1342d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // The function is recursive, so we don't want to create BV on stack. 1352d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Instead of a getAndClearFirstOne loop we use the slower iterator. 1362d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (typename BV::Iterator it(v[from]); it.hasNext(); ) { 1372d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr idx = it.next(); 1382d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (uptr res = findPath(idx, targets, path + 1, path_size - 1)) 1392d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return res + 1; 1402d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1412d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return 0; 1422d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1432d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1442d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Same as findPath, but finds a shortest path. 1452d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr findShortestPath(uptr from, const BV &targets, uptr *path, 1462d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines uptr path_size) { 1472d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines for (uptr p = 1; p <= path_size; p++) 1482d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines if (findPath(from, targets, path, p) == p) 1492d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return p; 1502d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines return 0; 1512d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1522d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1532d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines private: 1542d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines void check(uptr idx1, uptr idx2) const { 1552d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LT(idx1, size()); 1562d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines CHECK_LT(idx2, size()); 1572d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines } 1582d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV v[kSize]; 1592d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines // Keep temporary vectors here since we can not create large objects on stack. 1602d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines BV t1, t2; 1612d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines}; 1622d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1632d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines} // namespace __sanitizer 1642d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines 1652d1fdb26e458c4ddc04155c1d421bced3ba90cd0Stephen Hines#endif // SANITIZER_BVGRAPH_H 166