libsanitizer/sanitizer_common/sanitizer_bvgraph.h

   1 //===-- sanitizer_bvgraph.h -------------------------------------*- C++ -*-===//
   2 //
   3 // This file is distributed under the University of Illinois Open Source
   4 // License. See LICENSE.TXT for details.
   5 //
   6 //===----------------------------------------------------------------------===//
   7 //
   8 // This file is a part of Sanitizer runtime.
   9 // BVGraph -- a directed graph.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #ifndef SANITIZER_BVGRAPH_H
  14 #define SANITIZER_BVGRAPH_H
  15
  16 #include "sanitizer_common.h"
  17 #include "sanitizer_bitvector.h"
  18
  19 namespace __sanitizer {
  20
  21 // Directed graph of fixed size implemented as an array of bit vectors.
  22 // Not thread-safe, all accesses should be protected by an external lock.
  23 template<class BV>
  24 class BVGraph {
  25  public:
  26   enum SizeEnum { kSize = BV::kSize };
  27   uptr size() const { return kSize; }
  28   // No CTOR.
  29   void clear() {
  30     for (uptr i = 0; i < size(); i++)
  31       v[i].clear();
  32   }
  33
  34   bool empty() const {
  35     for (uptr i = 0; i < size(); i++)
  36       if (!v[i].empty())
  37         return false;
  38     return true;
  39   }
  40
  41   // Returns true if a new edge was added.
  42   bool addEdge(uptr from, uptr to) {
  43     check(from, to);
  44     return v[from].setBit(to);
  45   }
  46
  47   // Returns true if at least one new edge was added.
  48   uptr addEdges(const BV &from, uptr to, uptr added_edges[],
  49                 uptr max_added_edges) {
  50     uptr res = 0;
  51     t1.copyFrom(from);
  52     while (!t1.empty()) {
  53       uptr node = t1.getAndClearFirstOne();
  54       if (v[node].setBit(to))
  55         if (res < max_added_edges)
  56           added_edges[res++] = node;
  57     }
  58     return res;
  59   }
  60
  61   // *EXPERIMENTAL*
  62   // Returns true if an edge from=>to exist.
  63   // This function does not use any global state except for 'this' itself,
  64   // and thus can be called from different threads w/o locking.
  65   // This would be racy.
  66   // FIXME: investigate how much we can prove about this race being "benign".
  67   bool hasEdge(uptr from, uptr to) { return v[from].getBit(to); }
  68
  69   // Returns true if the edge from=>to was removed.
  70   bool removeEdge(uptr from, uptr to) {
  71     return v[from].clearBit(to);
  72   }
  73
  74   // Returns true if at least one edge *=>to was removed.
  75   bool removeEdgesTo(const BV &to) {
  76     bool res = 0;
  77     for (uptr from = 0; from < size(); from++) {
  78       if (v[from].setDifference(to))
  79         res = true;
  80     }
  81     return res;
  82   }
  83
  84   // Returns true if at least one edge from=>* was removed.
  85   bool removeEdgesFrom(const BV &from) {
  86     bool res = false;
  87     t1.copyFrom(from);
  88     while (!t1.empty()) {
  89       uptr idx = t1.getAndClearFirstOne();
  90       if (!v[idx].empty()) {
  91         v[idx].clear();
  92         res = true;
  93       }
  94     }
  95     return res;
  96   }
  97
  98   void removeEdgesFrom(uptr from) {
  99     return v[from].clear();
 100   }
 101
 102   bool hasEdge(uptr from, uptr to) const {
 103     check(from, to);
 104     return v[from].getBit(to);
 105   }
 106
 107   // Returns true if there is a path from the node 'from'
 108   // to any of the nodes in 'targets'.
 109   bool isReachable(uptr from, const BV &targets) {
 110     BV &to_visit = t1,
 111        &visited = t2;
 112     to_visit.copyFrom(v[from]);
 113     visited.clear();
 114     visited.setBit(from);
 115     while (!to_visit.empty()) {
 116       uptr idx = to_visit.getAndClearFirstOne();
 117       if (visited.setBit(idx))
 118         to_visit.setUnion(v[idx]);
 119     }
 120     return targets.intersectsWith(visited);
 121   }
 122
 123   // Finds a path from 'from' to one of the nodes in 'target',
 124   // stores up to 'path_size' items of the path into 'path',
 125   // returns the path length, or 0 if there is no path of size 'path_size'.
 126   uptr findPath(uptr from, const BV &targets, uptr *path, uptr path_size) {
 127     if (path_size == 0)
 128       return 0;
 129     path[0] = from;
 130     if (targets.getBit(from))
 131       return 1;
 132     // The function is recursive, so we don't want to create BV on stack.
 133     // Instead of a getAndClearFirstOne loop we use the slower iterator.
 134     for (typename BV::Iterator it(v[from]); it.hasNext(); ) {
 135       uptr idx = it.next();
 136       if (uptr res = findPath(idx, targets, path + 1, path_size - 1))
 137         return res + 1;
 138     }
 139     return 0;
 140   }
 141
 142   // Same as findPath, but finds a shortest path.
 143   uptr findShortestPath(uptr from, const BV &targets, uptr *path,
 144                         uptr path_size) {
 145     for (uptr p = 1; p <= path_size; p++)
 146       if (findPath(from, targets, path, p) == p)
 147         return p;
 148     return 0;
 149   }
 150
 151  private:
 152   void check(uptr idx1, uptr idx2) const {
 153     CHECK_LT(idx1, size());
 154     CHECK_LT(idx2, size());
 155   }
 156   BV v[kSize];
 157   // Keep temporary vectors here since we can not create large objects on stack.
 158   BV t1, t2;
 159 };
 160
 161 } // namespace __sanitizer
 162
 163 #endif // SANITIZER_BVGRAPH_H