[sanitizer] implement node removal in Deadlock graph

git-svn-id: https://llvm.org/svn/llvm-project/compiler-rt/trunk@201509 91177308-0d34-0410-b5e6-96231b3b80d8

1 files changed, 40 insertions, 0 deletions

diff --git a/lib/sanitizer_common/sanitizer_bvgraph.h b/lib/sanitizer_common/sanitizer_bvgraph.h
index 8d3e6afe8..c54955a5a 100644
--- a/lib/sanitizer_common/sanitizer_bvgraph.h
+++ b/lib/sanitizer_common/sanitizer_bvgraph.h
@@ -33,6 +33,13 @@ class BVGraph {
       v[i].clear();
   }
 
+  bool empty() const {
+    for (uptr i = 0; i < size(); i++)
+      if (!v[i].empty())
+        return false;
+    return true;
+  }
+
   // Returns true if a new edge was added.
   bool addEdge(uptr from, uptr to) {
     check(from, to);
@@ -49,6 +56,39 @@ class BVGraph {
     return res;
   }
 
+  // Returns true if the edge from=>to was removed.
+  bool removeEdge(uptr from, uptr to) {
+    return v[from].clearBit(to);
+  }
+
+  // Returns true if at least one edge *=>to was removed.
+  bool removeEdgesTo(const BV &to) {
+    bool res = 0;
+    for (uptr from = 0; from < size(); from++) {
+      if (v[from].setDifference(to))
+        res = true;
+    }
+    return res;
+  }
+
+  // Returns true if at least one edge from=>* was removed.
+  bool removeEdgesFrom(const BV &from) {
+    bool res = false;
+    t1.copyFrom(from);
+    while (!t1.empty()) {
+      uptr idx = t1.getAndClearFirstOne();
+      if (!v[idx].empty()) {
+        v[idx].clear();
+        res = true;
+      }
+    }
+    return res;
+  }
+
+  void removeEdgesFrom(uptr from) {
+    return v[from].clear();
+  }
+
   bool hasEdge(uptr from, uptr to) const {
     check(from, to);
     return v[from].getBit(to);