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