1*3cab2bb3Spatrick //===-- sanitizer_bvgraph.h -------------------------------------*- C++ -*-===// 2*3cab2bb3Spatrick // 3*3cab2bb3Spatrick // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4*3cab2bb3Spatrick // See https://llvm.org/LICENSE.txt for license information. 5*3cab2bb3Spatrick // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6*3cab2bb3Spatrick // 7*3cab2bb3Spatrick //===----------------------------------------------------------------------===// 8*3cab2bb3Spatrick // 9*3cab2bb3Spatrick // This file is a part of Sanitizer runtime. 10*3cab2bb3Spatrick // BVGraph -- a directed graph. 11*3cab2bb3Spatrick // 12*3cab2bb3Spatrick //===----------------------------------------------------------------------===// 13*3cab2bb3Spatrick 14*3cab2bb3Spatrick #ifndef SANITIZER_BVGRAPH_H 15*3cab2bb3Spatrick #define SANITIZER_BVGRAPH_H 16*3cab2bb3Spatrick 17*3cab2bb3Spatrick #include "sanitizer_common.h" 18*3cab2bb3Spatrick #include "sanitizer_bitvector.h" 19*3cab2bb3Spatrick 20*3cab2bb3Spatrick namespace __sanitizer { 21*3cab2bb3Spatrick 22*3cab2bb3Spatrick // Directed graph of fixed size implemented as an array of bit vectors. 23*3cab2bb3Spatrick // Not thread-safe, all accesses should be protected by an external lock. 24*3cab2bb3Spatrick template<class BV> 25*3cab2bb3Spatrick class BVGraph { 26*3cab2bb3Spatrick public: 27*3cab2bb3Spatrick enum SizeEnum : uptr { kSize = BV::kSize }; size()28*3cab2bb3Spatrick uptr size() const { return kSize; } 29*3cab2bb3Spatrick // No CTOR. clear()30*3cab2bb3Spatrick void clear() { 31*3cab2bb3Spatrick for (uptr i = 0; i < size(); i++) 32*3cab2bb3Spatrick v[i].clear(); 33*3cab2bb3Spatrick } 34*3cab2bb3Spatrick empty()35*3cab2bb3Spatrick bool empty() const { 36*3cab2bb3Spatrick for (uptr i = 0; i < size(); i++) 37*3cab2bb3Spatrick if (!v[i].empty()) 38*3cab2bb3Spatrick return false; 39*3cab2bb3Spatrick return true; 40*3cab2bb3Spatrick } 41*3cab2bb3Spatrick 42*3cab2bb3Spatrick // Returns true if a new edge was added. addEdge(uptr from,uptr to)43*3cab2bb3Spatrick bool addEdge(uptr from, uptr to) { 44*3cab2bb3Spatrick check(from, to); 45*3cab2bb3Spatrick return v[from].setBit(to); 46*3cab2bb3Spatrick } 47*3cab2bb3Spatrick 48*3cab2bb3Spatrick // Returns true if at least one new edge was added. addEdges(const BV & from,uptr to,uptr added_edges[],uptr max_added_edges)49*3cab2bb3Spatrick uptr addEdges(const BV &from, uptr to, uptr added_edges[], 50*3cab2bb3Spatrick uptr max_added_edges) { 51*3cab2bb3Spatrick uptr res = 0; 52*3cab2bb3Spatrick t1.copyFrom(from); 53*3cab2bb3Spatrick while (!t1.empty()) { 54*3cab2bb3Spatrick uptr node = t1.getAndClearFirstOne(); 55*3cab2bb3Spatrick if (v[node].setBit(to)) 56*3cab2bb3Spatrick if (res < max_added_edges) 57*3cab2bb3Spatrick added_edges[res++] = node; 58*3cab2bb3Spatrick } 59*3cab2bb3Spatrick return res; 60*3cab2bb3Spatrick } 61*3cab2bb3Spatrick 62*3cab2bb3Spatrick // *EXPERIMENTAL* 63*3cab2bb3Spatrick // Returns true if an edge from=>to exist. 64*3cab2bb3Spatrick // This function does not use any global state except for 'this' itself, 65*3cab2bb3Spatrick // and thus can be called from different threads w/o locking. 66*3cab2bb3Spatrick // This would be racy. 67*3cab2bb3Spatrick // FIXME: investigate how much we can prove about this race being "benign". hasEdge(uptr from,uptr to)68*3cab2bb3Spatrick bool hasEdge(uptr from, uptr to) { return v[from].getBit(to); } 69*3cab2bb3Spatrick 70*3cab2bb3Spatrick // Returns true if the edge from=>to was removed. removeEdge(uptr from,uptr to)71*3cab2bb3Spatrick bool removeEdge(uptr from, uptr to) { 72*3cab2bb3Spatrick return v[from].clearBit(to); 73*3cab2bb3Spatrick } 74*3cab2bb3Spatrick 75*3cab2bb3Spatrick // Returns true if at least one edge *=>to was removed. removeEdgesTo(const BV & to)76*3cab2bb3Spatrick bool removeEdgesTo(const BV &to) { 77*3cab2bb3Spatrick bool res = 0; 78*3cab2bb3Spatrick for (uptr from = 0; from < size(); from++) { 79*3cab2bb3Spatrick if (v[from].setDifference(to)) 80*3cab2bb3Spatrick res = true; 81*3cab2bb3Spatrick } 82*3cab2bb3Spatrick return res; 83*3cab2bb3Spatrick } 84*3cab2bb3Spatrick 85*3cab2bb3Spatrick // Returns true if at least one edge from=>* was removed. removeEdgesFrom(const BV & from)86*3cab2bb3Spatrick bool removeEdgesFrom(const BV &from) { 87*3cab2bb3Spatrick bool res = false; 88*3cab2bb3Spatrick t1.copyFrom(from); 89*3cab2bb3Spatrick while (!t1.empty()) { 90*3cab2bb3Spatrick uptr idx = t1.getAndClearFirstOne(); 91*3cab2bb3Spatrick if (!v[idx].empty()) { 92*3cab2bb3Spatrick v[idx].clear(); 93*3cab2bb3Spatrick res = true; 94*3cab2bb3Spatrick } 95*3cab2bb3Spatrick } 96*3cab2bb3Spatrick return res; 97*3cab2bb3Spatrick } 98*3cab2bb3Spatrick removeEdgesFrom(uptr from)99*3cab2bb3Spatrick void removeEdgesFrom(uptr from) { 100*3cab2bb3Spatrick return v[from].clear(); 101*3cab2bb3Spatrick } 102*3cab2bb3Spatrick hasEdge(uptr from,uptr to)103*3cab2bb3Spatrick bool hasEdge(uptr from, uptr to) const { 104*3cab2bb3Spatrick check(from, to); 105*3cab2bb3Spatrick return v[from].getBit(to); 106*3cab2bb3Spatrick } 107*3cab2bb3Spatrick 108*3cab2bb3Spatrick // Returns true if there is a path from the node 'from' 109*3cab2bb3Spatrick // to any of the nodes in 'targets'. isReachable(uptr from,const BV & targets)110*3cab2bb3Spatrick bool isReachable(uptr from, const BV &targets) { 111*3cab2bb3Spatrick BV &to_visit = t1, 112*3cab2bb3Spatrick &visited = t2; 113*3cab2bb3Spatrick to_visit.copyFrom(v[from]); 114*3cab2bb3Spatrick visited.clear(); 115*3cab2bb3Spatrick visited.setBit(from); 116*3cab2bb3Spatrick while (!to_visit.empty()) { 117*3cab2bb3Spatrick uptr idx = to_visit.getAndClearFirstOne(); 118*3cab2bb3Spatrick if (visited.setBit(idx)) 119*3cab2bb3Spatrick to_visit.setUnion(v[idx]); 120*3cab2bb3Spatrick } 121*3cab2bb3Spatrick return targets.intersectsWith(visited); 122*3cab2bb3Spatrick } 123*3cab2bb3Spatrick 124*3cab2bb3Spatrick // Finds a path from 'from' to one of the nodes in 'target', 125*3cab2bb3Spatrick // stores up to 'path_size' items of the path into 'path', 126*3cab2bb3Spatrick // returns the path length, or 0 if there is no path of size 'path_size'. findPath(uptr from,const BV & targets,uptr * path,uptr path_size)127*3cab2bb3Spatrick uptr findPath(uptr from, const BV &targets, uptr *path, uptr path_size) { 128*3cab2bb3Spatrick if (path_size == 0) 129*3cab2bb3Spatrick return 0; 130*3cab2bb3Spatrick path[0] = from; 131*3cab2bb3Spatrick if (targets.getBit(from)) 132*3cab2bb3Spatrick return 1; 133*3cab2bb3Spatrick // The function is recursive, so we don't want to create BV on stack. 134*3cab2bb3Spatrick // Instead of a getAndClearFirstOne loop we use the slower iterator. 135*3cab2bb3Spatrick for (typename BV::Iterator it(v[from]); it.hasNext(); ) { 136*3cab2bb3Spatrick uptr idx = it.next(); 137*3cab2bb3Spatrick if (uptr res = findPath(idx, targets, path + 1, path_size - 1)) 138*3cab2bb3Spatrick return res + 1; 139*3cab2bb3Spatrick } 140*3cab2bb3Spatrick return 0; 141*3cab2bb3Spatrick } 142*3cab2bb3Spatrick 143*3cab2bb3Spatrick // Same as findPath, but finds a shortest path. findShortestPath(uptr from,const BV & targets,uptr * path,uptr path_size)144*3cab2bb3Spatrick uptr findShortestPath(uptr from, const BV &targets, uptr *path, 145*3cab2bb3Spatrick uptr path_size) { 146*3cab2bb3Spatrick for (uptr p = 1; p <= path_size; p++) 147*3cab2bb3Spatrick if (findPath(from, targets, path, p) == p) 148*3cab2bb3Spatrick return p; 149*3cab2bb3Spatrick return 0; 150*3cab2bb3Spatrick } 151*3cab2bb3Spatrick 152*3cab2bb3Spatrick private: check(uptr idx1,uptr idx2)153*3cab2bb3Spatrick void check(uptr idx1, uptr idx2) const { 154*3cab2bb3Spatrick CHECK_LT(idx1, size()); 155*3cab2bb3Spatrick CHECK_LT(idx2, size()); 156*3cab2bb3Spatrick } 157*3cab2bb3Spatrick BV v[kSize]; 158*3cab2bb3Spatrick // Keep temporary vectors here since we can not create large objects on stack. 159*3cab2bb3Spatrick BV t1, t2; 160*3cab2bb3Spatrick }; 161*3cab2bb3Spatrick 162*3cab2bb3Spatrick } // namespace __sanitizer 163*3cab2bb3Spatrick 164*3cab2bb3Spatrick #endif // SANITIZER_BVGRAPH_H 165