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) noexcept = 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