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