1 //===-- sanitizer_bvgraph.h -------------------------------------*- C++ -*-===//
3 // The LLVM Compiler Infrastructure
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
8 //===----------------------------------------------------------------------===//
10 // This file is a part of Sanitizer runtime.
11 // BVGraph -- a directed graph.
13 //===----------------------------------------------------------------------===//
15 #ifndef SANITIZER_BVGRAPH_H
16 #define SANITIZER_BVGRAPH_H
18 #include "sanitizer_common.h"
19 #include "sanitizer_bitvector.h"
21 namespace __sanitizer {
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.
28 enum SizeEnum : uptr { kSize = BV::kSize };
29 uptr size() const { return kSize; }
32 for (uptr i = 0; i < size(); i++)
37 for (uptr i = 0; i < size(); i++)
43 // Returns true if a new edge was added.
44 bool addEdge(uptr from, uptr to) {
46 return v[from].setBit(to);
49 // Returns true if at least one new edge was added.
50 uptr addEdges(const BV &from, uptr to, uptr added_edges[],
51 uptr max_added_edges) {
55 uptr node = t1.getAndClearFirstOne();
56 if (v[node].setBit(to))
57 if (res < max_added_edges)
58 added_edges[res++] = node;
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".
69 bool hasEdge(uptr from, uptr to) { return v[from].getBit(to); }
71 // Returns true if the edge from=>to was removed.
72 bool removeEdge(uptr from, uptr to) {
73 return v[from].clearBit(to);
76 // Returns true if at least one edge *=>to was removed.
77 bool removeEdgesTo(const BV &to) {
79 for (uptr from = 0; from < size(); from++) {
80 if (v[from].setDifference(to))
86 // Returns true if at least one edge from=>* was removed.
87 bool removeEdgesFrom(const BV &from) {
91 uptr idx = t1.getAndClearFirstOne();
92 if (!v[idx].empty()) {
100 void removeEdgesFrom(uptr from) {
101 return v[from].clear();
104 bool hasEdge(uptr from, uptr to) const {
106 return v[from].getBit(to);
109 // Returns true if there is a path from the node 'from'
110 // to any of the nodes in 'targets'.
111 bool isReachable(uptr from, const BV &targets) {
114 to_visit.copyFrom(v[from]);
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]);
122 return targets.intersectsWith(visited);
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'.
128 uptr findPath(uptr from, const BV &targets, uptr *path, uptr path_size) {
132 if (targets.getBit(from))
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))
144 // Same as findPath, but finds a shortest path.
145 uptr findShortestPath(uptr from, const BV &targets, uptr *path,
147 for (uptr p = 1; p <= path_size; p++)
148 if (findPath(from, targets, path, p) == p)
154 void check(uptr idx1, uptr idx2) const {
155 CHECK_LT(idx1, size());
156 CHECK_LT(idx2, size());
159 // Keep temporary vectors here since we can not create large objects on stack.
163 } // namespace __sanitizer
165 #endif // SANITIZER_BVGRAPH_H