libmemunreachable/Tarjan.h

   1 /*
   2  * Copyright (C) 2016 The Android Open Source Project
   3  *
   4  * Licensed under the Apache License, Version 2.0 (the "License");
   5  * you may not use this file except in compliance with the License.
   6  * You may obtain a copy of the License at
   7  *
   8  *      http://www.apache.org/licenses/LICENSE-2.0
   9  *
  10  * Unless required by applicable law or agreed to in writing, software
  11  * distributed under the License is distributed on an "AS IS" BASIS,
  12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  13  * See the License for the specific language governing permissions and
  14  * limitations under the License.
  15  */
  16
  17 // Based on system/update_engine/payload_generator/tarjan.cc
  18
  19 #ifndef LIBMEMUNREACHABLE_TARJAN_H_
  20 #define LIBMEMUNREACHABLE_TARJAN_H_
  21
  22 #include <algorithm>
  23
  24 #include "Allocator.h"
  25
  26 template<class T>
  27 class Node {
  28  public:
  29   allocator::set<Node<T>*> references_in;
  30   allocator::set<Node<T>*> references_out;
  31   size_t index;
  32   size_t lowlink;
  33
  34   T* ptr;
  35
  36   Node(T* ptr, Allocator<Node> allocator) : references_in(allocator), references_out(allocator),
  37       ptr(ptr) {};
  38   Node(Node&& rhs) = default;
  39   void Edge(Node<T>* ref) {
  40     references_out.emplace(ref);
  41     ref->references_in.emplace(this);
  42   }
  43   template<class F>
  44   void Foreach(F&& f) {
  45     for (auto& node: references_out) {
  46       f(node->ptr);
  47     }
  48   }
  49  private:
  50   DISALLOW_COPY_AND_ASSIGN(Node<T>);
  51 };
  52
  53 template<class T>
  54 using Graph = allocator::vector<Node<T>*>;
  55
  56 template<class T>
  57 using SCC = allocator::vector<Node<T>*>;
  58
  59 template<class T>
  60 using SCCList = allocator::vector<SCC<T>>;
  61
  62 template<class T>
  63 class TarjanAlgorithm {
  64  public:
  65   TarjanAlgorithm(Allocator<void> allocator) : index_(0),
  66     stack_(allocator), components_(allocator) {}
  67
  68   void Execute(Graph<T>& graph, SCCList<T>& out);
  69  private:
  70   static constexpr size_t UNDEFINED_INDEX = static_cast<size_t>(-1);
  71   void Tarjan(Node<T>* vertex, Graph<T>& graph);
  72
  73   size_t index_;
  74   allocator::vector<Node<T>*> stack_;
  75   SCCList<T> components_;
  76 };
  77
  78 template<class T>
  79 void TarjanAlgorithm<T>::Execute(Graph<T>& graph, SCCList<T>& out) {
  80   stack_.clear();
  81   components_.clear();
  82   index_ = 0;
  83   for (auto& it: graph) {
  84     it->index = UNDEFINED_INDEX;
  85     it->lowlink = UNDEFINED_INDEX;
  86   }
  87
  88   for (auto& it: graph) {
  89     if (it->index == UNDEFINED_INDEX) {
  90       Tarjan(it, graph);
  91     }
  92   }
  93   out.swap(components_);
  94 }
  95
  96 template<class T>
  97 void TarjanAlgorithm<T>::Tarjan(Node<T>* vertex, Graph<T>& graph) {
  98   assert(vertex->index == UNDEFINED_INDEX);
  99   vertex->index = index_;
 100   vertex->lowlink = index_;
 101   index_++;
 102   stack_.push_back(vertex);
 103   for (auto& it: vertex->references_out) {
 104     Node<T>* vertex_next = it;
 105     if (vertex_next->index == UNDEFINED_INDEX) {
 106       Tarjan(vertex_next, graph);
 107       vertex->lowlink = std::min(vertex->lowlink, vertex_next->lowlink);
 108     } else if (std::find(stack_.begin(), stack_.end(), vertex_next) != stack_.end()) {
 109       vertex->lowlink = std::min(vertex->lowlink, vertex_next->index);
 110     }
 111   }
 112   if (vertex->lowlink == vertex->index) {
 113     SCC<T> component{components_.get_allocator()};
 114     Node<T>* other_vertex;
 115     do {
 116       other_vertex = stack_.back();
 117       stack_.pop_back();
 118       component.push_back(other_vertex);
 119     } while (other_vertex != vertex && !stack_.empty());
 120
 121     components_.emplace_back(component);
 122   }
 123 }
 124
 125 template<class T>
 126 void Tarjan(Graph<T>& graph, SCCList<T>& out) {
 127   TarjanAlgorithm<T> tarjan{graph.get_allocator()};
 128   tarjan.Execute(graph, out);
 129 }
 130
 131 #endif // LIBMEMUNREACHABLE_TARJAN_H_