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(from, 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(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'.
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(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.
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:
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