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