sanitizer_bvgraph.h revision 2d1fdb26e458c4ddc04155c1d421bced3ba90cd0 
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
21namespace __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.
25template<class BV>
26class BVGraph {
27 public:
28  enum SizeEnum { kSize = BV::kSize };
29  uptr size() const { return kSize; }
30  // No CTOR.
31  void clear() {
32    for (uptr i = 0; i < size(); i++)
33      v[i].clear();
34  }
35
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.
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.
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".
69  bool hasEdge(uptr from, uptr to) { return v[from].getBit(to); }
70
71  // Returns true if the edge from=>to was removed.
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.
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.
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
100  void removeEdgesFrom(uptr from) {
101    return v[from].clear();
102  }
103
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'.
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'.
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.
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:
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