165 lines · c
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-exception6//7//===----------------------------------------------------------------------===//8//9// This file is a part of Sanitizer runtime.10// BVGraph -- a directed graph.11//12//===----------------------------------------------------------------------===//13 14#ifndef SANITIZER_BVGRAPH_H15#define SANITIZER_BVGRAPH_H16 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 __sanitizer163 164#endif // SANITIZER_BVGRAPH_H165