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
20namespace __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.
24template<class BV>
25class BVGraph {
26 public:
27 enum SizeEnum : uptr { kSize = BV::kSize };
28 uptr size() const { return kSize; }
29 // No CTOR.
30 void clear() {
31 for (uptr i = 0; i < size(); i++)
32 v[i].clear();
33 }
34
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.
43 bool addEdge(uptr from, uptr to) {
44 check(idx1: from, idx2: to);
45 return v[from].setBit(to);
46 }
47
48 // Returns true if at least one new edge was added.
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".
68 bool hasEdge(uptr from, uptr to) { return v[from].getBit(to); }
69
70 // Returns true if the edge from=>to was removed.
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.
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.
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
99 void removeEdgesFrom(uptr from) {
100 return v[from].clear();
101 }
102
103 bool hasEdge(uptr from, uptr to) const {
104 check(idx1: from, idx2: 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'.
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'.
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(from: idx, targets, path: path + 1, path_size: path_size - 1))
138 return res + 1;
139 }
140 return 0;
141 }
142
143 // Same as findPath, but finds a shortest path.
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, path_size: p) == p)
148 return p;
149 return 0;
150 }
151
152 private:
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