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 <assert.h> 23 #include <algorithm> 24 25 #include "Allocator.h" 26 27 namespace android { 28 29 template <class T> 30 class Node { 31 public: 32 allocator::set<Node<T>*> references_in; 33 allocator::set<Node<T>*> references_out; 34 size_t index; 35 size_t lowlink; 36 37 T* ptr; 38 39 Node(T* ptr, Allocator<Node> allocator) 40 : references_in(allocator), references_out(allocator), ptr(ptr){}; 41 Node(Node&& rhs) = default; 42 void Edge(Node<T>* ref) { 43 references_out.emplace(ref); 44 ref->references_in.emplace(this); 45 } 46 template <class F> 47 void Foreach(F&& f) { 48 for (auto& node : references_out) { 49 f(node->ptr); 50 } 51 } 52 53 private: 54 DISALLOW_COPY_AND_ASSIGN(Node<T>); 55 }; 56 57 template <class T> 58 using Graph = allocator::vector<Node<T>*>; 59 60 template <class T> 61 using SCC = allocator::vector<Node<T>*>; 62 63 template <class T> 64 using SCCList = allocator::vector<SCC<T>>; 65 66 template <class T> 67 class TarjanAlgorithm { 68 public: 69 explicit TarjanAlgorithm(Allocator<void> allocator) 70 : index_(0), stack_(allocator), components_(allocator) {} 71 72 void Execute(Graph<T>& graph, SCCList<T>& out); 73 74 private: 75 static constexpr size_t UNDEFINED_INDEX = static_cast<size_t>(-1); 76 void Tarjan(Node<T>* vertex, Graph<T>& graph); 77 78 size_t index_; 79 allocator::vector<Node<T>*> stack_; 80 SCCList<T> components_; 81 }; 82 83 template <class T> 84 void TarjanAlgorithm<T>::Execute(Graph<T>& graph, SCCList<T>& out) { 85 stack_.clear(); 86 components_.clear(); 87 index_ = 0; 88 for (auto& it : graph) { 89 it->index = UNDEFINED_INDEX; 90 it->lowlink = UNDEFINED_INDEX; 91 } 92 93 for (auto& it : graph) { 94 if (it->index == UNDEFINED_INDEX) { 95 Tarjan(it, graph); 96 } 97 } 98 out.swap(components_); 99 } 100 101 template <class T> 102 void TarjanAlgorithm<T>::Tarjan(Node<T>* vertex, Graph<T>& graph) { 103 assert(vertex->index == UNDEFINED_INDEX); 104 vertex->index = index_; 105 vertex->lowlink = index_; 106 index_++; 107 stack_.push_back(vertex); 108 for (auto& it : vertex->references_out) { 109 Node<T>* vertex_next = it; 110 if (vertex_next->index == UNDEFINED_INDEX) { 111 Tarjan(vertex_next, graph); 112 vertex->lowlink = std::min(vertex->lowlink, vertex_next->lowlink); 113 } else if (std::find(stack_.begin(), stack_.end(), vertex_next) != stack_.end()) { 114 vertex->lowlink = std::min(vertex->lowlink, vertex_next->index); 115 } 116 } 117 if (vertex->lowlink == vertex->index) { 118 SCC<T> component{components_.get_allocator()}; 119 Node<T>* other_vertex; 120 do { 121 other_vertex = stack_.back(); 122 stack_.pop_back(); 123 component.push_back(other_vertex); 124 } while (other_vertex != vertex && !stack_.empty()); 125 126 components_.emplace_back(component); 127 } 128 } 129 130 template <class T> 131 void Tarjan(Graph<T>& graph, SCCList<T>& out) { 132 TarjanAlgorithm<T> tarjan{graph.get_allocator()}; 133 tarjan.Execute(graph, out); 134 } 135 136 } // namespace android 137 138 #endif // LIBMEMUNREACHABLE_TARJAN_H_ 139
