contrib/compiler-rt/lib/sanitizer_common/sanitizer_bvgraph.h

   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
  21 namespace __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.
  25 template<class BV>
  26 class BVGraph {
  27  public:
  28   enum SizeEnum : uptr { 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