1276789Sdim//===-- sanitizer_bvgraph.h -------------------------------------*- C++ -*-===// 2276789Sdim// 3353358Sdim// Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions. 4353358Sdim// See https://llvm.org/LICENSE.txt for license information. 5353358Sdim// SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception 6276789Sdim// 7276789Sdim//===----------------------------------------------------------------------===// 8276789Sdim// 9276789Sdim// This file is a part of Sanitizer runtime. 10276789Sdim// BVGraph -- a directed graph. 11276789Sdim// 12276789Sdim//===----------------------------------------------------------------------===// 13276789Sdim 14276789Sdim#ifndef SANITIZER_BVGRAPH_H 15276789Sdim#define SANITIZER_BVGRAPH_H 16276789Sdim 17276789Sdim#include "sanitizer_common.h" 18276789Sdim#include "sanitizer_bitvector.h" 19276789Sdim 20276789Sdimnamespace __sanitizer { 21276789Sdim 22276789Sdim// Directed graph of fixed size implemented as an array of bit vectors. 23276789Sdim// Not thread-safe, all accesses should be protected by an external lock. 24276789Sdimtemplate<class BV> 25276789Sdimclass BVGraph { 26276789Sdim public: 27327952Sdim enum SizeEnum : uptr { kSize = BV::kSize }; 28276789Sdim uptr size() const { return kSize; } 29276789Sdim // No CTOR. 30276789Sdim void clear() { 31276789Sdim for (uptr i = 0; i < size(); i++) 32276789Sdim v[i].clear(); 33276789Sdim } 34276789Sdim 35276789Sdim bool empty() const { 36276789Sdim for (uptr i = 0; i < size(); i++) 37276789Sdim if (!v[i].empty()) 38276789Sdim return false; 39276789Sdim return true; 40276789Sdim } 41276789Sdim 42276789Sdim // Returns true if a new edge was added. 43276789Sdim bool addEdge(uptr from, uptr to) { 44276789Sdim check(from, to); 45276789Sdim return v[from].setBit(to); 46276789Sdim } 47276789Sdim 48276789Sdim // Returns true if at least one new edge was added. 49276789Sdim uptr addEdges(const BV &from, uptr to, uptr added_edges[], 50276789Sdim uptr max_added_edges) { 51276789Sdim uptr res = 0; 52276789Sdim t1.copyFrom(from); 53276789Sdim while (!t1.empty()) { 54276789Sdim uptr node = t1.getAndClearFirstOne(); 55276789Sdim if (v[node].setBit(to)) 56276789Sdim if (res < max_added_edges) 57276789Sdim added_edges[res++] = node; 58276789Sdim } 59276789Sdim return res; 60276789Sdim } 61276789Sdim 62276789Sdim // *EXPERIMENTAL* 63276789Sdim // Returns true if an edge from=>to exist. 64276789Sdim // This function does not use any global state except for 'this' itself, 65276789Sdim // and thus can be called from different threads w/o locking. 66276789Sdim // This would be racy. 67276789Sdim // FIXME: investigate how much we can prove about this race being "benign". 68276789Sdim bool hasEdge(uptr from, uptr to) { return v[from].getBit(to); } 69276789Sdim 70276789Sdim // Returns true if the edge from=>to was removed. 71276789Sdim bool removeEdge(uptr from, uptr to) { 72276789Sdim return v[from].clearBit(to); 73276789Sdim } 74276789Sdim 75276789Sdim // Returns true if at least one edge *=>to was removed. 76276789Sdim bool removeEdgesTo(const BV &to) { 77276789Sdim bool res = 0; 78276789Sdim for (uptr from = 0; from < size(); from++) { 79276789Sdim if (v[from].setDifference(to)) 80276789Sdim res = true; 81276789Sdim } 82276789Sdim return res; 83276789Sdim } 84276789Sdim 85276789Sdim // Returns true if at least one edge from=>* was removed. 86276789Sdim bool removeEdgesFrom(const BV &from) { 87276789Sdim bool res = false; 88276789Sdim t1.copyFrom(from); 89276789Sdim while (!t1.empty()) { 90276789Sdim uptr idx = t1.getAndClearFirstOne(); 91276789Sdim if (!v[idx].empty()) { 92276789Sdim v[idx].clear(); 93276789Sdim res = true; 94276789Sdim } 95276789Sdim } 96276789Sdim return res; 97276789Sdim } 98276789Sdim 99276789Sdim void removeEdgesFrom(uptr from) { 100276789Sdim return v[from].clear(); 101276789Sdim } 102276789Sdim 103276789Sdim bool hasEdge(uptr from, uptr to) const { 104276789Sdim check(from, to); 105276789Sdim return v[from].getBit(to); 106276789Sdim } 107276789Sdim 108276789Sdim // Returns true if there is a path from the node 'from' 109276789Sdim // to any of the nodes in 'targets'. 110276789Sdim bool isReachable(uptr from, const BV &targets) { 111276789Sdim BV &to_visit = t1, 112276789Sdim &visited = t2; 113276789Sdim to_visit.copyFrom(v[from]); 114276789Sdim visited.clear(); 115276789Sdim visited.setBit(from); 116276789Sdim while (!to_visit.empty()) { 117276789Sdim uptr idx = to_visit.getAndClearFirstOne(); 118276789Sdim if (visited.setBit(idx)) 119276789Sdim to_visit.setUnion(v[idx]); 120276789Sdim } 121276789Sdim return targets.intersectsWith(visited); 122276789Sdim } 123276789Sdim 124276789Sdim // Finds a path from 'from' to one of the nodes in 'target', 125276789Sdim // stores up to 'path_size' items of the path into 'path', 126276789Sdim // returns the path length, or 0 if there is no path of size 'path_size'. 127276789Sdim uptr findPath(uptr from, const BV &targets, uptr *path, uptr path_size) { 128276789Sdim if (path_size == 0) 129276789Sdim return 0; 130276789Sdim path[0] = from; 131276789Sdim if (targets.getBit(from)) 132276789Sdim return 1; 133276789Sdim // The function is recursive, so we don't want to create BV on stack. 134276789Sdim // Instead of a getAndClearFirstOne loop we use the slower iterator. 135276789Sdim for (typename BV::Iterator it(v[from]); it.hasNext(); ) { 136276789Sdim uptr idx = it.next(); 137276789Sdim if (uptr res = findPath(idx, targets, path + 1, path_size - 1)) 138276789Sdim return res + 1; 139276789Sdim } 140276789Sdim return 0; 141276789Sdim } 142276789Sdim 143276789Sdim // Same as findPath, but finds a shortest path. 144276789Sdim uptr findShortestPath(uptr from, const BV &targets, uptr *path, 145276789Sdim uptr path_size) { 146276789Sdim for (uptr p = 1; p <= path_size; p++) 147276789Sdim if (findPath(from, targets, path, p) == p) 148276789Sdim return p; 149276789Sdim return 0; 150276789Sdim } 151276789Sdim 152276789Sdim private: 153276789Sdim void check(uptr idx1, uptr idx2) const { 154276789Sdim CHECK_LT(idx1, size()); 155276789Sdim CHECK_LT(idx2, size()); 156276789Sdim } 157276789Sdim BV v[kSize]; 158276789Sdim // Keep temporary vectors here since we can not create large objects on stack. 159276789Sdim BV t1, t2; 160276789Sdim}; 161276789Sdim 162276789Sdim} // namespace __sanitizer 163276789Sdim 164276789Sdim#endif // SANITIZER_BVGRAPH_H 165