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