1 //===-- sanitizer_bvgraph.h -------------------------------------*- C++ -*-===//
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
7 //===----------------------------------------------------------------------===//
9 // This file is a part of Sanitizer runtime.
10 // BVGraph -- a directed graph.
12 //===----------------------------------------------------------------------===//
14 #ifndef SANITIZER_BVGRAPH_H
15 #define SANITIZER_BVGRAPH_H
17 #include "sanitizer_common.h"
18 #include "sanitizer_bitvector.h"
20 namespace __sanitizer {
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.
27 enum SizeEnum : uptr { kSize = BV::kSize };
28 uptr size() const { return kSize; }
31 for (uptr i = 0; i < size(); i++)
36 for (uptr i = 0; i < size(); i++)
42 // Returns true if a new edge was added.
43 bool addEdge(uptr from, uptr to) {
45 return v[from].setBit(to);
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) {
54 uptr node = t1.getAndClearFirstOne();
55 if (v[node].setBit(to))
56 if (res < max_added_edges)
57 added_edges[res++] = node;
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); }
70 // Returns true if the edge from=>to was removed.
71 bool removeEdge(uptr from, uptr to) {
72 return v[from].clearBit(to);
75 // Returns true if at least one edge *=>to was removed.
76 bool removeEdgesTo(const BV &to) {
78 for (uptr from = 0; from < size(); from++) {
79 if (v[from].setDifference(to))
85 // Returns true if at least one edge from=>* was removed.
86 bool removeEdgesFrom(const BV &from) {
90 uptr idx = t1.getAndClearFirstOne();
91 if (!v[idx].empty()) {
99 void removeEdgesFrom(uptr from) {
100 return v[from].clear();
103 bool hasEdge(uptr from, uptr to) const {
105 return v[from].getBit(to);
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) {
113 to_visit.copyFrom(v[from]);
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]);
121 return targets.intersectsWith(visited);
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) {
131 if (targets.getBit(from))
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))
143 // Same as findPath, but finds a shortest path.
144 uptr findShortestPath(uptr from, const BV &targets, uptr *path,
146 for (uptr p = 1; p <= path_size; p++)
147 if (findPath(from, targets, path, p) == p)
153 void check(uptr idx1, uptr idx2) const {
154 CHECK_LT(idx1, size());
155 CHECK_LT(idx2, size());
158 // Keep temporary vectors here since we can not create large objects on stack.
162 } // namespace __sanitizer
164 #endif // SANITIZER_BVGRAPH_H