Home | History | Annotate | Line # | Download | only in sanitizer_common 
      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
    165