libsanitizer/sanitizer_common/sanitizer_bvgraph.h

   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
  20 namespace __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.
  24 template<class BV>
  25 class 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