Home | History | Annotate | Download | only in sanitizer_common 
      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 { 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
    166