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